Обгрунтування господарських рішень та оцінювання ризиків - Донець Л.І. - РОЗДІЛ 13. Розв'язання матричних ігор методами лінійного програмування

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Змінні х1 , х2 , х3 , х4 , є основними, х5 , х6 , х7 - додатковими. Вектори р5, р , р7 утворюють одиничний базис і називаються базисними, причому р5 - перший базисний вектор.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблиця 13.2. Друга симплексна таблиця

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

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

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

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

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

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

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

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

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

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