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

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

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

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

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

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

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

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

Рассмотрим вопросы применения модели динамического программирования в обобщенном виде.

Пусть решается задача управления некоторым абстрактным объектом, который может пребывать в различных состояниях. Текущее состояние объекта отождествляется с некоторым набором параметров, обозначаемым в дальнейшем Принцип оптимальности Беллмана - №1 - открытая онлайн библиотека и именуемый вектором состояния. Предполагается, что задано множество Принцип оптимальности Беллмана - №2 - открытая онлайн библиотека всех возможных состояний. Для объекта определено также множество допустимых управлений (управляющих воздействий) X, которое, не умаляя общности, можно считать числовым множеством. Управляющие воздействия могут осуществляться в дискретные моменты времени Принцип оптимальности Беллмана - №3 - открытая онлайн библиотека , причем управленческое решение заключается в выборе одного из управлений Принцип оптимальности Беллмана - №4 - открытая онлайн библиотека . Планом задачи или стратегией управления называется вектор Принцип оптимальности Беллмана - №5 - открытая онлайн библиотека компонентами которого служат управления, выбранные на каждом шаге процесса. Ввиду предполагаемого отсутствия последействия между каждыми двумя последовательными состояниями объекта Принцип оптимальности Беллмана - №6 - открытая онлайн библиотека и Принцип оптимальности Беллмана - №7 - открытая онлайн библиотека существует известная функциональная зависимость, включающая также выбранное управление: Принцип оптимальности Беллмана - №8 - открытая онлайн библиотека , Принцип оптимальности Беллмана - №9 - открытая онлайн библиотека . Тем самым задание начального состояния объекта Принцип оптимальности Беллмана - №10 - открытая онлайн библиотека и выбор плана х однозначно определяют траекторию поведения объекта, как это показано на Рис. 5.1.

Эффективность управления на каждом шаге k зависит от текущего состояния Принцип оптимальности Беллмана - №11 - открытая онлайн библиотека , выбранного управления Принцип оптимальности Беллмана - №12 - открытая онлайн библиотека и количественно оценивается с помощью функций Принцип оптимальности Беллмана - №13 - открытая онлайн библиотека , являющихся слагаемыми аддитивной целевой функции, характеризующей общую эффективность управления объектом. (Отметим, что в определение функции Принцип оптимальности Беллмана - №13 - открытая онлайн библиотека включается область допустимых значений Принцип оптимальности Беллмана - №12 - открытая онлайн библиотека , и эта область, как правило, зависит от текущего состояния Принцип оптимальности Беллмана - №6 - открытая онлайн библиотека ) Оптимальное управление, при заданном начальном состоянии Принцип оптимальности Беллмана - №17 - открытая онлайн библиотека сводится к выбору такого оптимального плана Принцип оптимальности Беллмана - №18 - открытая онлайн библиотека ,при котором достигается максимум суммы значений Принцип оптимальности Беллмана - №19 - открытая онлайн библиотека на соответствующей траектории.

Основной принцип динамического программирования заключается в том, что на каждом шаге следует стремиться не к изолированной оптимизации функции Принцип оптимальности Беллмана - №13 - открытая онлайн библиотека , а выбирать оптимальное управление Принцип оптимальности Беллмана - №21 - открытая онлайн библиотека в предположении об оптимальности всех последующих шагов. Формально указанный принцип реализуется путем отыскания на каждом шаге k условных оптимальных управлений Принцип оптимальности Беллмана - №22 - открытая онлайн библиотека , Принцип оптимальности Беллмана - №10 - открытая онлайн библиотека , обеспечивающих наибольшую суммарную эффективность начиная с этого шага, в предположении, что текущим является состояние Принцип оптимальности Беллмана - №1 - открытая онлайн библиотека .

Принцип оптимальности Беллмана - №25 - открытая онлайн библиотека

Рис. 5.1

Обозначим Принцип оптимальности Беллмана - №26 - открытая онлайн библиотека максимальное значение суммы функций Принцип оптимальности Беллмана - №19 - открытая онлайн библиотека на протяжении шагов от k до п (получаемое при оптимальном управлении на данном отрезке процесса), при условии, что объект в начале шага k находится в состоянии Принцип оптимальности Беллмана - №1 - открытая онлайн библиотека . Тогда функции Принцип оптимальности Беллмана - №26 - открытая онлайн библиотека должны удовлетворять рекуррентному соотношению:

Принцип оптимальности Беллмана - №30 - открытая онлайн библиотека (14)

где Принцип оптимальности Беллмана - №31 - открытая онлайн библиотека .

Соотношение (14) называют основным рекуррентным соотношением динамического программирования. Оно реализует базовый принцип динамического программирования, известный также как принцип оптимальности Беллмана:

Оптимальная стратегия управления должна удовлетворять следующему условию: каково бы ни было начальное состояние Принцип оптимальности Беллмана - №11 - открытая онлайн библиотека на k-м шаге и выбранное на этом шаге управление Принцип оптимальности Беллмана - №12 - открытая онлайн библиотека , последующие управления (управленческие решения) должны быть оптимальными по отношению к состоянию Принцип оптимальности Беллмана - №8 - открытая онлайн библиотека , получающемуся в результате решения, принятого на шаге k.

Основное соотношение (14) позволяет найти функции Принцип оптимальности Беллмана - №26 - открытая онлайн библиотека только в сочетании с начальным условием, каковым в нашем случае является равенство

Принцип оптимальности Беллмана - №36 - открытая онлайн библиотека .

Сравнение рекуррентной формулы (14) с аналогичными соотношениями в рассмотренных выше примерах указывает на их внешнее различие. Это различие обусловлено тем, что в задаче распределения ресурсов фиксированным является конечное состояние управляемого процесса. Поэтому принцип Беллмана применяется не к последующим, а к начальным этапам управления, и начальное соотношение имеет вид

Принцип оптимальности Беллмана - №37 - открытая онлайн библиотека .

Важно еще раз подчеркнуть, что сформулированный выше принцип оптимальности применим только для управления объектами, у которых выбор оптимального управления не зависит от предыстории управляемого процесса, т. е. от того, каким путем система пришла в текущее состояние. Именно это обстоятельство позволяет осуществить декомпозицию задачи и сделать возможным ее практическое решение.

В то же время, говоря о динамическом программировании как о методе решения оптимизационных задач, необходимо отметить и его слабые стороны. Так, в предложенной схеме решения задачи (3)-(4) существенным образом используется тот факт, что система ограничений содержит только одно неравенство, и, как следствие, ее состояние задается одним числом - нераспределенным ресурсом Принцип оптимальности Беллмана - №1 - открытая онлайн библиотека . При наличии нескольких ограничений состояние управляемого объекта на каждом шаге характеризуется уже набором параметров Принцип оптимальности Беллмана - №39 - открытая онлайн библиотека , и табулировать значения функций Принцип оптимальности Беллмана - №40 - открытая онлайн библиотека необходимо для многократно большего количества точек. Последнее обстоятельство делает применение метода динамического программирования явно нерациональным или даже просто невозможным.