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

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

(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) достаточно решить каким-либо способом (например, с помощью симплекс-метода) одну из них, а затем по окончательной таблице определить решение второй.