Динамічне програмування

Размещено на http://www.allbest.ru/

Міністерство освіти і науки, молоді та спорту

Луцький національний технічний університет

Кафедра ПЦБ

Реферат на тему:

"Динамічне програмування"

Виконала: Христецька О.В.

Перевірив: Пасічник Р.В.

Луцьк

2014



Зміст

Вступ

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

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

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

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

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

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

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

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

Висновок

Література



Вступ

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



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

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

Примітка. В основі цього методу лежить принцип оптимальності Р. Беллмана.

У математичному вигляді задачу динамічного програмування (ДП) можна подати таким чином:

або

- цілі числа.

Математичні моделі задач динамічного та лінійного програмування подібні, але додаткові обмеження задачі ДП такі.

Адитивність (мультиплікативність) функції мети. Мультшшікативна функція шляхом логарифмування може бути перетворена в адитивну.

Лише одне обмеження:.

Цілочисловість:та- цілі числа.

До особливостей розв'язку задач ДП можна віднести.

1. Багатоетапність:

2. Побудова розв'язку задачі цілеспрямованим перебором у

прямому та зворотному напрямках ("лавиноподібна" стратегія).

3. Оптимум цільової функції на етапі t дійсний як відносно цього

етапу, так і відносно наступних етапів

4. Кожний етап - це окрема задача, яка може бути розв'язана різними методами, а забезпечення ЦФ етапу - це вектор:

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

Суть методу

Динамічне програмування полягає у визначенні оптимального рішення n-мірної задачі, розділяючи її n окремих етапів. Кожен з них є підзадачею по відношенню до однієї змінної.

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

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

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

Метод вдосконалить виконання завдань, що вирішуються за допомогою перебору варіантів або рекурсій.

Побудова алгоритму завдання

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

Іноді на 3-му кроці потрібно додатково запам'ятовувати деяку допоміжну інформацію про хід виконання кожної підзадачі. Це називається зворотним ходом.

Застосування методу

Динамічне програмування застосовується при наявності двох характерних ознак:

- оптимальність для підзадач;

- наявність в задачі перекриваються підзадач.

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

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

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

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

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

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

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

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

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

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

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

Нехай аналізується деякий керований процес, подання якого допускає декомпозицію на послідовні етапи (кроки), кількість яких n задана. Ефективність всього процесу Z може бути подана як сума ефективностей окремих кроків, тобто:

,

що має назву адитивного критерію (або як добуток ефективностей окремих кроків у вигляді:

,

що має назву мультиплікативного критерію).

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

Розв'язування задачі динамічного програмування полягає в знаходженні такого управління процесом у цілому, яке максимізує загальну ефективність:

(max ).

Оптимальним розв'язком цієї задачі є управління що складається з сукупності оптимальних покрокових управлінь:

і уможливлює досягнення максимальної ефективності:



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

Принцип оптимальності

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

Визначення закону керування для таких процесів пов'язане з рішенням так званої задачі багатокрокового вибору. Керування дискретними системами може бути прикладом таких багатокрокових процесів.

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

В основі методу динамічного програмування лежить принцип оптимальності, сформульований Беллманом Р.

Оптимальна стратегія визначається лише станом системи в даний момент і не залежить від того, як система прийшла в дану точку (рис.3.1).

Рис. 3.1.

Під стратегією ми розуміємо правило прийняття рішень.

Принцип оптимальності може бути сформульований і по-іншому.

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

Із принципу оптимальності можна одержати необхідні умови оптимальності для безперервних і дискретних систем.

Безперервні системи. Рівняння Беллмана

Об'єкт описується рівнянням

(3.1)

Визначити керування і траєкторію , що доставляють екстремум функціоналу

(3.2)

де фіксовано,

відкрита область.

Нехай відома оптимальна траєкторія , рис3.2. Розглянемо ділянку .

Відповідно до принципу оптимальності функціонал (3.2) досягає на ньому мінімум.

Введемо позначення

(3.3)

Рис. 3.2.

При певному керуванні мінімальне значення функціонала залежить тільки від і .

Функція називається функцією Беллмана.

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

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

(3.4)

Відповідно до теореми про середнє можна записати

(3.5)

У такий спосіб

(3.6)

Приймемо допущення, що функція має частинні похідні по всіх координатах і за часом .

Тоді, розклавши в ряд Тейлора, одержимо

(3.7)

Згідно (3.1), запишемо

Тоді (3.7) приймає наступний вид

(3.8)

Підставимо (3.8) в (3.6) і одержимо

(3.9)

Беручи до уваги, що і не залежать від , (3.9) можна перетворити до виду

(3.10)

У результаті одержуємо

(3.11)

Або у векторній формі

(3.12)

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

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

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

Фірма вирішила використати 5 млн.грн для капітальних вкладень у чотири проекти. Очікуваний прибуток від дискретного вкладання коштів у кожний з цих проектів наведений у таблиці (з кроком 1 млн.грн).

Розмір вкладу, млн.грн.		Прибуток, млн.грн.
	Проект№1	Проект№2	Проект№3	Проект№4
1	2	1.8	1.4	2.5
2	2.5	2.5	1.6	2.7
3	3	2.9	1.7	2.7
4	3	3.5	1.8	2.8
5	3	3.5	1.8	3

Потрібно розподілити 5 млн.грн між проектами так, щоб отримати максимальний прибуток. Математична модель задачі така:

де - кількість вкладених коштів у проекту.

Відповідь

:

з прибутком 8.4 млн.грн.

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

Літак у деякій точці летить на висотіта зі швидкістю. Йому необхідно піднятися на висоту та набути швидкість з мінімальною витратою палива. Дискретні витрати палива при збільшенні висоти або швидкості наведені на рисунку лініями, а витрати від поточної точки до кінцевої - кружочками. Перед розрахунком усі кружочки білі та пусті, а лінії - однакової пунктирної структури.

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

1. У точкулітак може потрапити з точки, де =З (0+3) або з точки , де також = 3 (0+3).

Шляхи можливого руху позначаються жирною лінією, а витрати палива на них - цифрами.

2. У точкита можна потрапити лише з точки . Задача полягає в обранні найекономнішого переміщення на даному етапі. Отже, для точки= 7

3. Для точки=9(3+6), а для= 12 Таким чином, необхідно охопити всі точки можливого переміщення літака, визначаючи для кожної з них - оптимальну витрату палива для переміщення з даної точки до , при цьому не забуваючи позначати оптимальний на даному етапі шлях, аж доки розв'язок не дійде до точки

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

Размещено на http://www.allbest.ru/

Відповідь:-

оптимальний шлях з витратою палива 23 од.

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

Необхідно завантажити транспортний засіб (судно, літак, вагон, вантажний автомобіль) або рюкзак вантажоємністю, наприклад, G = 20 т наявними речами з вагою g, та вартістю V/ таким чином, щоб сумарна вартість вантажу була максимальною. Дані про вагута вартість V/ речей наведені в таблиці. Математична модель задачі така:

-

цілі числа. де- кількість завантажених речей.

Річ	Вага, т	Вартість, тис.грн	Максимальна кількість, шт
1	3	30	6 (|20/3|)
2	5	60	4 (|20/5|)
3	9	80	2 (120/91)

1-а ітерація (використання)

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

Вага,т	Вартість, тис.грн	Х|	х2
0	0	0	0
3	ЗО	1	0
6	60	2	0
9	90	3	0
12	120	4	0
15	150	5	0
18	180	6	0
5	60	0
8	90	1
11	120	2
14	150	3
17	180	4
20	210	5
10	120	0	2
13	150	1	2
16	180	2	2
19	210	3	2
15	180	0	3
18	210	1	3
Вага,т	Вартість, тис.грн	Хі	х2
0-2	0	0	0
3-4	ЗО	1	0
5-7	60	0	1
8-9	90	1	1
10-12	120	0	2
13-14	150	1	2
15-17	180	0	3
18-20	210	1	3

2-а ітерація (використання>

Друга ітерація полягає в поступовому збільшеннівід 0 до 2 та заповненні вагового резерву значеннями з підсумкової таблиці першої ітерації (адже вони є оптимальними для . та ). Складання підсумкової таблиці аналогічне.

Вага, т	Вартість, тис.грн.	Хі	х2	Хз
0	0	0	0	0
3	ЗО	1	0	0
5	60	0	1	0
8	90	1	1	0
10	120	0	2	0
13	150	1	2	0
15	180	0	3	0
18	210	1	3	0
9	80	0	0
12	ПО	1	0
14	140	0	1
17	170	1	1
19	200	0	2
18	160	0	0	2
0-2	0	0	0	0
3-4	ЗО	1	0	0
5-7	60	0	1	0
8-9	90	1	1	0
10-12	120	0	2	0
13-14	150	1	2	0
15-17	180	0	3	0
18-20	210	1	3	0

Відповідь:=1,=3,=0 з вартістю 210 тис.грн.



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

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

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

де - витрати на покращення стану конструктиву (таблична

функція сформована на основі довідників та експертним шляхом); - дата ремонту окремого конструктиву;

- витрати на ремонт конструктиву в дату;

- нижня границя стану конструктиву,



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

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

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

Функція Беллмана повинна бути диференціюємою, а ця вимога не виконується при наявності обмежень.

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

Для лінійних задач із квадратичними функціоналами вид відомий і рішення виходить у замкнутому виді.

При чисельному рішенні рівняння Беллмана можна порівняно легко враховувати обмеження на .



Висновок

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

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

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

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

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

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

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

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



Література

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

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

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

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

...