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

align="BOTTOM" border="0" />. Виберемо серед всіх значень Метод динамічного програмування мінімальне. Оскільки обидва доданки в (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) було отримано в припущенні, що функція Беллмана Метод динамічного програмування має неперервні похідні другого порядку, що не завжди виконується.

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

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

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

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

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