"justify">) можливі результати попереднього кроку
) вплив управління на всі залишилися до кінця процесу кроки.
В задачах динамічного програмування перший пункт враховують, роблячи на кожному кроці умовні припущення про можливі варіанти закінчення попереднього кроку і проводячи для кожного з варіантів умовну оптимізацію. Виконання другого пункту забезпечується тим, що в задачах динамічного програмування умовна оптимізація проводиться від кінця процесу до початку. Спершу оптимізується останній m-й крок, на якому не треба враховувати можливі впливи обраного управління xm на всі наступні кроки, так як ці кроки просто відсутні. Роблячи припущення про умови закінчення (m - 1) -го кроку, для кожного з них проводять умовну оптимізацію m-го кроку і визначають умовне оптимальне керування xm. Аналогічно поступають для (m - 1) -го кроку, роблячи припущення про исходах закінчення (m - 2) -го кроку і визначаючи умовне оптимальне керування на (m - 1) -му кроці, що приносить оптимальний виграш на двох останніх кроках - (m- 1) -му і m-му. Так само діють на всіх інших кроках до першого. На першому кроці, як правило, не треба робити умовних припущень, так, як стан системи перед першим кроком зазвичай відомо.
Для цього стану вибирають оптимальне шаговое керування, що забезпечує оптимальний виграш на першому і всіх наступних кроках. Це управління є безумовним оптимальним керуванням на першому кроці і, знаючи його, визначаються оптимальне значення виграшу і безумовні оптимальні управління на всіх кроках.
2. Складання математичної моделі динамічного програмування
Додатково введемо такі умовні позначення: - Стан процесу; - безліч можливих станів процесу перед i-му кроком; - виграш з i-го кроку до кінця процесу, i=
Можна визначити наступні основні етапи складання математичної моделі задачі динамічного програмування.
. Розбиття задачі на кроки (етапи). Крок не повинен бути занадто дрібним, щоб не проводити зайвих розрахунків і не повинен бути занадто великим, ускладнюючим процес крокової оптимізації.
. Вибір змінних, що характеризують стан s модельованого процесу перед кожним кроком, і виявлення накладаються на них обмежень. В якості таких змінних слід брати фактори, що представляють інтерес для дослідника.
. Визначення безлічі крокових управлінь xi, i=і накладаються на них обмежень, тобто області допустимих управлінь x.
. Визначення виграшу
? i (s, xi), (1.1)
який принесе на i-му кроці управління xi, якщо система перед цим перебувала в стані s.
. Визначення стану s, в яке переходить система зі стану s під впливом управління xi,
s=fi (s, xi), (1.2)
де fi - функція переходу на i-му кроці зі стану s в стан s.
. Складання рівняння, що визначає умовний оптимальний виграш на останньому кроці, для складання s модельованого процесу
Wm (S)=max {? m (s, xm)}. (1.3) € X
7. Складання основного функціонального управління динамічного програмування, що визначає умовний оптимальний виграш для даного стану s з i-го кроку і до кінця процесу через вже відомий умовний оптимальний виграш с (i + 1) -го кроку і до кінця:
Wi (S)=max {? i (s, xi) + Wi + 1 (fi (s, xi))}. (1.4) € X
У це рівняння у вже відому функцію Wi + 1 (s), що характеризує умовний оптимальний виграш с (i + 1) -го кроку до кінця процесу, замість стану s підставлено новий стан s=fi (s , xi), в яке система переходить на i-му кроці під впливом управління xi.
Зауважимо, що структура моделі динамічного програмування відрізняється від статичної моделі лінійного програмування. Дійсно, в моделях лінійного програмування, керуючі змінні - це одночасно і змінні стану модельованого процесу, а в динамічних моделях окремо вводяться змінні управління xi, і змінні, що характеризують зміна стану s під впливом управління. Таким чином, структура динамічних моделей більш складна, що природно, оскільки в цих моделях додатково враховується фактор часу.
Етапи вирішення задачі динамічного програмування.
Після того як виконані пункти 1-7, і математична модель складена, приступають до її розрахунку.
Основні етапи рішення задачі динамічного програмування:
. Визначення безлічі можливих станів Sm для останнього кроку.
. Проведення умовної оптимізації для кожного стану s € Sm на останньому m-му кроці за формулою (1.3) і визначення умовного оптимального упр...
