---
title: "Динамическое программирование"
source: "https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5"
wiki: "systems-analysis.info/wiki"
article: "Динамическое_программирование"
language: "ru"
categories:
  - "Категория:Russian"
  - "Категория:Исследование операций"
revision_id: 231
wiki_created_at: 2026-09-06T22:05:48Z
wiki_modified_at: 2026-09-06T22:05:48Z
downloaded_at: 2026-09-07T22:18:29Z
---

# Динамическое программирование

**Динамическое программирование** (**ДП**; англ. *dynamic programming, DP*) — это метод решения сложных задач оптимизации, основанный на разбиении исходной задачи на последовательность более простых подзадач<sup>[\[1\]](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_note-bigenc-dp-1)[\[2\]](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_note-ru-wiki-dp-2)</sup>. Метод применяется к многошаговым процессам принятия решений, где оптимальное решение всей задачи может быть построено из оптимальных решений её подзадач.

Термин был введён американским математиком Ричардом Беллманом в 1950-х годах<sup>[\[3\]](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_note-rechetnikov-dp-3)</sup>. В этом контексте слово «программирование» используется в значении «планирование» или «составление оптимального плана действий», а не написание компьютерного кода<sup>[\[4\]](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_note-en-wiki-dp-4)</sup>.

## Ключевые свойства и теоремы

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

### Принцип оптимальности Беллмана

Центральным концептом метода является **принцип оптимальности Беллмана** (англ. *Bellman's principle of optimality*). Он гласит: какими бы ни были первоначальное состояние и первоначальное решение, последующие решения должны составлять оптимальную стратегию относительно состояния, полученного в результате первого решения<sup>[\[3\]](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_note-rechetnikov-dp-3)</sup>.

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

### Перекрывающиеся подзадачи

Задача обладает свойством **перекрывающихся подзадач** (англ. *overlapping subproblems*), если при её рекурсивном решении одни и те же подзадачи возникают многократно. ДП позволяет избежать повторных вычислений, сохраняя решения уже встреченных подзадач (этот приём называется мемоизацией или табуляцией), что значительно повышает эффективность по сравнению с наивным рекурсивным перебором.

## Уравнение Беллмана

Из принципа оптимальности вытекает основное рекуррентное соотношение метода — **уравнение Беллмана**<sup>[\[1\]](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_note-bigenc-dp-1)</sup>. Оно связывает «ценность» (оптимальный выигрыш или стоимость) текущего состояния с ценностями последующих состояний. В общем виде для детерминированного многошагового процесса с аддитивной целевой функцией оно имеет вид:

$$
V_{k - 1}(x) = \max\limits_{y \in U(x)}\{\varphi_{k}(x,y) + V_{k}(f_{k}(x,y))\}
$$

где:

- $k$ — номер шага (от $m$ до 1);
- $x$ — состояние системы на шаге $k - 1$;
- $y$ — управляемое решение, принимаемое на шаге $k$;
- $\varphi_{k}(x,y)$ — выигрыш (или стоимость) на k-м шаге;
- $f_{k}(x,y)$ — функция, задающая новое состояние системы;
- $V_{k}(s)$ — оптимальное значение целевой функции для подзадачи, начинающейся на шаге $k$ в состоянии $s$.

Уравнение решается последовательно, как правило, «с конца», двигаясь от последнего шага к первому.

## Примеры применения

- **Задача о кратчайшем пути в графе**: Эта задача обладает свойством оптимальной подструктуры, так как любой участок кратчайшего пути сам является кратчайшим. Алгоритмы Беллмана-Форда и Флойда-Уоршелла являются классическими примерами применения ДП для решения этой задачи<sup>[\[5\]](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_note-mit-amp-5)</sup>.
- **Задача о рюкзаке**: Задача об оптимальном заполнении рюкзака ограниченной ёмкости предметами с разной ценностью и весом. ДП позволяет решить эту задачу, рассматривая предметы последовательно и вычисляя на каждом шаге максимальную ценность для всех возможных значений оставшейся ёмкости.
- **Задача о распределении ресурсов**: Распределение ограниченного ресурса (например, инвестиций) между несколькими проектами для максимизации общего эффекта.

## Ограничения

Главным ограничением метода является **проклятие размерности** (англ. *curse of dimensionality*) — термин, введённый Беллманом для обозначения экспоненциального роста числа состояний и, как следствие, вычислительной сложности, при увеличении числа переменных, описывающих состояние системы<sup>[\[6\]](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_note-ru-wiki-curse-6)[\[7\]](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_note-utexas-ormm-7)</sup>. Это ограничивает практическое применение точного ДП для задач очень большой размерности.

## Связанные понятия

- [Исследование операций](https://systems-analysis.info/wiki/%D0%98%D1%81%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9 "Исследование операций")
- Теория оптимального управления
- Марковский процесс принятия решений (стохастическое обобщение)
- Уравнение Гамильтона — Якоби — Беллмана (аналог для непрерывного времени)

## Примечания

1.  <span id="cite_note-bigenc-dp-1">↑ <sup>[1,0](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_ref-bigenc-dp_1-0)</sup> <sup>[1,1](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_ref-bigenc-dp_1-1)</sup> "Динамическое программирование". *Большая российская энциклопедия*. <a href="https://bigenc.ru/c/dinamicheskoe-programmirovanie-00423a" class="external autonumber" rel="nofollow">[1]</a></span>
2.  <span id="cite_note-ru-wiki-dp-2">[↑](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_ref-ru-wiki-dp_2-0) "Динамическое программирование". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Динамическое_программирование" class="external autonumber" rel="nofollow">[2]</a></span>
3.  <span id="cite_note-rechetnikov-dp-3">↑ <sup>[3,0](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_ref-rechetnikov-dp_3-0)</sup> <sup>[3,1](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_ref-rechetnikov-dp_3-1)</sup> Решетников А. Н., Коченков А. В., Пиров Д. М., Рябоконь Д. А. (2011). *Динамическое программирование. Примеры применения*. Учебное пособие, ННГУ им. Лобачевского (ВМиК). <a href="https://itslearningakarmazyan.files.wordpress.com/2015/09/dynamic-programming.pdf" class="external autonumber" rel="nofollow">[3]</a></span>
4.  <span id="cite_note-en-wiki-dp-4">[↑](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_ref-en-wiki-dp_4-0) "Dynamic programming". *Wikipedia*. <a href="https://en.wikipedia.org/wiki/Dynamic_programming" class="external autonumber" rel="nofollow">[4]</a></span>
5.  <span id="cite_note-mit-amp-5">[↑](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_ref-mit-amp_5-0) Bradley S. P., Hax A. C., Magnanti T. L. (1977). *Applied Mathematical Programming*. Addison-Wesley. <a href="http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf" class="external autonumber" rel="nofollow">[5]</a></span>
6.  <span id="cite_note-ru-wiki-curse-6">[↑](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_ref-ru-wiki-curse_6-0) "Проклятие размерности". *Википедия*. <a href="https://ru.wikipedia.org/wiki/Проклятие_размерности" class="external autonumber" rel="nofollow">[6]</a></span>
7.  <span id="cite_note-utexas-ormm-7">[↑](https://systems-analysis.info/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#cite_ref-utexas-ormm_7-0) Jensen P. A. (2004). *Dynamic Programming – Models*. Operations Research Models and Methods, Univ. of Texas. <a href="https://utw11041.utweb.utexas.edu/ORMM/models/unit/dynamic/index.html" class="external autonumber" rel="nofollow">[7]</a></span>