Решение игры в чистых стратегиях

Пример 3.1. Найти оптимальные чистые стратегии и значения следующей матричной игры:

Чтобы упростить эту игру, умножим каждый элемент матрицы А на 12, а затем каждому элементу прибавим 6 (чтобы избавиться от отрицательных чисел) - см. свойство 3:

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

В этом случае говорят, что первая стратегия доминирует четвертую стратегию.

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

Игра А' эквивалентна исходной игре в том смысле, что в них оптимальные стратегии одинаковы (свойство 3), a ν(A') = 12ν(A)+6

В игре А' применяем принцип минимакса (3). Вычислим левую часть равенства (З):

max{6,1,3}=6.

Вычислим правую часть равенства (З):

min{l0,7} =7.

Так как равенство (3) не выполнено, то в игре А' и, значит, в игре А, оптимальных чистых стратегий нет.

Пример3.2. Решить следующую игру

Решение: Доминируемых стратегий нет, т.е. упростить игру невозможно. Оптимальных чистых стратегий нет, т.к. равенство (3) не выполнено. Поэтому надо решить игру в смешанных стратегиях.

Чтобы исключить случай v ≤0 (см. (4),(8)) избавимся от отрицательных элементов матрицы, прибавив ко всем элементам 4. Тогда получим эквивалентную игру

Задача (1)-(3) и (5)-(7) запишутся:

min z= ξ₁+ ξ₂+ ξ₃

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

5ξ₁+3ξ₂+2ξ₃≥1,

4ξ₁+6ξ₂+ ξ₃≥1,

2ξ₁+7ξ₂+8ξ₃≥1,

5ξ₁+4ξ₂+ ξ₃≥1,

ξ₁≥0, ξ₂≥0, ξ₃≥0;

max w=h₁+h₂+h₃₊h₄

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

5h₁+4h₂+2h₃+5h₄≤1

3h₁+6h₂+7h₃+4h₄≤1

2h₁+ h₂+8h₃+ h₄≤1

h₁≤0,…,h₄≤0

Последняя (оптимальная) симплекс-таблица для двойственной задачи (задачи второго игрока) имеет вид:

		h1	h2	h3	h4	h5	h6	h7
w	7/29		5/29		3/29	4/29	3/29
h1	5/29		16/29		27/29	7/29	-2/29
h3	2/29		18/29		5/29	-3/29	5/29
h7	3/29		144/29		65/29	10/29	36/29

Отсюда находим решение задачи ЛП: = (5/29,0, 2/29, 0) - точка максимума, w* =7/29 - максимальное значение целевой функции.

Оптимальную смешанную стратегию игрока П и значение игры А' находим по формулам (8):

v (A') =1/ w* = 29/7; у* = (5/7, 0, 2/7, 0).

В исходной игре А: v (А)= v (A')-4=1/7.

Задание № 5. Решение матричной игры: а) показать существование или отсутствие чистых оптимальных стратегий; б) выполнить доминирование; в) свести исходную матричную игру к паре двойственных задач линейного программирования.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. 16.

17. 18.

19. 20.