Дискретная форма динамического программирования

где u -- ограниченное в общем случае управление, т.е. ; Дt -- дискрет времени, равный .

При заданном начальном состояний объекта и свободном правом конце необходимо за фиксированное время обеспечить минимум заданного функционала

или в виде аддитивной целевой функции

Таким образом, J есть функция (к + 1) выбираемых переменных , присутствующих в (к +1) уравнениях связи, т.е. можно попытаться решить задачу с помощью множителей Лагранжа. Однако это сложно из-за большой размерности задачи, поэтому применим иной подход.

Выведем сначала функциональное уравнение Беллмана, рассуждая следующим образом. Пусть минимизируемое значение функционала J в начальный момент времени определенным образом зависит от начального состояния системы, т.е. от t0 и x(t0). Обозначим эту зависимость через , называемую функцией Беллмана, понимая под этим не любое значение функционала, а его минимум при оптимальном поведении системы.

Представим теперь, что система функционировала некоторое время , в результате чего к моменту она пришла в новое состояние . Тогда, согласно принципу оптимальности, оставшееся значение минимизируемого функционала

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

Поэтому, преследуя цель минимизации суммарных потерь, как текущих так и последующих, можно записать:

Рассуждая аналогичным образом при переходе к следующему шагу от момента к моменту и т.д. к моменту , можно записать следующее функциональное уравнение:

Развивая этот же подход применительно к многомерному неавтономному объекту, можно получить функциональное уравнение Беллмана:

Пошаговый выбор управления с помощью уравнения (1.5) удобен для расчетов на ЭВМ. В этом случае численное решение обычно осуществляют с правого конца задачи. Поскольку краевые условия на правом конце не определены однозначно, то расчеты начинают, задавшись множеством значений вектора , разбивая, например, диапазон возможных значений на R- 1 участков. В результате для каждого из R n вариантов конечного состояния определяется единственное управление на последнем шаге (в предположении, что управления на остальных шагах будут найдены позже), поскольку при заданном только от него зависит последнее слагаемое в функции (1.3):

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

На следующем шаге, являющемся уже типичным для расчетов, снова формируются варианты состояния , а затем для каждого из них численно определяется управление , но уже исходя из минимума суммы двух слагаемых, причем второе слагаемое отыскивается в памяти ЭВМ в соответствии с переходом из B ;

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

Теперь, поскольку управление найдено и, значит, определено значение , представляющее собой минимизируемое значение функционала, осталось выявить конкретные значения , соответствующие данной оптимальной траектории. Для этого на основании уравнения (1.7) и известного управления определяется состояние , которому соответствует свое запомненное управление . Продолжая теперь движение слева направо, последовательно восстанавливают всю программу управления и оптимальную траекторию за все к шагов.

Рис 1.1 Иллюстрация численного решения с правого конца задачи при дискретной форме динамического программирования

Рассмотренным методом решаются задачи, когда на правом конце часть фазовых координат закреплена. Например, на рис. (1.1) представлен случай перехода из точки А в точку В с произвольной конечной скоростью; Тогда движение справа налево, как это показано на рис. (1.1), при к = 3 требует переменного объема запоминаемых результатов, поскольку по координатам x1 и x2 вначале оценивается малое число вариантов, а потом число растет, вплоть до момента достижения точки А. При этом основное содержание расчета на каждом шаге остается прежним.

Нужно отметить, что, несмотря на определенную утомительность рассмотренной вычислительной процедуры, метод динамического программирования сводит задачу минимизации функции переменных отдельным шагам расчетами минимизации функции Беллмана, зависящей только от г переменных. Это экономит время расчета, требуя, правда, значительного объема памяти ЭВМ. Достоинством метода при численных расчетах является также и снижение объема вычислений при сужении области допустимых управлений или допустимого множества значений . Однако с увеличением размерности задачи дискретизация увеличивает число вариантов расчета запоминаемых результатов в степени n, что известно как «проклятие размерности», и требует иных подходов к применению динамического программирования.