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

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)


Ясно, що останнє співвідношення різне для кожної з траєкторій Метод динамічного програмування і відповідного цій траєкторії керування Метод динамічного програмування на відрізку Метод динамічного програмування

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
Страницы: 1 2

Похожие рефераты: