Рассмотрим класс задач исследования операций, в которых процесс протекания операции является многошаговым, т.е. развернут во времени. Тат как этот класс задач описывает явно динамику процесса, то они получили название задач динамического программирования.

До сих пор мы рассматривали задачи исследования операций в статической постановке. В таких задачах имелись две группы переменных, соответствующих стратегиям (планам) и неконтролируемым факторам, а в задачах линейного и нелинейного программирования при отсутствии неконтролируемых факторов – только первая группа переменных. В динамических задачах для описания состояний процесса удобно ввести еще одну группу переменных, называемых фазовыми переменными.

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

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

Процесс протекания операции обычно описывается уравнением вида:

.                      (4.1)

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

При фиксированном начальном состоянии  последовательность управляющих векторов  определяет однозначно из уравнения (4.1) последовательность фазовых состояний , которая называется траекторией процесса.

Задача состоит в выборе такого управления , которое вместе с определяемой им траекторией доставляет максимум целевой функции:

.               (4.2)

На управление накладываются некоторые ограничения, которые обычно записывают в виде:

,                      (4.3)

где множества  могут задаваться ограничениями типа равенств и неравенств.

Существуют различные постановки задач динамического программирования, отличающиеся теми или иными деталями, но в них всегда присутствует уравнение хода процесса вида (4.1), целевая функция вида (4.2) и ограничения на управления вида (4.3). В качестве других ограничений чаще всего выступает условие достижения в конце процесса заданного множества:

                     (4.4)

или фазовые ограничения на всю траекторию

.                  (4.5)

Условие (4.4) или (4.5) накладывает дополнительные ограничения на допустимое управление. Исключим пока эти условия и рассмотрим простейшую постановку вида (4.1) – (4.3).

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

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

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

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

,

а с учетом уравнения (4.1)

.                  (4.6)

Условно оптимальное управление  получается как решение задачи максимизации уравнения (4.6) при каждом фиксированном .

Далее на -м шаге в состоянии  условно оптимальный результат:

или с учетом уравнения (4.1)

.             (4.7)

Из решения задачи максимизации уравнения (4.7) находим условно оптимальное управление .

Продолжая процесс построения рекуррентных соотношений, имеем для произвольного -го шага:

 (4.8)

Из решения задач (4.8) получаем цепочку условно оптимальных результатов:

и условно оптимальных управлений

.

По условию задачи  фиксировано и известно, поэтому значение динамической задачи равно , оптимальное управление на первом шаге:

,

подставляя значение  в уравнение (4.1), получаем следующее состояние  и оптимальное управление на втором шаге:

 и т.д.

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

Из принципа оптимальности можно непосредственно получить рекуррентные соотношения вида (4.8). Для этого наряду с исходной задачей рассмотрим класс динамических задач, которые описываются теми же уравнениями (4.1), целевыми функциями (4.2) и ограничениями на управление (4.3), но в которых может измениться начальный момент времени и начальное состояние (конечный момент времени фиксирован).

Таким образом, произвольная задача этого класса состоит в том, чтобы, начиная с -го шага и состояния , выбрать такое управление на последующих шагах вплоть до -го, которое с учетом уравнений (4.1) и ограничений (4.3) для  доставляет максимум критерию:

.

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

Таким образом, имеем уравнение:

                   (4.9)

Уравнение (4.9), называемое уравнением Беллмана, играет фундаментальную роль в теории динамического программирования. С помощью этого уравнения можно определить функцию , называемую функцией Беллмана, на всех шагах, если известно ее значение в начальный или конечный момент. Значение этой функции в конечный момент определить несложно. Действительно, так как операция содержит  шагов, то -й шаг уже не совершается, поэтому для задачи рассматриваемого класса с начальным моментом  и начальным состоянием  максимальное значение равно , т.е.

.

Нетрудно заметить, что если ввести , положив его равным , то соотношения (4.6) – (4.8) определяют функцию Беллмана, т.е.

.

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

Вернемся к условию (4.4). Для управления полетом ракеты требование выполнения условия (4.4) означает достижение в конечный момент заданного пункта, а для управления процессом производства – достижение определенного уровня выпуска продукции.

Условие (4.4) выделяет из всех возможных траекторий некоторые допустимые, а так как траектория складывается в результате выбора определенных управлений, то это условие, в конечном счете, накладывает ограничения и на допустимые управления. Функцию Беллмана на последнем шаге строят лишь на множестве , т.е. полагают:

      для      .

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

.                (4.10)

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

рассматриваются только такие состояния , из которых за один шаг можно попасть в множество  и т.д.

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