Практикум по динамическому программированию

Московский государственный технический университет 
имени Н. Э. Баумана 
 
 
 
 
Н. П. Деменков 
 
 
 
Практикум по динамическому  
программированию 
 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1 

Д30 
УДК 681.3.06(075.8) 
ББК 22.18 
 Д30 
 
Издание доступно в электронном виде на портале ebooks.bmstu.ru  
по адресу: http://ebooks.bmstu.ru/catalog/200/book1266.html 
 
Факультет «Информатика и системы управления» 
Кафедра «Системы автоматического управления» 
 
Рекомендовано Редакционно-издательским советом   
МГТУ им. Н.Э. Баумана в качестве учебного пособия 
 
Рецензенты:  
канд. техн. наук, доцент Е. Д. Панин,  
д-р техн. наук, профессор В. В. Сюзев 
 
 
Деменков, Н. П.  
 
Практикум по динамическому программированию : учебное 
пособие / Н. П. Деменков. — Москва : Издательство МГТУ  
им. Н. Э. Баумана, 2015. — 95, [5] с. : ил. 
ISBN 978-5-7038-4213-3 
Изложены примеры решения задач оптимального управления на основе динамического программирования Р. Беллмана. 
Для студентов МГТУ им. Н. Э. Баумана, изучающих дисциплины 
«Оптимальное управление детерминированными процессами», «Управление в технических системах»,  «Алгоритмическое и программное обеспечение систем управления», «Основы автоматики и системы автоматического управления». Настоящее издание будет полезным также для  
научных работников, инженеров, аспирантов и студентов старших курсов 
технических университетов. 
 
УДК 681.3.06(075.8) 
ББК 22.18 
 
 
 
 
 
 
© МГТУ им. Н. Э. Баумана, 2015 
© Оформление. Издательство 
ISBN 978-5-7038-4213-3   
  
   МГТУ им. Н. Э. Баумана, 2015 
2 

 
Предисловие 
Динамическое программирование — один из наиболее мощных методов оптимизации. С задачами принятия рациональных 
решений, выбора наилучших вариантов, оптимального управления 
имеют дело специалисты разного профиля. Среди методов оптимизации динамическое программирование занимает особое положение. Этот метод исключительно привлекателен благодаря  
простоте и ясности своего основного принципа — принципа оптимальности. Сфера приложения принципа оптимальности чрезвычайно широка, круг задач, к которым он может быть применен, до 
настоящего времени еще полностью не очерчен. Динамическое 
программирование с самого начала выступает как средство практического решения задач оптимизации. 
Динамическое программирование, наряду с принципом максимума, является основным математическим методом, с помощью 
которого определяется оптимальное управление. В отличие от 
принципа максимума, который формулируется таким образом, что 
оказывается ориентированным прежде всего на определение оптимального управления в виде оптимальной программы, динамическое программирование позволяет определять оптимальное 
управление только в форме синтезирующей функции. 
Цель настоящего учебного пособия — ознакомить студентов  
с вычислительными аспектами решения задач оптимального 
управления на основе современных подходов и программных 
средств. В пособии изложены вычислительные проблемы решения 
задач оптимального управления методом динамического программирования и показаны пути их решения. 
Пособие рассчитано на студентов МГТУ им. Н.Э. Баумана, изучающих дисциплины «Оптимальное управление детерминированными процессами», «Управление в технических системах», «Алгоритмическое и программное обеспечение систем управления», 
«Основы автоматики и системы автоматического управления». 
Настоящее издание будет полезным также для научных работников, инженеров, аспирантов и студентов старших курсов технических университетов. 
 
3 

 
Введение 
Динамическое программирование в теории управления и 
теории вычислительных систем — метод решения сложных задач путем разбиения их на более простые. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше 
исходной.  
Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико. 
Словосочетание «динамическое программирование» впервые 
было использовано в 1940-е годы Р. Беллманом для описания 
процесса нахождения решения задачи, в которой ответ на одну 
задачу можно получить только после решения предшествующей. 
Первоначально эта область знаний была определена как системный анализ и инжиниринг и признана международной некоммерческой ассоциацией специалистов Institute of Electrical and 
Electronics Engineers (IEEE). Вклад Р. Беллмана в динамическое 
программирование был увековечен в названии «уравнение Беллмана», которое является основным результатом теории динамического программирования. Тем самым Беллман переформулировал оптимизационную задачу в рекурсивной форме. 
Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи.  
В общем случае можно решить задачу, в которой присутствует 
оптимальная подструктура, выполняя следующие три шага: 
1) разбиение задачи на подзадачи меньшего размера; 
2) нахождение оптимального решения подзадач рекурсивно, с 
таким же трехшаговым алгоритмом; 
3) использование полученного решения подзадач для конструирования решения исходной задачи. 
4 

Подзадачи решают делением их на подзадачи еще меньшего 
размера и т. д., пока не приходят к тривиальному случаю задачи, 
решаемой за заданное время.  
Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, используемые для решения некоторого 
количества задач (не одной) большего размера (т. е. несколько раз 
выполняется одно и то же). Ярким примером является вычисление 
последовательности Фибоначчи. 
Чи́сла Фибона́ччи — элементы числовой последовательности 
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 
2584, 4181, 6765, 10946, …, в которой каждое последующее число 
равно сумме двух предыдущих. Последовательность названа по 
имени средневекового математика Леонардо Пизанского (известного как Фибоначчи). Иногда число 0 не рассматривают как член 
последовательности. 
Более формально последовательность чисел Фибоначчи {
}
n
F
 
задается линейным рекуррентным соотношением 
 
0
0,
F =
 
1
1,
F =
 
n
F =
1
n
F −+
2
n
F −, n ≥ 2, n ∈ Z. 
Даже при вычисления всего двух чисел Фибоначчи — 
3
F =
2
1
F
F
+
 и  
4
F =
3
2
F
F
+
 — число F2 будет определено дважды. Если продолжать дальше и вычислить число F5, то F2 будет получено еще  
2 раза, так как для вычисления F5 нужны опять числа F3 и F4.  
Таким образом, при простом рекурсивном подходе затрачивается время на вычисление решения задач, которые уже были 
решены. 
Чтобы избежать такого хода событий, следует сохранять решения уже решенных подзадач. Когда снова потребуется решение 
подзадачи, ее не вычисляют заново, а вызывают решение из памяти ЭВМ. Этот подход называется кешированием.  
Таким образом, динамическое программирование использует 
следующие свойства задачи: 
• перекрытие подзадачи; 
• оптимальность подструктуры; 
• возможность запоминания решения часто встречающихся 
подзадач. 
Динамическое программирование обычно придерживается 
двух подходов к решению задач: 
5 

1) нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем 
комбинируются для решения исходной задачи; используется запоминание для решений часто встречающихся подзадач; 
2) восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной, вычисляются заранее и затем используются для построения решения 
исходной задачи. Этот подход лучше нисходящего программирования в смысле размера необходимого стека и числа вызовов 
функций, но иногда бывает нелегко заранее выяснить, решение 
каких подзадач потребуется в дальнейшем. 
Языки программирования могут запоминать результат вызова 
функции с определенным набором аргументов (мемоизация), чтобы 
ускорить вычисление по имени. Мемоизация (запоминание, от англ. 
memoization в программировании) — кеширование результатов выполнения функций, чтобы предотвратить повторные вычисления и 
вызовы функций. Эта специализированная оптимизационная методика позволяет увеличить скорость выполнения компьютерных программ. Вместо повторяющегося вызова функции сразу подставляется 
результат вычисления такого же выражения, взятый из специального 
кеша с результатами. В некоторых языках такая возможность встроена (например, в языках Scheme, Common Lisp, Perl), а в других требует дополнительных расширений (например, в C++). 
Различают сериальное динамическое программирование, включенное во все учебники по исследованию операций, и несериальное 
динамическое программирование, которое в настоящее время слабо 
известно, хотя было открыто в 1960-е годы. 
Обычное динамическое программирование является частным 
случаем несериального динамического программирования, когда 
граф взаимосвязей переменных — просто путь. Несериальное динамическое программирование, являясь естественным и общим 
методом для учета структуры задачи оптимизации, рассматривает 
множество ограничений и/или целевую функцию как рекурсивно 
вычислимую функцию. Это позволяет находить решение поэтапно, используя информацию, полученную на предыдущих этапах, 
причем эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно 
разрежен, то объем вычислений на каждом этапе может сохраняться в разумных пределах. 
6 

Одно из основных свойств задач, решаемых с помощью динамического программирования, — аддитивность. 
Динамическое программирование наряду с принципом максимума является основным математическим методом, с помощью 
которого определяется оптимальное управление. В отличие от 
принципа максимума, который формулируется таким образом, что 
оказывается ориентированным прежде всего на нахождение оптимального управления в виде оптимальной программы, динамическое программирование позволяет определять оптимальное управление только в форме синтезирующей функции. 
Динамическое программирование хорошо обосновано для дискретных процессов, но не всегда применимо для непрерывных. 
Это связано с тем, что при выводе функционального уравнения 
Беллмана приходится делать предположение, непосредственная 
проверка которого по уравнениям движения и функционалу невозможна. И только после решения уравнения Беллмана можно 
проверить, выполняется сделанное предположение или нет. Функциональное уравнение Беллмана для непрерывных процессов 
представляет собой дифференциальное уравнение в частных производных. Это уравнение обычно имеет весьма сложный вид, и 
численное его решение зачастую весьма затруднительно. 
Если иметь в виду не только задачи оптимального управления, 
необходимо отметить, что динамическое программирование обладает большой универсальностью. Его можно использовать для решения широкого класса задач оптимизации. 
 
 
 
7 

 
Глава 1. ПРОЦЕДУРЫ ДИНАМИЧЕСКОГО  
ПРОГРАММИРОВАНИЯ ДЛЯ ДИСКРЕТНЫХ СИСТЕМ 
1.1. Классические задачи  
динамического программирования 
Классическими для динамического программирования являются: 
• задача о наибольшей общей подпоследовательности: даны 
две последовательности, требуется найти самую длинную общую 
подпоследовательность; 
• задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность; 
• задача о редакционном расстоянии (расстояние Левенштейна): даны две строки, требуется найти минимальное количество 
стираний, замен и добавлений символов, преобразующих одну 
строку в другую; 
• задача о вычислении чисел Фибоначчи; 
• задача о порядке перемножения матриц: даны матрицы A1, …, 
An, требуется минимизировать количество скалярных операций для 
их перемножения; 
• задача о выборе траектории; 
• задача последовательного принятия решения; 
• задача об использовании рабочей силы; 
• задача управления запасами; 
• задача о рюкзаке (ранце): из неограниченного множества 
предметов со свойствами «стоимость» и «вес» («масса») требуется 
отобрать некое число предметов таким образом, чтобы получить 
максимальную суммарную стоимость при ограниченном суммарном весе (массе); 
• алгоритм Флойда — Уоршелла: найти кратчайшие расстояния 
между всеми вершинами взвешенного ориентированного графа; 
• алгоритм Беллмана — Форда: найти кратчайший путь во 
взвешенном графе между двумя заданными вершинами; 
8 

• максимальное независимое множество вершин в дереве: дано 
дерево, найти максимальное множество вершин, из которых никакие две не связаны ребром. 
1.2. Принцип оптимальности. Уравнение Беллмана 
Нахождение оптимального управления в динамических системах во многих случаях можно облегчить, если процесс управления 
удается разбить естественным или искусственным путем на отдельные шаги. 
Метод динамического программирования состоит в том, что 
оптимальное управление строится пошагово. На каждом шаге оптимизируется управление только этого шага. Вместе с тем на каждом шаге управление выбирается с учетом последствий, так как 
управление, оптимизирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса. Управление на каждом шаге должно быть оптимальным с 
точки зрения процесса в целом. 
Согласно принципу оптимальности, каким бы ни было начальное 
состояние системы перед очередным шагом, управление выбирается 
так, чтобы выигрыш на данном шаге и оптимальный выигрыш на 
всех последующих шагах были максимальными. 
Так, если система в начале n-го шага находится в состоянии 
1
n
x − и выбирается произвольное управление 
,
n
u
 то система придет 
в новое состояние 
n
x =
1
(
,
)
n
n
n
T
x
u
−
= x′  и последующие управления 
1, ...,
n
k
u
u
+
 должны выбираться оптимальными относительно состояния 
.
n
x  Последнее означает, что при этих управлениях максимизируется величина 
1
1
(
,
),
k
i
i
i
i n
L x
u
−
= +
∑
 т. е. показатель эффективности на последующих до конца процесса шагах 
1, ..., .
n
k
+
 
Обозначим 
n
J =
1
(
,
).
k
i
i
i
i n
L x
u
−
=
∑
 
Выбрав оптимальное управление 
*
n
U =
*
*
(
,...,
)
n
k
u
u
 на оставшихся 
шагах 
1,
k
n
−
+
 получим величину 
*
max
,
n
n
J
J
=
 которая зависит 
только от 
1,
n
x −
 т. е. 
*
1
(
)
n
n
J
x −
=
max
n
n
U
J . 
9 

Назовем величину 
*
1
(
)
n
n
J
x−
 условным максимумом. Если мы 
теперь выберем на n-м шаге некоторое произвольное управление 
n
u , то система придет в состояние 
n
x  (рис. 1.1). 
 
 
 
Рис. 1.1 
 
Согласно принципу оптимальности, необходимо выбирать 
управление 
n
u  так, чтобы оно в совокупности с оптимальным 
управлением на последующих шагах (начиная с (
1)-го)
n +
 приводило бы к общему показателю эффективности на шагах
1,
k
n
−
+
 
начиная с n-го и до конца. Это положение можно записать в аналитической форме: 
 
*
1
(
)
k
k
J
x −
=
1
max
(
,
);
k
k
k
k
u
L
x
u
−
 
*
1
1
max
(
,
)
(
),
L
x
u
J
x
−
+
+
 n = k − 1, k − 2, …, 1. (1.1) 
 
*
1
(
)
n
n
J
x −
=
n
n
n
n
n
k
u
Уравнение (1.1) получило название основного функционального 
уравнения динамического программирования или основного 
рекуррентного уравнения Беллмана. 
Из уравнения (1.1) может быть получена функция 
*
1
2
(
),
k
k
J
x
−
−
 
если известна функция 
*
1
(
).
k
k
J
x −
 Аналогично можно получить 
*
2
3
(
),
k
k
J
x
−
−
 если найдена 
*
1
2
(
)
k
k
J
x
−
−
 и т. д., пока не будет вычислена величина 
*
1
0
(
),
J
x
 представляющая, по определению, максимальное значение показателя эффективности процесса в целом: 
*
1
0
0
(
)
max (
,
).
 

U
J
x
J x U
=
 
10