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

Рішення гри mn у загальному випадку може бути зведене до розв’язання задачі лінійного програмування. Нехай гра mn задана платіжною матрицею (табл. 7.1). Необхідно визначити оптимальні стратегії і , де – ймовірності застосування відповідних чистих стратегій ; , .

Будемо вважати, що ціна гри ; цього завжди можна досягти, зробив-ши всі елементи (див. зауваження 7.1).

Якщо гравець A застосовує змішану стратегію проти будь-якої чистої стратегії гравця B, то він одержує середній виграш (математичне очікування виграшу) .

Усі середні виграші a_j не менше ціни гри v, тому маємо систему нерівностей:

(7.1)

Кожну з нерівностей поділимо на число і введемо нові змінні: . Тоді система (7.1) матиме вид:

де тому що і .

Мета гравця A – максимізувати свій гарантований виграш, тобто ціну гри v.

Поділивши на рівність , маємо . Максимізація ціни гри v еквівалентна мінімізації величини , тому задача може бути сформульована наступним чином.

Дано:		(7.2)
Знайти такий план , при якому

Це задача лінійного програмування. Розв’язуючи задачу (7.2), отримаємо оптимальне рішення і оптимальну стратегію.

Оптимальна стратегія забезпечує гравцю B середній програш, не більший, ніж ціна гри v за будь-якої стратегії гравця A. Тому змінні задовольняють нерівностям

Якщо позначити , то одержимо систему нерівностей:

де тому що і .

Мета гравця B – мінімізувати свій гарантований програш, тобто ціну гри v.

Поділивши на рівність , маємо . Мінімізація ціни гри v еквівалентна максимізації величини , тому задача може бути сформульована наступним чином.

Дано:		(7.3)
Знайти такий план , при якому

Розв’язок задачі лінійного програмування (7.3) визначає оптимальну стратегію гравця B. При цьому ціна гри

_.

Задачі (7.2) і (7.3) є взаємно-подвійними задачами лінійного програмування. При визначенні оптимальних стратегій у конкретних задачах варто обрати ту із взаємно-подвійних задач, розв’язання якої легше, а рішення іншої задачі знайти за допомогою теорем подвійності.

Задача 7.3. Підприємство може випускати три види продукції (A₁, A₂, A₃), одержуючи при цьому прибуток, який залежить від попиту, що може бути в одному з чотирьох станів (B₁, B₂, B₃, B₄). Дано матрицю (табл. 7.3), її елементи a_ij характеризують прибуток, що одержить підприємство при випуску одиниці i-ї продукції за j-м станом попиту. Визначити оптимальні пропорції у випуску продукції за умови максимізації середнього гарантованого прибутку.

Рішення

Таблиця 7.3

	B1	B2	B3	B4
A1	0	1	3	5
A2	6	7	1	–1
A3	4	4	2	1

1. Задача зводиться до ігрової моделі, у якій гра підприємства A проти попиту B задана платіжною матрицею (див. табл. 7.3).

Перш ніж розв’язувати задачу, треба спробувати спростити гру,

провівши аналіз платіжної матриці і відкинувши явно невигідні або дублюючі стратегії. Друга стратегія гравця B (другий стовпець матриці (див. табл. 7.3)) є явно невигідною для гравця B у порівнянні з першою (елементи другого стовпця більше елементів першого стовпця), оскільки мета гравця B – зменшити свій програш. Тому другий стовпець можна відкинути. Одержимо матрицю P:

.

2. Визначимо нижню і верхню ціни гри P в табл. 7.4.

Таблиця 7.4

	B1	B3	B4	i
A1	0	3	5	0
A2	6	1	–1	–1
A3	4	2	1	1
j	6	3	5	1 3

Нижня ціна гри , верхня ціна . Оскільки , гра не має сідлової точки, і оптимальне рішення шукаємо в змішаних стратегіях гравців:

і _.

Ціна гри .

3. Матриця P даної гри має від’ємний елемент, тому переходимо до еквівалентної гри з платіжною матрицею

,

де k – найбільший за модулем від’ємний елемент матриці P, тобто (див. зауваження 7.1).

Таким чином,

.

Ціна еквівалентної гри .

4. Позначивши , складемо дві взаємно-подвійні задачі лінійного програмування (див. (7.2) і (7.3)).

Задача 1	Задача 2

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

Приводимо задачу 2 до канонічного виду:

Будуємо розширену матрицю системи обмежень

.

Базисні змінні: y₄, y₅, y₆; вільні змінні: y₁, y₂, y₃. Базисний розв’язок: . Він є опорним планом (усі його компоненти невід’ємні).

Перевіряємо даний опорний план на оптимальність.

Заповнюємо першу симплексну таблицю.

Таблиця 7.5

Б	сБ	b	y1	y2	y3	y4	y5	y6
			–1	–1	–1	0	0	0
y4	0	1	1	4	6	1	0	0
y5	0	1	7	2	0	0	1	0
y6	0	1	5	3	2	0	0	1
		0	1	1	1	0	0	0

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

Опорний план не є оптимальним, тому що серед оцінок оптимальності є додатні оцінки.

Переходимо до нового опорного плану. Змінним y₁, y₂, y₃ відповідають однакові додатні оцінки оптимальності, які дорівнюють 1. Тому вводимо в базис одну з цих змінних, наприклад, y₂. Змінну y₄ виводимо з базису, тому що їй відповідає мінімальне значення із симплексних відносин: .За допомогою елементарних перетворень у другому стовпці розширеної матриці будуємо одиничний вектор, у якого 1 розташована в ключовому рядку I.

.

Базисні змінні: y₂, y₅, y₆; вільні змінні: y₁, y₃, y₄. Новий базисний розв’язок – новий опорний план.

Заповнюємо другу симплекс-таблицю.

Таблиця 7.6

Б	сБ	b	y1	y2	y3	y4	y5	y6
			–1	–1	–1	0	0	0
y2	–1	1/4	1/4	1	3/2	1/4	0	0
y5	0	1/2	13/2	0	–3	–1/2	1	0
y6	0	1/4	17/4	0	–5/2	–3/4	0	1
		–1/4	3/4	0	–1/2	–1/4	0	0

Опорний план не є оптимальним, тому що серед оцінок оптимальності є додатна оцінка 3/4.

Знов переходимо до нового опорного плану. Змінну y₁ вводимо в базис, оскільки цій змінній відповідає додатна оцінка 3/4. Змінну y₄ виводимо з базису, тому що їй відповідає мінімальне значення із симплексних відносин: .За допомогою елементарних перетворень у першому стовпці розширеної матриці будуємо одиничний вектор, у якого 1 знаходиться в ключовому рядку III.

.

Базисні змінні: y₁, y₂, y₅; вільні змінні: y₃, y₄, y₆. Базисний розв’язок – новий опорний план.

Заповнюємо третю симплекс-таблицю:

Таблиця 7.7

Б	сБ	b	y1	y2	y3	y4	y5	y6
			–1	–1	–1	0	0	0
y2	–1	4/17	0	1	28/17	5/17	0	–1/17
y5	0	2/17	0	0	14/17	11/17	1	–26/17
y1	–1	1/17	1	0	–10/17	–3/17	0	4/17
		–5/17	0	0	–1/17	–2/17	0	–3/17

Опорний план є оптимальним, тому що в останньому рядку всі оцінки недодатні. Отже,

, , .

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

, , ;

.

7. Визначимо оптимальний розв’язок задачі 1 за допомогою теорем подвійності. На основі першої теореми подвійності . На основі другої теореми подвійності компоненти оптимального розв’язку задачі 1 дорівнюють абсолютним значенням оцінок оптимальності, що відповідають змінним , у підсумковій симплекс-таблиці 7.7.

, , .

За цими даними знаходимо оптимальну стратегію :

; ; ; .

Повертаючись до вихідної гри, одержимо оптимальну ціну

.

Висновок: оптимальна стратегія підприємства , тобто підприємство має випустити 40% продукції A₁ і 60% продукції A₃, а продукцію A₂ не випускати. Оптимальна стратегія попиту (тут враховано, що другий стовпець вихідної матриці був відкинутий як невигідний), тобто оптимальний попит у 20% перебуває в стані B₁ і в 80% – у стані B₃.

При вирішенні довільної кінцевої гри розміру mn доцільно дотримуватись наступної схеми:

1. Виключити з платіжної матриці явно невигідні стратегії в порівнянні з іншими стратегіями. Такими стратегіями для гравця A (гравця B) є ті, котрим відповідають рядки (стовпці) з елементами, меншими (більшими) у порівнянні з відповідними елементами деякого з інших рядків (стовпців).

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

3. Якщо гра не має сідлової точки, то рішення треба шукати в змішаних стратегіях. Для ігор розміру mn рекомендується симплекс-метод, для ігор розміру 22, 2 n, n 2 можливе геометричне рішення.