Приведение матричной игры к задаче линейного программирования

Нахождение решения игры в смешанных стратегиях сводится к решению задачи линейного программирования, точнее говоря к решению пары взаимосопряженных задач.

Пусть А - платежная матрица игры размерности , т.е.

Так как в смешанных стратегиях всегда существует оптимальная стратегия первого игрока и цена игры, то для нее должно выполняться неравенство

(4)

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

тогда условие (справедливое для вектора вероятностного распределения) можно переписать в виде Разделив обе части неравенства (4) на , получаем

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

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

Находя решение этой задачи, переходим к решению по формулам

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

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

Находя решение этой задачи, переходим к решению по формулам

Пример 4 Для матрицы из предыдущего примера имеем следующие задачи. Для 1-го игрока

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

Для второго игрока

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

Как следует из симплекс-метода, легче решить задачу для 2-го игрока. Для этого даже не потребуется введения искусственных переменных. За исходный базис можно принять дополнительные переменные, необходимые для перехода к канонической форме задачи. Опуская расчеты, приведем последнюю симплекс-таблицу, которая получена на четвертом шаге.

Базис
		-1/10	0	1	13/50	-3/25	-1/10	0,04
		61/5 0	1	0	-3/250	18/125	1/50	0,152
		27/50	0	0	21/250	1/125	7/50	0,064
		33/50	0	0	41/250	4/125	3/50	0,256

Таким образом , при том, что Отсюда

Проверив, что убеждаемся в правильности полученного ответа.

Из этой же таблицы находим решение двойственной задачи. Получаем, что

при том же Отсюда получаем

и

Таким образом, смешанные оптимальные стратегии 1-го игрока U* и 2-го игрока Z найдены, также как и цена игры v.