Тема 8. Модели динамического программирования
Динамическое программирование связано с возможностью представления процесса управления в виде цепочки последовательных действий или шагов, развернутых во времени и ведущих к цели. Таким образом, процесс управления можно разделять на части и представить его в виде динамической последовательности и интерпретировать в виде пошаговой программы, развернутой во времени. Это позволяет спланировать программу будущих действий. Поскольку вариантов возможных планов — программ множество, то, необходимо из них выбрать лучший, оптимальный по какому-либо критерию в соответствии с поставленной целью.
1. Предмет динамического программирования
Динамическое программирование представляет собой математический аппарат, который подходит к решению некоторого класса задач путем их разложения на части, небольшие и менее сложные задачи. При этом отличительной особенностью является решение задач по этапам, через фиксированные интервалы, промежутки времени, что и определило появление термина динамическое программирование. Следует заметить, что методы динамического программирования успешно применяются и при решении задач, в которых фактор времени не учитывается. В целом математический аппарат можно представить как пошаговое или поэтапное программирование. Решение задач методами динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения.
Из этого следует, что планирование каждого шага должно проводиться с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию.
Таким образом, динамическое программирование в широком смысле представляет собой оптимальное управление процессом, посредством изменения управляемых параметров на каждом, и, следовательно, воздействуя на ход процесса, изменяя на каждом шаге состояние системы.
В целом динамическое программирование представляет собой стройную теорию для восприятия и достаточно простую для‚ применения в коммерческой деятельности при решении как линейных, так и нелинейных задач.
Динамическое программирование (ДП) является одним из разделов оптимального программирования. Для него характерны специфические методы и приемы, применительные к операциям, в которых процесс принятия решения разбит на этапы (шаги). Методами ДП решаются вариантные оптимизационные задачи с заданными критериями оптимальности, с определенными связями между переменными и целевой функцией, выраженными системой уравнений или неравенств. При этом, как и в задачах, решаемых методами линейного программирования, ограничения могут быть даны в виде равенств или неравенств. Однако если в задачах линейного программирования зависимости между критериальной функцией и переменными обязательно линейны, то в задачах ДП эти зависимости могут иметь еще и нелинейный характер. ДП можно использовать как для решения связанных с динамикой процесса или системы, так и для статических задач, связанных, например, с распределением ресурсов. Это значительно расширяет область применения ДП для решения задач управления. А возможность упрощения процесса, которая достигается за счет ограничения области и количества исследуемых при переходе к очередному этапу вариантов увеличивает достоинства этого комплекса методов.
Вместе с тем ДП свойственны и недостатки. Прежде всего в нем нет единого универсального метода решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации. Последнее достигается с помощью методов анализа вариантов и переработки списка состояний. Для процессов с непрерывным временем ДП рассматривается как предельный вариант дискретной схемы решения. Получаемые при этом результаты практически совпадают с теми, которые получаются методами максимума Л. С. Понтрягина или Гамильтона — Якоби — Беллмана. ДП применяется для решения задач, в которых поиск оптимума возможен при поэтапном подходе, например, распределение дефицитных капитальных вложений между новыми направлениями их использования; разработка правил управления спросом или запасами, устанавливающими момент пополнения запаса и размер пополняющего заказа; разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; составления календарных планов текущего и капитального ремонтов оборудования и его замены; поиск кратчайших расстояний на транспортной сети, формирование последовательности развития коммерческой операции и т.д.
1 Динамическое программирование
Динамическое программирование – метод оптимизации, приспособленный к операциям, в которых процесс принятия решений может быть разбит на отдельные этапы (шаги). Такие операции называют многошаговыми.
В основе метода динамического программирования лежит принцип оптимальности, сформулированный Беллманом. Этот принцип и идея включения конкретной задачи оптимизации в семейство аналогичных многошаговых задач приводят к рекуррентным соотношениям – функциональным уравнениям – относительно оптимального значения целевой функции. Их решение позволяет последовательно получить оптимальное управление для исходной задачи оптимизации.
Дадим общее описание модели динамического программирования.
Рассматривается управляемая система, которая под влиянием управления переходит из начального состояния 
в конечное состояние
. Предположим, что процесс управления системой можно разбить на n шагов. Пусть
,
,…,
— состояния системы после первого, второго,…, n-го шага. Схематически это показано на рис. 1.
Состояние 
системы после k-го шага (k=1,2,…,n) характеризуется параметрами
, которые называют фазовыми координатами. Состояние
можно изобразить точкой s-мерного пространства, называемого фазовым пространством. Последовательное преобразование системы (по шагам) достигается с помощью некоторых мероприятий
, которые составляют управление системой U=
,
где 
— управление на k-м шаге, переводящее систему из состояния
в состояние
(рис.1). Управление
на k-м шаге заключается в выборе значений определенных управляющих переменных
.
Предполагаем впредь, что состояние системы в конце k-го шага зависит только от предшествующего состояния системы 
и управления
на данном шаге (рис.1). Такое свойство получило название отсутствия последствия. Обозначим эту зависимость в виде
(1.1)
Равенства (1.1) получили название уравнений состояний. Функции полагаем заданными.
Варьируя управления U, получим различную «эффективность» процесса, которую будем оценивать количественно целевой функцией Z, зависящей от начального состояния системы и от выбранного управления U:
(1.2)
Показатель эффективности k-го шага процесса управления, который зависит от состояния 
вначале этого шага и управления
, выбранного на этом шаге, обозначим через
(рис. 1). В рассматриваемой задаче пошаговой оптимизации целевая функция (1.2) должна быть аддитивной, т.е.
(1.3)
Обычно условиями процесса на управление на каждом шаге накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называются допустимыми.
Задачу пошаговой оптимизации можно сформулировать так: определить совокупность допустимых управлений 
, переводящих систему из начального состояния
в конечное состояние
и максимизирующих (минимизирующих) показатель эффективности (1.3).
Для единообразия формулировок (но не вычислительных процедур!) в дальнейшем будем говорить только о задаче максимизации, имея в виду, что если необходимо минимизировать Z, то заменив Z на Z’=-Z перейдем к максимизации Z’.
Начальное состояние 
и конечное состояние
могут быть заданы однозначно или могут быть указаны множество
начальных состояний и множество
конечных состояний так, что
. В последнем случае в задаче пошаговой оптимизации требуется определить совокупность допустимых управлений, переводящих систему из начального состояния
в конечное
и максимизирующих целевую функцию (1.3). Управление, при котором достигается максимум целевой функции (1.3) называется оптимальным управлением и обозначается через U*=
.
Если переменные управления принимают дискретные значения, то модель ДП называется дискретной. Если же указанные переменные изменяются непрерывно, то модель ДП называется непрерывной. В зависимости от числа параметров состояний (s) и числа управляющих переменных на каждом шаге (r) различают одномерные и многомерные модели ДП. Число шагов в задаче может быть либо конечным, либо бесконечным.
ДП применяется при оптимизации как детерминированных, так и стохастических процессов.
В некоторых задачах, решаемых методом ДП, процесс управления естественно разбивается на шаги. Например, при распределении на несколько лет ресурсов деятельности предприятия шагом естественно считать временной период; при распределении средств между n предприятиями номером шага естественно шага номер очередного предприятия. В других задачах разбиение на шаги вводится искусственно. Например, непрерывный управляемый процесс можно рассматривать как дискретный, условно разбив его на некоторые временные отрезки – шаги. Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.