6.5.2. Зведення матричної гри до задачі лінійного програмування

Якщо матрична гра не має сідлової точки, то знаходження її розв’язку, особливо за великої кількості стратегій, — доволі складна задача, яку можна ефективно розв’язати методами лінійного програмування.

Задача розглядається в такому формулюванні: знайти вектори ймовірностей із метою визначення оптимального значення ціни гри та оптимальних стратегій.

Зауважимо, що доведено основну теорему теорії ігор: кожна скінчена гра має принаймні один розв’язок, який можливий в області змішаних стратегій.

Отже, нехай маємо скінченну матричну гру з платіжною матрицею

.

Оскільки оптимальні стратегії гравців А і В дозволяють отримати виграш

,

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

. (6.23)

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

. (6.24)

Ці два співвідношення застосовують для знаходження розв’язку гри.

Отже, потрібно знайти , щоб

за умов

,

,

.

Зауважимо, що ціна гри невідома і має бути визначена під час розв’язування задачі.

Модель ігрової задачі може бути спрощена.

З (6.23) маємо:

Поділивши всі обмеження на , дістанемо:

Нехай , тоді

Згідно з умовою , звідки.

Отже, цільова функція початкової задачі набирає такого вигляду:

.

У результаті задача лінійного програмування:

(6.25)

за умов

(6.26)

. (6.27)

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

За аналогією запишемо задачу лінійного програмування для визначення оптимальної стратегії гравця В. Нехай

.

Тоді маємо таку лінійну модель:

за умов

.

Очевидно, що задача лінійного програмування для гравця В є двоїстою до задачі гравця А, а тому оптимальний розв’язок однієї з них визначає оптимальний розв’язок спряженої.

Розглянемо приклад на застосування методів лінійного програмування до знаходження оптимального розв’язку гри.

Задача 6.35.

Агрофірма «Зоря» розробила шість бізнес-планів (А₁, А₂, А₃, А₄, А₅, А₆) для реалізації в наступному році. Залежно від зовнішніх умов (погодних умов, стану ринку тощо) виокремлено п’ять ситуацій (В₁, В₂, В₃, В₄, В₅). Для кожного варіанту А_і бізнес-плану та зовнішньої ситуаціїобчислено прибутки, наведені в такій таблиці:

Варіант бізнес-плану	Зовнішні ситуації
	В1	В2	В3	В4	В5
	Прибутки тис. грн.
А1	1,0	1,5	2,0	2,7	3,2
А2	1,2	1,4	2,5	2,9	3,1
А3	1,3	1,6	2,4	2,8	2,1
А4	2,1	2,4	3,0	2,7	1,8
А5	2,4	2,9	3,4	1,9	1,5
А6	2,6	2,7	3,1	2,3	2,0

Потрібно вибрати варіант бізнес-плану або комбінацію з розроблених планів.

Розв’язування.Маємо гру, платіжною матрицею якої є відповідні елементи наведеної таблиці. Легко переконатися, що домінуючих стратегій у цій грі немає.

Далі визначаємо:

;

;

,

а також

;

;

.

Отже, , тобто сідлової точки немає, а це означає, що потрібно скористатися моделлю (6.25)—(6.27):

за умов

.

Розв’язуємо цю задачу симплексним методом.