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

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

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

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

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

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

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

Ø последующее состояние, в котором оказывается система после выбора решения на 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 на соответствующей траектории.