Динамическое программирование

Найти оптимальное управление набором высоты и скорости, при котором общий расход горючего минимален.

Из условия следует, что состояние физической системы S (самолета) характеризуется двумя параметрами: скоростью V и высотой Н. Поэтому решение будем искать на плоскости VOH, а точнее на ограниченном прямыми V=V₀, V=V_k и Н=Н₀, Н=H_k прямоугольнике, который и является областью допустимых состояний. Начальное S₀(V₀, Н₀) и конечное S_k(V_k, H_k) состояния вполне определены, как две точки S₀ и S_k на плоскости (см. рисунок).

 

 

 

 

 

 

 

 

 

 

 

 

 

Взаимосвязь между  различными подходами к решению задач динамической оптимизации

 

Классическая задача вариационного  исчисления является частным случаем задачи динамического программирования, в которой управляющими параметрами являются скорости изменения фазовых координат во времени, причем на значения управляющих параметров не накладывается никаких ограничений. Из необходимого условия динамического программирования – выполнения уравнения Беллмана – выводятся необходимые условия вариационного исчисления – уравнения Эйлера, Лежандра, условие Вейерштрасса и условия Вейерштрасса-Эрдмана для точки излома.

 

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

 

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

Таким образом, при выполнении решения  по методу динамического программирования, а именно при выполнении уравнения Беллмана и граничного условия для этого уравнения, выполняются и условия принципа максимума. Однако из принципа максимума не вытекает выполнение уравнения Беллмана, поскольку в этом случае не требуется вводить предположение о непрерывной дифференцируемости функции оптимального поведения.

Кроме того, при численном определении  оптимальных управлений эти два  метода представляют собой весьма различные подходы к динамической задаче оптимизации: динамическое программирование приводит к нелинейному дифференциальному уравнению в частных производных, а принцип максимума – к двум системам обыкновенных дифференциальных уравнений.

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