1.3.2. Сведение решения игры к задаче линейного программирования

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

(1.21)

при условиях

(1.22)

(1.23)

где - элементы некоторой матрицы размером с вещественными элементами.

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

(1.24)

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

(1.25)

при условиях

(1.26)

(1.27)

(1.28)

Аналогично, задача для игрока В сводится к задаче линейного программирования

(1.29)

при условиях

(1.30)

(1.31)

(1.32)

Из теоремы фон Неймана следует, что обе задачи имеют решение. Находя решение задачи (1.25)-(1.28) и (1.29)-(1.32), мы получим оптимальные стратегии игроков А и В в виде и соответственно. Цена игры получится из значения (равенство следует из теории двойственности для задач линейного программирования). Для решения задач (1.25)-(1.28) и (1.29)-(1.32) достаточно решить каким-либо способом (например, с помощью симплекс-метода) одну из них, а затем по окончательной таблице определить решение второй.

Пример 1.7

Найти решение и цену игры, заданной матрицей

Решение

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

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

(1.33)

(1.34)

тогда, очевидно, наши задачи будут эквивалентны следующим:

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

(1.35)

Решим вторую из задач симплекс-методом:

Т аблица 1.4						Таблица 1.5
	Базис перем.				Свободные члены	Базис перем.				Свободные члены
		6	2	5	1		4	-2/5	13/5	3/5
		4	3	7	1		1	-3/5	17/5	2/5
		5	5	6	1		1	1/5	6/5	1/5
	Z	-1	-1	-1	0	Z	0	1/5	1/5	1/5

После первой же итерации получаем оптимальное решение и . Отсюда получаем и т.е. По таблице 1.5 из теории двойственности получаем оптимальное решение первой задачи отсюда

Упражнение 1.16

Найти решение и цену игр, заданных следующими матрицами:

1)	2)	3)
4)	5)	6)
7)	8)	9)

Упражнение 1.17

Петя и Вася хотят назначить Наташе свидание. Никто из молодых людей не знает точно, когда она будет дома. Известно, что она с равной вероятностью может возвратиться домой в 3, в 4 и в 5 часов. Наташа отдает предпочтение Пете, поэтому, если Вася позвонит первым, она попросит его подождать несколько минут, чтобы дать возможность Пете застать ее дома. Если же Петя не позвонит в течение этого времени, то Наташа сама позвонит Васе и примет его приглашение. Вечер, который они собираются провести, не обещает быть особенно шумным, так как у юношей есть всего по 2 копейки, которые они должны истратить на разговор по телефону – автомату. Считая чистыми стратегиями обоих юношей звонки Наташе в 3,4 и 5 часов, а платежом – разность «вероятность того, что Наташа проведет вечер с Петей» минус «вероятность того, что Наташа проведет вечер с Васей», - составить матрицу игры и найти оптимальные стратегии за молодых людей.