- •1.Економіка як об’єкт математичного моделювання. Особливості та принципи математичного моделювання економіки. Класифікація економіко-математичних моделей
- •2. Особливості та принципи математичного моделювання економіки. Етапи побудови економіко-математичних моделей.
- •3.Загальна постановка оптимізаційної задачі, її структура. Цільова функція задачі лп. Система лінійних обмежень та її геометрична інтерпретація.
- •4.Приклади задач математичного моделювання в економіці. Класифікація задач і методів математичного програмування.
- •5.Система лінійних обмежень та її геометрична інтерпретація. Допустимий та оптимальний розвязки задачі лп, властивості розв’язків.
- •6. Алгоритм графічного методу розвязку задач лп, що містять дві змінні.
- •7. Форми запису задач лп, їх еквівалентність та способи перетворення.
- •8. Знаходження опорного розвязку . Симплексні таблиці, симплексні перетворення. Критерії оптимального розвязку задачі лп.
- •10. Основна та двоїста задачі як пара взаємоспряжених задач. Правила побудови двоїстої задачі. Знаходження розв’язків однієї задачі по розвязках іншої.
- •9. Опорний розвязок. Штучний базис, запис цільової функції та розвязок м-задачі лінійного програмування.
- •11. Правила побудови двоїстої задачі. Основні теореми двоїстості та їх економічний зміст.
- •13.Задачі цілочисельного лп. Геометрична інтерпретація системи обмежень задач цілочислового програмування.
- •15. Транспортна задача закритого типу. Методи північно-західного кута та найменшого елемента для побудови опорного розв’язку транспортної задачі і умова його невиродженості
- •Метод найменшої елемента
- •16. Метод потенціалів та умова існування оптимального розв’язку транспортної задачі. Побудова циклів пере розрахунку для знаходження нового опорного розв’язку
- •17. Відкрита транспортна задача, її математична модель. Розвязок відкритої транспортної задачі.
- •18. Загальна задача нелінійного програмування. Алгоритм застосування графічного методу розвязку задач нлп
- •19. Задачі дробово-лінійного програмування. Застосування симплексного методу для розв’язування задач дробово-лінійного програмування
- •20. Економічний зміст, деякі основні типи задач та моделі динамічного програмування. Алгоритм методу динамічного програмування
- •21. Поняття про принципи оптимальності Беллмана та його застосування
- •22.Загальна постановка задачі схоластичного програмування, її особливості щодо оперативного управління та перспективного планування. Класифікація
- •25. Матричні ігри двох осіб. Гра у чистих стратегіях. Максимінна та мінімаксна стратегія. Сідлова точка.
- •26. Змішані стратегії. Приведення задачі ігор зі змішаними стратегіями до задачі лп. Основна теорема теорії матричних ігор.
- •Нехай маємо скінченну матричну гру з платіжною матрицею
20. Економічний зміст, деякі основні типи задач та моделі динамічного програмування. Алгоритм методу динамічного програмування
Всі економічні процеси та явища є динамічними, оскільки вони функціонують і розвиваються не тільки у просторі, але й у часі. Для народного господарства в цілому, його галузей, регіонів чи окремих підприємств з метою їх стабільного функціонування та розвитку необхідно розробляти стратегічні та тактичні плани. Стратегічні плани містять параметри діяльності об’єктів, які характеризують їх віддалене майбутнє. Отже, вони мають розроблятися на основі динамічних моделей, для знаходження розв’язків яких застосовуються методи динамічного програмування.
Динамічне програмування являє собою математичний апарат, що дає змогу здійснювати планування багатокрокових керованих процесів, а також процесів, які розвиваються у часі.
Отже, динамічне програмування не є окремим методом розв’язування задач, а являє собою теорію, що поєднує ряд однотипних ідей та прийомів, які застосовуються для розв’язування досить різних за змістом задач.
До задач динамічного програмування належать такі, що пов’язані з оптимальним розподілом капіталовкладень, розподілом продукції між різними регіонами, визначенням найкоротшого шляху завезення товарів споживачам, задачі щодо заміни устаткування, оптимального управління запасами тощо.
Економічні процеси можна уявити складеними з кількох етапів (кроків). На кожному з них здійснюється вплив на розвиток всього процесу. Тому у разі планування багатоетапних процесів прийняття рішень на кожному етапі має враховувати попередні зміни та бути підпорядкованим кінцевому результату. Динамічне програмування дає змогу прийняти ряд послідовних рішень, що забезпечує оптимальність розвитку процесу в цілому.
Слід зазначити, що оптимальні плани стосовно окремих відрізків планового періоду не завжди є оптимальними для всього інтервалу планування. Наприклад, недостатньо визначити оптимальний план виробництва на один місяць і орієнтуватися на нього протягом тривалого часу. Досить ймовірно, що в наступні місяці виробництво за тим самим планом може стати неоптимальним, оскільки за його розроблення можливості дальшого розвитку не враховувались. Доцільніше визначати оптимальні плани на кожен місяць з урахуванням змін у попередніх періодах. Лише тоді річний оптимальний план виробництва буде сумарним результатом оптимальних рішень, що приймалися для кожного місяця.
На практиці часто доводиться зустрічатись з випадками, коли метою (ціллю) оптимізації є встановлення найкращої послідовності тих чи інших робіт (виробничих операцій, етапів будівництва різних споруд тощо). З подібною метою зустрічаються при розв’язанні задач так званого динамічного програмування.
Однією
з перших задач такого роду, що привернули
увагу математиків, була так звана задача
про комівояжера (мандрівного торговця).
Суть її така: є
міст
з
заданими між ними відстанями
.
Потрібно, відправившись з
,
вибрати такий маршрут пересування
,
при якому комівояжер, побувавши в кожному
місті по одному разу, повернувся б до
вихідного пункту
,
пройшовши при цьому мінімально можливий
сумарний шлях.
Основний спосіб динамічного програмування полягає в знаходженні правил домінування, які дозволяють робити порівняння варіантів розвитку послідовностей і завчасне відсіювання безперспективних варіантів. У ряді випадків в задачах динамічного програмування вдається одержати такі сильні правила домінування, що вони визначають елементи оптимальної послідовності однозначно один за одним. В такому випадку правила домінування називають розв’язувальними правилами.
Розв’язувальні
правила звичайно виводяться за допомогою
принципу оптимальності Беллмана. Суть
принципу оптимальності така. Нехай
критерій
(задається
формулою або алгоритмом), який дає
числову оцінку якості варіанта
(послідовності)
,
можна застосовувати не тільки до всієї
послідовності, але і до будь-якого її
початкового відрізку
.
Послідовність
,
якій відповідає екстремальне значення
критерію
,
називається оптимальною. Якщо будь-який
початковий відрізок оптимальної
послідовності також оптимальний (в
класі всіх послідовностей, складених
з тих же елементів, і можливо, такий, що
має ті ж початок і кінець, що і даний
відрізок), то вважають, що для відповідної
задачі справедливий принцип оптимальності.
Розглянемо зразок розв’язання задачі про комівояжера методом динамічного програмування:
1.
Введення даних про пункти
і
відстані між пунктами i та j
dij (dij =0 при i=j)
.
2. Обчислення всіх можливих варіантів відстаней, що складаються з трьох дільниць A0, Ai1, Ai2, Ai3. Вони групуються по останньому пункту і з них залишаються ті варіанти, що об’єднують однакові пункти, але мають найменший шлях.
3. До тих варіантів, що залишились додають ще четверту дільницю і повторюють процедуру з пункту 2. Це повторюється для п’ятої, шостої і т. д. дільниць, доки не повертається в пункт А0. Той варіант (чи варіанти), що залишилися, і визначають найкоротший шлях, по якому комівояжеру можна об’їздити всі місті Аi (i=0,…,n), якщо він почне та закінчить свою подорож в А0.
