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

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

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

На рисунке 1 дана иллюстрация этого принципа на примере задачи с одной фазовой координатой x.

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

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

Найти , (1)

Максимальное значение целевого функционала задачи с начальным состоянием и начальным моментом времени обозначим

(2)

и назовем эту функцию – функцией оптимального поведения. Отметим, что в то время как представляет собой функционал, зависящий от управления , то - является функцией зависящей от параметра: и .

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

, (3)

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

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

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

, (4)

В динамическом программировании существенную роль играет предположения относительно функции ФОП:

1)Однозначная функция,

2) Непрерывно дифференцируемая функция от параметров.

Предположив это, можно в окрестности точки ФОП разложить в ряд Тейлора:

(5)

Подставляя (5)в (4), получаем:

. (7)

Рассмотрим предел следующего выражения: , тогда

Из (1): .

. (8)

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

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

(9)

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

. (10)

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

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

Для решения задач Динамического программирования, память ЭВМ должна содержать - ячеек памяти, где - размер сетки (число дискретных значений) применяющихся каждой фазовой координатой.

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

123

Не нашли, что искали? Воспользуйтесь поиском по сайту: