Математичне моделювання засобами динамічного програмування - Курсовая работа

Актуальність роботи полягає у тому, що у наш час наука приділяє все велику увагу питанням організації та управлінню, це призводить до необхідності аналізу складних цілеспрямованих процесів під кутом зору їх структури і організації. Існують різні методи вирішення даних моделей, одним із таких методів є метод динамічного програмування. Динамічне програмування - математичний метод, заслуга створення й розвитку якого належить, перш за все, Роберту Беллману, яким було сформульовано принцип оптимальності, який лежить в основі методу. Цінність методів динамічного програмування полягає частково в тому, що вони дозволяють для ряду задач, які не можуть бути розвязані за допомогою класичного аналізу, знайти обчислювальний алгоритм, за допомогою якого знайдемо розвязок задачі. Задача про завантаження є класичним представником методу динамічного програмування, в якій обмежений ресурс розподіляється між кінцевим числом видів (економічної) діяльності.Динамічне програмування - це розділ математичного програмування, в якому розглядаються задачі прийняття оптимальних рішень в багатоетапних керованих процесах. Керуванням називається сукупність рішень, які приймаються на кожному етапі процесу [1, с.271]. На кожному кроці здійснюється розподіл і перерозподіл, які беруть участь в операції з метою поліпшення її результату в цілому. Ці розподіли в динамічному програмуванні називаються управліннями операцією і позначаються буквою . У більшості практичних задач показник ефективності операції в цілому являє собою суму ефективності дій на всіх етапах (кроках) операції: де - ефективність операції на-му кроці.Безсумнівно приваблива ідея розбиття задачі великої розмірності на підзадачі меншої розмірності, що включають всього по декілька змінних, та подальшого розвязання всієї задачі по частинах. Метод можна використовувати для вирішення досить широкого кола задач, включаючи задачу розподілу ресурсів, заміни та управління запасами, задачу про завантаження. Набір рекурентних обчислювальних процедур, що звязують різні етапи, забезпечує отримання допустимого оптимального розвязку задачі в цілому при досягненні останнього етапу. Походження назви динамічне програмування, ймовірно, повязано з використанням методів ДП в задачах прийняття рішень через фіксовані проміжки часу (наприклад, в задачах управління запасами). Сформулюємо загальний принцип, що лежить в основі розвязання всіх задач динамічного програмування («принцип оптимальності»): «Який би не був стан системи S перед черговим кроком, треба вибрати управління на цьому кроці так, щоб виграш на даному кроці плюс оптимальний виграш на всіх наступних кроках були максимальними»[6, с.109]1, показує можливі маршрути між початковим містом, що перебуває у вузлі 1, і кінцевим пунктом, який знаходиться у вузлі 7. Розглядаючи вузли, що відносяться до першого етапу, помічаємо, що кожен з вузлів 2,3,4 повязаний з початковим вузлом 1 єдиною дугою (мал.2). Найкоротший шлях до вузла 2 дорівнює 7 км (з вузла 1); Найкоротший шлях до вузла 3 дорівнює 8 км (з вузла 1); Найкоротший шлях до вузла 4 дорівнює 5 км (з вузла 1).Задача про завантаження - це задача про раціональне завантаження судна (літака, автомобіля, тощо), яке має обмеження за обсягом або вантажопідйомністю. Завдання полягає у завантаженні судна такими вантажами, які приносять найбільший сумарний прибуток [5, с.418]. Рекурентне рівняння процедури зворотної прогонки виводиться для загальної задачі завантаження судна вантажопідйомністю W предметів (вантажів) n найменувань. Нехай - кількість предметів і-го найменування, що підлягають завантаженню, - прибуток, який приносить один завантажений предмет і-го найменування, - вага одного предмета і-го найменування. Три елементи моделі динамічного програмування визначаються таким чином: 1 . Етап i ставиться відповідно до предмету і-го найменування, 2.Необхідно завантажити транспортний засіб таким чином, щоб загальна цінність вантажу була максимальною: де - число предметів вантажу-го типу, що завантажуються в транспортний засіб; виступає в якості управління ). Обмежуючими умовами є: Перша умова вимагає, щоб загальна маса предметів не перевищувала вантажопідйомності транспортного засобу, а друга - щоб предмети, з яких складається вантаж різних типів, були неподільні. Нехай літак потрібно завантажити 4 видами предметів, щоб ефект від цих предметів (наприклад, вартість) був максимальним. Величина може приймати значення 0,1,2; відповідна вартість предметів другого виду дорівнює 0;85;170 одиниць, а для предметів першого виду складе 46,24,2 одиниць. 47 од. можна загрузити один предмет першого виду, два предмети другого виду або по одному предмету першого і другого видів.Динамічне програмування - це розділ математичного програмування, в якому розглядаються задачі прийняття оптимальних рішень в багатоетапних керованих процесах. При цьому багатоетапність або відображає реальне протікання процесу в часі або вводиться штучно поділом процесу на окремі етапи. Основою поетапного розвязання задачі динамічного програмуван

Зміст

Вступ

РОЗДІЛ 1. Динамічне програмування

1.1Загальні відомості, постановка задачі динамічного програмування

1.2Метод динамічного програмування

1.3 Рекурентна природа обчислень в динамічному програмуванні

РОЗДІЛ 2. Задача ОПТИМАЛЬНОГО завантаження

2.1 Загальні відомості

2.2 Постановка задачі оптимального завантаження

2.3 Приклад розвязку задачі про завантаження

Висновки

Список використаних джерел

Додаток 1

Додаток 2

Додаток 3 моделювання динамічне програмування вантаж