40108

Функция выигрыша в матричных играх без седловой точки. Смешанные и оптимальные смешанные стратегии. Метод сведения решения матричных игр к задаче линейного программирования

Доклад

Менеджмент, консалтинг и предпринимательство

Функция выигрыша в матричных играх без седловой точки. Парная игра с нулевой суммой задается формально матрицей игры матрицей А = {ij} элементы которой определяют выигрыш первого игрока и проигрыш второго если первый игрок выберет iю стратегию а второй jю стратегию. Пара i0j0 называется седловой точкой матрицы решением игры если выполняются условия: mx по столбцу I игрок min по строке II игрок Значение функции выигрыша в седловой точке называется ценой игры. Тогда выигрыш первого игрока при условии что он выбирает...

Русский

2013-10-15

119.5 KB

24 чел.

23. Функция выигрыша в матричных играх без седловой точки. Смешанные и оптимальные смешанные стратегии. Метод сведения решения матричных игр к задаче линейного программирования.

Матричной называют парную игру с нулевой суммой при условии, что каждый игрок имеет конечное число чистых стратегий. Парная игра с нулевой суммой задается формально матрицей игры – матрицей А = {aij}, элементы которой определяют выигрыш первого игрока (и проигрыш второго), если первый игрок выберет i-ю стратегию, а второй - j-ю стратегию. Пара  (i0,j0) называется седловой точкой матрицы (решением игры), если выполняются условия:  (max по столбцу (I игрок), min по строке (II игрок))

Значение функции выигрыша в седловой точке называется ценой игры.

Седловая точка обеспечивает равновесие в игре, но она существует не всегда (н-р, в 2-х пальцевой игре Морра ее нет). В случае, когда нет седловой точки игрокам не выгодно пользоваться одной и той же стратегией, так как в этом случае противник будет выбирать наилучший для себя вариант. Тогда выбор стратегий должен быть вероятностным – выбор осуществляется случайным образом с определенными вероятностями.

Если обозначить через  вероятности выбора i-ой стратегии первым игроком. При этом:

Сумма равна 1, так как он обязан что-то выбрать, у него нет возможности не выбрать

А через  вероятности выбора j-ой стратегии вторым игроком:

то наборы  и  называются смешанными стратегиями первого и второго игроков соответственно. Смешанная стратегия – это набор вероятностей чистых стратегий.

Тогда выигрыш первого игрока при условии, что он выбирает i-ю стратегию, а второй – j-ю стратегию составит .

Функция выигрыша первого игрока  – мат. ожидание выигрыша первого игрока. Соответственно средний выигрыш второго игрока = –M(x, y)

Любая матричная игра имеет решение в смешанных стратегиях, т.е. существует   

Решение задачи (нахождение оптимальных смешанных стратегий) заключается в нахождении седловой точки функции M(x, y) на множестве . Оптимальность понимается в том смысле, что набор устраивает игроков, никто не хочет выбирать другие стратегии.

Тогда  и  называются оптимальными смешанными стратегиями игроков. Задачи заключается в нахождении оптимальных смешанных стратегий игроков и цены игры

Метод сведения решения матричных игр к задаче линейного программирования. (II метод)

Пусть игра определена матрицей   и ценой игры V. По следствию теоремы об оптимальности смешанных стратегий:

Если для смешанных стратегий () и числа V одновременно выполняются (1) и (2), то

– оптимальные стратегии игроков   (m + n неравенств)       (*)

1) Рассмотрим левую часть:

Решение СЛАУ сводится к задаче ЛП.

(1)

2) Рассмотрим правую часть (аналогично):

V меняем на W, так как системы (1)-(2) независимы, поэтому они имеют разные переменные.

(2)

Допустим, решили задачи и получили:

Если в этих решениях последние координаты совпадали бы, то выполнялись бы неравенства:

 

Тогда для каких-то  выполнялось бы следствие теоремы оптимальности.

Покажем двойственность.

Необходимо получить двойственные задачи.

Обозначим

{неравенства (3)-(4) лучше написать в развернутом виде, чтобы была видна двойственность}

  (3)

ЗАМ:

Аналогично для второй задачи:

   (4)

Задачи (3) и (4) – двойственные, т.е. решение одной можно найти из решения другой (в последней симплекс-таблице в строке оценок на местах, соответствующих дополнительным переменным). Значения линейных форм в оптимальной точке совпадут. Поэтому, получив решения , получим

Алгоритм решения:

  1.  по матрице А построить задачи (3) и (4)
  2.  найти решения задач

тогда  – цена игры, оптимальные стратегии игроков:

Преимущества и недостатки метода:

+ сразу получаем решение игры, т.е. не надо переобозначать

+ можно решать игры с любой ценой игры

– больше на 2 переменные

– надо вводить дополнительные переменные, так как


 

А также другие работы, которые могут Вас заинтересовать

30777. Подбор башенного крана 16.38 KB
  Подбор башенного крана требуемая грузоподъёмность крана Qтр = Qэл Qстр Qосн т Qэл масса монтируемого элемента Qстр масса строповочного приспособления Qосн масса монтажной оснастки т. Высота подъёма крюка Hкр = hо hз hэл hстр м hо превышение монтажного горизонта над уровнем стоянки крана hз запас по высоте для обеспечения безопасности монтажа hэл высота монтируемого элемента hстр высота строповки м Расчёт вылета стрелы крана производят по формуле б = а 2 b c м где а ширина подкраннового пути b ...
30778. Технико-экономическое сравнение вариантов 13.75 KB
  Исходя из того требуется ли нам выполнить проект быстро или дешево выбирают метод монтажа по раннее подсчитанным показателям : механоёмкости трудоёмкости продолжительности монтажа себестоимости выполнения работ и приведённым затратам. Механоёмкость затраты машинного времени на выполнение единицы монтажа также по ЕНиР. Продолжительность монтажа считается по количеству машиночасов всех монтажных кранов с учётом частичного совмещения во времени их работы на объекте. Себестоимость монтажа сумма прямых затрат и накладных расходов.
30779. Монтаж одноэтажных промышленных зданий. Методы монтажа. Продольная и поперечная схема 16.88 KB
  В этом случае кран двигаясь вдоль пролета монтирует все колонны а затем перемещаясь поперек пролета ведет секционный монтаж. Перед монтажом колонн проверяют их размеры и наносят риски облегчающие установку колонны в стакан фундамента или на оголовки подколенников. Тяжелые колонны обычно монтируют с транспортных средств или предварительно раскладывают колонны основанием обращенным к фундаментам. Тяжелые колонны поднимают и переводят в вертикальное положение способом поворота или скольжения.
30780. Основные технологические процессы при монтаже ж\б колонн в стаканы фундаментов 14.26 KB
  Тяжелые колонны обычно монтируют с транспортных средств или предварительно раскладывают колонны основанием обращенным к фундаментам. Колонны легкого типа как правило предварительно доставляют в зону монтажа и раскладывают вершинами обращенными к фундаменту. Тяжелые колонны поднимают и переводят в вертикальное положение способом поворота или скольжения. Особо тяжелые и нетранспортабельные железобетонные колонны бетонируют в инвентарных формах на позициях обеспечивающих удобное движение монтажного крана и установку с каждой позиции одной...
30781. Монтаж многоэтажных каркасных зданий, последовательность монтажа элементов 15.51 KB
  Монтаж многоэтажных каркасных зданий последовательность монтажа элементов. Монтаж совокупность технологических процессов связанных с доставкой конструктивных элементов установкой и закреплением. Методы монтажа техническое решение определяющее способ возведения конструкции и последующей сборки: По степени укрупнения: А поэлементный подъём и установка в проектное положение отдельных готовых конструктивных элементов Б крупноблочный конструкции предварительно собираются в блок укрупнит.сборка В монтаж сооружения целиком В...
30782. Монтаж многоэтажных каркасных зданий, расположение монтажных кранов, зон складирования, привязка подкрановых путей 15.6 KB
  Монтаж многоэтажных каркасных зданий расположение монтажных кранов зон складирования привязка подкрановых путей. При размещении привязке монтажных кранов на стройгенплане должны быть удовлетворены следующие условия: четкая ритмичная работа кранов и связанных с ними других строительных механизмов и машин безопасные условия труда машинистов и обслуживающего персонала снижение себестоимости и трудоемкости работ сокращение временина установку кранов и устройство подкрановых путей. Положение оси подкрановых путей относительно строящегося...
30783. Основные технологические процессы при монтаже колонн верхних ярусов многоэтажных зданий 15.14 KB
  Колонны высотой на один или два этажа стропят фрикционными или рамочными захватами а рамы штыревыми. Эти приспособления бывают одиночными для закрепления одной колонны групповыми для четырех колонн и в виде совокупности групповых кондукторов обеспечивающей монтаж элементов яруса на значительной части здания. Нижняя обойма обхватывает выступающую над перекрытием часть колонны предыдущего яруса а две другие закрепляют устанавливаемую колонну. После окончательного закрепления колонны одиночный кондуктор разъединяют...
30784. Основные технологические процессы при монтаже ригелей и плит перекрытия 13.13 KB
  Плиты поднимают четырехветвевыми стропами сразу выверяют и приваривают к ригелям. В безбалочных перекрытиях по капителям укладывают осевые плиты а по ним плитывкладыши.
30785. Виды защитных покрытий и требования к ним 14.84 KB
  Защитные покрытия предназначены для защиты зданий и их элементов от внешних агрессивных воздействий окружающей среды. Защитные покрытия в зависимости от поражающих факторов бывают : Гидроизоляционные Антикоррозийные Огнеупорные теплоизоляционные светонепроницаемые и др.войлок Противокоррозийные покрытия защищают от коррозии наносятся окраской распылением.