МЕТОДДИНАМІЧНОГО ПРОГРАМУВАННЯ
1 Принцип оптимальності
Оптимальне керування в будь-який моментчасу не залежить від передісторії процесу і визначається тільки станом системив поточний момент і метою керування. Якщо в якийсь період часу керування булонеоптимальним, то наслідки цього в майбутньому виправити вже не можна. Підметою керування розуміються вимоги, яким повинна задовольняти керована система,наприклад, це може бути приведення системи в заданий стан або забезпеченняпевних умов руху протягом заданого періоду часу.
Отже, принцип оптимальності характеризуєнаступний за заданим станом рух системи, але він може не мати місця длятраєкторії, що передує цьому стану.
2 Метод динамічного програмування
Розглянемо застосування методу динамічногопрограмування до розв’язання неперервних задач оптимального керування. У цьомувипадку треба виконати дискретизацію початкової задачі, тобто початкову задачупотрібно замінити близькою їй дискретною задачею. Розглянемо динамічну систему,закон руху якої описується автономним диференціальним рівнянням
/>,(1)
де />, /> – кусково-неперервні функції.
Припустимо, що початковий стан системи /> заданий, а накерування накладено обмеження />. Вважатимемо, що час руху /> фіксований.Цільовий функціонал задачі в цьому випадку матиме вигляд:
/>.(2)
Для дискретизації неперервної задачі (1) – (2)розіб'ємо відрізок /> на /> інтервалів довжиною
/>
кожний, де /> – натуральне число. Значенняфункцій /> і/> будемодалі визначати лише в дискретні моменти часу />, де />. Для цього введемо позначення />, />, і замінимодиференціальне рівняння (1) різницевим, апроксимуючи першу похідну значеннями вдискретні моменти часу:
/>.
З останнього співвідношення випливає, що
/>, />.(3)
Інтегральному цільовому функціоналу (2)відповідає інтегральна сума
/>.(4)
Отже, ми перейшли до дискретної задачі, уякій потрібно знайти такі керування />, що задовольняють обмеженню />, />, і мінімізуютьфункціонал (4) за початкових умов />. Очевидно, що результатирозв’язання цієї задачі будуть тим точніше апроксимувати початкову неперервнузадачу, чим більше />.
Розглянемо співвідношення
/>, />,
де />, …, /> визначаються за рекурентнимиформулами (3), і позначимо
/>.
Величина /> – це частина інтегральної суми(4), що відноситься до моментів часу
/>,
/>
і залежить від стану /> системи в момент часу
/>.
Відповідно до принципу оптимальності,керування /> наостанньому етапі треба обирати так, щоб
/>.
Далі будемо розглядати лише задачі, у якихзазначений мінімум досягається в єдиній точці.
На наступному етапі визначимо керування />, для якого
/>,
де
/>,
а
/>
– керування, що залежить від стану, у якомуперебуває система. Отже, на передостанньому відрізку часу знайдене оптимальнекерування як функція від стану />, в якому перебуватиме система намомент часу
/>.
Повторюючи цю процедуру, на />-му етапі потрібновизначити оптимальне керування />, що задовольняє співвідношенню
/>(5)
де
/>
відповідно до (3). Співвідношення (5)називаються рекурентними співвідношеннями Беллмана.
Після того, як на останньому етапі будезнайдено значення /> і оптимальне керування />, то за відомимзначенням /> можнавизначити послідовно />, />, …, />, />, />. При цьому значення /> відповідаємінімальному значенню функціонала (4).
Наведений алгоритм розв’язання задачіоптимального керування методом динамічного програмування можна перенести назагальний випадок задачі керування з векторним законом руху (1), тобто якщо />, />.
3 Принцип оптимальності для задачі оптимальногокерування з фіксованим часом і вільним правим кінцем
Розглянемо автономну систему
/>,(6)
з цільовим функціоналом
/>,(7)
у якому початковий і кінцевий моменти часу /> і /> задані, ізаданий початковий стан />.
Починаючи з будь-якого моменту часу />, відрізокоптимальної траєкторії />, /> від точки /> до точки /> також є оптимальноютраєкторією.
Відносно початкового відрізка оптимальноїтраєкторії до точки /> можна стверджувати, що цей відрізокє оптимальною траєкторією, лише у тому випадку, коли точка /> фіксована (наприклад, убагатоточкових задачах керування), тобто коли за умовами припустима траєкторіяобов'язково повинна проходити через точку />. Якщо ж задана тільки початковаточка />, товідрізок оптимальної траєкторії може і не бути оптимальною траєкторією, тобтоможе не доставляти оптимальне значення функціоналу (7).
4 Рівняння Беллмана в задачі з фіксованим часомі вільним правим кінцем
Розглянемо систему з законом руху (6) ікритерієм оптимальності (2). Початковий стан системи заданий:
/>,(8)
час руху /> відомий, а кінцевий стан /> – невідомий.Побудована таким чином задача – це задача з фіксованим часом і вільним правимкінцем.
Позначимо через />, /> оптимальну траєкторію, якавідповідає оптимальному керуванню />. Зафіксуємо деякий момент часу /> і відповіднуйому точку /> наоптимальній траєкторії. Відповідно до принципу оптимальності, відрізоктраєкторії /> відточки /> доточки /> єоптимальною траєкторією і надає найменшого значення функціоналу
/>
серед всіх припустимих процесів /> на відрізкучасу /> зпочатковим станом />, тобто
/>.
Припустимо, що для будь-якої точки /> фазовогопростору /> ібудь-якого моменту часу /> існує оптимальна траєкторія зпочатковою умовою />, яка надає найменшого значенняфункціоналу />.Позначимо це мінімальне значення через
/>.
Функція />, що задана у всіх точках />, простору />, />, називаєтьсяфункцією Беллмана.
Припустимо, що />, />, – оптимальний процес іоптимальна траєкторія /> задовольняє початковій умові />. Тоді
/>
визначає цільовий функціонал (2) початковоїзадачі.
Розглянемо приріст /> і відповідний йому момент часу />. Очевидно, щоостаннє співвідношення можна переписати так:
/>.(9)
Відповідно до принципу оптимальності, відрізокоптимальної траєкторії від точки /> до точки /> також є оптимальною траєкторією,тобто
/>,
тому співвідношення (9) можна переписати увигляді
/>.(10)
Очевидно, що другий доданок в (10) залежитьвід стану системи /> (оскільки оптимальне значенняфункціонала /> залежитьвід початкового стану системи /> і для кожного початкового стану /> оптимальнезначення функціонала /> різне). У цей стан />, у свою чергу, системапопадає під дією керування />, яке діє на інтервалі часу />. Отже,значення /> залежатимевід вибору керування на відрізку />.
Дійсно, розглянемо різні припустимікерування /> навідрізку />.Їм відповідатиме набір траєкторій /> , що виходять із точки />, яка лежить наоптимальній траєкторії />. На кожній траєкторії із цьогонабору фазова точка в момент часу /> попаде в деякий стан />.
Виберемо керування /> на відрізку /> так, щоб траєкторія /> на цьомувідрізку була оптимальною. Це оптимальне керування в загальному випадку різнедля кожної траєкторії пучка. Очевидно, що вибираючи одне – оптимальне – середвсіх можливих керувань />, /> для кожної із траєкторій />, ми фіксуємоподальший стан кожної із них і при цьому одержуємо мінімальне значенняфункціонала
/>,
яке дорівнює
/>.
Очевидно, що це значення залежить від стану/>. Аоскільки, як було встановлено раніше, стан /> залежав від вибору керування /> на відрізку />, то й значення/> такожзалежатиме від того, яким було обрано керування />, />.
Розглянемо значення функціонала /> на траєкторіяхз набору, побудованого вище при />. Оскільки відрізок кожноїтраєкторії /> відточки /> доточки /> єоптимальним відповідно до принципу максимуму, то значення функціонала дорівнює
/>.(11)
Ясно, що останнє співвідношення різне длякожної з траєкторій /> і відповідного цій траєкторіїкерування /> навідрізку />.Виберемо серед всіх значень /> мінімальне. Оскільки обидвадоданки в (11) залежать тільки від вибору керування /> на інтервалі />, то і мінімальнезначення (11) залежатиме тільки від вибору керування на цьому інтервалі, тобто
/>.
Побудований набір траєкторій є підмножиноюбільш широкої множини всіх припустимих функцій, на яких шукається найменшезначення функціонала />. Тому в загальному випадку маємісце нерівність
/>.(12)
Але оскільки оптимальна траєкторія /> належить допобудованого набору траєкторій, то в співвідношенні (12) насправді має місцерівність, тобто
/>.
Звідси з урахуванням (11) одержимо
/>, (13)
тобто оптимізація процесу проводитьсятільки для />,тому що для /> траєкторія вже оптимальна.
Розглянемо поведінку останньогоспіввідношення при />, тобто коли інтервал />, на якомушукається оптимальне керування, звужується до точки. Відповідно до закону руху
/>.
Вважатимемо, що функція Беллмана /> неперервнодиференційована по всіх своїх аргументах. Тоді
/> (14)
Позначатимемо далі
/>.
Співвідношення (14) з урахуванням цьогопозначення набуде вигляду
/>.
Використовуючи останнє співвідношення,рівність (13) можна подати у вигляді
/> (15)
Оскільки функції /> і /> у правій частині (15) не залежатьвід />, їхможна винести за знак мінімуму. Після скорочень одержимо
/>.
Припустимо, що функція /> є неперервною навідрізку />.Розділивши останнє співвідношення на />, при /> одержимо
/>.(16)
Останнє співвідношення називаєтьсярівнянням Беллмана. Воно є аналогом рекурентних рівнянь Беллмана дискретноїзадачі оптимального керування для випадку неперервної системи.
Замінивши /> на />, де /> – оптимальна траєкторія, одержимоз (16)
/>.(17)
До рівняння Беллмана додаються крайовіумови, що випливають безпосередньо з визначення функції Беллмана:
/>.(18)
Рівняння Беллмана – це диференціальнерівняння в частинних похідних відносно функції />. Але це рівняння не є лінійнимчерез наявність у (17) операції мінімізації. Фактично це означає підстановку врівняння такого />, на якому досягається мінімум іяке змінюється в залежності від значень /> і />.
5 Рівняння Беллмана в задачі з фіксованими кінцямита вільним часом
Додамо до задачі (2), (6), (9) умовузакріплення правого кінця траєкторії />, де /> – задано, а /> – невідомо. У цьомувипадку функція Беллмана залежатиме тільки від поточного стану системи. Дійсно,згідно з визначенням функції Беллмана
/>.
Якщо підінтегральна функція не залежить від/>, тозначення інтеграла /> при фіксованих /> і /> залежить тільки віддовжини інтервалу інтегрування />, який можна визначити завтономної системи (6), якщо відомі точки /> і /> фазової траєкторії. Тому різниця /> – це функціявід аргументів /> і />, а /> не залежить явно від />. У цьомувипадку /> ірівняння Беллмана для задачі із закріпленими кінцями набуває вигляду
/>.
6 Рівняння Беллмана в задачі швидкодії
Розглянемо задачу оптимальної швидкодії зфіксованими кінцями і вільним часом, закон руху якої має вигляд (6) і заданіпочатковий стан /> та кінцевий стан />. Час /> невідомий і йогопотрібно знайти з умови мінімізації цільового функціонала
/>.
У задачі з фіксованими кінцями і вільнимчасом функція Беллмана залежить тільки від поточного стану системи і незалежить від моменту, починаючи з якого розглядається її еволюція (доведенняаналогічно п. 5), тобто />.
Вважатимемо, що функція /> неперервна на будь-якомувідрізку /> ідля будь-якої точки фазового простору /> і будь-якого моменту часу /> існуєоптимальна траєкторія, а функція /> неперервно диференційована засвоїми аргументами. Тоді необхідна умова оптимальності у вигляді рівнянняБеллмана (17), (18) для даної задачі матиме вигляд:
/>,
або
/>
за заданих крайових умов />.
Очевидно, що якщо процес /> – оптимальний, то,будучи підставленим у рівняння Беллмана, він дасть тотожність
/>.
Зауваження. Оскільки функція Беллмана /> дорівнюємінімальному значенню цільового функціонала, що характеризує перехід системи вкінцевий стан зі стану />, то в задачі оптимальноїшвидкодії ця функція показує оптимальний час переходу /> зі стану /> у фіксований стан />.
7 Зв'язок методу динамічного програмування ізпринципом максимуму
Розглянемо задачу оптимального керування зфіксованими кінцями та вільним часом (6) з цільовим функціоналом />, і крайовими умовами/>, />. Вважатимемо,що час /> невідомий.
Оптимальне керування будемо вибирати середкусково-неперервних вектор-функцій />. За принципом динамічногопрограмування для оптимального процесу /> існує такий розв’язок /> рівнянняБеллмана
/>,(19)
що /> – значення, на якому досягаєтьсямінімум у лівій частині рівняння (19).
Доведемо, що з рівняння (19) випливаєіснування деякого вектора />, який задовольняє співвідношеннямпринципу максимуму. Нехай /> – функція Беллмана, що відповідаєоптимальному процесу />. Розглянемо нову змінну
/>
і нову функцію
/>,
де />.
Використовуючи ці позначення, перетвориморівняння Беллмана. Очевидно, що
/>, />, />,
тому
/>
Оскільки />, то останнє співвідношення можнапривести до вигляду:
/>.(20)
Позначимо
/>, />.
Тоді формула (20) стає аналогом функціїПонтрягіна
/>,
де />.
Це означає, що на оптимальному процесі /> функціяПонтрягіна набуває максимального значення, рівного 0. Очевидно, що функціяПонтрягіна не залежить від />, тому що /> і />, /> не залежать від />.
Доведемо, що спряжені змінні /> задовольняють спряженійсистемі
/>, />.(21)
Для цього припустимо, що функція Беллмана /> має неперервнічастинні похідні другого порядку. Позначимо
/>.(22)
Оскільки оптимальне керування /> однозначновизначає оптимальну траєкторію />, то функція /> досягає на кожномуфіксованому /> позмінній /> максимальногозначення, рівного 0, у точці />, що відповідає оптимальномукеруванню /> вцій точці. У цьому випадку для функції /> в будь-який момент часу дляпроцесу /> будевиконана умова
/>, />, />.(23)
Продиференціюємо співвідношення (22):
/>, />.
Тоді відповідно до (23) для оптимальногопроцесу дістанемо
/>, />.(24)
Оскільки
/>,
то співвідношення (24) можна переписати увигляді:
/>,
або, з урахуванням позначень (21),
/>, />.
Оскільки />, то
/>,
а це, у свою чергу означає, що
/>, />.
Отже, встановлено теоретичний зв'язокпринципу максимуму з методом динамічного програмування. Але на практицівиконати подібну операцію не завжди можливо. Так наприклад, рівняння (21) булоотримано в припущенні, що функція Беллмана /> має неперервні похідні другогопорядку, що не завжди виконується.
Обидва методи придатні для задач, у якихвідсутні обмеження на керування, і всі функції гладкі. Кожний з цих методівможе бути застосований там, де не працює інший. Рівняння Беллмана вимагаєбільше припущень для застосування (неперервність і диференційованість функцій),а принцип максимуму складніше використовувати для розв’язання дискретних задач.