183704 (Метод динамічного програмування)

МЕТОД ДИНАМІЧНОГО ПРОГРАМУВАННЯ

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)

тобто оптимізація процесу проводиться тільки для , тому що для траєкторія вже оптимальна.

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