Принцип оптимальности Беллмана
Формулировка принципа оптимальности:
Оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальные решения и первоначальные состояния и решение (управление) в начальный момент времени, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения.
Если вы не используете наилучшим образом то, чем вы располагаете, то вы никогда не распорядитесь наилучшим образом и тем, что вы могли иметь в дальнейшем.
Задача. На рисунке (Рис. 1) дана иллюстрация принципа Беллмана на примере задачи с одной фазовой координатой:
Кривая - соответствующая оптимальная траектория. При этом предполагается, что начальное состояние и конечное фиксировано (задача с фиксированными концами). Вся траектория разделена на две части (“1” и “2”) относительно момента времени .
Согласно принципу оптимальности Беллмана траектория “2”, определенная при , должна представлять собой оптимальную траекторию по отношению к начальному состоянию. Вторая часть оптимальной траектории не зависит от того, каким образом и как она пришла в начальное состояние .
Возвращаемся к задаче оптимального управления. Дадим постановку ОУ. Предположим, что общая задача управления имеет вид:
Найти максимум функционала , (1)где – функция координат конечной точки и конечного значения времени.
; ; ;
Пусть задача 1 имеет решение.
Максимальное значение целевого функционала задачи 1 с начальным состоянием и и начальным моментом времени обозначим и назовем – функцией оптимального поведения. (2)
Отметим, что в то время как представляет собой функционал, зависящий от управления , то - является функцией зависящей от параметра: и .
Тем самым наша исходная задача (1)является “погруженной” в более высокий класс задач, характеризуемый значениями начальных параметров. Оптимальное значение целевого функционала исходной задачи (1)имеет вид
. (3)
Если является функцией ФОП с начальным состоянием и моментом времени , то согласно принципу оптимальности:
– будет ФОП для второй части оптимальной траектории с начальным моментом времени и начальным состоянием (см. рис. 1).
Тогда эта траектория “2” является оптимальной для начального состояния и начального момента времени .
При этом прирост ФОП на протяжении всего промежутка времени между и может происходить только за счет изменения подынтегральной функции и управления.
Значение ФОП на всем интервале времени начинающимся в момент времени представляет собой сумму двух частей этого интервала.
(4)
В динамическом программировании существенную роль играет предположение, что ФОП является однозначной функцией и является дифференцируемой функцией от параметров.
Следовательно, можно разложить в ряд Тейлора в окрестности точки
, где (5)в правой части - вектор приращения, - скалярное произведение, (6)
(7)
,
,
,
. (8)
Рассмотрим предел следующего выражения: , тогда
. (9)
Уравнение (9)является основным дифференциальным уравнением в частных производных, используемым в динамическом программировании. Оно называется уравнением Беллмана.
Так как второй член в квадратных скобках уравнения (9)представляет собой скалярное произведение вектора и вектора - столбца , то уравнение можно записать следующим образом
. (10)
С уравнением связано, в качестве граничного условия, ограничение, накладываемое на конечное состояние:
. (11)
Это условие показывает, что значение ФОП для задачи с начальным моментом и начальным состоянием, которые являются соответственно конечный момент времени и конечное состояние . Если бы уравнение Беллмана было решено, то мы получили бы ФОП и, следовательно, оптимальное значение целевой функции для исходной задачи можно было бы определить как частное значение этой функции .
В общем случае это уравнение в частных производных первого порядка, как правило, нелинейное. Как правило, нелинейное уравнение не имеет аналитического решения. Следовательно, необходимо применять какие – либо численные методы решения. Это уравнение Беллмана можно представить в виде разносных схем для использования на ЭВМ. Но современные ЭВМ не позволяют найти решение с большой размерностью.
Если, например, каждую фазовую координату разбить на 100 значений, а , то память должна состоять из 100мил ячеек. Это трудно реализовать на ЭВМ. Беллман назвал это препятствие – “проклятие размерности”.