Графическое решение игры два на два.

1 B2

Снова рассмотрим пример 6. Отложим на оси абсцисс отрезок единичной длины. На концах этого отрезка нарисуем вертикальные оси I-I и II-II. Отложим на оси I-I значения выигрышей первого игрока при использовании им первой стратегии. На оси II-II отложим выигрыши первого игрока при использовании им второй стратегии. Соединим точки отрезками прямых. Ломаная B₁ KB₂  - нижняя граница выигрыша. На этой границе лежит минимальный выигрыш игрока А при любой его смешанной стратегии. Точка К, в которой этот выигрыш достигает максимума, определяет решение и цену игры. Для смешанной стратегии второго игрока можем также записать:

 или .

Стратегию второго игрока можно найти и непосредственно, если на графике поменять игроков местами, а вместо максимума нижней границы выигрыша р ассмотреть минимум верхней границы проигрыша. В любом случае точка К является одновременно точкой максимина и минимакса.

5.2. Решение игр  и m×2.

Рассмотрим графическую интерпретацию игры . Построение аналогично случаю два на два. Здесь n стратегий противника изображаются отрезками n прямых. Далее рассматривается нижняя граница, которая представляет собой ломаную. Максимум ломаной достигается в одной из вершин, где пересекаются две стратегии противника, которые являются активными.

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

Пример 7. Решить игру со следующей платежной матрицей:

Решение. Эта игра имеет 2 стратегии со стороны первого игрока и три стратегии со стороны второго. Поэтому графическим способом определим одну из стратегий второго игрока, которая является неактивной. Построим график относительно стратегий первого игрока.

Из графика видно, что для второго игрока явно невыгодной является первая стратегия, которая является неактивной. Таким образом, из матрицы игры исключаем первый столбец и приходим к матрице размерности два на два следующего вида: . Для этой матрицы запишем систему уравнений - для первого игрока, и систему:  - для второго игрока. Решение этих систем дает следующий результат: .

Игра размера , как уже отмечалось выше, предварительно решается графически с точки зрения второго игрока. При этом определяются активные стратегии второго игрока. На графике применяется минимаксная стратегия, и рассматривается минимум верхней границы проигрыша. Рассмотрим пример.

Пример 8. Решить матричную игру со следующей матрицей: .

Решение. Построим график, где слева отложим значения проигрышей второго игрока при использовании им первой стратегии, а справа – значения проигрышей второго игрока при использовании им второй стратегии.

Из графика видно, что вторая стратегия для первого игрока является невыгодной, поскольку при её применении выигрыш первого игрока (и, соответственно, проигрыш второго) будет меньше. Таким образом, активными стратегиями первого игрока будут первая и третья. Соответственно запишем системы уравнений для смешанных стратегий игроков:

Решение системы:  

Решением системы будут значения  Таким образом, решение игры выглядит так: .

Решение игр . Эквивалентность матричной игры паре двойственных ЗЛП

Рассмотрим матричную игру размером  ( ).

Сведем её к задаче линейного программирования в общем виде. Имеем:

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

Для первого игрока имеем систему неравенств (с учетом того, что первый игрок стремится как можно больше выиграть, цена игры для него будет превышать v):

                

Введем новые переменные делением на цену игры: , тогда получим ЗЛП.

                

При построении целевой функции учитываем, что цена игры для первого игрока максимизируется.

Аналогично имеем для второго игрока систему неравенств:

Разделив на цену игры и введя новые переменные , получим ЗЛП для второго игрока:

Здесь целевая функция задана на максимум, т.к. цена игры для второго игрока минимизируется.

В результате получили пару симметричных двойственных ЗЛП. Согласно первой теореме двойственности, , следовательно, цена игры v имеет одно и тоже значение для обоих игроков.

 

Элементарные методы решения матричных игр , , .

Игра .

Наиболее простой матричной игрой является игра , в которой игроки имеют по две чистых стратегии.

Пусть матрица такой игры

.                                               (2.1)

Если седловой точки нет, то решением игры являются смешанные стратегии                                                       (2.2)

.                                                (2.3)

При стратегии В1 игрока В, При стратегии В2 игрока В.

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

Кроме того, .

Решение этих уравнений даёт:

,                                       (2.4)

,                                       (2.5)

.                                       (2.6)

Аналогично, применение оптимальных стратегии  обеспечивает проигрыш V игроку В при любых стратегиях А, что приводит к системе

                                           (2.7)

Ее решение даётся формулами

                                     (2.8)

                                     (2.9)

Пример (п.2.1)

Во многих учебниках приводится пример игры в «орла и решку», суть которой состоит в следующем. Каждый из двух партнёров, не зная хода другого, кладёт свою монету орлом или решкой вверх и при совпадении наименований второй игрок (В) платит первому (А) единицу, а при несовпадении первый платит второму. Очевидно платёжная матрица такой игры будет:

Седловой точки нет. Тогда, согласно формул: (2.4), (2.5), (2.6), (2.8) и (2.9), оптимальными стратегиями будут

, , цена игры .

Примечание. Отмечу, что матрица этой игры симметрична и на первый взгляд может показаться, что симметричность матрицы ведёт к справедливой (безобидной) игре для обоих игроков. На самом деле симметричность не гарантирует справедливости, напротив, кососимметричные матрицы (когда ) соответствуют совершенно справедливой игре, то есть при оптимальных стратегиях, как это легко установить, цена игры .

Пример (п.2.2)

Цех заготовитель поставляет в сборочный цех детали двух видов a и b. По договору между цехами оговорены ежедневно два срока поставки этих деталей, причём, при поставке в первый срок деталей вида «а» сборочный цех платит заготовительному премию 50 руб., при поставке же изделий «а» выплачивается премия 20 руб. При поставке же изделий вида «b» в первый срок премия составляет 30 руб., а во второй – 40 руб. Определить оптимальные стратегии поставок и получения деталей.

Решение. Принимая цех-заготовитель за игрока А, а сборочный за В, составим матрицу игры.

Таблица 2.1

Матрица игры заданная таблицей

	I срок	II срок
Детали «а» Детали «b»	50 30	20 40

Значит, ,

,

,

, следовательно, седловой точки нет. Для нахождения оптимальных стратегий применим формулы (2.4), (2.5), (2.6), (2.8) и (2.9):

; ;

; ;

 (руб.).

Таким образом, цех-изготовитель поставляет детали вида а и b с вероятностями , , при этом гарантированная премия 35 рублей, а сборочный цех получает эти детали в сроки I и II с вероятностями ,  и выплачивает 35 рублей премии заготовительному цеху ежедневно. Полученные вероятности и определяют оптимальные стратегии

, .

Примечание. Игры  допускают простое графическое толкование и решение, следующее из него. Действительно, пусть игра задана матрицей (2.1). На оси абсцисс отложим отрезок 0D, равный 1, и условимся считать, что левый конец отрезка  – стратегии А₂, тогда промежуточная точка N с координатой x соответствует некоторой смешанной стратегии первого игрока, причём, , , так как при  имеем  и , и при  имеем  и .

Вводя ось 0y, можно построить прямую, отвечающую стратегии второго игрока, её уравнение  (при каждом x, y даёт значение выигрыша игрока А, когда В применяет стратегию В₁). Отметим, что для построения В₁ достаточно провести из концов отрезка 0D прямые, не перпендикулярные ему, на левой прямой отложить , на правой –  и, соединив их получим прямую В₁В_1, отвечающую стратегии В₁ рис. 2.1. Затем аналогично строим стратегию В₂ (её уравнение ). Заметим , что при каждом x точки на прямых В₁В₁ и В₂В₂ отвечают выигрышем первого игрока при применении вторым игроком стратегий В₂ и В₁ соответственно. Откуда следует, что ломаная В₂КВ₁ рис. 2.2 отвечает нижней границе выигрыша игрока А, а значит в точке её максимума, то есть цена игры  и точка N отвечает оптимальной стратегии игрока А: .

Для нахождения оптимальной стратегии игрока В, исходя из графика, можно воспользоваться формулами:

;                                          (2.10)

.                                         (2.11)

В справедливости формул (2.10) и (2.11) легко убедиться, подставив значения LB₂ и LB₁, ,  и значение , тогда получим формулы, совпадающие с (2.10) и (2.11).

Аналогично, меняя ролями x и y, можно построить решение для игрока А.

 

B1(50)

B2(40)

B1(30)

0

0

D

D

a21

x

x

    

рис. 2.1. Графическое толкование игры             рис. 2.2. Графическое толкование игры  

Решение игры .

Пусть игра задана матрицей

.

Строим прямые, соответствующие стратегиям игрока В рис. 2.3.

Ломаная  соответствует нижней границе выигрыша, точка К на ней даёт решение игры: , , .

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

, .

0

0

рис. 2.3. Иллюстрация решения игры         рис. 2.4. Иллюстрация решения игры

Решение игры .

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

Пусть игра задана матрицей

.

Решение задачи находим для игрока В рис. 2.4.

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

Оптимальными стратегиями для игрока А являются вторая и третья. При этом

, .

Матрица оптимальных стратегий имеет вид . Тогда решение можно найти по формулам (2.4), (2.5), (2.6), (2.8) и (2.9).

Следовательно, решение игры таково:

, , .

Решение матричных игр .

При решении произвольной конечной игры размера  рекомендуется придерживаться следующей схемы:

1. Исключить из платёжной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими стратегиями для игрока А (игрока В) являются те, которым соответствуют строки (столбцы) с элементами заведомо меньшими (большими) по сравнению с элементами других строк (столбцов).

2. Определить верхнюю и нижнюю цены игры и проверить, имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена игры совпадает с верхней (нижней) ценой.

3. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера  рекомендуется симплексный метод, а для игр размером , ,  следует руководствоваться выводами предыдущих пунктов.

Пример (п.2.3)

Магазин может завести в различных пропорциях товары четырёх типов . Их реализация и прибыль магазина зависят от вида товара и состояния спроса.

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

Таблица 2.2

Матрица прибыли

Тип товара	Спрос
	В1	В2	В3	В4	В5
А1 А2 А3 А4	200 300 400 700	400 400 500 300	600 600 600 500	400 500 500 200	700 800 800 100

Будем рассматривать возникшую ситуацию как игровую. Сторона А стремится увеличить прибыль, а потому для неё стратегия  заведомо выгодна по сравнению со стратегией . Точно так же стратегия  уступает стратегии , и исходные данные упрощаются табл. 2.3.

Для игрока В естественным является выбор стратегии с большим спросом. Поэтому стратегия  менее выгодна, чем стратегия , в свою очередь, стратегия  невыгодна по сравнению со стратегией .

Таблица 2.3 Матрица игры заданная таблицей     Таблица 2.4 Матрица игры заданная таблицей

В А В1 В2 В3 В4 В5  А3 А4 400 700 500 300 600 500 500 200 800 100

В А В1 В3 В5 А3 А4 400 700 600 500 800 100

 

Следовательно, имеет смысл анализировать игру , заданную табл. 1.4. Решение этой матрицы даёт оптимальную стратегию завоза товаров , т.е. нужно завести  товара третьего типа и  товара четвёртого типа, а товары первого и второго типов не завозить, при этом средняя гарантированная прибыль (цена игры) .

Пример (п.2.4)

Предполагается оснастить цех новой технологической линией. Промышленность выпускает три типа линий. На каждой из линий можно изготовлять пять различных видов изделий. Учитывая расходы сырья, трудоёмкость, спрос и др., составлена матрица предполагаемой прибыли

.

Нужно выбрать тип технологической линии, при которой прибыль будет наибольшей.

         

 

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

 

 

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: