13.1. Розв'язання матричної гри в змішаних стратегіях

магниевый скраб beletage

Гра розміром m X n в загальному випадку не має геометричної інтерпретації. Її розв'язування трудомістке, але принципових труднощів не має, оскільки може бути зведене до розв'язування пари двоїстих задач лінійного програмування.

розв'язання матричних

Нехай задано матричну гру m X n платіжною матрицею (13.1).a

a

av(13.1)\ami am2оптимальна змішана стратегія

Нехай SA =

An

P0

A1 A2 po Po

гравця А, p > 0, i = 1, m , p - ймовірність використання чистоїi=1

- оптимальна

стратегії A , ^ P = 1; SB =

Bn

qO

B1 B2

WO q0

змішана стратегія гравця В, qj > 0, j = 1, n , ^qj = 1, qj - ймовірність

j=i

використання чистої стратегії Bj, v - невідома ціна гри. Без обмеження узагальненості будемо вважати, що v > 0 . Цього можна добитися, якщо всі будуть a j > 0 .

Якщо гравець А застосовує свою оптимальну стратегію SA , а гравець В - деяку чисту стратегію Bj, тоді середній виграш складає a1Jpl + a2jP2 +... + amjPm, j = 1, n . Для оптимальної стратегії S"A всі середні виграші не можуть бути меншими, ніж ціна гри v (стратегія SA гравця А гарантує йому виграш не менш, ніж v , незалежно від вибору стратегії Bj гравцем В). В результаті таких міркувань одержимо систему нерівностей:

a11 P1 + a21 P2 + .

. + am1 Pm

> v,

a12 P1 + a22 P2 + .

. + am 2 Pm

> v,

a1nP1 + a2nP2 + .

.. + amn Pm

> v.

Перетворимо систему (13.2), поділивши всі члени на v , v > 0 і ввівши позначення

Xt = —, i = 1, m

(13.4)

v

a11x1

+ a21x2

+.

. + am1xm

> 1,

a12 x1

+ a22 x2

+.

. + am2 xm

> 1,

a1nx1

+ a2nx 2

+.

.. + amn xm

> 1.

Ціль гравця А полягає в тому, щоб максимізувати свій гарантований виграш, тобто ціну гри v .

1

m 1 З умови > pt = 1 випливає x1 + x2 +... + xm =— . Максимізація

i=1

ціни гри еквівалентна мінімізації величини — , тому задачу можна

v

(13.2)

(13.3)

сформулювати таким чином: визначити значення змінних

(13.5)

Xj > 0 , i = 1,m, так щоб вони задовольняли системі обмежень (13.4) і надавали мімінімум цільовій функції

Lx = x1 + x2 +... + xm ^ min.

Задача (13.4), (13.5) є задачею лінійного програмування, розв'язавши яку отримаємо оптимальне рішення матричної гри.

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

1 ^ max . Тоді визначимо систему обмежень (в лівих частинах

v

(13.6)

(13.7)

(13.8)

записані програші гравця В, які повинні не перевищувати ціни гри v , яку б чисту стратегію не застосовував би гравець А):

аіА + + ••

+ amqn

< v,

a2lql + a22q2 + ••

•+a2nqn

< v,

«mq + am 2 P2 +

•• + amnPn

< v-

Перетворимо систему (13.6), поділивши всі члени на v , v > 0

і ввівши позначення

Уі = — , J = і, n

v

«ііУі + ai2 У 2 + ••• + «іпУП < 1 «2і Уі + a22 У 2 + ••• + а2пУп < і

am1 Уі + am2У2 + ••• + «тпУп < L

^ і З умови ^ qj = і випливає Уі + У2 + ••• + ym = — . Мінімізація

J=і

і

ціни гри еквівалентна максимізації величини —, тому задачу

v

можна сформулювати таким чином: визначити значення змінних

yj > 0, j = 1,n , так щоб вони задовольняли системі обмежень (13.8) і надавали максимум цільовій функції

Ly = У + У2 +... + Уп ^ max .

Задача (13.8), (13.9) є задачею лінійного програмування, розв'язавши яку отримаємо оптимальне рішення матричної гри.

Проаналізував отримані задачі лінійного програмування (13.4), (13.5) і (13.8), (13.9) можна зробити висновок, що вони складають пару взаємнодвоїстих задач лінійного програмування. Очевидно, що при знаходженні оптимальних стратегій в конкретних задачах слід розв'язувати ту з взаємнодвоїстих задач, розв'язування якої менш трудомістке, а рішення другої знайти за допомогою теорем двоїстості.

Послідовність дій при розв'язанні матричної гри розміром m X n

Скоротити розмірність платіжної матриці гри шляхом виключення заздалегідь невигідних стратегій

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

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

Розв'язання однієї з пари двоїстих задач симплексним методом.

Виписування рішення матричної гри в змішаних стратегіях.

(13.9)

Приклад 13.1. Фірма може випускати три види продукції А1, А2, А3, отримуючи при цьому прибуток, який залежить від попиту, який може приймати один з чотирьох станів В1, В2, В3, В4. Прибуток, який отримає фірма при випуску i -го виду продукції' 4 3 4 2 3 4 6 5 2 5 13

Л

'ij

при j -му стані попиту aij є елементами матриціВизначити оптимальні пропорції випуску продукції.

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

Визначимо верхню і нижню ціни гри за алгоритмом знаходження максиміну (мінімаксу)

За формулою (12.5) маємо vm = max{2, 3, і} = 3 . За формулою

(12.6) маємо vm = min{4, 5, 6, 5} = 4 . Верхня і нижня ціни гри не

співпадають vm Ф v , тому гра сідлової точки не має.

Тому цю гру можна розв'язати в змішаних стратегіях шляхом зведення матричної гри пари до двоїстих задач.

(13.10)

(13.11)

Задача лінійного програмування, що відповідає визначенню оптимальної стратегії гравця А, має вигляд:

4хі + 3х2 + 2х3 > і, 3хі + 4х2 + 5х3 > і, 4хі + 6х2 + х3 > і, 2хі + 5х2 + 3х3 > і, хі > 0, i = і,3,

Lx = хі + х2 + х3 ^ min

Задача лінійного програмування, що відповідає визначенню оптимальної стратегії гравця В, має вигляд:

4 Уі + 3 У2 + 4У3 + 2У4 < і, 3 Уі + 4 У2 + 6 У3 + 5 У4 < і, *2Уі + 5У2 + У3 + 3У4 < і,          (13.12)

Уі > 0, j = Ї4,

Ly = y + У2 + У3 + y4 ^ max (13.13)

З аналізу пари взаємнодвоїстих задач лінійного програмування (13.10), (13.11) і (13.12), (13.13) випливає, що розв'язувати симплексним методом доцільно задачу (13.12), 13.13), оскільки вона не потребує введення штучних змінних.

Симплекс-метод знаходження оптимальних значень цільової функції це універсальний метод розв'язання задач лінійного програмування (ЗЛП), який розроблено Дж.Данцингом. В його основі лежить алгоритм симплексних перетворень системи лінійних рівнянь, що доповнений правилом, яке забезпечує перехід не до будь-якого, а до "кращого" опорного плану.

Суть симплексного методу полягає в тому, що спочатку отримують допустимий розв'язок, який задовольняє всім обмеженням, але не обов'язково оптимальний (початковий опорний план); опти- мальність досягається послідовним поліпшуванням початкового варіанту за декілька ітерацій. Напрямок переходу від одного опорного плану до другого вибирається за критерієм оптимальності (цільової функції).

Симплекс-метод основується на властивостях ЗЛП:

Якщо є екстремум, то він єдиний.

Множина всіх планів ЗЛП опукла.

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

Кожній вершині багатокутника розв'язків відповідає опорний план ЗЛП.

Якщо потрібно максимізувати цільову функцію, то можна перейти до мінімуму max Ly = min(-Ly).

Зведемо задачу (13.12), (13.13) до канонічного виду шляхом введення додаткових змінних - y5, y6, y7.

Якщо нерівність в системі обмежень ЗЛП має знак " < ", то додаткову змінну вводять зі знаком "+"; якщо нерівність має знак " > ", то додаткову змінну вводять зі знаком "- ".

ЗЛП (13.12), (13.13) в канонічній формі має наступний вигляд

4 y + 3 y2 + 4 Уз + 2 y4 + y5 < 1, 3Уі + 4 y 2 + 6 Уз + 5 У4 + Уб < 1, ' 2Уі + 5У2 + Уз + 3У4          + У7 < 1,

y > 0, j = їй,

-Ly = Уі - у2 - У3 - У4 ^ min

У векторній формі система обмежень (13.15) має вид

Р1У1 + Р2У2 + Р3У3 + Р4У4 + Р5У5 + РбУб + Р7У7 = Рс (13.15)

 

' 4Л

 

' 3Л

 

 

 

' 2Л

 

'1Л

 

' 0Л

 

' 0Л

де РІ =

3

v 2.

, Р2 =

4

v 5.

, Р3 =

б

,1.

, Р4 =

5

v 3.

, Р5=

0

v 0.

, Рб=

1

v 0.

, Р7 =

0

,1.

Ро = 1 .

Змінні x1, x2, x3, x4, є основними, x5, x6, x7 - додатковими. Вектори р5, р6, р7 утворюють одиничний базис і називаються базисними, причому р5 - перший базисний вектор.

Для здобуття одиничної матриці, яка складена з векторів при базисних змінних, слід вводити штучні змінні в систему обмежень таким чином:

якщо додаткова змінна має знак мінус, то в це рівняння вводять штучну змінну із знаком плюс;

якщо додаткова змінна має знак плюс, то в це рівняння штучну змінну вводити не потрібно.

Штучні змінні одночасно вводять в цільову функцію з невідомим додатнім коефіцієнтом М.

В нашому випадку штучні змінні вводити не слід.

Заповнимо першу симплекс-таблицю. Початкова симп- лекс-таблиця заповнюється таким чином. У першому рядку записують коефіцієнти цільової функції. У стовпець "Базис" записують базисні вектори. У стовпці "С" записують коефіцієнти цільової функції при базисних векторах. У стовпцях "р0", "р/', "р2", "р3", "р4", "р5", "Рб", "Р7" записують компоненти відповідних векторів.

Перша симплексна таблиця

Для заповнення клітин таблиці, які знаходяться в двох останніх рядках потрібно елементи стовпця "С" помножити на відповідні елементи стовпця, що розраховується, і відняти число, що стоїть в першому рядку (за винятком стовпця "р0"). Наприклад, для заповнення клітин стовпця "р2" помножимо елементи стовпця "С" на відповідні елементи стовпця "р2" і віднімемо число - 1: 03 + 04 + 05 - (- 1) = 1.

Таблиця 13.1

Б

С

Ро

-1

Рі

-1

Р2

-1

Рз

-1

Р4

0

Р5

0

Рб

0

Р7

Зо

Р5

0

1

4

3

4

2

1

0

0

1/4

Рб

0

1

3

4

б

5

0

1

0

1/6

Р7

0

1

2

5

1

3

0

0

1

1/1

ly - рядок

0

1

1

1

1

0

0

0

 

Останній рядок симплекс-таблиці називається індексним. В ньому, починаючи зі стовпця "рх", містяться оцінки оптимальності, за допомогою яких перевіряють оптимальність опорного плану, що відповідає даній таблиці. Значення складових опорного плану розташовані в стовпці "р0", причому небазисним змінним присвоюють нульові значення.

Першій симплекс-таблиці 13.1 відповідає опорний план:

Уі = 0 У 2 = 0 Уз = 0 У 4 = 0 У5 = 1, Уб = 1 У7 = 1.

Оптимальність опорного плану перевіряють за індексним рядком за допомогою критерію оптимальності.

Критерій оптимальності опорного плану:

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

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

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

У нашому випадку опорний план, що відповідає першій симп- лекс-таблиці, є не оптимальним.

Для переходу до наступної симплекс-таблиці в індексному рядку вибирають найбільшу додатну оцінку, починаючи із стовпця "рі".

У нашому випадку є чотири найбільших додатних оцінок, які співпадають, тому серед них виберемо будь-яку, наприклад це число 1 в стовпці "р3".

Стовпець, який відповідає найбільшій додатній оцінці, називається Розв'язувальним. Він показує який вектор слід ввести в базис.

В нашому випадку вектор "р3" слід ввести в базис.

Найдемо симплексне відношення оптимальності 00: елементи стовпця "р0" поділимо на додатні елементи розв'язувального стовпця. Рядок, який відповідає найменшому відношенню оптимальності 00, називається Розв'язувальним. Він показує який вектор слід вивести з базису.

В нашому випадку 90 = min j j = ^ . Таким чином, вектор

Р6 слід вивести з базису.

ГенеРальний елемент - це елемент, який розташований на перетині розв'язувального стовпця і розв'язувального рядка. У нашому випадку це число 6.

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

Розв'язувальний стовпець доповнити нулями. Якщо у розв'язувальному рядку є нулі, то відповідні стовпці переписати без змін.

Всі інші елементи розрахувати за допомогою методу прямокутників: якщо г - генеральний елемент, с - старий елемент, то п - новий елемент знаходять за формулою:

с - а•

n =

Таблиця 13.2

 

 

 

-1

-1

-1

-1

0

0

0

С.В.

Б

С

Ро

 

 

 

 

 

 

Рі

Р2

Рз

Р4

Р5

Рб

Р7

 

Р 5

0

2/6

2

2/6

0

-8/6

1

-4/6

0

1/6

Рз

-1

1/6

3/6

4/6

1

5/6

0

1/6

0

1/3

Р7

0

5/6

9/6

26/6

0

13/6

0

-1/6

1

5/9

L -

рядок

-1/6

1/2

2/6

0

1/6

0

-1/6

0

 

Симплексній таблиці 13.2 відповідає опорний план: У1 = 0, У2 = 0, У3 = 1/6, У4 = 0, y5 = 2/6, y6 = 0, y7 = 5/6. Він не є оптимальним, оскільки в індексному рядку є додатні оцінки.

г

Г        b

Таким чином, друга симплекс-таблиця має вид: Друга симплексна таблиця

За правилам, що описані вище, перейдемо до третьої симплексної таблиці:

Таблиця 13.3

Б

С

Ро

-1

Рі

-1

Р2

-1

Рз

-1

Р4

0

Р5

0

Рб

0

Р7

%

Рі

-1

1/6

1

1/6

0

-4/6

1/2

-2/6

0

-

Рз

-1

1/12

0

7/12

1

7/6

-3/12

2/6

0

1/14

Р7

0

7/12

0

49/12

0

19/6

3/4

1/3

1

7/38

Ly - рядок

-1/4

0

1/4

0

1/2

-1/4

0

0

 

Третій симплексній таблиці відповідає опорній план: Уі = 1/6, y2 = 0, Уз = 1/12, y4 = 0, y5 = 0, Уб = 0, y7 = 7/12. Він є не оптимальним, оскільки в індексному рядку є додатні оцінки.

Третя симплексна таблиця

Четверта симплексна таблиця

Перейдемо до четвертої симплексної таблиці:

Таблиця 13.4

Б

С

Ро

-1

-1

-1

-1

0

0

0

%

 

 

Рі

Р2

Рз

Р4

Р5

Рб

Р7

 

Рі

-1

3/14

1

 

 

0

 

 

0

 

Р 4

-1

1/14

0

1/2

6/7

1

-3/14

2/7

0

 

Р7

0

5/14

0

 

 

0

 

 

1

 

Ly -

рядок

-2/7

0

0

-3/7

0

-1/7

-1/7

0

 

Симплекс-таблиці 13.4 відповідає опорний план: У1 = 3/14, y2 = 0, У3 = 0, y 4 = 1/14, y 5 = 0, У6 = 0, У7 = 5/14. Він є оптимальним і єдиним, оскільки в індексному рядку немає додатних оцінок при небазисних векторах.

3

Таким чином, маємо рішення: y1 =— , y2 = 0 , y3 = 0 ,

  • 1        • / г ч 2   г 2

y4 = — , значення цільової функції min(-Ly) = —— ^ max Ly = — .

1        7

Оскільки maxLy =— , то v = —. За формулою (13.7) y v      2

знайдемо ймовірності використання чистих стратегій

3 7 3  Л 17 1

  • (9і = Уі v ): 91 = 14• 2 = 4 , 92 = 0 , 93 = 0 , 94 = 14• 2 = 4 , тоді

B1 B2 B3 Bt ^

^B = 3        1

B 3 0 0 1 14          4

1 1

  • Рішення другої з пази двоїстих задач: x1 = 0 , x2 = — , x3 =— . За формулою (13.3) знайдемо ймовірності використання чистих стратегій (Рі = xl v ): Р1 = 0 , Р2 =1 , Р3 =1, тоді

/ л л л \

^А =

Таким чином, фірмі (гравцю А) слід випускати 50% продукції А2, 50% продукції А3, продукцію А1 не випускати. Це дозволить фірмі отримати гарантовану середню величину прибутку, яка

дорівнює ціні гри v = 7, при будь-якому стані попиту.

А1

А2

A3

0

1

1

 

 

 

2

2

Щодо станів попиту можна зробити висновок, що оптимальний попит в 75% знаходиться в стані B1 і в 25% - в стані B4.