Теоретико-игровые методы принятия решений (Еремеев А

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

Данный метод также относится к точным методам решения матричных игр и применим к игре 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] доказано, что сформулированные задачи являются двойственными задачами линейного программирования, т.е. минимум линейной формы для одной из них совпадает с максимумом для другой. Для решения данных задач можно использовать, например, симплекс-метод.

Содержание