Для игры, в которой игрок Л имеет т стратегий, а игрок В - только две, решение находится аналогично. Главное отличие состоит в том, что здесь строятся графики функций, представляющих ожидаемые платежи второго игрока, соответствующие чистым стратегиям игрока А. В результате ведется поиск минимаксной точки верхней огибающей построенных прямых.

УПРАЖНЕНИЯ 14.4.2

1. Решите графически игру с подбрасыванием монет из примера 14.4.2.

2. Робин часто ездит между двумя городами. При этом есть возможность выбрать один из двух маршрутов: маршрут А представляет собой скоростное шоссе в четыре полосы, маршрут В - длинную обдуваемую ветром дорогу. Патрулирование дорог осуществляется ограниченным числом полицейских. Если все полицейские расположены на одном маршруте, Робин с ее страстным желанием ездить очень быстро, несомненно, получит штраф в 100 долл. за превышение скорости. Если полицейские патрулируют на двух маршрутах в соотношении 50 на 50, то имеется 50 % -ная вероятность, что Робин получит штраф в 100 долл. на маршруте А и 30 % -ная вероятность, что она получит такой же штраф на маршруте В. Кроме того, маршрут В длиннее, поэтому бензина расходуется на 15 долл. больше, чем на маршруте А. Определите стратегию как для Робин, так и для полиции.

3. Решите графически следующие игры, в которых платежи выплачиваются игрокуА.

-3 4

4. Дана следующая игра двух лиц с нулевой суммой.

a) Проверьте, что смешанные стратегии с вероятностями (1/6,0,5/6) для игрока А и с вероятностями (49/54, 5/54, 0) для игрока В являются оптимальными, и определите цену игры.

b) Покажите, что цена игры равна

3 3

Решение матричных игр методами линейного программирования. Теория игр находится в тесной связи с линейным программированием, так как любую конечную игру двух лиц с нулевой суммой можно представить в виде задачи линейного программирования и наоборот. Дж. Данциг [3] отмечает, что, когда в 1947 году создатель теории игр Дж. фон Нейман впервые ознакомился с симплекс-методом, он сразу установил эту взаимосвязь и обратил особое внимание на концепцию двойственности в линейном программировании. Этот раздел иллюстрирует решение матричных игр методами линейного программирования.

Оптимальные значения вероятностей xt, i = 1, 2, т, игрока А могут быть определены путем решения следующей максиминной задачи.

т т т

/=1 (=1 ,=1

х1 + х2 + ... +хт = 1, х. > 0, i=l, 2.....т.

Чтобы сформулировать эту задачу в виде задачи линейного программирования, положим

v = min £Xi-*/.Zai!*- -Zfll .jr.-

Отсюда вытекает, что

Za*.-v- у=1.2,..-, л.

Следовательно, задача игрока А может быть записана в виде

максимизировать z = v

при ограничениях

v-Vi -0 7 = 1-2,..../!,

х, + х2 + ... + хт = 1,

х, > О, i = l, 2, т,

v не ограничена в знаке. Отметим последнее условие, что цена игры v может быть как положительной, так и отрицательной.

Оптимальные стратегии yv у2, уп игрока В определяются путем решения задачи

limax ZX-IX.....1ХЛ

mm j max

y>0, /-1,2.....re.

Используя процедуру, аналогичную приведенной выше для игрока А, приходим к выводу, что задача для игрока В сводится к следующему.

Минимизировать w - v

при ограничениях

ZV,0 = 1.2...., п

у,+у2+ ... +(/ = !,

7 = 1

i/.>0, ; = 1, 2, п,

v не ограничена в знаке.

Две полученные задачи оптимизируют одну и ту же (не ограниченную в знаке) переменную и, которая является ценой игры. Причиной этого служит то, что задача игрока В является двойственной к задаче игрока А (вам предлагается доказать это утверждение в упражнении 14.4.3.5, используя определение двойственности из главы 4). Это означает, что оптимальное решение одной из задач автоматически определяет оптимальное решение другой.

Пример 14.4.4

Решим следующую матричную игру методами линейного программирования.

Значение цены игры v находится между -2 и 2. Задача линейного программирования для игрока А

Максимизировать z = v

при ограничениях

v - Зхг + 2х2 + Ъх3 < О, v + - 4х2 + 6х3 < О, v + 3x1+x2-2x3<0,

xv х2, х3 > О,

v не ограничена в знаке. Оптимальным решением является = 0,39, х2 = 0,31, х, = 0,29 и v = -0,91. Задача линейного программирования для игрока В

Минимизировать z = v

при ограничениях

о-3у,+у2 + 3у3>0, v + 2yx-Ayt+yt>0, и + 5у, + 6у2-2у3>0,

v не ограничена в знаке. Оптимальным решением является у, = 0,32, у2 = 0,08, у3 = 0,60 и v = -0,91.