Принцип оптимальности Беллмана

Формулировка принципа оптимальности:

Оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальные решения и первоначальные состояния и решение (управление) в начальный момент времени, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения.

Если вы не используете наилучшим образом то, чем вы располагаете, то вы никогда не распорядитесь наилучшим образом и тем, что вы могли иметь в дальнейшем.

Задача. На рисунке (Рис. 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мил ячеек. Это трудно реализовать на ЭВМ. Беллман назвал это препятствие – “проклятие размерности”.