Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Приклади розв’язування динамічних задач



Задача 6.23.

Фірма планує нарощувати виробничі потужності на чотирьох підприємствах, маючи для цього 4 млн грн. Для кожного з підприємств розроблено інвестиційні проекти, які відбивають прогнозовані сумарні витрати С та доходи D, пов’язані з реалізацією кожного проекту. Зміст цих проектів ілюструє таблиця:

 

Проект Підприємство

 

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

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

Розв’яжемо цю задачу за алгоритмом (методом) зворотного прогону. Кроками задачі вважатимемо кожне з чотирьох підприємств, оскільки для кожного з них маємо вибрати оптимальний інвестиційний проект за обмежених грошових ресурсів.

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

Змінні задачі візьмемо так, щоб послідовно керувати процесом розподілу коштів:

— обсяг капіталовкладень, виділених на кроках 1—4;

— те саме на кроках 2—4;

— те саме на кроках 3 і 4;

— те саме на кроці 4.

— обсяги інвестицій на і-му підприємстві .

— оптимальні обсяги інвестицій на і-му підприємстві.

Рекурентне співвідношення для зворотного прогону від кроку 4-го до 1-го (від четвертого підприємства до першого) подається у вигляді:

,

, ,

де — сумарна ефективність інвестицій з і-го кроку до останнього.

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



Виконаємо поетапні розрахунки за цією моделлю.

Етап 4.

.

Результати розрахунків подамо таблицею:

 

Дохід Оптимальний розв’язок
     
     
   
 
 

Етап 3.

за умов

,

Результати розрахунків відбиває таблиця:

 

Дохід Оптимальний розв’язок  
     
     
   
 
2 або 4
               

 

Розрахунки виконуються так. Нехай потрібно знайти . Обчислюємо

.

Отже,

,

,

.

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



.

Етап 2.

за умов

, .

Результати розрахунків подаємо таблицею:

 

Дохід Оптимальний розв’язок
       
     
   
 
 

 

Етап 1.

за умов

, .

Виконуємо розрахунки лише для х1 = 4, подаючи їх у вигляді таблиці:

 

Дохід Оптимальний розв’язок
 

 

Знайдемо оптимальний план. Із таблиці першого кроку випливає, що , тобто для першого підприємства реалізується другий проект, який використовує 1 млн грн. інвестицій з ефективністю 3 млн грн. Отже, для другого, третього і четвертого підприємств залишається 4 – 1 = 3 млн грн. інвестицій. Із таблиці другого кроку маємо, що за умов х2 = 3 максимальний ефект настає в разі реалізації для другого підприємства першого проекту (k2 = 1), ефективність становить 4 млн грн. Отже, х3 = 3 – 1 = 2, тобто для третього і четвертого підприємств слід використати 2 млн грн. інвестицій. Із таблиці третього кроку за умов х3 = 2 маємо, що k3 = 0. Отже, х4 = 2, а йому відповідають капітальні вкладення k4 = 2, ефективність яких 8 млн грн. Остаточно маємо: ефективність 4 млн грн. інвестицій становить 3 + 4 + 8 = 15 (млн грн.).

Задача 6.24.

Підприємство розробляє стратегію поповнення запасів деякої продукції для заданого періоду часу, який складається з N етапів (підперіодів). Для кожного з них відомий розмір попиту, причому він не є однаковим для всіх етапів. Щоб задовольнити попит, підприємство може придбати необхідну кількість продукції, замовивши її у виробника, або виготовити її самостійно. Передбачається, що запаси поповнюються миттєво, запізнення поставки та дефіцит неприпустимі. Залежно від ринкової кон’юнктури підприємству може бути вигідно створювати запаси продукції для задоволення попиту в майбутні періоди часу, що пов’язано, проте, з додатковими витратами на зберігання запасів.

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

Дані задачі вміщено в таблиці:

 

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

 

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

Нехай — кількість етапів планового періоду. Тоді для і-го етапу застосуємо такі позначення: хі — запас продукції на початок етапу; yi — обсяг замовленої продукції (розмір замовлення); hi — витрати на зберігання 1 тис. од. продукції запасу; kі — витрати на розміщення замовлення; — попит на продукцію; Ciyi — витрати, що пов’язані із купівлею (виробництвом) продукції yi.

Визначимо f (xi, yi) як мінімальні витрати на етапах , якщо рівень запасів хі.

Рекурентні залежності, що відповідають схемі зворотного прогону, набирають вигляду:

за умов

, , .

Для N-го етапу маємо:

за умов

, .

Розглянемо покроковий розрахунок оптимальної стратегії управління запасами.

Етап 4. Маємо

за умов

.

Можливі варіанти розв’язків ілюструє таблиця:

 

Оптимальний розв’язок
   
   
 

Етап 3. Маємо

за умов .

Результати розрахунків подамо у вигляді таблиці:

Доходи Оптимальний розв’язок
     
     
     
       
       
         

 


Розрахунки виконуємо так. Наприклад, обчислимо і . Оскільки за умовою , то може набувати значень 0, 1, 2, 3, 4, 5, а — відповідно значень 0, 1, 2, 3, 4, 5. Тепер знайдемо і для і . Для і маємо:

.

Аналогічно:

,

.

Далі обчислюємо:

Отже, при .

Так само виконуємо розрахунки для х = 1, 2, 3, 4, 5, а результати вміщуємо у відповідну таблицю.

Етап 2. У таблицю записуємо лише остаточні результати:

Маємо b3 = 5.

за умов

.

 

Етап 1. Діємо так, як і на етапі 2, складаючи таблицю результатів:

 


Оптимальні розв ’язки
         
         
         
         
         
         
           
              0 або 2
               
                 
                   

 

 

Оптимальні розв’язки
2 або 4

 


Маємо b1 = 4.

за умов

.

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

Інформацію про перший оптимальний план містить таблиця:

 

Етап Запас Розмір замовлення Попит Залишок продукції на кінець етапу Витрати на придбання продукції та її зберігання
Разом        

 

Інформація про другий оптимальний план:

 

Етап Запас Розмір замовлення Попит Залишок продукції на кінець етапу Витрати на придбання продукції та її зберігання
Разом        

 

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

 

Теорія ігор

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

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

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

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

Характерною особливістю ігрової ситуації є взаємодія протилежних (не завжди) інтересів двох чи більше «розумних» суперників, кожний з яких намагається оптимізувати свої рішення. Існує багато різних ігор, серед яких найпоширеніші стратегічні. У таких іграх джерелом невизначеності є відсутність інформації про його стратегію. Кожна протидіюча сторона (гравці) мають можливість вибору одного (або кількох) варіантів дій — стратегій. Стратегією гравця називають план, за яким він здійснює вибір у будь-якій можливій ситуації, і володіючи будь-якою фактично можливою інформацією.

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

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

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

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

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

гравець А — стратегії , гравець В — стратегії .

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

Нехай (Аі; Вj) — виграш гравця А,

;

— виграш гравця В,

.

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

Тоді в разі маємо .

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

,

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

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

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

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

.

Таку стратегію гравця А називають максимінною, а розмір його гарантованого виграшу — нижньою ціною гри.

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

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

.

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

,

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

Імовірності (або частоти) вибору кожної стратегії задаються відповідними векторами.

Для гравця А: ,

де ;

Для гравця В: ,

де .

Очевидно, що , ; , .

Розглянемо гру, в якій є сідлова точка.

Задача 6.34.

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

За умови існування такої матриці розв’язок задачі — сідлову точку, ціну та оптимальні стратегії гри — можна знайти значно ефективніше:

 

Гравець A Гравець В

 

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

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

.

У разі вибору гравцем А першої стратегії, залежно від дій гравця В він може отримати 6, 3, 8 або 9 одиниць. Але завжди його виграш буде не меншим за , тобто незалежно від поведінки гравця В. Якщо розглянути можливі наслідки вибору гравцем А другої стратегії, то аналогічно його гарантований виграш становитиме . Для третьої стратегії відповідно маємо: .

Отже, нижня ціна гри: , а гравець А для максимізації мінімального виграшу має обрати другу з трьох можливих стратегій. Така стратегія є максимінною в цій грі.

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

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

Оскільки , ця гра має сідлову точку, ціна гри дорівнює 5. Оптимальною максимінною стратегією гравця А є друга з трьох можливих стратегій його дій. Для гравця В оптимальною є також друга з чотирьох можливих.


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!