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

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

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

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

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

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

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

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

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

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

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

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

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

Задача (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. Розвязання матричних ігор методами лінійного програмування

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

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

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

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

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

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

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

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

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

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

З аналізу пари взаємнодвоїстих задач лінійного програмування (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) в канонічній формі має наступний вигляд

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 4,50 out of 5)

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