§ 3. Общий метод решения матричных игр.

Практика показывает, что в большинстве матричных игр оптимальные чистые стратегии не существует. Однако в любой матричной игре существуют оптимальные смешанные стратегии (см. свойство 6).

Для решения игры (1) всмешанных стратегиях сводят ее к паре двойственных задач линейного программирования, применяя неравенство (4). Прямая задача ЛП:

minz=ξ ₁+ξ ₂+...+ξ _m (1)

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

a₁₁ξ ₁+a₂₁ξ ₂+…+a_m1ξ _m≥1,

a₁₂ξ ₁+a₂₂ξ ₂+…+a_m2ξ _m≥1, (2)

………………………….

a_1nξ ₁+a_2nξ ₂+…+a_mnξ _m≥1,

ξ ₁≥0,…,ξ _m≥0 (3)

где

ξ ₁=x_i*/ν, i=1,…,m; z=1/ν, (4)

a (x₁*,…,x_n*)=x* -оптимальная смешанная стратегия первого игрока. Задача (1)-(3)соответствует первому игроку, т.е. решая ее симплекс-методом находят оптимальную смешанную стратегию Iигрока и значение игры по формулам (4).

Двойственная задача ЛП:

maxw=₁+₂+…+_n (5)

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

a₁₁₁+a₂₁₂+…+a_m1_m≥1,

a₁₂₁+a₂₂₂+…+a_m2_m≥1, (6)

………………………….

a_1n₁+a_2n₂+…+a_mn_m≥1,

₁≥0,…, _m≥0, (7)

где

_j=y_j*/ν,j=1,…,n;w=1/ν, (8)

a (у₁*,...,у_n*)=у* - оптимальная смешанная стратегия IIигрока. Задача (5)-(7) соответствует второму игроку, т.е. решая ее симплекс-методом, находят оптимальную смешанную стратегию IIигрока и значение игры по формулам (8).

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

Решение: Доминируемых стратегий нет, т.е. упростить игру невозможно. Оптимальных чистых стратегий нет, т.к. равенство (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;

maxw=₁+₂+₃₊₄

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

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

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

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

₁≤0,…,₄≤0

Примеры решения таких задач ЛП приведены в разделеIIв достаточном количестве. Поэтому подробное решение здесь приводить не будем.

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

		1	2	3	4	5	6	7
w	7/29	0	5/29	0	3/29	4/29	3/29	0
1	5/29	1	16/29	0	27/29	7/29	-2/29	0
3	2/29	0	18/29	1	5/29	-3/29	5/29	0
7	3/29	0	144/29	0	65/29	10/29	36/29	1

Отсюда находим решение задачи ЛП: = (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.

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