1.3.5 Пошук оптимальних змішаних стратегій за допомогою задач лінійного програмування.

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

ЗАУВАЖЕННЯ. Якщо до усіх елементів матриці А додати деяку константу або помножити всі елементи на константу, то оптимальні стратегії гравців не змінюються.

Тому, не обмежуючи спільності, можна вважати, що

Для цього до усіх елементів матриці А треба додати достатньо велике число С > 0( наприклад С=max ). При цьому виграш буде додатнім. Істинне значення гри може бути отримане відніманням С із модифікованого значення.

Тепер покажемо, що пошук оптимальної змішаної стратегії для кожного гравця можна звести до пошуку оптимального рішення деякої задачі лінійного програмування (ЗЛП).

Перший гравець вибирає стратегію р таким чином, щоб його виграш був максимальним для р

За визначенням

Запишемо послідовність рівностей та нерівностей

, для усіх j=1,…,n, де

. Нерівність справедливо, оскільки – це деяка чиста стратегія 2-го гравця, а чисті стратегії є підмножиною змішаних стратегій. Мінімум виграшу по усім стратегіям не може бути більше виграшу за довільної стратегії із цієї множини. В результаті отримаємо

, для усіх j=1,…,n

так як >0 (за зауваженням), то ділимо праву і ліву частину на

j=1,…,n

і робимо заміну змінних

і=1,…,m (1)

отримаємо

для усіх j=1,…,n

Відмітимо, що > 0, і=1,…,m. Так як >0, >0, і=1,…,m. Сумуючи праву і ліву частину рівності (1), маємо

, так как

А тоді, якщо , то

Отримаємо ЗЛП для пошуку оптимальної змішаної стратегії для 1-го гравця виду

(2)

j=1,…,n (3)

> 0, і=1,…,m (4)

Задача (2)-(4) – це ЗЛП, в якій коефіцієнти цільової функції і праві частини обмеження дорівнюють одиниці.

Розглянемо пошук оптимальної стратегії для 2-го гравця. Він прагне мінімізувати свій програш, тобто для q  . Тоді

, для усіх і=1,…,m, де – чиста стратегія 1-го гравця. Отримаємо

і=1,…,m

Ділимо обидві частини нерівності > 0 і проводимо заміну змінних