- •Розділ 1. Предмет, особливості та сфери застосування математичного програмування в економіці. Класифікація задач
- •1.1. Предмет курсу «математичне програмування»
- •1.2. Найпростіша класифікація задач математичного програмування
- •1.3. Програма дисципліни «Оптимізаційні методи та моделі»
- •Тема 9. Задачі динамічного програмування
- •Тема 10. Моделі та методи стохастичного програмування
- •Тема 11. Елементи теорії ігор
- •Розділ 2. Загальна задача лінійного програмування та методи її розв’язування
- •2.1. Загальна математична модель лінійного програмування
- •2.2. Форми запису задач лп
- •2.3. Геометрична інтерпретація злп
- •2.4. Основні аналітичні властивості розв’язків задач лінійного програмування
- •2.5. Графічний метод розв’язування задач лінійного програмування
- •2.5.1. Основи графічного методу
- •2.5.2. Навчальні завдання. Розв’язування задач графічним методом
- •2.6. Симплексний метод розв’язування задач лп
- •2.6.1. Теоретичні відомості
- •2.6.2. Навчальні завдання розв’язування задач симплекс-методом
- •Розділ 3. Двоїстість у лінійному програмуванні
- •3.1. Поняття двоїстості. Правила побудови двоїстих задач
- •3.2. Теорема двоїстості
- •3.3. Навчальні завдання
- •Розділ 4. Економічна інтерпретація двоїстих задач. Аналіз оптимальних планів лінійних економіко-математичних моделей
- •4.1. Економічна інтерпретація двоїстої задачі
- •4.2. Навчальні завдання
- •Розділ 5. Транспортна задача
- •5.1. Постановка транспортної задачі
- •5.2. Метод потенціалів
- •5.3. Навчальні завдання
- •Розділ 6. Вибрані розділи математичного програмування
- •6.1. Цілочислове програмування
- •6.1.1. Постановка задачі
- •6.1.2. Метод Гоморі
- •6.1.3. Метод «віток і меж»
- •6.1.4. Приклади цілочислових економічних задач
- •6.2. Дробово-лінійне програмування
- •6.2.1. Постановка задачі та алгоритм розв’язування
- •6.2.2. Приклади дробово-лінійних задач
- •6.3. Нелінійне програмування
- •6.3.1. Постановка задачі
- •6.3.2. Труднощі розв’язування задач нелінійного програмування
- •6.3.3. Метод множників Лагранжа
- •6.3.4. Приклади задач нелінійного програмування
- •6.4. Динамічне програмування
- •6.4.1. Сутність динамічного програмування. Принципи оптимальності
- •6.4.2.Методикарозв’язування динамічних задач
- •6.4.3. Приклади розв’язування динамічних задач
- •6.5 Теорія ігор
- •6.5.1. Основні поняття теорії ігор
- •6.5.2. Зведення матричної гри до задачі лінійного програмування
- •6.6. Стохастичне програмування
- •6.6.1 Постановка задач і методи розв’язування
- •6.6.2. Приклади стохастичних економічних задач
6.5 Теорія ігор
6.5.1. Основні поняття теорії ігор
В умовах ринкової економіки дедалі частіше виникають конфліктні ситуації, коли два або більше колективи (індивідууми) мають протилежні цілі та інтереси, причому результат дій кожної зі сторін залежить від дій супротивника.
На практиці будують моделі конфліктних ситуацій, які називають іграми. Для розв’язування таких задач застосовують математичний апарат теорії ігор.
Зауважимо, що учасники ігрової ситуації не завжди мають протилежні цілі. Наприклад, дві фірми, які надають однакові послуги, об’єднуються з метою спільного протистояння більшому супернику. Часто однією зі сторін гри є природні процеси чи явища, наприклад погодні, тобто маємо гру людини та погоди. Погодою людина практично не керує, але вона має пристосуватися до її постійних змін.
Характерною особливістю ігрової ситуації є взаємодія протилежних (не завжди) інтересів двох чи більше «розумних» суперників, кожний з яких намагається оптимізувати свої рішення. Існує багато різних ігор, серед яких найпоширеніші стратегічні. У таких іграх джерелом невизначеності є відсутність інформації про його стратегію. Кожна протидіюча сторона (гравці) мають можливість вибору одного (або кількох) варіантів дій — стратегій. Стратегією гравця називають план, за яким він здійснює вибір у будь-якій можливій ситуації, і володіючи будь-якою фактично можливою інформацією.
Ігри будуються за певними правилами й відбуваються в результаті певної кількості ходів. Ходом теорії ігор називають вибір однієї з можливих, визначених правилами гри дій і реалізацію цієї дії. Кожному ходові гравців відповідає певний виграш (програш), який вони одержують (сплачують).
Завдання кожного гравця — знайти оптимальну стратегію, яка за багаторазового повторення гри забезпечує йому максимально можливий середній виграш.
Якщо у грі беруть участь два гравці, то така гра називається парною (грою двох осіб). Часто у грі беруть участь багато сторін.
Найчастіше розглядається гра з двома гравцями, в яких виграші однієї сторони дорівнюють програшу іншої, а сума виграшів обох сторін дорівнює нулю, що в теорії ігор називають грою двох осіб з нульовою сумою. Ці ситуації є типовими у практичній діяльності менеджерів, маркетологів, спеціалістів рекламних служб, які щоденно приймають рішення в умовах гострої конкуренції, неповноти інформації тощо. Основною метою розв’язування задач цього класу є розробка рекомендацій щодо вибору оптимальних стратегій дії конфліктуючих сторін із застосуванням методичних підходів теорії ігор.
Отже, маємо два гравці А і В (гра двох осіб з нульовою сумою). Кожний гравець обирає одну з можливих стратегій:
гравець А — стратегії , гравець В — стратегії.
Результати (плата) за всіма можливими варіантами гри задаються, як правило, спеціальними функціями (що залежать від стратегій гравців) у вигляді платіжної матриці.
Нехай (Аі; Вj) — виграш гравця А,
;
—виграш гравця В,
.
Оскільки гра з нульовою сумою, то .
Тоді в разі маємо.
Отже, мета гравця А максимізувати , а гравця В — її мінімізувати. Нехай, тобто маємо матрицю
,
рядки якої відповідають стратегіям Аі, а стовпці — стратегіям Вj.
Матриця А називається платіжною, а також матрицею гри. Елемент цієї матриці aij — виграш гравця А, якщо він вибрав стратегію Ai, а гравець В — стратегію Bj.
Із багатьох критеріїв, які пропонуються теорією гри для вибору раціональних варіантів рішень, найпоширенішим (песимістичним) є критерій мінімаксу-максиміну. Сутність його полягає ось у чому.
Нехай гравець А вибрав стратегію Аі. Тоді в найгіршому випадку він отримає виграш, що дорівнює . Якщо навіть гравець В знає його стратегію, гравець А має діяти так, щоб максимізувати свій мінімальний виграш:
.
Таку стратегію гравця А називають максимінною, а розмір його гарантованого виграшу — нижньою ціною гри.
Стратегія, яка забезпечує цей виграш, називається максимінною і позначається .
Гравець В, який програє суми в розмірі елементів платіжної матриці, навпаки, має обрати стратегію, що мінімізує його максимально можливий програш за всіма варіантами дій гравця А. Стратегію гравця В називають мінімаксною і позначають . Розмір його програшу —верхня ціна гри:
.
Оптимальний розв’язок цієї задачі досягається тоді, коли жодній стороні не вигідно змінювати обрану стратегію, оскільки суперник може у відповідь обрати іншу стратегію, яка дасть йому кращий результат. Якщо
,
тобто , то гра називаєтьсяцілком визначеною. Цілком визначені ігри називаються іграми із сідловою точкою. У цій ситуації оптимальним для обох гравців є вибір чистих стратегій — максимінної для гравця А і мінімаксної для В. Адже, якщо один із гравців додержує оптимальної стратегії, то для іншого відхилення від його оптимальної стратегії не може бути вигідним. Якщо гра не має сідлової точки, тобто і, то максимінно-мінімаксні стратегії не є оптимальними: кожна зі сторін може поліпшити свій результат, обираючи інший підхід. Оптимальний розв’язок такої гри знаходять, застосовуючизмішані стратегії, які є певними комбінаціями початкових чистих стратегій.
Імовірності (або частоти) вибору кожної стратегії задаються відповідними векторами.
Для гравця А: ,
де ;
Для гравця В: ,
де .
Очевидно, що ,;,.
Розглянемо гру, в якій є сідлова точка.
Задача 6.34.
За умови існування такої матриці розв’язок задачі — сідлову точку, ціну та оптимальні стратегії гри — можна знайти значно ефективніше:
Гравець A |
Гравець В
|
Розв’язування. Насамперед визначають домінуючу стратегію. Перша стратегія гравця А домінує над третьою, оскільки всі значення його виграшів за будь-яких дій суперника є не гіршими, ніж у разі вибору третьої стратегії, тобто всі елементи першого рядка платіжної матриці не менші за відповідні елементи її третього рядка. Тому третя стратегія гірша за першу й може бути вилучена з платіжної матриці.
Аналізуючи далі можливі дії гравця B, зауважимо, що його перша стратегія домінує над четвертою, яку можна відкинути як більш збиткову, а тому невигідну для цього гравця. Отже, маємо таку платіжну матрицю:
.
У разі вибору гравцем А першої стратегії, залежно від дій гравця В він може отримати 6, 3, 8 або 9 одиниць. Але завжди його виграш буде не меншим за , тобто незалежно від поведінки гравця В. Якщо розглянути можливі наслідки вибору гравцем А другої стратегії, то аналогічно його гарантований виграш становитиме. Для третьої стратегії відповідно маємо:.
Отже, нижня ціна гри: , а гравець А для максимізації мінімального виграшу має обрати другу з трьох можливих стратегій. Така стратегія є максимінною в цій грі.
Гравець В, який намагається мінімізувати свій програш, обираючи першу стратегію, може програти 6,6 або 4 одиниці. Але за будь-яких варіантів дій гравця А він може програти не більш як . Для другої стратегії маємо, для третьої —, для четвертої —. Отже, верхня ціна гри.
І гравцю В доцільно вибирати другу стратегію, яка є мінімаксною у грі.
Оскільки , ця гра має сідлову точку, ціна гри дорівнює 5. Оптимальною максимінною стратегією гравця А є друга з трьох можливих стратегій його дій. Для гравця В оптимальною є також друга з чотирьох можливих.