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

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

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

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

Задача. На рисунке (Рис. 1) дана иллюстрация принципа Беллмана на примере задачи с одной фазовой координатой:

Принцип оптимальности Беллмана - student2.ru

Кривая Принцип оптимальности Беллмана - student2.ru - соответствующая оптимальная траектория. При этом предполагается, что начальное состояние и конечное фиксировано (задача с фиксированными концами). Вся траектория разделена на две части (“1” и “2”) относительно момента времени Принцип оптимальности Беллмана - student2.ru .

Согласно принципу оптимальности Беллмана траектория “2”, определенная при Принцип оптимальности Беллмана - student2.ru , должна представлять собой оптимальную траекторию по отношению к начальному состоянию. Вторая часть оптимальной траектории не зависит от того, каким образом и как она пришла в начальное состояние Принцип оптимальности Беллмана - student2.ru .

Возвращаемся к задаче оптимального управления. Дадим постановку ОУ. Предположим, что общая задача управления имеет вид:

Найти максимум функционала Принцип оптимальности Беллмана - student2.ru , (1)где Принцип оптимальности Беллмана - student2.ru – функция координат конечной точки и конечного значения времени.

Принцип оптимальности Беллмана - student2.ru ; Принцип оптимальности Беллмана - student2.ru ; Принцип оптимальности Беллмана - student2.ru Принцип оптимальности Беллмана - student2.ru ;

Принцип оптимальности Беллмана - student2.ru

Пусть задача 1 имеет решение.

Максимальное значение целевого функционала задачи 1 с начальным состоянием Принцип оптимальности Беллмана - student2.ru и и начальным моментом времени Принцип оптимальности Беллмана - student2.ru обозначим Принцип оптимальности Беллмана - student2.ru и назовем – функцией оптимального поведения. (2)

Отметим, что в то время как Принцип оптимальности Беллмана - student2.ru представляет собой функционал, зависящий от управления Принцип оптимальности Беллмана - student2.ru , то Принцип оптимальности Беллмана - student2.ru - является функцией зависящей от Принцип оптимальности Беллмана - student2.ru параметра: Принцип оптимальности Беллмана - student2.ru и Принцип оптимальности Беллмана - student2.ru .

Тем самым наша исходная задача (1)является “погруженной” в более высокий класс задач, характеризуемый значениями Принцип оптимальности Беллмана - student2.ru начальных параметров. Оптимальное значение целевого функционала исходной задачи (1)имеет вид

Принцип оптимальности Беллмана - student2.ru . (3)

Если Принцип оптимальности Беллмана - student2.ru является функцией ФОП с начальным состоянием Принцип оптимальности Беллмана - student2.ru и моментом времени Принцип оптимальности Беллмана - student2.ru , то согласно принципу оптимальности:

Принцип оптимальности Беллмана - student2.ru – будет ФОП для второй части оптимальной траектории с начальным моментом времени Принцип оптимальности Беллмана - student2.ru и начальным состоянием Принцип оптимальности Беллмана - student2.ru (см. рис. 1).

Тогда эта траектория “2” является оптимальной для начального состояния Принцип оптимальности Беллмана - student2.ru и начального момента времени Принцип оптимальности Беллмана - student2.ru .

При этом прирост ФОП на протяжении всего промежутка времени между Принцип оптимальности Беллмана - student2.ru и Принцип оптимальности Беллмана - student2.ru может происходить только за счет изменения подынтегральной функции и управления.

Значение ФОП на всем интервале времени начинающимся в момент времени Принцип оптимальности Беллмана - student2.ru представляет собой сумму двух частей этого интервала.

Принцип оптимальности Беллмана - student2.ru (4)

В динамическом программировании существенную роль играет предположение, что ФОП является однозначной функцией и является дифференцируемой функцией от Принцип оптимальности Беллмана - student2.ru параметров.

Следовательно, можно разложить Принцип оптимальности Беллмана - student2.ru в ряд Тейлора в окрестности точки Принцип оптимальности Беллмана - student2.ru

Принцип оптимальности Беллмана - student2.ru , где Принцип оптимальности Беллмана - student2.ru (5)в правой части - вектор приращения, Принцип оптимальности Беллмана - student2.ru - скалярное произведение, Принцип оптимальности Беллмана - student2.ru (6)

Принцип оптимальности Беллмана - student2.ru (7)

Принцип оптимальности Беллмана - student2.ru ,

Принцип оптимальности Беллмана - student2.ru ,

Принцип оптимальности Беллмана - student2.ru ,

Принцип оптимальности Беллмана - student2.ru

Принцип оптимальности Беллмана - student2.ru . (8)

Рассмотрим предел следующего выражения: Принцип оптимальности Беллмана - student2.ru , тогда

Принцип оптимальности Беллмана - student2.ru . (9)

Уравнение (9)является основным дифференциальным уравнением в частных производных, используемым в динамическом программировании. Оно называется уравнением Беллмана.

Так как второй член в квадратных скобках уравнения (9)представляет собой скалярное произведение вектора Принцип оптимальности Беллмана - student2.ru и вектора - столбца Принцип оптимальности Беллмана - student2.ru , то уравнение можно записать следующим образом

Принцип оптимальности Беллмана - student2.ru . (10)

С уравнением связано, в качестве граничного условия, ограничение, накладываемое на конечное состояние:

Принцип оптимальности Беллмана - student2.ru . (11)

Это условие показывает, что значение ФОП для задачи с начальным моментом и начальным состоянием, которые являются соответственно конечный момент времени Принцип оптимальности Беллмана - student2.ru и конечное состояние Принцип оптимальности Беллмана - student2.ru . Если бы уравнение Беллмана было решено, то мы получили бы ФОП и, следовательно, оптимальное значение целевой функции для исходной задачи можно было бы определить как частное значение этой функции Принцип оптимальности Беллмана - student2.ru .

В общем случае это уравнение в частных производных первого порядка, как правило, нелинейное. Как правило, нелинейное уравнение не имеет аналитического решения. Следовательно, необходимо применять какие – либо численные методы решения. Это уравнение Беллмана можно представить в виде разносных схем для использования на ЭВМ. Но современные ЭВМ не позволяют найти решение с большой размерностью.

Если, например, каждую фазовую координату разбить на 100 значений, а Принцип оптимальности Беллмана - student2.ru , то память должна состоять из 100мил ячеек. Это трудно реализовать на ЭВМ. Беллман назвал это препятствие – “проклятие размерности”.




Наши рекомендации