Реферат Метод динамічного програмування
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
МЕТОД ДИНАМІЧНОГО ПРОГРАМУВАННЯ
1 Принцип оптимальності
Оптимальне керування в будь-який момент часу не залежить від передісторії процесу і визначається тільки станом системи в поточний момент і метою керування. Якщо в якийсь період часу керування було неоптимальним, то наслідки цього в майбутньому виправити вже не можна. Під метою керування розуміються вимоги, яким повинна задовольняти керована система, наприклад, це може бути приведення системи в заданий стан або забезпечення певних умов руху протягом заданого періоду часу.
Отже, принцип оптимальності характеризує наступний за заданим станом рух системи, але він може не мати місця для траєкторії, що передує цьому стану.
2 Метод динамічного програмування
Розглянемо застосування методу динамічного програмування до розв’язання неперервних задач оптимального керування. У цьому випадку треба виконати дискретизацію початкової задачі, тобто початкову задачу потрібно замінити близькою їй дискретною задачею. Розглянемо динамічну систему, закон руху якої описується автономним диференціальним рівнянням
де
Припустимо, що початковий стан системи
Для дискретизації неперервної задачі (1) – (2) розіб'ємо відрізок
кожний, де
З останнього співвідношення випливає, що
Інтегральному цільовому функціоналу (2) відповідає інтегральна сума
Отже, ми перейшли до дискретної задачі, у якій потрібно знайти такі керування
Розглянемо співвідношення
де
Величина
і залежить від стану
Відповідно до принципу оптимальності, керування
Далі будемо розглядати лише задачі, у яких зазначений мінімум досягається в єдиній точці.
На наступному етапі визначимо керування
де
а
– керування, що залежить від стану, у якому перебуває система. Отже, на передостанньому відрізку часу знайдене оптимальне керування як функція від стану
Повторюючи цю процедуру, на
де
відповідно до (3). Співвідношення (5) називаються рекурентними співвідношеннями Беллмана.
Після того, як на останньому етапі буде знайдено значення
Наведений алгоритм розв’язання задачі оптимального керування методом динамічного програмування можна перенести на загальний випадок задачі керування з векторним законом руху (1), тобто якщо
3 Принцип оптимальності для задачі оптимального керування з фіксованим часом і вільним правим кінцем
Розглянемо автономну систему
з цільовим функціоналом
у якому початковий і кінцевий моменти часу
Починаючи з будь-якого моменту часу
Відносно початкового відрізка оптимальної траєкторії до точки
4 Рівняння Беллмана в задачі з фіксованим часом і вільним правим кінцем
Розглянемо систему з законом руху (6) і критерієм оптимальності (2). Початковий стан системи заданий:
час руху
Позначимо через
серед всіх припустимих процесів
Припустимо, що для будь-якої точки
Функція
Припустимо, що
визначає цільовий функціонал (2) початкової задачі.
Розглянемо приріст
Відповідно до принципу оптимальності, відрізок оптимальної траєкторії від точки
тому співвідношення (9) можна переписати у вигляді
Очевидно, що другий доданок в (10) залежить від стану системи
Дійсно, розглянемо різні припустимі керування
Виберемо керування
яке дорівнює
Очевидно, що це значення залежить від стану
Розглянемо значення функціонала
Ясно, що останнє співвідношення різне для кожної з траєкторій
Побудований набір траєкторій є підмножиною більш широкої множини всіх припустимих функцій, на яких шукається найменше значення функціонала
Але оскільки оптимальна траєкторія
Звідси з урахуванням (11) одержимо
тобто оптимізація процесу проводиться тільки для
Розглянемо поведінку останнього співвідношення при
.
Вважатимемо, що функція Беллмана
неперервно диференційована по всіх своїх аргументах. Тоді
(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) було отримано в припущенні, що функція Беллмана має неперервні похідні другого порядку, що не завжди виконується.
Обидва методи придатні для задач, у яких відсутні обмеження на керування, і всі функції гладкі. Кожний з цих методів може бути застосований там, де не працює інший. Рівняння Беллмана вимагає більше припущень для застосування (неперервність і диференційованість функцій), а принцип максимуму складніше використовувати для розв’язання дискретних задач.
Вважатимемо, що функція Беллмана
Позначатимемо далі
Співвідношення (14) з урахуванням цього позначення набуде вигляду
Використовуючи останнє співвідношення, рівність (13) можна подати у вигляді
Оскільки функції
Припустимо, що функція
Останнє співвідношення називається рівнянням Беллмана. Воно є аналогом рекурентних рівнянь Беллмана дискретної задачі оптимального керування для випадку неперервної системи.
Замінивши
До рівняння Беллмана додаються крайові умови, що випливають безпосередньо з визначення функції Беллмана:
Рівняння Беллмана – це диференціальне рівняння в частинних похідних відносно функції
5 Рівняння Беллмана в задачі з фіксованими кінцями та вільним часом
Додамо до задачі (2), (6), (9) умову закріплення правого кінця траєкторії
Якщо підінтегральна функція не залежить від
6 Рівняння Беллмана в задачі швидкодії
Розглянемо задачу оптимальної швидкодії з фіксованими кінцями і вільним часом, закон руху якої має вигляд (6) і задані початковий стан
У задачі з фіксованими кінцями і вільним часом функція Беллмана залежить тільки від поточного стану системи і не залежить від моменту, починаючи з якого розглядається її еволюція (доведення аналогічно п. 5), тобто
Вважатимемо, що функція
або
за заданих крайових умов
Очевидно, що якщо процес
Зауваження. Оскільки функція Беллмана
7 Зв'язок методу динамічного програмування із принципом максимуму
Розглянемо задачу оптимального керування з фіксованими кінцями та вільним часом (6) з цільовим функціоналом
Оптимальне керування будемо вибирати серед кусково-неперервних вектор-функцій
що
Доведемо, що з рівняння (19) випливає існування деякого вектора
і нову функцію
де
Використовуючи ці позначення, перетворимо рівняння Беллмана. Очевидно, що
тому
Оскільки
Позначимо
Тоді формула (20) стає аналогом функції Понтрягіна
де
Це означає, що на оптимальному процесі
Доведемо, що спряжені змінні
Для цього припустимо, що функція Беллмана
Оскільки оптимальне керування
Продиференціюємо співвідношення (22):
Тоді відповідно до (23) для оптимального процесу дістанемо
Оскільки
то співвідношення (24) можна переписати у вигляді:
або, з урахуванням позначень (21),
Оскільки
а це, у свою чергу означає, що
Отже, встановлено теоретичний зв'язок принципу максимуму з методом динамічного програмування. Але на практиці виконати подібну операцію не завжди можливо. Так наприклад, рівняння (21) було отримано в припущенні, що функція Беллмана
Обидва методи придатні для задач, у яких відсутні обмеження на керування, і всі функції гладкі. Кожний з цих методів може бути застосований там, де не працює інший. Рівняння Беллмана вимагає більше припущень для застосування (неперервність і диференційованість функцій), а принцип максимуму складніше використовувати для розв’язання дискретних задач.
