Суть методов динамического программирования

В задачах динамического программирования экономический процесс зависит от времени (или от нескольких периодов времени), поэтому находится ряд оптимальных решений (последовательно для каждого этапа), обеспечивающих оптимальное развитие всего процесса в целом. Динамическое программирование представляет собой математический аппарат, позволяющий осуществлять оптимальное планирование управляемых процессов и процессов, зависящих от времени. Поэтапное проведение оптимизации называется многошаговым процессом принятия решения. Экономический процесс называется управляемым, если можно влиять на ход его развития.
В основе метода динамического программирования (ДП) лежит принцип последовательной оптимизации: решение исходной задачи оптимизации большой размерности заменяется решением последовательности задач оптимизации малой размерности. Основным условием применимости метода ДП является возможность разбиения процесса принятия решений на ряд однотипных шагов или этапов, каждый из которых планируется отдельно, но с учетом результатов, полученных на других шагах. Например, деятельность отрасли промышленности в течение ряда хозяйственных лет или же последовательность тестов, применяемых при контроле аппаратуры, и т. д. Некоторые процессы (операции) расчленяются на шаги естественно, но существуют такие операции, которые приходится делить на этапы искусственно, например процесс наведения ракеты на цель.
Этот принцип гарантирует, что управление, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения процесса в целом, так как это управление выбирается с учетом последствий на предстоящих шагах.

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

Принцип оптимальности Беллмана. Еще раз подчеркнем, что смысл подхода, реализуемого в динамическом программировании, заключен в замене решения исходной многомерной задачи последовательностью задач меньшей размерности.

Перечислим основные требования к задачам, выполнение которых позволяет применить данный подход:

Ø объектом исследования должна служить управляемая система (объект) с заданными допустимыми состояниями и допустимыми управлениями;

Ø задача должна позволять интерпретацию как многошаговый процесс, каждый шаг которого состоит из принятия решения о выборе одного из допустимых управлений, приводящих к изменению состояния системы;

Ø задача не должна зависеть от количества шагов и быть определенной на каждом из них;

Ø состояние системы на каждом шаге должно описываться одинаковым (по составу) набором параметров;

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

Рассмотрим вопросы применения модели динамического программирования в обобщенном виде. Пусть стоит задача управления некоторым абстрактным объектом, который может пребывать в различных состояниях. Текущее состояние объекта отождествляется с некоторым набором параметров, обозначаемым в дальнейшем ξ и именуемый вектором состояния. Предполагается, что задано множество Ξ всех возможных состояний. Для объекта определено также множество допустимых управлений (управляющих воздействий) X, которое, не умаляя общности, можно считать числовым множеством. Управляющие воздействия могут осуществляться в дискретные моменты времени k (k ∊1: n), причем управленческое решение заключается в выборе одного из управлений x_k ∊ Х. Планом задачи или стратегией управления называется вектор х = (х ₁, х ₂,.., x_{n -1}), компонентами которого служат управления, выбранные на каждом шаге процесса. Ввиду предполагаемого отсутствия последействия между каждыми двумя последовательными состояниями объекта ξ _k и ξ _{k +1} существует известная функциональная зависимость, включающая также выбранное управление: ξ _{k +1} = φ _k (x_k, ξ _k), k ∊1: п -1. Тем самым задание начального состояния объекта ξ₁∊Ξ и выбор плана х однозначно определяют траекторию поведения объекта, как это показано на рис. 5.1.

Эффективность управления на каждом шаге k зависит от текущего состояния ξ _k, выбранного управления x_k и количественно оценивается с помощью функций f_k (х_k, ξ _k), являющихся слагаемыми аддитивной целевой функции, характеризующей общую эффективность управления объектом. (Отметим, что в определение функции f_k (х_k, ξ _k) включается область допустимых значений х_k, и эта область, как правило, зависит от текущего состояния ξ _k.) Оптимальное управление, при заданном начальном состоянии ξ₁, сводится к выбору такого оптимального плана х*, при котором достигается максимум суммы значений f_k на соответствующей траектории.