Алгоритм третього методу Гоморi

1. Зводимо ЗЛП (4.24) – (4.26) до МКЗЛП з цiлочисельними коефіцієнтами,

що визначає цiлочисельний МДБР x (0), для якого , j = 1,...,n.

2. Нехай на s -й iтерацiї одержана повністю цiлочисельна МКЗЛП з непрямими обмеженнями виду

що визначає цiлочисельний N -вимiрний МДБР x (s)= для якого

, j = 1,...,N.

3. Якщо i = 1,...,M, то кінець: x (s) є оптимальним розв'язком ПЦЗЛП.

4. Якщо для деякого i, такого, що j = 1,...,N, то кінець: ПЦЗЛП

(4.24) – (4.27) не має допустимих розв'язкiв. Якщо таких i немає, то

5. Знаходимо індекс l з умови: де мінімум визначається на

множині тільки тих i, для яких < 0. Знаходимо  = max (), де максимум

визначається на множині j = M +1,...,N, i будуємо додаткове обмеження (4.32) при

m= M та n= N.

6. Розширюємо симплекс-таблицю за рахунок (M +1)-го рядка (додаткове обмеження) та (N +1)-го стовпця, що відповідає додатковій змінній xN+1.

7. Знаходимо індекс k з умови: , де мінімум визначається на множині тільки тих j, для яких , j < 0. Переходимо до нового цiлочисельного МДБР x (s +1), виконуючи симплекс-перетворення з ведучими рядком (M+1) i стовпцем k. Якщо k — індекс однієї з додаткових змінних, то переходимо до пункту

8, iнакше — до пункту 3, заміняючи s на s +1, M на M +1, N на N +1.

8. Виключаємо з подальшого розгляду (викреслюємо) k -й стовпець та (M +1)-й (останній) рядок симплекс-таблицi, перенумеровуємо решту додаткових змінних для збереження неперервної нумерації всіх змінних задачі i переходимо до пункту 3, заміняючи s на s +1.

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

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

Стельмах

Стельмах

29-32.

Задачі теорії гри

Теорія ігор вперше була систематично викладена Нейманом і Моргенштерном та оприлюднена лише 1944 року в монографії «Теорія ігор і економічної поведінки», хоча окремі результати були опубліковані ще в 20-х роках. Нейман і Моргенштерн написали оригінальну книгу, яка містила переважно економічні приклади, оскільки економічні задачі простіше за інші описати за допомогою чисел. Під час другої світової війни і одразу після неї теорією ігор серйозно зацікавились військові, які одразу побачили в ній математичний апарат для дослідження стратегічних проблем і підготовки рішень. Потім головна увага знову була звернута до економічних проблем. Нині сфера застосування теорії ігор значно розширилась. Так, у соціальних науках апарат теорії ігор застосовується у психології для аналізу торгових угод та переговорів, а також для вивчення принципів формування коаліцій тощо.

Основні поняття теорії ігор

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

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

За умов ринкової економіки все частіше мають місце конфліктні ситуації, коли два або більше колективів (індивідуумів) мають протилежні цілі та інтереси, причому результат дії кожної із сторін залежить і від дії супротивника. Класичним прикладом конфліктної ситуації в економіці є відношення продавець — покупець (монополія — монопсонія). Складніші ситуації виникають, коли в суперечці інтересів беруть участь об'єднання чи коаліції.

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

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

Теорія ігор — це математичний апарат, що розглядає конфліктні ситуації, а також ситуації спільних дій кількох учасників. Завдання теорії ігор полягає у розробленні рекомендацій щодо раціональної поведінки учасників гри.

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

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

Існує дуже багато різних ігор. Прикладом «гри» в буквальному розумінні цього слова, передусім, є спортивна, карточна гра, шахи тощо. Від реальної конфліктної ситуації гра відрізняється не лише спрощеною формою, а також наявністю певних правил, за якими мають діяти її учасники. Дослідження таких формалізованих ігор звичайно не може дати чітких рекомендацій для реальних умов, проте є найзручнішим об'єктом для вивчення конфліктних ситуацій і оцінки можливих рішень з різних поглядів. Розраховані на основі ігрових моделей оптимальні плани не визначають єдино правильне рішення за складних реальних умов, проте слугують математично обґрунтованою підставою для прийняття таких рішень.

Класифікація ігор проводиться відповідно до вибраного критерію. Ігри можуть розрізнятися залежно від кількості гравців, кількості стратегій, властивостей функцій виграшу, можливостей взаємодії між гравцями.

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

Залежно від кількості стратегій розрізняють скінченні та нескінченні ігри. Якщо кожен гравець має скінченну кількість стратегій, то гра — скінченна, в іншому разі — нескінченна.

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

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

Матричні ігри двох осіб

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

Отже, маємо два гравці А і В (гра двох осіб з нульовою сумою). Кожний гравець вибирає одну із можливих стратегій: позначимо стратегії гравця А - , стратегії гравця В - .

Результати (плата) за всіма можливими варіантами гри задаються спеціальними функціями, які залежать від стратегій гравців, як правило, у вигляді платіжної матриці.

Нехай виграш гравця А, виграш гравця В.

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

Отже, мета гравця А — максимізувати величину , а гравця В — мінімізувати її. Нехай , тобто маємо матрицю А:

,

де рядки відповідають стратегіям , а стовпці — стратегіям .

Матриця А називається платіжною, а також матрицею гри. Елемент цієї матриці — це виграш гравця А, якщо він вибрав стратегію , а гравець В — стратегію .

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

Нехай гравець А вибрав стратегію , тоді у найгіршому разі він отримає виграш, що дорівнює , тобто навіть тоді, якщо гравець В і знав би стратегію гравця А. Передбачаючи таку можливість, гравець А має вибрати таку стратегію, щоб максимізувати свій мінімальний виграш, тобто .

Така стратегія гравця А позначається і має назву максимінної, а величина гарантованого виграшу цього гравця називається нижньою ціною гри.

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

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

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

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

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

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

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

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: