Динамическое программирование — это вычислительный метод для решения задач определенной структуры. Возникло и сформировалось в 1950-1953 гг. благодаря работам Р. Беллмана над динамическими задачами управления запасами. В упрощенной формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму.

Основные необходимые свойства задач, к которым возможно применить этот принцип:

1. Задача должна допускать интерпретацию как n-шаговый процесс принятия решений.
2. Задача должна быть определена для любого числа шагов и иметь структуру, не зависящую от их числа.
3. При рассмотрении k-шаговой задачи должно быть задано некоторое множество параметров, описывающих состояние системы, от которых зависят оптимальные значения переменных. Причем это множество не должно изменяться при увеличении числа шагов.
4. Выбор решения (управления) на k-м шаге не должен оказывать влияния на предыдущие решения, кроме необходимого пересчета переменных.

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

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

Постановку задачи динамического программирования рассмотрим на примере инвестирования, связанного с распределением средств между предприятиями. В результате управления инвестициями система последовательно переводится из начального состояния S₀В конечное S_n. Предположим, что управление можно разбить на n шагов и решение принимается последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. На каждом шаге необходимо определить два типа переменных - переменную состояния системы S_k переменную управления x_k . Переменная S_k определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге. В зависимости от состояния S на этом шаге можно применить некоторые управления, которые характеризуются переменной xk которые удовлетворяют определенным ограничениям и называются допустимыми. Допустим.  = (x₁ , x₂ , ..., x_k , ..., x_n ) - управление, переводящее систему на состояния S₀ в состояние S_n , a S_k - есть состояние системы на k-м шаге управления. Тогда последовательность состояний системы можно представить в виде графа, представленного на рис. 2.11.

рис. 2.11

Применение управляющего воздействия x_k  на каждом шаге переводит систему в новое состояние S¹  (S, x_k) и приносит некоторый результат W_k (S, x_k). Для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оптимальное управление x*_k , такое, чтобы результат, который достигается за шаги с k-го по последний n-й, оказался бы оптимальным. Числовая характеристика этого результата называется функцией Беллмана F_k (S) и зависит от номера шага k и состояния системы S. Задача динамического программирования формулируется следующим образом: требуется определить такое управление , переводящее систему из начального состояния S₀ в конечное состояние S_n , при котором целевая функция принимает наибольшее (наименьшее) значение F(S₀ ,) => extr.

Рассмотрим более подробно особенности математической модели динамического программирования:

1. задача оптимизации формулируется как конечный многошаговый процесс управления;
2. целевая функция (выигрыш) является аддитивной и равна сумме целевых функций каждого шага:
   
3. выбор управления x_k на каждом шаге зависит только от состояния системы k этому шагу S_k-1, и не влияет на предшествующие шаги (нет обратной связи);
4. состояние системы S_k после каждого шага управления зависит только от предшествующего состояния системы S_k-1 и этого управляющего воздействия x_h (отсутствие последействия) и может быть записано в виде уравнения состояния: S_k = f_k(S_k-1 , x_k), k = 1, n;
5. на каждом шаге управление x_k зависит от конечного числа управляющих переменных, а состояние системы зависит S_k – от конечного числа параметров;
6. оптимальное управление представляет собой вектор , определяемый последовательностью оптимальных пошаговых управлений:  = (x*₁ , x*₂ , ..., x*_k , ..., x*_n ), число которых и определяет количество шагов задачи.

Принцип оптимальности и математическое описание динамического процесса управления. 
В основе метода ДП лежит принцип оптимальности, впервые сформулированный в 1953 г. американским математиком Р.Э.Беллманом: каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. При решении задачи на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максимальный выигрыш именно на данном шаге. Однако, например, при покупке новой техники взамен устаревшей на ее приобретение затрачиваются определенные средства, поэтому доход от ее эксплуатации в начале может быть небольшой, а в следующие годы новая техника будет приносить больший доход. И наоборот, если принято решение оставить старую технику для получения дохода в текущем году, то в дальнейшем это приведет к значительным убыткам. Этот пример демонстрирует следующий факт: в многошаговых процессах управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на весь процесс. Кроме того, при выборе управления на данном шаге следует учитывать возможные варианты состояния предыдущего шага. Например, при определении количества средств, вкладываемых в предприятие в i-м году, необходимо знать, сколько средств осталось в наличия к атому году и какой доход получен в предыдущем (i - 1)-м году. Таким образом, при выборе шагового управления необходимо учитывать следующие требования:

1. возможные исходы предыдущего шага S_k-1 ;
2. влияние управления x_k на все оставшиеся до конца процесса шаги (n-k).

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

Условная оптимизация

На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге оптимальное управление - х*_n определяется функцией Беллмана: F(S) = max {W_n (S, x_n )}, в соответствии с которой максимум выбирается из всех возможных значений x_n , причем x_n € X. 
Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге. В общем виде это уравнение имеет вид F_n(S) = max {W_n (S, x_n ) + F_k+1(Sⁿ(S, x_k )} x_k € X. 
Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация

После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, осуществляется второй этап решения задачи, называемый безусловной оптимизацией. Пользуясь тем, что на первом шаге (k = 1) состояние системы известно - это ее начальное состояние S₀ , можно найти оптимальный результат за все n шагов и оптимальное управление на первом шаге x₁, которое этот результат доставляет. После применения этого управления система перейдет в другое состояниеS¹(S, x*₁ ), зная которое, можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге x*₂ , и так далее до последнего n-го шага. Вычислительную схему динамического программирования можно строить на сетевых моделях, а также по алгоритмам прямой прогонки (от начала) и обратной прогонки (от конца к началу). Рассмотрим примеры решения различных по своей природе задач, содержание которых требует выбора переменных состояния и управления.