Принцип оптимальности Беллмана
Подчеркнем, что смысл подхода, реализуемого в динамическом программировании, заключен в замене решения исходной многомерной задачи последовательностью задач меньшей размерности. Перечислим основные требования к задачам, выполнение которых позволяет применить данный подход: 1. объектом исследования должна служить управляемая система (объект) с заданными допустимыми состояниями и допустимыми управлениями; 2. задача должна позволять интерпретацию как многошаговый процесс, каждый шаг которого состоит из принятия решения о выборе одного из допустимых управлений, приводящих к изменению состояния системы; 3. задача не должна зависеть от количества шагов и быть определенной на каждом из них; 4. состояние системы на каждом шаге должно описываться одинаковым (по составу) набором параметров; 5. последующее состояние, в котором оказывается система после выбора решения на k -м шаге, зависит только от данного решения и исходного состояния к началу k- гошага. Данное свойство является основным с точки зрения идеологии динамического программирования и называется отсутствием последействия. Рассмотрим вопросы применения модели динамического программирования в обобщенном виде. Пусть решается задача управления некоторым абстрактным объектом, который может пребывать в различных состояниях. Текущее состояние объекта отождествляется с некоторым набором параметров, обозначаемым в дальнейшем
Эффективность управления на каждом шаге k зависит от текущего состояния Основной принцип динамического программирования заключается в том, что на каждом шаге следует стремиться не к изолированной оптимизации функции
Рис. 5.1
Обозначим
где Соотношение (14) называют основным рекуррентным соотношением динамического программирования. Оно реализует базовый принцип динамического программирования, известный также как принцип оптимальности Беллмана: Оптимальная стратегия управления должна удовлетворять следующему условию: каково бы ни было начальное состояние Основное соотношение (14) позволяет найти функции
Сравнение рекуррентной формулы (14) с аналогичными соотношениями в рассмотренных выше примерах указывает на их внешнее различие. Это различие обусловлено тем, что в задаче распределения ресурсов фиксированным является конечное состояние управляемого процесса. Поэтому принцип Беллмана применяется не к последующим, а к начальным этапам управления, и начальное соотношение имеет вид
Важно еще раз подчеркнуть, что сформулированный выше принцип оптимальности применим только для управления объектами, у которых выбор оптимального управления не зависит от предыстории управляемого процесса, т. е. от того, каким путем система пришла в текущее состояние. Именно это обстоятельство позволяет осуществить декомпозицию задачи и сделать возможным ее практическое решение. В то же время, говоря о динамическом программировании как о методе решения оптимизационных задач, необходимо отметить и его слабые стороны. Так, в предложенной схеме решения задачи (3)-(4) существенным образом используется тот факт, что система ограничений содержит только одно неравенство, и, как следствие, ее состояние задается одним числом - нераспределенным ресурсом
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|