Динамическое программирование
Введение в динамическое программирование
Понятие динамического программирования обычно связывают не сколько с некоторым классом задач, сколько с определённым подходом реализации решения задачи. Для применения метода задача приводится к модели задачи динамического программирования, а затем подбирается оптимальное решение последовательным включением в рассмотрение элементов исследуемой модели.
Рассмотрим основные понятия и обозначения, используемые при построении модели.
S – состояние системы. Описывается набором параметров (х1, х2,… , хm). Для краткости будем отождествлять набор параметров, описывающих состояние системы, с этим состоянием.
Si – состояние системы к началу i-го шага.
Система меняет своё состояние по шагам под действием управления U=(u1, u2,… ,un), где каждая компонента представляет собой одно из возможных управленческих решений (принимаемое на соответствующем шаге). Это управление переводит систему из начального состояния S1 в некоторое новое состояние.
Система рассматривается на протяжении n шагов.
W(U) – целевая функция. Оценивает качество управления. Обычно при описании этой функции используют понятие «доход» и говорят о максимизации дохода (выгоды) или минимизации затрат.
Wi(ui, Si) – доход на i-м шаге, получаемый при нахождении системы в состоянии Si при реализации управления ui.
Fi(Si) – максимальный доход, получаемый начиная с i-го и до n-ного шага, если (i–1)-ый шаг система завершила в состоянии Si.
Модель задачи динамического программирования
Пусть состояние системы можно описать набором параметров (х1, х2,… , хm). Система рассматривается на протяжении n шагов. На каждом из шагов реализуются управленческие решения, составляющие в совокупности управление U=(u1, u2,… ,un). Качество управления оценивается целевой функцией W(U).
Цель: для данного начального состояния системы определить оптимальное управление U*, максимизирующее целевую функцию.
Любая задача, которую можно описать в терминах данной модели может быть решена с привлечением аппарата динамического программирования.
Алгоритм метода динамического программирования
Для применения этого алгоритма должны выполняться два условия:
- Отсутствие последствия: доход на некотором шаге зависит только от текущего состояния системы и выбранного управления и не зависит от предшествующих состояний системы.
- Условие аддитивности целевой функции
: значение целевой функции можно вычислить как сумму частных целевых функций на каждом шаге.
При выполнении указанных условий, для решения задачи можно применять принцип оптимальности Беллмана: каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы сумма доходов на данном шаге и оптимального дохода на всех последующих шагах была максимальной.
В соответствии с данным принципом, решение задачи осуществляется следующим образом.
- Начинаем применять алгоритм с последнего шага (k=n), при этом считаем, что .
- Находим оптимальное управленческое решение на данном шаге, учитывая оптимальный план для последующих шагов:
.
- Переходим к предшествующему шагу (уменьшаем k на 1).
- Алгоритм завершается при достижении первого шага. Выбранный набор управленческих решений составит оптимальное управление:
.
Примечание: при выполнении алгоритма следует отслеживать получаемые управленческие решения, т.к. именно они представляют собой решение задачи динамического программирования.
Виды решаемых задач
В предыдущем пункте приведено описание алгоритма решения одного из видов задач динамического программирования. В этой задаче требуется разработать оптимальный план управления на несколько шагов вперёд (время считается меняющимся по шагам).
Другой вид задачи – задача о распределении ресурсов. В этой задаче требуется распределить ресурсы оптимальным образом между несколькими предприятиями/направлениями/задачами, приносящими тот или иной доход в зависимости от используемых ресурсов. Здесь общее решение также подбирается последовательным наращиванием сложности модели, заключающимся в добавлении еще одного предприятия к уже рассмотренным (аналог перехода к предшествующему шагу). Отличие данной задачи заключается в том, что порядок выбора предприятий (и т.п.) не задан жёстко в отличие от последовательности моментов времени, поэтому может использоваться произвольная нумерация для рассматриваемых предприятий.
Обычно задачи динамического программирования имеют нелинейную целевую функцию, однако применение данных методов имеет смысл и при решении некоторых ЗЛП.
