Динамічне програмування - Реферат

Для вибору оптимального рішення при виконанні завдань програмування іноді потрібно перебирати великукількість комбінацій даних, що навантажує память персонального компютера.Динамічне програмування - це метод оптимізації, який полягає в тому, що переміщення функції мети до оптимуму відбувається крок за кроком, причому кожний крок визначається лише поточним станом і не залежить від попередніх подій: Примітка. До особливостей розвязку задач ДП можна віднести. Кожний етап - це окрема задача, яка може бути розвязана різними методами, а забезпечення ЦФ етапу - це вектор: До типових задач динамічного програмування відносяться задачі: розрахунку траєкторії літака, про рюкзак, про інвестиції, про розклад поїздів, завантаження торгового судна, прогнозування термінів ремонту будівельних конструкцій тощо. Динамічне програмування полягає у визначенні оптимального рішення n-мірної задачі, розділяючи її n окремих етапів. Динамічне програмування передбачає побудову такого алгоритму завдань, при якому завдання так розбивається на дві або більше підзадач, щоб її рішення складалося з оптимального вирішення всіх підзадач, що входять до неї.Для народного господарства в цілому, його галузей, регіонів чи окремих підприємств з метою їх стабільного функціонування та розвитку необхідно розробляти стратегічні та тактичні плани. Динамічне програмування являє собою математичний апарат, що дає змогу здійснювати планування багатокрокових керованих процесів, а також процесів, які розвиваються у часі. Отже, динамічне програмування не є окремим методом розвязування задач, а являє собою теорію, що поєднує ряд однотипних ідей та прийомів, які застосовуються для розвязування досить різних за змістом задач. До задач динамічного програмування належать такі, що повязані з оптимальним розподілом капіталовкладень, розподілом продукції між різними регіонами, визначенням найкоротшого шляху завезення товарів споживачам, задачі щодо заміни устаткування, оптимального управління запасами тощо. Динамічне програмування дає змогу прийняти ряд послідовних рішень, що забезпечує оптимальність розвитку процесу в цілому.У техніці існує великий клас обєктів і процесів, керування якими здійснюється на основі обмеженого числа рішень, прийнятих послідовно в деякі фіксовані моменти часу. Керування дискретними системами може бути прикладом таких багатокрокових процесів. В основі методу динамічного програмування лежить принцип оптимальності, сформульований Беллманом Р. Оптимальна стратегія визначається лише станом системи в даний момент і не залежить від того, як система прийшла в дану точку (рис.3.1). Із принципу оптимальності можна одержати необхідні умови оптимальності для безперервних і дискретних систем.Фірма вирішила використати 5 млн.грн для капітальних вкладень у чотири проекти. Проект№1 Проект№2 Проект№3 Проект№4 Потрібно розподілити 5 млн.грн між проектами так, щоб отримати максимальний прибуток.Літак у деякій точці летить на висоті та зі швидкістю . У точку літак може потрапити з точки , де =З (0 3) або з точки , де також = 3 (0 3). У точки та можна потрапити лише з точки . Для точки =9(3 6), а для = 12 Таким чином, необхідно охопити всі точки можливого переміщення літака, визначаючи для кожної з них - оптимальну витрату палива для переміщення з даної точки до , при цьому не забуваючи позначати оптимальний на даному етапі шлях, аж доки розвязок не дійде до точки Оптимальний шлях від точки до точки визначається шляхом переміщення між цими точками по незаборонених шляхах.Потім має вирішуватись задача динамічного програмування, тобто побудови дерева часових варіантів ремонту пошкодження ("часто, але потроху", "рідко, але грунтовно") для визначення найдешевшого варіанта ремонту конструкції з урахуванням терміну її служби.Метод динамічного програмування широко застосовується для оптимізації дискретних систем. Істотним недоліком методу є великий обєм обчислень і необхідної памяті для зберігання проміжних результатів при рішенні задач на ЕОМ, причому, вимоги до памяті сильно зростають при збільшенні розмірності задачі.1) ДП являє собою, насамперед, засіб рішення задач, які можуть бути вирішені й іншими методами. Цінність же методу полягає в іншому підході: багатокроковий процес прийняття рішень заміняється послідовністю однокрокових процесів ухвалення рішення. Зокрема, варіаційні задачі з обмеженнями типу нерівностей, рішення яких повязане зі значними труднощами, легко вирішуються методом ДП.

Зміст

Вступ

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

2. Економічна сутність динамічного програмування

3. Принцип оптимальності. Рівняння Беллмана

4. Задача про інвестиції

5. Задача розрахунку траєкторії літака

6. Задача про рюкзак (завантаження транспортного засобу)

7. Задача прогнозування термінів ремонту будівельних конструкцій

8. Область застосування методу динамічного програмування

Висновок

Література

Переваги методу динамічного програмування (ДП).

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

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

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

3) ДП має велику загальність і може застосовуватись для широкого кола задач.

Недоліки методу ДП.

1) У ДП відсутній загальний алгоритм, придатний для всіх задач. Кожна задача має свої власні труднощі й у кожному випадку треба знайти найбільш підходящу методику оптимізації.

2) Принциповим недоліком методу ДП є великий необхідний обєм памяті ЕОМ при рішенні дискретних задач.

1. Зайченко Ю.П. Дослідження операцій. - К.: ЗАТ "ВІПОЛ", 2000. - 688 с.

2. Бабіч В.І. Математичні методи дослідження операцій у будівництві: Навчальний посібник. - Київ.: КНУБА 2006. - 107 с.

3. Исследование операций: В 2-х т. // Т.1. Методические основы и математические методы / Майзер X., Эйджин Н., Тролл Р. и др.; Под ред. [и с. предисл.] Дж. Моудера, С. Элмаграби; Перевод с англ. под ред. И.М. Макарова, И.М. Бескровного -М.:Б. и., 1981.

Размещено на .ru