3. Сведение матричной игры к задаче линейного программирования

Коротко говоря, задача линейного программирования есть за­дача максимизации (или минимизации) линейной функции (назы­ваемой целевой функцией) при наличии линейных ограничений. Обычно ограничения имеют вид нестрогих неравенств, а на пере­менные налагается условие неотрицательности. Таким образом, самая обычная форма задачи линейного программирования та­кова: найти (х₁,...,x_т) так, чтобы

максимизировать (3.6)

при условиях , j=1,…, n, (3.7)

x_i > 0, (3.8)

или в матричных обозначениях:

максимизировать хС^T (3.9)

при условиях хА < В, (3.10)

х > 0. (3.11)

Следует указать, что такая форма записи задачи линейного про­граммирования не является наиболее общей. Действительно, может потребоваться не максимизировать целевую функцию, а ми­нимизировать ее. Некоторые ограничения могут иметь форму ра­венств, а некоторые переменные принимать и отрицательные зна­чения. Следует, однако, указать, что минимизация функции равно­сильна максимизации этой функции, взятой с противоположным знаком, равенство можно заменить двумя противоположными не­равенствами, а переменную, не имеющую ограничения на знак, можно выразить в виде разности двух неотрицательных перемен­ных. Поэтому, строго говоря, при рассмотрении задачи в виде (3.6) - (3.11) мы не теряем общности.

Множество всех точек, удовлетво­ряющих ограничениям (3.7) и (3.8), мы будем называть допу­стимым множеством задачи (3.6) - (3.8). Максимум выраже­ния (3.6) называется значением задачи.

Можно показать, что решение матричной игры можно свести к задаче линейного программирования. Действительно, если игрок I использует стратегию (х₁,...,х_m), он обеспечивает себе ожидаемый выигрыш не менее λ, где λ – любое число, такое, что

, j= 1,…,n.

Поэтому задача нахождения оптимальной стратегии для игрока I сводится к задаче линейного программирования:

максимизировать λ (3.12)

при условиях , j=1,…, n, (3.13)

, (3.14)

x_i > 0, i=1,…,m. (3.15)

Аналогично задача игрока II сводится к задаче линейного программирования:

минимизировать μ (3.16)

при условиях , i=1,…,m. (3.17)

, (3.18)

y_j > 0, j=1,…,n. (3.19)

Пусть требуется решить матричную игру Г = <х,у.Н>, x =={1,2, ...,m}, y =={1,2, ...,n}, для v > 0 (в противном случае можно прибавить достаточно большую константу, ко всем элементам матрицы выигры­шей этой игры, что не меняет множест­ва оптимальных стратегий игроков). Сведем данную игру Г к паре двойственных друг другу задач линейного прог­раммирования. Значением игры является минимальное из чисел v', для которых найдется вектор

(3.20)

удовлетворяющий неравенствам

H(i,Y)  v', (3.31)

а вектор Y*, для которого справедливы неравенства эти, при v' = v будет оптимальной стратегией игрока II. Таким образом, чтобы найти значение игры, надо найти минимальное значение v' , удовлетворяющее неравенству (3.21). В подробной записи неравенства (3.21) записываются следующим образом:

Положим и_j = _j /v' и разделим обе части последнего неравенства на v' оно примет следующий вид:

Учитывая, что

задача минимизации v' сведется к задаче максимизации 1/v, или, что то же самое, максимизации при ограничениях:

Пусть u* =(u₁*, u₂*, …, u_n*) — оптимальный план этой задачи линейного программирования; тогда

(3.22)

а оптимальная стратегия игрока II равна

Y* = (₁*, ₂*, …, _n*), где

(3.23)

Так как v>0 и оптимальная стратегия игрока II существует, все u_j* не могут одновременно равняться нулю, поэтому равенство (3.23) имеет смысл. Симметрич­ные рассуждения приводят нас к решению следующей задачи линейного программирования:

найти

при ограничениях

Если t* =(t₁*, t₂*, …, t_m*) - оптимальный план этой задачи, то

(3.24)

(3.25)

Последняя задача двойственна первой из рассмотрен­ных, поэтому имеет место равенство

.

Пример 3.4. Найти решение игры с матрицей вы­игрышей

Все элементы этой матрицы положительны, а седловой точки она не имеет.

Напишем задачу линейного программирования:

которая в канонической форме принимает вид

и₁ + и₂ + и₃ + и₄ = 1/v`—► max; (3.26)

5и₁ + 6 и₂ + 3и₃ + и₅ == 1,

10u₁ + 5и₂ + 12и₃ + 10u₄ + u₆ = 1, (3.27)

10 u₁ + 5и₃ + 20и₄ + u₇ = 1,

Таким образом, необходимо найти такие неотрица­тельные u_j, удовлетворяющие равенствам (3.27), при ко­торых линейная функция (3.26) достигает максимума.

В результате применения симплекс-метода находим

u* = (0, 1/6, 0, 1/60),

t* = (1/12, 1/10, 0),

1/v = 11/60.

Переходя от задачи линейного программирования к матричной игре и используя формулы (3.22) — (3.25), окончательно получим

Х* = (5/11, 6/11, 0),

У* = (0, 10/11, 0, 1/11),

v = 60/11.