4. Сведение матричной игры к задаче

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Решение матричной игры можно свести к решению стандартной задачи линейного программирования (ЛП).

Рассмотрим игру с m n-матрицей выигрышей Н.

Теорема 9. Тройка (Х^*, Y^*, v) является решением игры

Г = < S_m‚ S_n, H > тогда и только тогда, когда (Х^*, Y^*, kv + а) является решением игры Г' = < S_m‚ S_n, kH + а >, где а - любое вещественное число, k > 0.

В силу теоремы 9 всегда можно добиться того, чтобы было

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

Любую матричную игру можно свести к задаче ЛП, вернее, к паре двойственных друг другу задач ЛП. Благодаря этому становится возможным применение симплекса-метода для решения матричных игр.

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

Т = х + … + х + … + х → min

при условиях

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

L = y + … + y + … + y → max

при условиях

Решив эти задачи, найдем x ,y и v из соотношений

v = 1 ∕ T_min = 1 ∕ L_max, x = vx , i = , y = vy , j = .

П р и м е р 12

Решить игру Н = .

Решение. Чтобы гарантировать v > 0, прибавим ко всем элементам матрицы Н константу +1. Тогда получим матрицу

Н =

Пара двойственных задач ЛП будет в данном случае выглядеть следующим образом.

Минимизировать Максимизировать

Т = х₁' + х₂' + х₃' L = y₁' + y₂' + y₃' + y₄'

при условиях при условиях

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

Номер итера- ции	Базисные перемен- ные	hi0'	y1'	y 7 2'	y3'	y4'	y5	y6	y7	hi0'
										hip'
0	y5 y6 y7	1 1 1	6 11 11	7 6 1	4 13 6	1 11 21	1 0 0	0 1 0	0 0 1	1/7 1/6 1
	L	0	-1	-1	-1	-1	0	0	0
Ι	y2' y6 y7	1/7 1/7 6/7	6/7 41/7 71/7	1 0 0	4/7 67/7 38/7	1 71/7 /7 71/7 146/7	1/7 -6/7 -1/7	0 1 0	0 0 1	1 1/71 3/73
	L	1/7	-1/7	0	-3/7	-6/7	1/7	0	0
ΙΙ	y2' y4'	10/71 1/71		1 0		0 1			0 0
			41/71		67/71		-6/71	7/71
	y7	40/71		0		0			1
	L	11/71	25/71	0	27/71	0	5/71	6/71	0

После второй итерации симплексного метода получим оптимальное решение

у = 0, у = 10/71, у = 0, у = 1/71 и L_max = T_min = 11/71.

Отсюда v' = 1/ L_max = 1/ T_min = 71/11 и у = 71/11 · 0 = 0,

у = · , у = · 0 = 0, у = · .

Таким образом, оптимальная стратегия игрока ΙΙ есть

Y^* = (0, 10/11, 0, 1/11), v = v' – 1 = 71/11 – 1 = 60/11.

Из индексной строки против переменных у₅, у₆, у₇ получаем оптимальное решение первой задачи

x = 5/71, x = 6/71, x + 0, откуда x = 71/11 · 5/71 = 5/11,

x = 71/11 · 6/71 = 6/11, x = 71/11 · 0 = 0 и Х^* = (5/11, 6/11, 0).

Итак,

(Х^*, Y^*, v) = ((5/11, 6/11, 0), (0, 10/11, 0, 1/11), 60/11).

22