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

Пусть – матрица антагонистической игры с элементами(это условие обеспечивает положительность цены игрыv).

Пусть – смешанная стратегия первого игрока,– смешанная стратегия второго игрока. Тогда из неравенств свойства 2 оптимальных стратегий смешанного расширения игры получаем:

, ,

Разделим уравнения и неравенства систем на v>0:

, ,

Введем замену: ,,;. Тогда:

, ,

Так как первый игрок максимизирует величину гарантированного выигрыша (v) и, соответственно, минимизирует величину , а второй игрок максимизирует величину, то получаем следующие двойственные друг другу задачи линейного программирования:

, ,

(4) (4д)

В теореме фон Неймана-Нэша п. 2.5 будет доказано, что если – решения задачи (4) и (4д) соответственно, то– цена игры, а координаты оптимальных стратегий вычисляются по формулам:

;

.

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

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

Примеры

Пример 4. Решить матричную игру методом сведения к задаче линейного программирования, если матрица игры имеет вид:

.

Решение

Так как матрица игры содержит неположительные элементы, то рассмотрим матрицу , где,,. Тогда матрицаимеет положительные элементы. Найдем оптимальные стратегии игроков в игре.

Выпишем задачу линейного программирования для второго игрока:

,

(5)

Каноническая форма задачи (5) имеет вид:

,

Таблица симплекс-метода решения задачи представлена ниже.

			1	1	1	0	0	0
B
	0	1	2	1	3	1	0	0
	0	1	3	3	1	0	1	0	1/3
	0	1	3	1	2	0	0	1
		0	-1	-1	-1	0	0	0
	0	2/3	1	0	8/3	1	-1/3	0	1/4
	1	1/3	1	1	1/3	0	1/3	0
	0	2/3	2	0	5/3	0	-1/3	1
		1/3	0	0	-2/3	0	1/3	0
	1	1/4	3/8	0	1	3/8	-1/8	0
	1	1/4	7/8	1	0	-1/8	3/8	0
	0	1/4	11/8	0	0	-5/8	-1/8	1
		1/2	1/4	0	0	1/4	1/4	0

Критерий останова выполнен, оптимальным решением задачи является вектор, оптимальное значение функции цели равно. Следовательно, цена игры, а, согласно лемме о масштабе, цена исходной игры. Решение двойственной к (5) задачи находится из симлексной таблицы как оценки, стоящие на последней итерации под столбцами исходного базиса (в примере,,). Таким образом,. Возвращаясь к исходным стратегиям игроков, получаем:,,, то есть. Аналогично.