Решение игры методом линейного программирования

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

Рассмотрим игру, заданную матрицей: . Будем считать, что все элементы C_ij > 0. Если это не так, то прибавим ко всем элементам матрицы C некоторое число M > 0 (C_ij + M = ), такое, что получим матрицу , для которой все > 0. Игра с матрицей эквивалентна игре с матрицей C в том смысле, что оптимальные смешанные стратегии этих игр совпадают, а цена игр отличается на число M (во второй игре цена больше на M, чем в первой).

Рассмотрим игру двух лиц A и B с нулевой суммой. У игрока A – m чистых стратегий A_i, ; а у игрока B – n чистых стратегий B_j, .

Платежная матрица имеет вид:

Пусть α ≠ β, седловой точки нет и смешанные стратегии игроков будем искать в виде.

При любой стратегии B_j игрока B выигрыш игрока A должен быть не менее чем цена игры v, то есть:

(1).

Разделим на v левую и правую части:

(2).

Обозначим (3), тогда (4) и получим:

, (5).

Подставим (4) в выражение получим:

=> , и так как v → max, то , отсюда получим целевую функцию:

.

Математическая модель задачи игрока A имеет вид:

или

, где , .

Рассуждая аналогично относительно действий игрока B, получим задачу игрока B:

, где , .

Решив пару двойственных задач линейного программирования, получим решение игры.