Метод линейного программирования

Данный метод также относится к точным методам решения матричных игр и применим к игре G(m´n)при условии, что все элементы матрицы игры a_ij, i =1, …, m, j =1, …, n, положительны (этого легко добиться прибавлением ко всем элементам матрицы положительной константы, большей, чем модуль наименьшего отрицательного элемента или нуля, если отрицательных элементов нет).

Рассмотрим ситуацию, когда игрок A применяет свою оптимальную смешанную стратегию, а игрок B последовательно отвечает своими чистыми стратегиями B₁, …, B_n. Поскольку оптимальные стратегии обладают свойством устойчивости, то справедлива следующая система неравенств:

(3.2)

Введем новые переменные:

.

Система неравенств (3.2) теперь примет вид:

(3.3)

Так целью игры для игрока A является максимизация цены игры V, то получаем задачу линейного программирования:

при системе ограничений (3.3).

Решив эту задачу, найдем цену игры V и вероятности p_i в оптимальной смешанной стратегии S_A =(p_i), i =1,…,m,игрока A:

.

Аналогичные построения проводятся и для игрока B, учитывая, что целью игрока B является минимизация цены игры V.

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

при системе ограничений

.

Решив данную задачу, найдем вероятности q_j в оптимальной смешанной стратегии S_B =(q_j), j =1, …, n,игрока B.

В [5] доказано, что сформулированные задачи являются двойственными задачами линейного программирования, т.е. минимум линейной формы для одной из них совпадает с максимумом для другой. Для решения данных задач можно использовать, например, симплекс-метод.