Задача динамічного програмування. Загальний випадок icon

Задача динамічного програмування. Загальний випадок




Скачати 121.16 Kb.
НазваЗадача динамічного програмування. Загальний випадок
Дата06.09.2012
Розмір121.16 Kb.
ТипЗадача

Задача динамічного програмування. Загальний випадок


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

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

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

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

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

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

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

Виграш на і-м кроку при керуванні хі, якщо система могла S

(6.1.)

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

(6.2.)

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

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

(6.3.)

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

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

(6.4.)

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

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

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

(6.5.)

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

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

,

де .

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

(6.6.)

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

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


Таблиця 6.5

x

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 тис.грн. Керуваннями хі - є засоби, що виділяються підприємствам.

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

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


Таблиця 6.6

S

x3(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. Умовну оптимізацію передостаннього кроку здійснюємо відповідно до вираження (6.3.):

S=0; x=0; ; x2=0

S=100; x=||0, 100||; ; x2=100

S=200; x=||0, 100, 200||; ; x2=100

S=300; x=||0, 100, 200, 300||; ; x2=200

S=400; x=||0, 100, 200, 300, 400||; ; x2=100

S=500; x=||0, 100, 200, 300, 400, 500||; ;

S=600; x=||0, 100, 200, 300, 400, 500, 600||; ; x2=100

S=700; x=||0, 100, 200, 300, 400, 500, 600, 700||; ; x2=100

Результат умовної оптимізації на 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.)

S=So=700; x=||0, 100, 200, 300, 400, 500, 600, 700||; ; x1=0

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

x*=||0, 100, 600||, а максимальний приріст виробництва відповідає 270 тис. грн.


ТЕСТИ

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


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

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

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

4. При рішенні задач ДП звичайно сутужніше визначити етапи, чим стани.

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

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

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

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

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

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


ЗАВДАННЯ

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




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

х

f1(x)

f2(x)

f3(x)

f4(x)

1

0.1

0.5 +0. 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 +0. i

0.5 +0. i

0.7 +0. i

4

0.3 +0. i

0.9 +0. i

0.6 +0. i

0.8 +0. i

5

0.5 +0. i

1.2 +0. i

0.7 +0. i

0.9 +0. i

6

0.8 +0. i

1.5 +0. i

0.8 +0. i

0.9 +0. i

7

0.9 +0. i

1.5 +0. 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 +0. i

1.1 +0. i

0.9 +0. i

10

2+0. i

1.5 +0. i

1.1 +0. i

0.9 +0. i

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


ІІІ. Задача про розподіл людських ресурсів. Для виконання робіт направляється 6 чоловік. Оцінка ефективності на роботи на різних ділянках визначається функціями fi(x), i=1, 2, 3, поданої в наступній таблиці:


х

f1(x)

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+i

5

350+i

300+i

600+i

6

500+i

550+i

650+i


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

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

Схожі:

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


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