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

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




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

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

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

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

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

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

^ 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.3. Задача динамічного програмування. Загальний випадок

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

Перше питання, на яке потрібно відповісти: якими параметрами характеризується стан S системи ,що управляється, перед кожним кроком? Від правильного вибору цих параметрів часто залежить можливість успішно вирішити задачу оптимізації. В трьох конкретних прикладах, що розв'язувалися вище, стан системи характеризувався дуже невеликим числом параметрів; двома координатами-в першому прикладі, одним числом-в другому і третьому. Але такі прості задачі рідко зустрічаються на практиці. Якщо стан системи описується багатьма параметрами (так званими "фазовыми координатами"), то стає важко перед кожним кроком перебрати всі їхні варіанти і для кожного знайти оптимальне умовне управління.

Останнє ще більше ускладнюється, коли число можливих варіантів велике. В цьому випадку виникає по вираженню Р. Беллмана "прокляття багатомірності". Звичайно задачі динамічного програмування вирішуються не вручну, а на ЕОМ.

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

Оскільки при збільшенні числа кроків т зросте обсяг розрахунків, то число кроків треба вибирати раціонально: 1) крок повинен бути достатньо малим для того ,щоб процедура шагового управління була достатньо проста, і 2) крок повинен бути не занадто малим, щоб не ускладнювати процедуру пошуку оптимального рішення. На практиці нас цікавить не строго оптимальне, а "прийнятне" рішення, що не дуже відрізняється від оптимального по значенню виграша L*.

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

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

1i=f i (S, x i ). (6.1.)

Під впливом управнения хi на i-м кроку система переходить в новий стан

S'=φi (S, xi ). (6.2.)

Функції fi і φi повинні бути записані. Помітимо, що в загальному випадку аргументи функцій fi і φ i-вектори.

Основне рекурентне рівняння динамічного програмування, що висловлює умовний оптимальний виграш^ Li (S) (починаючиз i-г кроку і до кінця), для засобу "зворотної прогонки" висловлюється через вже відому функцію Li+1 (S):

Li (S)=max{fi (S, xi)+Li+1 (φi (S, xi))}.

Цьому виграшу відповідає умовне оптимальне рівняння на i-м кроку xi (S).


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

Lm(S) =max xm {fm (S, xm) } . (6.4.)


Таким чином, знаходиться умовне оптимальне управління xm (S), для якого цей максимум досягається.

Роблячи умовну оптимізацію (т-1)-го, (т-2)-го і т.д. кроків по формулі (6.3.), приймаючі в ній i= (m-1), (т-2),..., визначаємо для кожного з кроків умовне оптимальне управління xi (S),при якому максимум досягається.

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

L*=Li (S)=max xSo { f1(*)+12(S,xi)}. (6.5.)

На закінчення робиться безумовна оптимізація управління: береться оптимальне управління на першому кроці х*1 = x1(Sо), і далі по вже отриманим рекомендаціям проходяться умовні оптимальні управління до кінця.

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

m

L = П li

i=1

де 1i > 0.

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

Li (S)=maxx i { fi (S,xi ) * Li+1 i (S, xi) ) } . (6.6.)

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

Приклад. Для збільшення кількості продукції трьом підприємствам виділено 700 тис. грн. Використання кожним підприємством хi тис.грн. забезпечить зростання створюваної продукції fi (x ) (таб. 6.5.) Визначити оптимальний розподіл коштів.

Таблиця 6.5



Х


fi(x)

Підприємство 1

Підприємство 2

Підприємство 3

0

0

0

0

100

30

50

40

200

50

80

50

300

90

90

110

400

110

150

120

500

170

190

180

600

180

210

220

700

210

220

240

Рішення


1. Стан S системи характеризується кількістю коштів, з яким ми підходимо до кожного кроку.

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

2. B даній задачі кількість кроків визначається числом підприємств (т=3). Вважаємо за перший крок вкладення коштів в підприємство 1, за другий - в підприємство 2, за третій - в підприємство 3.

3. Умовну оптимiзацiю починаємо з останнього кроку в відповідності з вираженням (6.4.). Одержуємо таблицю 6.6.

Таблиця 6.6


S

Хз(S)

L3(S)

0

0

0

100

100

40

200

200

50

300

300

110

400

400

120

500

500

180

600

600

220

700

700

240

4. Умовну оптимiзацiю передостаннього кроку здійснюємо в відповідності з вираженням (6.3.):






Результат умовної оптимізації на 2-му кроці записані в таблицю 6.7.

Таблиця 6.7

S

X2

L2

0

0

0

100

100

50

200

100

90

300

200

120

400

100

160

500

300

400

500

190

600

100

230

700

100

270

5. Умовну оптимізацію першого кроку також здійснюємо в відповідності з вираженням (6

6. Безумовна оптимізація дасть таке оптимальне управління


х*=ІІ 0,100,600ІІ , а

максимальний приріст виробництва відповідає 270 тис. Грн.

ТЕСТИ

(Вірно (В) або невірно (Н)?)

1. В моделях ДП кількість кроків дорівнюється кількості підзадач.

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

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

4. При рішенні задач ДП звичайно більш важко визначити етапи, ніж стани.

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

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

7. Реалізація алгоритмів прямої і зворотної прогонки для однієї і тієї же задачі може призвести до отримання різних оптимальних рішень.

8. Задачі динамічного програмування можуть припускати як аддитивну, так і мультипликативну декомпозицию.

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

10. Принцип оптимальности не містить інформації про засоби рішення підзадач, що виникають на кожному етапі.

ЗАДАЧІ


Розв’язати наступні задачі засобом динамічного програмування:


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





ІІ. Задача про розподіл матеріальних ресурсів. Є запас ресурсів 10 (умовних одиниць). Вимагається розподілити ці засоби між чотирма фірмами (т=4). Для простоти припускається, що розподіляються тільки цілі кількості засобів. Функції прибутків fi(x) задані в наступній таблиці.



х

F 1(x)

f2(X)

f3(x)

f4(X)

1

0.1

0.5 +O.i

0.3 +0.i

0.4 +0.i

2

0.1 +0.I

0.7 +0.i

0.4 +0.i

0.6 +0.i

3

0.2 +0.i

0.8 +O.i

0.5 +0.i

0.7 +0.i

4

0.3 +0.i

0.9 +O.i

0.6 +0.i

0.8 +0.i

5

0.5 +0.i

1.2 +O.i

0.7 +0.i

0.9 +0.i

6

0.8 +0.i

1.5 +O.i

0.8 +0.i

0.9 +0.i

7

0.9 +0.i

1.5 +O.i

0.9 +0.i

0.9 +0.i

8

1.2 +0.i

1.5 +0.i

1.0+0.i

0.9 +0.i

9

1.4 +0.i

1.5 +O.i

1.1 +0.1

0.9 +0.i

10

2+0.i

1.5 +O.i

1.1 +0.i

0.9 +0.i

Де i - номер студента

III. Задача про розподіл людских ресурсів. Для виконання робіт направляється 6 чоловік. Оцінка ефективності на роботи на різноманітних дільницях визначається функціями

fi (x), i=1, 2,3, наведеної в наступній таблиці:

Х

f1(Х)
f2(X)

f3 (X)

0

0

0

0

1

50+i

30+i

200+i

2

100+i

60+i

350+i

3

150+i

120+2i

450+i

4

250+i

180+i

550+t

5

350+i

300+i

600+i

6

500+i

550+i

650+i

Де i - номер студента

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






Схожі:

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

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

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


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