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

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




Скачати 127.64 Kb.
Назва6. Динамічне програмування
Дата20.09.2012
Розмір127.64 Kb.
ТипДокументи

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

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

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

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

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

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

Нехай деяка операція складається з m етапів (кроків), і ефективність операції характеризується показателем (критерієм) L, що для скорочення будемо називати "прибутком".

Припустимо, що прибуток L за всю операцію складається з прибутків на окремих кроках:



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

Обозначимо управління операцією в цілому, через вектор х=ІІх1 , х 2 …., хm ІІ, де хi-управління на i-м кроку, що, в загальному випадку, може бути теж вектором або функцією, а не тільки числом.

Потрібно знайти таке управління х, при якому прибуток L звертається в максимум:



Те управління х* ,при якому цей максимум досягається називається оптимальним управлінням. Воно складається з сукупності оптимальних крокових управлінь:

х*=ІІх*1 , х *2 …., х*m ІІ

Приклад 1. Володар автомашини експлуатує її на протязі m років. Спочатку кожного року він може прийняти одне з трьох рішень:

1) продати машину і замінити її новою;

2) зробити ремонт і продовжувати експлуатацію;

3) продовжувати експлуатацію.

Управління на кожному кроку (шаговое управління) полягає в виборі одного з цих трьох рішень. Безпосередньо числами вони не висловлюються, але можна приписати першому чисельне значення 1, другому 2, третьому 3. Які потрібне прийняти рішення по роках (т. е. як чередовати управління 1, 2, 3), щоб


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



Де 1i - видаток на машину в i-м році, необхідно звернути в мінімум. Управління операцією в цілому являє собою яку-або комбінацію чисел 1, 2, 3, наприклад: Х= (3,3,2,2,2,2,3,1,3...),

oо означає перші два року експлуатувати машину без ремонту, наступні чотири року її ремонтувати, сьомий рік - не ремонтувати, а в початку восьмого - продати, купити нову, після цього знову експлуатувати без ремонту і т. д. потрібно вибрати сукупність чисел 1, 2, 3, при якій величина (6.1) мінімальна.

Приклад 2. Плануються інвестиції в групу фірм Ф12,….Фк на період m років. З початку на всі інвестиції виділено М гривень. В процесі діяльності фірм частина одержуваного від інвестицій прибутку знов інвестується в ці фірми. Ставиться питання: яку кількість засобів з початку кожного року інвестувати в кожне підприємство, щоб сумарний прибуток за m років був максимальним.

Сумарний прибуток являє собою суму прибутків на окремих кроках (роках):



і значить володіє властивістю аддитивності. Управління хi на i-м кроку полягає в тому, що спочатку i-го року в фірми інвестуються якісь кошти xi =ІІ X11, X12, …..X1k II де Хij - засоби що інвестуються на першому році в j-ю фірму. Таким чином, шаговое управління в даному випадку, є векторне, а в попередньому прикладі воно висловлювалося просто числом. Вимагається знайти такий розподіл засобів по рокам:



При якому величина L звертається в максимум?

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




В цій задачі, на відміну від трьох попередніх, немає природного розподілу на кроки (роки); його потрібно вводити штучно, для чого, наприклад, можна відрізок АВ поділити на т частин, провести через крапки ділення прямі перпендикулярні АВ, і вважати, за крок перехід з однієї прямої на іншу. Шаговое управління на i-м кроку являє собою кут φij який складає дільницю шляху з прямої АВ.

Вимагається вибрати таке управління х=|| φ1 , φ2 , ..φm || при якому сумарні витрати на спорудження всіх дільниць дороги мінімальні.

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

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

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

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

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


6.2. Приклади рішення задач динамічного програмування. 1. Прокладка найбільш вигідного шляху між двома пунктами.


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

Рис 6.2.

Вимагається прокласти такий шлях з А, в В, при якому сумарні витрати мінімальні.

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

Будемо використати алгоритм зворотної прогонки. В пункт В можна влучити тільки з пунктів В1 і В2 Запишемо вартості прокладки відрізків з цих пунктів в пункт В в колах цих пунктів (рис. Б. З). Оптимальне управління з цих пунктів покажемо рядками.



Рис. 6.3.

Зрозуміло, що з пункту В1 у нас змушений рух тільки на схід, а з пункту В2 - тільки на північ. Таким чином умовна оптимизація останнього кроку зроблена, і умовна оптимальна вартість для кожної з точок В1 і В2 записана в відповідному колі. Передостанній крок міг бути зроблений з пунктів С12 и С3.



Знайдемо для кожної з них умовне оптимальне управління (покажемо його стрілкою з відповідної крапки) і умовну оптимальну вартість (цифра буде поставлена всередині відповідного гуртка). Для крапки с1 управління змушене: іти на схід; вартість з цієї крапки до кінцевої крапки складе 18 одиниць. Це число записуємо в колі при путкті C1. Для крапки C2 управління вже не змушене; можна іти або на північ, або на схід. В першому випадку витрати складуть одну одиницю і від В, ще 7 одиниць, всього 8 одиниць. Якщо підемо на схід витратимо 7+2=9 одиниць. Значить умовно оптимальне управління в путкті C2 - іти на північ (відзначаємо це стрілкою, а число 8 записуємо в колі крапки С2).

Для крапки Сз управління знову змушене (ставимо стрілку строго на північ і записуємо число 7+2=9 одиниць в колі при Сз).

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

В колі при путкті А записані оптимальні видатки на всіх споруди шляху з А: в В: L*=34.



Рис. 6.4.

Якщо рухатися з крапки А по направляючим стрілкам ,що відповідають умовно оптимальним шаговим рішенням, отримаємо безумовне оптимальне управління;

Х*=|| C, В, В, C, В, В, В, В, C, C, C,B || де C - крок на північ; В - крок на схід.

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


Якщо б ми намагалися вирішити задачу "наївним" засобом; вибирати на кожному шазі, починаючи з першого, саме вигідне тільки для цього кроку направлення, то отримали б:



^ Видатки для такого рішення будуть рівні

L= 2+1+4+2+3+4+2+4+3+1+11+7 =45,

що більше, ніж L*=34. В даному випадку різниця не дуже велика, але в інших випадках вона може бути істотною.

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

2. Задача розподілу ресурсів

В розпорядженні є запас засобів (ресурс) К=10 (умовних одиниць), який може бути розподілений між т=5 фірмами П1 , П2..., П5. Кожна з фірм при вкладенні в неї х одиниць ресурсу дасть прибуток φ(х), i=1,5 , наведений в таблиці 6.1.

Таблиця 6.1.



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

^ Проведемо умовну оптимізацію починаючи з останнього 5-го кроку. Вимагається так розподілити засоби К між фірмами, щоб в купіі це дало максимальний прибуток. Хоча в умовіі задача не містить інформації про час, вона легко вирішується засобом динамічного програмування, якщо вважати за перший крок вкладення засобів в фірму П1 за другий-в П2 и

т. д.

В такій задачі "шаговими управліннями" є засоби х1 ,x2 ,…x5, що інвестуються фірмам. Потрібно знайти такий вектор X=|| X1, X2 ,…..,X5 || при якому сумарний прибуток:



^ Почнемо оптимізацію з останнього 5-го кроку. Нехай ми підійшли до цього кроку

з залишком засобів S. Очевидно, що цю суму можна вкласти в фірму φ5, т. т.

Χ5 (S) =S і умовний оптимальний виграш 15(S) = φ5(S)

Задаваючись всіма можливими значеннями S ми вже для кожного S будемо знати 15(S). Таким чином останній крок буде оптимізован. Далі переходимо до передостаннього, 4-го кроку. Нехай ми підійшли до нього з запасом засобів S. Обозначим Im-1 (S) - умовний оптимальний виграш на двох останніх кроках. Якщо


Ми виділимо на 4-м кроці 4-ої фірмі засобу х, то на останній 5-й крок залишиться S-x. Виграш на двох останніх кроках буде рівний



І потрібно знайти таке х, при якому цей виграш максимальний:

1m-1(S) = maxxS4(x) + 15(S-x) }

Цей максимум і є умовний оптимальний виграш за два останніх крока, а те значення х, при якому цей максимум досягається - умовне оптимальне управління на 4-му кроці.

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

Таблиця 6.2.



Щоб було більш зрозуміло, як заповнювалася таблиця 6.2, проілюструємо отримання умовно оптимального рішення на 3-м кроці, якщо ми підійшли до нього з запасом засобів S=7 (припустимо, що 4-й і 5-й кроки вже оптимівані).

Складемо допоміжну таблицю 6.3. В першому її стовбці перерахуємо всіх можливі значення х на 3-му кроку, які не більше ніж S=7. В третьому стовбці-виграш на третьому кроку від вкладення засобів х на фірму 3 (заповнюється по стовбцю φ3(x) таблиці 6.1).

В четвертому - умовно оптимальний виграш в усіх інших кроках (4-му і 5-му) за умови, що ми підійшли до четвертого кроку з засобами ,що залишалися (заповнюється по стовбцю i=4 таблиці 6.2). В п'ятому стовбці - сума двох виграшів: шагового і оптимізованого подальшого при даному вкладенні х в третій крок. З всіх виграшів останнього стовбця вибирається максимальний (в таблиці 6.3 він рівний 13 (7) =3,6 , а відповідне управління Хз (7) =2.

Таблиця 6.3




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

Отож , в результаті послідовної оптимізації 5-го, 4-го, 3-го, 2-го і 1-го кроків ми отримаємо повний список всіх рекомендацій по оптимальному управлінню і безумовний виграш L за всю операцію - в даному випадку вони рівні 5.6. На 1-му кроку заповнений тільки один рядок, бо стан системи перед початком першого кроку в точності відомо; So=K=10. Оптимальні управління на всіх кроках виділені рамкою. Таким чином, ми отримали оптимальне рішення: треба виділити першій фірмі дві одиниці з десяти; другій - 5 одиниць; третій - дві; четвертій - жодної; п'ятій - одну одиницю. При такому розподілі прибуток буде максимальний і рівний 5.6.

^ 3. Задача про завантаження машини.

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

В якості прикладу розглянемо наступну задачу; є набір предметів П1,... Пn (кожний в єдиному примірнику); відомі їх ваги q1,..., qn і вартості С1.,,..., Сn Вантажопідйомність машини дорівнює


Визначити, що з предметів потрібнo взяти в машину, щоб їхня сумарна вартість була максимальна. Конкретний чисельний приклад наведений в таблиці 6.4.

Таблиця 6.4.

Предмет Пі

П1

П2

Пз

П4

П5

П6

Вага qі

4

7

11

12

16

20

Вартість С

7

10

15

20

27

34

Процес завантаження машини можна уявити собі як по-шаговий, при якому на кожному кроку шукається відповідь на питання; брати даний предмет (i=1, 6) в машину або не брати?

Управління х, на i-м кроку рівно одиниці, якщо i-й предмет береться в машину, і нулю - якщо не береться.

Стан системи S перед черговим кроком характеризується вагою, що залишилася до повного завантаження машини. Як і раніше, будемо придавати S тільки цілі значення. Умовна оптимізація рішення показана в таблиці 6.5.

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






В таблиці 6.5. Виділений оптимальний виграш L*=57 і оптимальні шагові

управління, при яких цей виграш досягається:

Х* 1 =0; Х* 2 =1; Х* 3 =0; Х* 4 =1; Х* 5 =0




Схожі:

6. Динамічне програмування icon6. Динамічне програмування
Динамічне програмування являє собою математичний апарат, розроблений із метою підвищення ефективності при рішенні деякого класу задач...
6. Динамічне програмування iconДинамічне програмування
Характерним для динамічного програмування є поетапний (багатокроковий) процес рішення оптимізаційної задачі
6. Динамічне програмування iconЗадача динамічного програмування. Загальний випадок
Але у відмінності від лінійного програмування динамічне програмування не зводиться до якийсь стандартної обчислювальної процедури;...
6. Динамічне програмування iconЗадача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,"умовно", в іншому- "безумовно".
Але на відміну від лінійного програмування, динамічне програмування не зводиться до будь-якої стандартної обчислювальної процедури;...
6. Динамічне програмування iconФормат опису модуля
Лп симплекс-методом, транспортна задача лп, задачі оптимізації на мережах, задачі з цілочисельними змінними, ігрові задачі до, моделі...
6. Динамічне програмування icon2007 Динамічне гасіння коливань мостових кранів із використанням хвильових ланцюгових передач
Динамічне гасіння коливань мостових кранів із використанням хвильових ланцюгових передач: Автореф дис канд техн наук: 05. 05. 05...
6. Динамічне програмування iconКритерії оцінювання знань І вмінь студентів
«Інформатика» денної та заочної форми навчання. Фахове вступне випробування базується на матеріалах навчальних дисциплін з програмування:...
6. Динамічне програмування icon5. Цілісне програмування
Цілісні програмування орієнтовано на рішення задач математичного програмування, у яких усі або деякі перемінні повинні приймати тільки...
6. Динамічне програмування iconДокументи
1. /Математичне програмування/~$Р_2_8.doc
2. /Математичне...

6. Динамічне програмування iconДокументи
1. /Математичне програмування/~$Р_2_8.doc
2. /Математичне...

Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи