Задача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,\"умовно\", в іншому- \"безумовно\". icon

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




Скачати 154.5 Kb.
НазваЗадача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,"умовно", в іншому- "безумовно".
Дата20.09.2012
Розмір154.5 Kb.
ТипЗадача

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 - номер студента

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






Схожі:

Задача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,\"умовно\", в іншому- \"безумовно\". iconЗадача динамічного програмування. Загальний випадок
Але у відмінності від лінійного програмування динамічне програмування не зводиться до якийсь стандартної обчислювальної процедури;...
Задача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,\"умовно\", в іншому- \"безумовно\". iconДинамічне програмування
Характерним для динамічного програмування є поетапний (багатокроковий) процес рішення оптимізаційної задачі
Задача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,\"умовно\", в іншому- \"безумовно\". icon1. Моделі І критерії ефективності
Тема Задачі динамічного програмування І методи сітьового планування І управління
Задача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,\"умовно\", в іншому- \"безумовно\". icon1. Моделі І критерії ефективності
Тема Задачі динамічного програмування І методи сітьового планування І управління
Задача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,\"умовно\", в іншому- \"безумовно\". icon1. Моделі І критерії ефективності
Тема Задачі динамічного програмування І методи сітьового планування І управління
Задача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,\"умовно\", в іншому- \"безумовно\". iconНазва модуля: Програмування для систем реального часу
Програмування таймера. Сторожовий таймер. Послідовні інтерфейси. Паралельні інтерфейси. Оптимізація програмного забезпечення систем...
Задача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,\"умовно\", в іншому- \"безумовно\". iconПитання на екзамен з дисципліни «Економіко математичне моделювання». Модуль «Математичне програмування»
Перша стандартна форма задачі лп. (Основна задача лінійного програмування з обмеженнями-рівностями)
Задача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,\"умовно\", в іншому- \"безумовно\". iconПитання на іспит з дисципліни «Математичне програмування та дослідження операцій»
Загальна математична модель лінійного програмування. Форми запису задач лп. Геометрична інтерпретація злп
Задача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,\"умовно\", в іншому- \"безумовно\". iconПитання на іспит з дисципліни «Математичне програмування та дослідження операцій»
Загальна математична модель лінійного програмування. Форми запису задач лп. Геометрична інтерпретація злп
Задача динамічного програмування. Загальний випадок Загальна ідея динамічного програмування: пошагова оптимізація, що проходить в одному напрямі,\"умовно\", в іншому- \"безумовно\". iconКритерії оцінювання знань І вмінь студентів
«Інформатика» денної та заочної форми навчання. Фахове вступне випробування базується на матеріалах навчальних дисциплін з програмування:...
Додайте кнопку на своєму сайті:
Документи


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