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

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




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

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


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

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

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

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


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

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

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

, (6.1.)

де - прибуток на i-м кроку.

Якщо L має таку властивість, його називають “адитивним показником”.

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

Позначимо керування операцією в цілому, через вектор x=||x1, x2, ... , xm||, де хi - керування на i-м кроку, що, у загальному випадку, може бути теж вектором або функцією, а не тільки числом.

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

.

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

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

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

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

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

Показник ефективності (у даному випадку це витрати) дорівнює:

,

де - витрата на машину в i-м році, необхідно перетворити в мінімум.

Керування операцією в цілому являє собою яку комбінацію чисел 1, 2, 3, наприклад:

x=(3, 3, 2, 2, 2, 2, 3, 1, 3 ...),

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

Приклад 2. Плануються інвестиції в групу фірм Ф1, Ф2, ... , Фk на період m років. На початку на всі інвестиції виділено M гривень. У процесі діяльності фірм частина одержуваного від інвестицій прибутку знову інвестується в ці фірми. Ставиться питання: яка кількість засобів на початку кожного року інвестувати в кожне підприємство, щоб сумарний прибуток за m років був максимальним.

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

,

і значить має властивість адитивності. Керування хi на i-м кроку перебуває в тому, що спочатку i-го року у фірми інвестуються якісь засоби хi=||x11, x12, ... , x1k||, де xij - засоби що інвестуються на першому році в j-ю фірму. Таким чином, крокове керування в даному випадку, є векторне, а в попередньому прикладі воно виражалося просто числом.

Потрібно знайти такий розподіл засобів по роках:



при який розмір L звертається в максимум?

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



Рис. 6.1.


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

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

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

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

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

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

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


^ 6.2. Приклади рішення задач динамічного програмування.

1. Прокладка найвигіднішого шляху між двома пунктами.

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




Мал.6.2.

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

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

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



Мал. 6.3.


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

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

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

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



Мал. 6.4.

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

: **=||C, B B, C, B, B, B, B, C, C, C,

B|| де С - крок на північ; У - крок на схід.

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

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

х=||C, B B, C, C, C, B, B, C, B, B, B||

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

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

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

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


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

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

Таблиця 6.1.

х

f(х)

f2(х)

f3(х)

f4(х)

f5(х)

1

0.5

0.1

0.6

0.3

1.0

2

1

0.5

1.1

0.6

1.2

3

1.4

1.2

1.2

1.3

1.3

4

2

1.8

1.4

1.4

1.3

5

2.5

2.5

1.6

1.5

1.3

6

2.8

2.9

1.7

1.5

1.3

7

3.0

3.5

1.8

1.5

1.3

8

3.0

3.5

1.8

1.5

1.3

9

3.0

3.5

1.8

1.5

1.3

10

3.0

3.5

1.8

1.5

1.3


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

Проведемо умовну оптимізацію починаючи з останнього 5-го кроку.

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

У такій задачі “кроковими керуваннями” є засоби х1, х2, ... , х5, що інвестуються фірмам.

Потрібно знайти такий вектор х=||х1, х2, ... , х5||, при якому сумарний прибуток:

був би максимальний.

Почнемо оптимізацію з останнього 5-го кроку. Нехай ми підійшли до цього кроку з залишком засобів S. Очевидно, що цю суму можна вкласти у фірму й умовної оптимальний виграш .

Задаючись усіма можливими значеннями s ми вже для кожного s будемо знати . У такий спосіб останній крок буде оптимізован. Далі переходимо до передостанньому, 4-му кроку. Нехай ми підійшли до нього з запасом засобів S. Призначим - умовний оптимальний виграш на двох останніх кроках. Якщо ми виділимо на 4-м кроку 4-ой фірмі засобу х, то на останній 5-й крок залишиться S-x. Виграш на двох останніх кроках буде дорівнює



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



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

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

Таблиця 6.2.




i=5

i=4

i=3

i=2

i=1

S

x5(S)



x4(S)



x3(S)



x2(S)



x1(S)



1

[1]

[1.0 ]

[0]

[1.0 ]

0

1.0

0

1.0







2

2

1.2

1

1.3

1

1.6

0

1.6







3

3

1.3

2

1.6

[2]

[2.1 ]

0

2.1







4

4

1.3

3

2.3

2

2.4

0

2.4







5

5

1.3

3

2.5

1

2.9

0

2.9







6

6

1.3

4

2.6

2

3.4

5

3.5







7

7

1.3

5

2.7

2

3.6

5

4.1







8

8

1.3

5

2.8

4

3.7

[5]

[4.6]







9

9

1.3

6

2.8

5

3.9

7

5.1







10

10

1.3

7

2.8

5

4.1

7

5.6








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

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

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

Таблиця 6.3

x

7-x







7

0

1.8

0

1.8

6

1

1.7

1.0

2.7

5

2

1.6

1.3

2.9

4

3

1.4

1.6

3.0

3

4

1.2

2.3

3.5

[2]

5

1.1

2.5

[3.6]

1

6

0.6

2.6

3.2

0

7

0

2.7

2.7


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

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


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

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

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

Конкретний чисельний приклад приведений у таблиці 6.4.


Таблиця 6.4.

Предмет Пі

П1

П2

П3

П4

П5

П6

Вага

4

7

11

12

16

20

Вартість С

7

10

15

20

27

34


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

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

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

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


Таблиця 6.5.




i=6

i=5

i=4

i=3

i=2

i=1

S

x6

6

x5

5

x4

4

x3

3

x2

2

x1

i

0

[0]

0

0

0

0

0

0

0

0

0







1

0

0

0

0

0

0

0

0

0

0







2

0

0

0

0

0

0

0

0

0

0







3

0

0

0

0

0

0

0

0

0

0







4

0

0

0

0

0

0

0

0

0

0







5

0

0

0

0

0

0

0

0

0

0







6

0

0

0

0

0

0

0

0

1

0







7

0

0

0

0

0

0

0

0

1

10







8

0

0

0

0

0

0

0

0

1

10







9

0

0

0

0

0

0

0

0

1

10







10

0

0

0

0

0

0

1

0

0

10







11

0

0

0

0

0

0

0

15

0

15







12

0

0

0

0

1

20

0

20

0

20







13

0

0

0

0

1

20

0

20

0

20







14

0

0

0

0

1

20

0

20

0

20







15

0

0

0

0

1

20

0

20

0

20







16

0

0

[1]

27

0

27

0

27

0

27







17

0

0

1

27

0

27

0

27

0

27







18

0

0

1

27

0

27

0

27

0

27







19

0

0

1

27

0

27

0

27

1

30







20

1

34

0

34

0

34

0

34

0

34







21

1

34

0

34

0

34

0

34

0

34







22

1

34

0

34

0

34

0

34

0

34







23

1

34

0

34

0

34

0

34

1

37







24

1

34

0

34

0

34

0

34

1

37







25

1

34

0

34

0

34

0

34

1

37







26

1

34

0

34

0

34

0

34

1

37







27

1

34

0

34

0

34

0

34

1

44







28

1

34

0

34

[1]

47

0

47

0

47







29

1

34

0

34

1

47

0

47

0

47







30

1

34

0

34

1

47

0

47

0

47







31

1

34

0

34

1

47

1

49

0

49







32

1

34

0

34

1

54

1

54

0

54







33

1

34

0

34

1

54

0

54

0

54







34

1

34

0

34

1

54

0

54

0

54







35

1

34

0

34

1

54

0

54

[1]

57

[0]

57


У таблиці 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
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи