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

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

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

Саати.

На рис. 1 дана иллюстрация этого принципа. На примере задачи с одной фазовой координатой. Кривая , соответствующая оптимальной траектории (получена с помощью оптимального управления). При этом предполагается, что начальное и конечное состояние фиксированное, то есть начальное и конечное состояние задано. Вся траектория разделена на 2 части, относительно момента времени . Согласно принципу оптимальности Беллмана траектория (2), определённая при должна представлять собой оптимальную траекторию, по отношению к начальному состоянию , следовательно, вторая часть оптимальной траектории сама по себе должна быть оптимальной траекторией в независимости от того, как она пришла в состояние, являющегося начальным состоянием для второй части траектории.

Предположим, что общая задача управления имеет вид:

найти функционала

, где – функция конечного значения времени.

Максимальное значение целевого функционала задачи с начальным состоянием х и начальным моментом времени t и обозначим и назовём эту функцию - функцией оптимального поведения (ФОП).

Отметим, что J представляет собой функционал, зависящий от управления {u(t)}, то является функцией зависящей от n+1 параметра: x и t. Тем самым наша исходная задача оказывается, погруженной в более широкий класс задач характеризуемых значением n+1 начальных параметров. Оптимальное значение целевого функционала исходной задачи будет Если является ФОП с начальным состоянием x, и моментом времени t, то согласно принципу оптимальности

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

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

В ДП существенную роль играют предположения относительно ФОП: предполагается, что она однозначная функция, a так же является непрерывно дифференцируемой функцией, то есть она имеет частные производные. В окрестности точки (x,t) ФОП можно разложить в ряд Тейлора

, или

.

, откуда

Рассмотрим предел этого выражения при , тогда

.

Так как

.

Данное уравнение является основным дифференциальным уравнением в частных производных, используемым в ДП. Оно называется уравнением Беллмана. Так как второй член в квадратных скобках представляет собой скалярное произведение вектора , то уравнение Беллмана можно записать следующим образом

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

.

Это условие показывает, что значение ФОП для задачи с начальным моментом и начальным состоянием, которые являются соответственно конечное состояние равно и конечный момент времени равно

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

.

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

Современные ЭВМ не обладают такой памятью, чтобы найти приближенные решения. Задачи ДП требуют, чтобы память машин содержала ячеек памяти, где q-размер сетки, то есть число дискретных значений, принимаемых каждой фазовой координатой, если например каждая фазовая координата разбита на 100 ячеек, а n=4, то память должна состоять 100 000 000 ячеек. Это очень трудно реализовать на ЭВМ. Беллман называет это «проклятием размерности» («curse of dimensionality»).

Дата добавления: 2015-12-08