5.10. Сведение матричной игры к задаче линейного программирования Рассмотрим игру, платежная матрица которой имеет размерность

A= .

Матрица не содержит седловой точки, поэтому решение игры представлено в смешанных стратегиях:

При оптимальной стратегии игрока А выполняется условие:

(5.14)

(5.15)

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

(5.16)

Величина V (цена игры) неизвестна, но можно считать V > 0, имея в виду, что элементы матрицы А неотрицательны. Этого всегда можно добиться, прибавив ко всем элементам матрицы некоторое положительное число. Преобразуем систему ограничений, разделив все члены неравенства на величину V. В результате получим

(5.17)

Из условия

Решение игры должно максимизировать значение V, следовательно, функция

должна принимать минимальное значение. Таким образом, получена задача линейного программирования:

. (5.18)

при ограничениях типа (5.15) и условиях неотрицательности:

Решая ее, находим значение t_i и величину 1/V, затем определяем значения

(5.19)

Для определения стратегии игрока В запишем следующие условия:

(5.20)

Разделив все члены неравенства на V, получим

(5.21)

где

Переменные U_j должны быть определены таким образом, чтобы выполнялось условие (5.19) и достигался максимум функции

(5.22)

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