---
title: "Динамично програмиране"
source: "https://systems-analysis.info/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%D0%B5"
wiki: "systems-analysis.info/int"
article: "Динамично_програмиране"
language: "bg"
categories:
  - "Category:Bulgarian"
  - "Category:Operations research"
revision_id: 8655
wiki_created_at: 2026-09-07T01:20:42Z
wiki_modified_at: 2026-09-07T01:20:42Z
downloaded_at: 2026-09-07T23:26:39Z
---

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

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

Терминът е въведен от американския математик Ричард Белман през 50-те години на XX век<sup>[\[3\]](https://systems-analysis.info/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%D0%B5#cite_note-rechetnikov-dp-3)</sup>. В този контекст думата „програмиране" се използва в смисъл на „планиране" или „съставяне на оптимален план за действие", а не писане на компютърен код<sup>[\[4\]](https://systems-analysis.info/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%D0%B5#cite_note-en-wiki-dp-4)</sup>.

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

Приложимостта на динамичното програмиране към дадена задача се определя от наличието на две фундаментални свойства.

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

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

С други думи, всяка част от оптималната траектория сама по себе си е оптимална. Това свойство позволява да се раздели общата задача на последователност от по-прости подзадачи и да се решават рекурсивно.

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

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

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

От принципа на оптималността произтича основното рекурентно съотношение на метода — **уравнението на Белман**<sup>[\[1\]](https://systems-analysis.info/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%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/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%D0%B5#cite_note-mit-amp-5)</sup>.
- **Задача за раницата**: Задача за оптималното запълване на раница с ограничен капацитет с предмети с различна стойност и тегло. ДП позволява да се реши тази задача, като предметите се разглеждат последователно и на всяка стъпка се изчислява максималната стойност за всички възможни стойности на оставащия капацитет.
- **Задача за разпределение на ресурси**: Разпределение на ограничен ресурс (например инвестиции) между няколко проекта с цел максимизиране на общия ефект.

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

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

## Свързани понятия

- Изследване на операциите
- Теория на оптималното управление
- Марковски процес на вземане на решения (стохастично обобщение)
- Уравнение на Хамилтон — Якоби — Белман (аналог за непрекъснато време)

## Бележки

1.  <span id="cite_note-bigenc-dp-1">↑ <sup>[1.0](https://systems-analysis.info/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%D0%B5#cite_ref-bigenc-dp_1-0)</sup> <sup>[1.1](https://systems-analysis.info/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%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/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%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/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%D0%B5#cite_ref-rechetnikov-dp_3-0)</sup> <sup>[3.1](https://systems-analysis.info/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%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/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%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/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%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/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%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/int/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%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>