Метод динамического программирования. Принцип оптимальности и уравнение Беллмана.

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

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

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

Назовем величину условным максимумом. Еслимы теперь выберем на k -м шаге некоторое произвольное управление , то система придет в состояние . Согласно принципу оптимальности, необходимо выбирать управление так, чтобы оно в совокупности с оптимальным управлением на последующих шагах (начиная с (k+1)-го) приводило бы к общему показателю эффективности на шагах, начиная с k -uго и до конца. Это положение в аналитической форме можно записать в виде следующего соотношения:

,

, (1)

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

Из уравнения (1) может быть получена функция , если известно функция . Аналогично можно получить , если известно и т. д., пока не будет определена величина , представляющая по определению максимальное значение показателя эффективности процесса в целом:

.

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

В результате последовательного решения п частных задач на условный максимум определяют две последовательности функций: - условные максимумы и соответствующие им - условные оптимальные управления. Указанные последовательности функций в дискретных задачах получают в табличной форме, а в непрерывных моделях - аналитически. По­сле выполнения первого этапа (условнойоптимизациии) приступают ко второму этапу - безусловной оптимизации.

Если начальное состояние задано , то непосредственно

определяют максимум целевой функции

,

а затем - искомое безусловное оптимальное управление по цепочке

. (2)

Если задано множество начальных состояний , то дополнительно решают еще одну задачу на максимум

,

откуда находят , а затем по цепочке (2) - безусловное оптимальное управление.

В рассмотренных рекуррентных соотношениях предписывают начи­нать вычисления с последнего этапа и затем передвигаться назад до этапа 1. Такой метод вычислений известен как алгоритм обратной прогонки. Если расчеты осуществляются в естественном порядке следования этапов, то та­кой метод вычислений известен как алгоритм прямой прогонки.

Приведем рекуррентные соотношения для этого случая. Уравнения со­стояний для прямого хода удобно записывать в виде

.

Введем в рассмотрение условные максимумы показателя эффективности за k шагов, от 1-го до k- говключительно, - величину . Повторив приве­денные рассуждения, придем к следующей системе уравнений Беллмана:

;

.

В результате решения этих уравнений получим последовательности

; .

Далее определим безусловное оптимальное управление по цепочке

.