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

Метод динамического программирования был разработан Р. Веллманом [5]. Он применим не только для решения задач оптимизации систем управления, но и для самых различных технических и экономических задач. При обосновании этого метода предполагается, что функционал качества является дифференцируемой функцией фазовых координат системы. Заметим, что это условие выполняется не всегда.

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

где — некоторые, в общем случае нелинейные функции фазовых координат и управлений. Число последних для общности принято равным числу фазовых координат.

Уравнения (12.156) можно представить также в матричной форме:

где — матрицы-столбцы фазовых координат и управлений размером .

В качестве критерия оптимальности примем минимум функционала

Функции вообще говоря, могут содержать в явном виде текущее время Однако это не меняет принципиальной постановки задачи.

Целью управления является перевод системы из состояния при в состояние при . Такая задача управления называется терминальной, и она соответствует определению в фазовом пространстве оптимальной траектории с закрепленными концами.

Будем считать, что фазовые координаты и управления должны принадлежать некоторым замкнутым (ограниченным) пространствам, т. е.

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

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

произвольной точки в фазовом пространстве в смысле минимума функционала

Минимум функционала (12.160) зависит от начального момента времени и начальной точки Обозначим этот минимум через Функция для некоторой совокупности фазовых координат может, вообще говоря, не существовать, так как может не существовать допустимого управления, удовлетворяющего (12.156).

Если найдены функция и требуемое управление и то, положив , где а — матрица-столбец начальных условий, мы получим решение исходной задачи.

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

Примем начальные условия: при оптимальное управление и реализует минимум функционала (12.160), а — оптимальная траектория в фазовом пространстве. Выберем произвольный момент времени принадлежащий интервалу и обозначим через точку на оптимальной траектории Принцип оптимальности гласит следующее.

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

Итак, в соответствии с изложенным введем функциональное уравнение

на основании которого может быть найдено оптимальное управление и

Если на промежутке выбрать промежуточную точку то на основании принципа оптимальности

Функция и оптимальное управление обычно не могут быть найдены аналитическим путем. Для этой цели применяются приближенные методы с использованием вычислительных машин. Рассмотрим идею приближенного расчета.

Пусть — фиксированное значение времени, а — малый отрезок времени, причем Тогда

где функции связаны условиями (12.157).

Вид управления и на интервале не оказывает влияния на первое слагаемое в правой части (12.163). Поэтому на рассматриваемом интервале времени следует так выбрать управление, чтобы минимизировать второе слагаемое в правой части (12.163) при выполнении условий

На основании принципа оптимальности перепишем (12.163) следующим образом:

На интервале управление и должно быть выбрано так, чтобы минимизировать правую часть (12.165). От этого выбора зависят оба слагаемых правой части.

Заменим на малом интервале матричную функцию и функцию их фиксированными значениями в точке а производную х отношением конечных разностей Тогда вместо (12.165) можно записать приближенно

Кроме того, имеем

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

Далее фиксируется произвольное значение Минимум правой части первого равенства (12.168) вычисляется по тем значениям и из множества для которых точка определяемая вторым равенством (12.168), соответствует значению Если для какой-либо точки X таких значений и не существует, то функция не определена в точке х.

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

На втором шаге рассматривается момент времени Из (12.166) и (12.167) можно получить

Далее фиксируется произвольная точка Минимум правой части (12.169) вычисляется по тем значениям и для которых точка определяемая вторым равенством (12.169), принадлежит подмножеству Находится значение функции на некотором подмножестве из На интервале управление и принимается постоянным и равным значению и реализующим На интервале управление, как функция было определено после первого шага. Так как связано с вторым равенством (12.169), то после двух шагов оказывается определенным управление на интервале времени . Это будет кусочно-постоянная функция с интервалами постоянства, равными

Последующие шаги рассчитываются аналогично. Если весь интервал управления Т разбит на шагов, то после -го шага определяется функция на подмножестве из X и управление и как кусочно-постоянная функция с интервалами постоянства Если начальная точка принадлежит подмножеству для которого определена функция то, положив получаем — минимум функционала (12.161) исходной задачи управления и и — оптимальное управление. Подставляя затем оптимальное управление в (12.156) или (12.157) и решая систему исходных дифференциальных уравнений, можно определить оптимальную траекторию движения

Если не принадлежит подмножеству то задача не имеет решения. Надо учитывать при этом, что вся задача решалась приближенно, в том числе найдено было приближенно и подмножество Х.

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

Серьезным недостатком метода является то, что с ростом размерности задачи (порядка дифференциального уравнения) весьма серьезно возрастают требования к быстродействию и объему памяти вычислительных машин. Действительно, на шаге вычисляется функцияф (Т — к зависящая от переменных и определенная на множестве Ее надо хранить в памяти машины до тех пор, пока не будет вычислена функция Это значит, что в памяти машины должна храниться таблица, в которой записаны значения для различных точек из Этих точек оказывается много, так как таблица должна достаточно точно и равномерно определять функцию Кроме того, в памяти машины приходится запоминать кусочно-постоянную в общем случае n-мерную функцию управления зависящую от и вычисленную при значениях аргумента с интервалом

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

Уравнение Веллмана. Введем предположение, что функция имеет непрерывные частные производные по всем своим аргументам: Тогда в равенстве (12.166) функцию можно представить следующим образом:

Здесь — величина более высокого порядка малости, чем Входящие в правую часть (12.170) производные удовлетворяют (12.156).

Поэтому

Подставим (12.171) в (12.166). Функция не зависит от управления и в момент Поэтому ее можно вынести за знак минимума. Деля полученное равенство на и переходя к пределу при имеем

при условиях

Уравнение (12.172) и представляет собой уравнение Беллмана с краевым условием Сумма первых двух членов (12.172) есть полная производная функции по времени. Поэтому уравнение Беллмана можно записать в другом виде:

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

Заметим, что если функции не зависят явно от времени, то решение уравнения (12.174) — функция и оптимальное управление и, которое реализует минимум в (12.174), тоже не зависит явно от времени, т. е. , однако в общем случае

Аналитическое нахождение функции в явной форме удается только в некоторых частных случаях. Один из таких случаев рассмотрен в следующем параграфе.