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

Предположим, что цена игры положительна ( > 0). Если это не так, то согласно утверждению 1. п. 2.3 всегда можно подобрать такое число с, прибавление которого ко всем элементам матрицы выигрышей даёт матрицу с положительными элементами, и следовательно, с положительным значением цены игры. При этом оптимальные смешанные стратегии обоих игроков не изменяются.

Итак, пусть дана матричная игра с матрицей А порядка m хn. Согласно утверждению 2. п. 2.3 оптимальные смешанные стратегии Х^о = (х₁, ..., х_m),

Y^о = (y₁, ..., y_n) соответственно игроков 1 и 2 и цена игры  должны удовлетворять соотношениям.

(2.4)

(2.5)

Разделим все уравнения и неравенства в (2.4) и (2.5) на  (это можно сделать, т.к. по предположению  > 0) и введём обозначения :

, ,

Тогда (2.4) и (2.5) перепишется в виде :

, , , ,

, , , .

Поскольку первый игрок стремится найти такие значения х_i и, следовательно, t_i , чтобы цена игры  была максимальной, то решение первой задачи сводится к нахождению таких неотрицательных значений t_i , при которых

, . (2.6)

Поскольку второй игрок стремится найти такие значения y_j и, следовательно, s_j, чтобы цена игры  была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений s_j, , при которых

, .

Формулы (2.6) и (2.7) выражают двойственные друг другу задачи линейного программирования.

Решив эти задачи, получим значения t_i , s_j и цену игры .

Тогда смешанные стратегии x_i и y_j находятся по следующим формулам :

(2.8)