Решение задачи динамического программирования.

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

На окончательной стадии для каждого шага определяется окончательное (безусловное) оптимальное управление.
Предварительная (условная) оптимизация проводится по шагам, в обратном порядке:
от последнего шаги к первому;
Окончательная (безусловная) оптимизация-также по шагам, но в естественном порядке:
от первого шага к последнему.

Введем следующие обозначения: -условный оптимальный выигрыш, получаемый на всех последующих шагах, начиная с i-го и до конца;
он достигается при оптимальном управлении на всех этих шагах и равен максимальному выигрышу, который можно получить на всех этих шагах вместе, если перед их началом система находится в состоянии .
-условное оптимальное управление на i-ом шаге, которое, совместно с оптимальным управлением на всех последующих шагах, обращает выигрыш на всех шагах, начиная с данного, в максимум.
Поставим задачу-построить алгоритм определения функций условного оптимального выигрыша    и условного оптимального управления    для всех шагов    Рассмотрим i-ыи шаг процесса управления. Пусть в результате i-1 предыдущих шагов система пришла в состояние    , и мы выбираем какое-то управление    на i-ом шаге. Если мы его применим, то, во-первых, получим на данном i-ом шаге какой-то выигрыш    Он зависит от состояния системы Q так и от управления :
      (1)
Кроме того, мы получим какой-то выигрыш на всех оставшихся шагах. На основании принципа оптимальности, будем считать, что он максимален. Чтобы найти этот выигрыш, мы должны знать состояние системы перед следующим, (i+1)-м шагом. Под влиянием управления       на i-ом шаге система из состояния Q   (в котором она была перед этим шагом) перейдет в какое-то новое состояние    Это новое состояние будет зависеть, опять-таки, от прежнего состояния Q и примененного управления
  (2)
Запишем выигрыш, который мы получим на всех шагах, начиная с i-го, если на i-ом шаге будет применено любое (возможно, не оптимальное) управление а на всех последующих (i+1)-го до N-го оптимальное управление.
Этот выигрыш будет равен выигрышу zi на данном i-ом шаге, плюс условный оптимальный выигрыш на всех последующих шагах, начиная с (i+1)-го, определяемый для нового состояния системы ;
  (3)
обозначим такой "полуоптимальный" выигрыш через    тогда учитывая (2) и (3),
  (4)
Теперь, в соответствии с принципом оптимальности, мы должны выбрать такое управление при котором величина (4) максимальна и достигает значения:
  (5)
То управление    при котором этот максимум в (5) достигается, и есть условное оптимальное управление на i-ом шаге, а сама величина (5)-условный оптимальный выигрыш (на всех шагах, начиная с i-го и до конца). В уравнении (5) функции    и    известны. Неизвестными остаются функции:

   и    ; из них первая выражается через вторую. Формула (5) представляет собой так называемое основное функциональное уравнение динамического программирования или уравнение Беллмана. Оно позволяет определить функцию Zi(Q) , если известна следующая за ней по порядку
Что касается функции (условный оптимальный выигрыш на последнем шаге), то она может быть определена очень просто.
Действительно, за последним шагом нет следующего, и нужно обратить в максимум выигрыш на этом шаге:
  (6)
Максимум в формуле (6) берется не по всем возможным управлениям XN на N-ом шаге, а только по тем, которые приводят в систему в заданную область т.е. по тем, для которых    Это всегда нужно иметь в виду при использовании формулы (6). То управление    при котором достигается максимум выигрыша, и есть условное оптимальное управление на последнем шаге.

Теперь построим всю цепочку условных оптимальных управлений. Зная можно по общей формуле (5), полагая в ней i+1=n , найти функцию и соответствующее оптимальное управление ; затем и и так далее , вплоть до последнего шага от конца т.е. первого шага, для которого будут найдены функции Z1(Q) и X1(Q) . Функция Z1(Q) есть условный оптимальный выигрыш за всю операцию, т.е. на всех шагах начина с первого и до последнего (если первый шаг начинается с определенного состояния Q1).
Таким образом предварительная оптимизация закончена-найдены условный оптимальный выигрыш и условное оптимальное управление для каждого шага.

Рассмотрим вторую стадию оптимизации-нахождение безусловного или окончательного оптимального управления

Начнем с первого шага.

Предположим, что исходное состояние Q1 нам полностью известно. Подставим это состояние Q1 в формулу для условного оптимального выигрыша Z1(Q). Получим:
  (7)
Одновременно найдем оптимальное управление на первом шаге    Далее, зная исходное состояние Q1 и управление X1 , можем найти состояние системы после первого шага:    Зная это состояние можно найти оптимальное управление на втором шаге    затем    и т. д. Таким образом, идя по цепочке
  (8)
мы определили одно за другим, все шаговые оптимальные управления операций в целом    а также конечное состояние системы    Это условие будет выполняться, т.к. мы выбираем управление на последнем шаге так, чтобы    Рассмотрим теперь случай, когда исходное состояние системы ограничено условием .   В этом случае нужно найти такое начальное состояние при котором условный минимальный выигрыш за все шаги максимален.
  (9)
То начальное состояние для которого этот максимум достигается и нужно взять в качестве исходного. Далее оптимальное управление строится в соответствии с выражением (8), заменяя Q1 на
  (8a)
При изложении материала мы использовали систему символических формул, которая непригодна для непосредственного вычисления. Однако с их помощью можно организовать процедуру динамического программирования в следующей последовательности:

Выбрать способ описания процесса, т.е. параметры характеризующие состояние системы, фазовое пространство и способ деления операции на шаги.
Записать выигрыш на i-ом шаге в зависимости от состояния системы Q перед этим шагом и управления Xi
Записать для i-го шага функцию, выражающую изменение состояния системы от Q к Q` под действием управления Q`
Записать основное функциональное уравнение
(5)
Найти условный оптимальный выигрыш последнего N-го шага при этом должно выполняться условие Одновременно определить условное оптимальное управление Xn(Q) на последнем шаге.
Зная Zn(Q) по уравнению (5) для конкретного вида функций Zi(Q,Xi) и найти последовательно Wn-1(Q),Wn-2(Q),:,W1(Q) и соответствующие им условные оптимальные уравнения
Если начальное состояние системы Q1 задано, найти оптимальный выигрыш Zmax=Z1(Q1) и безусловные оптимальные управления в последовательности, указанной выражением (8).
Если начальное состояние Q1 задано условием то для определения Zmax нужно использовать выражение (9). Определение безусловных оптимальных управлений провести по схеме (8а).

Отметим преимущества и недостатки метода динамического программирования. К числу положительных качеств можно отнести:

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

К недостаткам относятся:

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