Динами́ческое программи́рование, раздел оптимального управления, посвящённый теории и методам решения многошаговых задач. В задачах оптимального управления среди возможных управлений ищется то, при котором достигается экстремальное (наименьшее или наибольшее) значение т. н. целевой функции – некоторой числовой характеристики процесса. В динамическом программировании под многошаговостью понимают либо многоступенчатую структуру процесса, либо то, что управление разбивается на ряд последовательных этапов (шагов), соответствующих, как правило, различным моментам времени. Иногда многошаговость проистекает из существа процесса, но она может вводиться и искусственно для того, чтобы обеспечить возможность применения методов динамического программирования. Под программированием в динамическом программировании понимают принятие решений (планирование), а слово «динамическое» указывает на существенную роль времени и порядка выполнения операций. Методы динамического программирования являются составной частью методов, используемых в исследовании операций, и применяются в задачах оптимального планирования (например, в задачах об оптимальном распределении ресурсов, в теории управления запасами, в задачах замены оборудования) и при решении многих технических проблем (например, в задачах управления последовательными химическими процессами, в задачах оптимальной прокладки дорог).

Пусть процесс управления некоторой системой $X$ состоит из $m$ шагов (этапов); на $i$-м шаге управление $y_i$ переводит систему из состояния $x_{i–1}$, в котором она находилась после $(i-1)$-го шага, в новое состояние $x_i$. При этом задана функция $f_i(x, y)$, и новое состояние определяется по этой функции значениями $x_{i–1}$, $y_i$ так, что $x_i=f_i(x_{i–1}, y_i), i=1, 2, ..., m$. Таким образом, управления $y_1, y_2, ..., y_m$ переводят систему из начального состояния $x_0∈X_0$ в конечное состояние $x_m∈X_m$, где $X_0$ и $X_m$ – совокупности допустимых начальных и конечных состояний системы $X$.

Одна из возможных постановок задач динамического программирования состоит в следующем. При заданном начальном состоянии $x_0$ требуется выбрать управления $y_1, y_2, ..., y_m$ таким образом, чтобы система $X$ перешла в допустимое конечное состояние и при этом заданная целевая функция $F(x_0, y_1, x_1, ..., y_m, x_m)$ достигла максимального значения $F^*$, т. е. $$F^*=\max F(x_0, y_1, x_1, ..., y_m, x_m),$$где максимум берётся по всем управлениям $y_1, ..., y_m$, для которых $x_m∈X_m$.

В динамическом программировании обычно предполагается, что целевая функция является аддитивной. В рассмотренном примере это означает, что $$F=\sum_{i=1}^m\varphi_i(x_{i-1},y_i).$$

Кроме того, в динамическом программировании предполагается, что в задаче отсутствует последействие: решения (управления), принимаемые на шаге $i$, оказывают влияние только на состояние $x_i$ системы в момент $i$. Оба упомянутых ограничительных условия можно ослабить, но только за счёт существенного усложнения метода.

В основе динамического программирования лежит принцип оптимальности, сформулированный Р. Беллманом. Пусть выбраны некоторые управления $y_1, y_2, ..., y_k$ и тем самым траектория $x_0, x_1, ..., x_k$ состояний и требуется завершить процесс, т. е. выбрать $y_{k+1}, ..., y_m$ (а значит, и $x_{k+1}, ..., x_m$). Если завершающая часть процесса не будет оптимальной в смысле достижения максимума функции $$F_k=\sum_{i=k+1}^m\varphi_i(x_{i-1},y_i),$$процесс не будет оптимальным. Пользуясь принципом оптимальности Беллмана, можно получить основное функциональное соотношение динамического программирования , которое состоит в следующем. Пусть $$ω_m(x)=0, \, \, \, ω_{k-1}(x)=max(\varphi_k(x, y)+ω_k(f_k(x, y))),\ k=1, 2, ..., m$$, где максимум берётся по всем управлениям $y$, допустимым на шаге $k$. Соотношение, определяющее зависимость $ω_{k–1}$ от $ω_k$, называется уравнением Беллмана. Смысл этих функций достаточно ясен: если система на шаге $k-1$ оказалась в состоянии $x$, то $ω_{k–1}(x)$ есть максимально возможное значение функции $F_k$. Одновременно с построением функций $ω_{k–1}(x)$ находятся условные оптимальные управления $y_k(x)$ на каждом шаге, т. е. значения оптимального управления при всевозможных предположениях о состоянии $x$ системы на шаге $k-1$. Окончательно оптимальные управления находятся последовательным вычислением величин $ω_0(x_0)=F^*, y_1, x_1, y_2, ..., y_m, x_m$.

С помощью динамического программирования решается не одна конкретная задача при определённом $x_0$, а сразу все подобные однотипные задачи при любом начальном состоянии. Численная реализация динамического программирования довольно сложна, т. к. требует запоминания большого количества информации, поэтому динамическое программирование целесообразно применять в тех случаях, когда необходимо многократно решать типовые задачи (например, определение оптимального режима полёта самолёта при меняющихся погодных условиях). Обычно задача динамического программирования формулируется для дискретных процессов, но в ряде случаев динамическое программирование применяется и для решения динамических задач с непрерывными параметрами.

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

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