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

y1 … yj … ym

I игрок:

, ,

, (1)

, (2)

II игрок:

, (3)

, (4)

Разделим на цену игры n 1, 2, 3, 4 уравнения:

(5)

(6)

(7)

(8)

Для первого игрока наши преобразования привели к задаче: Минимизировать линейную форму при ограничениях (1):

Для II игрока наши преобразования привели к задаче: Максимизировать линейную форму при ограничениях:

Это две задачи линейного программирования.

Задачи максимизации или минимизации линейных форм вида:

, где

— постоянный коэффициент при условиях:

Можно было бы ограничиться только третьим уравнением. Эта задача называется задачей линейного программирования, требуется найти максимум или минимум линейной формы от n переменных при m линейных ограничениях в виде равенств или неравенств. Это определение общей задачи линейного программирования.

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