Реферат: Метод динамічного програмування

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

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) булоотримано в припущенні, що функція Беллмана /> має неперервні похідні другогопорядку, що не завжди виконується.

Обидва методи придатні для задач, у якихвідсутні обмеження на керування, і всі функції гладкі. Кожний з цих методівможе бути застосований там, де не працює інший. Рівняння Беллмана вимагаєбільше припущень для застосування (неперервність і диференційованість функцій),а принцип максимуму складніше використовувати для розв’язання дискретних задач.