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

 

y1 … yj … ym

 

I игрок:

, ,

, (1)

, (2)

 

 

II игрок:

, (3)

 

, (4)

 

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

 

 

(5)

(6)

(7)

 

 

(8)

 

 

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

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

 

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

 

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

, где

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

 

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

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