Обгрунтування господарських рішень та оцінювання ризиків – Донець Л. І. – РОЗДІЛ 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.