Глава 12. Задачи оптимального управления и методы их приближенного решения

Постановка задачи оптимального управления

Пусть нестационарная динамическая система описывается системой обыкновенных дифференциальных уравнений (ОДУ)

Здесь —-вектор начальных условий,– анализируемый период времени (где величинане обязательно фиксирована!),—-вектор фазовых переменных системы,—— вектор управления. В той или иной форме могут быть заданы также условия на конце траектории системы, например, в виде. Заметим, что правильнее было бы последние условия задавать в виде, где— момент достижения системой состояния. Однако для простоты записи мы будем использовать первую запись (если не оговорено противное).

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

(1)

Напомним, что если время явно не входит в функцию, то динамическая система, описываемая системой ОДУ (1) называется стационарной.

На вектор в общем случае могут быть наложены ограничения вида

(2)

где –множество допустимых значений вектора фазовых переменных системы, – некоторое функциональное пространство, например, пространствонепрерывных на интервале функций (см. рис. 1).

На рис. 1 множество D_X = {x₁(t) | x^-₁(t) x₁(t) x⁺₁(t), t [t₀, ]}C⁽⁰⁾[t₀, ].

Рис. 1.  Пример области допустимых значений вектора фазовых координат для одномерной системы (n = 1).

На вектор управления также обычно накладываются некоторые ограничения вида

(3)

где –множество допустимых управлений, – некоторое функциональное пространство, например, пространствофункций "интегрируемых с квадратом" на интервале(см. рис. 2).

На рис. 2 множество D_U = {u₁(t) | u^-₁(t) u₁(t) u⁺₁(t), t [t₀, ]}L₂[t₀, ], а пространство допустимых управлений Ω_U, полагается, составляют кусочно-постоянные функции, имеющие на интервале [t₀, ] конечное число разрывов первого рода.

Рис. 2.  Пример множества допустимых управлений для системы с одномерным управлением (m = 1).

Примечание 1

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

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

(4)

где – некоторая одномерная функция указанных переменных.

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

Итого, задача оптимального управления динамической системой обычно формализуется следующим образом: найти такой вектор управления , удовлетворяющий условию (3), который на решениях системы ОДУ (1) обеспечивает минимум критерия оптимальности (4) при выполнении ограничений (2) на вектор фазовых переменных.

Заметим, что возможны и не интегральные формы функционалов качества управления, например:

, где – заданная точка;

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

Постановка задачи оптимального управления. Тест 1

Тело массой , находящееся в начальный момент временив состоянии покоя в точке с координатой, может перемещаться вдоль осипод действием силы тяги двигателя, которым оно снабжено (см. рис. 1).

Максимальная по величине сила тяги , которую может развить двигатель, равна.

При движении тела на него действует сила сопротивления среды , пропорциональная скорости движения тела, т.е., где– заданный коэффициент пропорциональности.

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

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

Рис. 1.  

Формализуйте поставленную задачу в виде задачи оптимального управления динамической системой.

 Ответ 

Введем обозначения

Таким образом, размерность вектора фазовых переменных системы равна и его можно записать в виде.

По второму закону Ньютона имеем

где – ускорение тела.

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

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

Ограничения на вектор фазовых переменных отсутствуют.

Требование постановки задачи о минимальном отличии отможно формализовать различными способами. Обычно используют метрику функционального пространства(гильбертово пространство)

Понятно, что минимуму этого функционала соответствует оптимальный случай.

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

Таким образом, в качестве критерия качества управления можно использовать функционал (двухкритериальная задача!)

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

Принцип максимума Л. С. Понтрягина

Для простоты записи положим, что и рассмотрим стационарную динамическую систему

(1)

Требуется найти управление , которое переводит эту систему из состоянияв состояниеи минимизируеткритерий оптимальности управления - функционал

(2)

Введем в рассмотрение константу и вспомогательную вектор-функцию, являющуюся решением системы ОДУ

или в векторной форме

где

(3)

гамильтониан динамической системы (1). Более удобна другая форма системы обыкновенных дифференциальных уравнений (ОДУ) для вспомогательной вектор-функции :

(4)

где --матрица частных производных вектор-функциипо:

Система ОДУ (4) называется сопряженной системой.

Теорема 1 (принцип максимума Л.С. Понтрягина). Пусть – допустимое управление, переводящее систему (1) из точкив точку, а– соответствующая фазовая траектория. Для оптимальности (в смысле минимума функционала (2)) процессанеобходимо существование такой константыи такого решениясистемы ОДУ (5), что вектор- функцияне тривиальна и для любого момента временивыполняется условие максимума

(5)

где гамильтониан системы определяется выражением (4)

Не тривиальность вектор-функции означает, что среди величинимеется хотя бы одна тождественно не равная нулю.

Отметим, что начальные условия для системы ОДУ (5) не заданы, т.е. можно получить только общее решение этой системы.

Примечание 1

Поскольку принцип максимума определяет лишь необходимое условие оптимальности, из того факта, что некоторая траектория удовлетворяет ему, не следует, что она оптимальна. Т.е. принцип максимума дает траектории лишь "подозрительные" на оптимальность. Для определения из их числа оптимальной траектории необходима дополнительная проверка.

Вслед за Федоренко Р.П. назовем систему уравнений (1), (2), (3), (4), (5) П-системой.

Рассмотрим теперь принцип максимума Л.С. Понтрягина для задачи оптимального быстродействия. Напомним, что в этом случае критерия оптимальности управления имеет вид (см. параграф 12.1)

(6)

Легко видеть, что гамильтониан системы (1) в этом случае равен

(7)

Теорема 2 (принцип максимума Л.С. Понтрягина для задачи оптимального быстродействия). Пусть – допустимое управление, переводящее систему (1) из точкив точку, а– соответствующая фазовая траектория. Для оптимальности (в смысле минимума функционала (6)) процессанеобходимо существование такого решениясистемы ОДУ (3), что вектор-функцияне тривиальна и для любого момента времении выполняется условие максимума

(8)

где гамильтониан системы определяется выражением (7)

Известно множество обобщений принципа максимума Л.С. Понтрягина. Рассмотрим некоторые из них.

1. Задача с подвижными концами. Здесь векторы не фиксированы, а заданы лишь некоторые гладкие многообразия(гладкие поверхности, расположенные в пространстве, размерность которых меньше) такие, что.

2. Дополнительные ограничения на вектор управления. Кроме требования минимизации критерия оптимальности заданы ограничения видагде– некоторые функционалы над.

3. Обобщение для нестационарных динамических систем.

4. Обобщение для динамических систем с параметрами: где^Т – неизвестный вектор параметров (констант). Требуется выбрать такой вектор и такое управление, чтобы перевести систему из состоянияв состояниеи минимизировать функционал.

Пример 1

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

Введем обозначения

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

Аналогично примеру 12.1.1 имеем следующее формальное описание системы (см. рис. 1):

(9)

Рис. 1.  К прим. 1.

Поставим задачу оптимального быстродействия – задачу о быстрейшем попадании рассматриваемой точки в начало координат из заданного начального состояния. Другими словами, поставим задачу перевода за кратчайшее время материальной точки, имеющей начальное положениеи начальную скорость, в начало координат с нулевой скоростью (чтобы точка перешла в начало координат и остановилась там).

Гамильтониан (7) системы (9) для задачи оптимального быстродействия имеет вид

а система ОДУ для вспомогательной вектор-функции — вид

(10)

Легко получить явное общее решение системы ОДУ (10)

где — произвольные постоянные.

Уравнение (8) имеет в данном случае вид

(11)

Из (11) следует, что оптимальное управление должно удовлетворять условию

т.е.

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

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

На отрезке времени, на котором , из (9) последовательно имеем

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

Аналогично, управлению соответствует семейство парабол, по которым фазовые точки движутся сверху вниз (т.к.) — см. рис. 2б.

Рис. 2.  Фазовые траектории системы (9): а – при u^*(t)≡1; б – при u^*(t)≡-1.

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

Рис. 3.  Варианты фазовых траекторий системы (9).

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

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

Рис. 4.  Вид оптимальных фазовых траекторий системы (9).

На рис. 4 дуга имеет уравнение, а дуга– уравнение.

Итак, согласно принципу максимума Л.С. Понтрягина оптимальные (по быстродействию) фазовые траектории системы (9) могут быть только вида, приведенного на рис. 4.

Метод решения задачи оптимального управления, использующий П-систему

Рассмотрим задачу оптимального управления

(1)

(2)

Напомним, что выражения (1), (2) совместно с выражением для соответствующего гамильтониана

(3)

сопряженной системой ОДУ для вспомогательной вектор-функции

(4)

и условием максимума

(5)

образуют П-систему задачи оптимального управления (1), (2).

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

Положим, что уравнение (5) можно разрешить относительно , т.е. найти функцию. Тогда формальноП-система (1), (2), (3), (4) (5) формально сводится к системе уравнений

(6)

(7)

Введем в рассмотрение П-процедуру:

1. Задаем некоторые начальные условия для функции.

2. С заданными начальными условиями решаем задачу Коши для сопряженной системы ОДУ (7) – находим функцию.

3. С найденной функцией решаем задачи (6) – отыскиваем оптимальную фазовую траекторию системы, соответствующую начальным условиям.

4. Находим разность (которая, очевидно, в общем случае не будет равна 0)

П-процедура устанавливает функциональную зависимость разности от вектора. Обозначим эту функциональную зависимость:

(8)

(9)

Теперь, формально, решение П-системы сводится к решению системы нелинейных алгебраических уравнений (9): найти вектор , при которомили, что то же самое, при котором.

Чаще всего для решения СНАУ (9) используют метод касательных (метод Ньютона). Напомним схему этого метода для одномерного случая (см. параграф 4.8).

Пусть . Система (9) при этом имеет вид (см. рис. 1)

(10)

где — соответствующие скалярные константы, а— скалярные функции.

Рис. 1.  К схеме метода касательных (метода Ньютона). Одномерный случай (n = 1).

Линейная функция, аппроксимирующая функцию в точке, записывается в виде

Приравняв правую часть этого выражения к нулю, получим итерационную формулу метода касательных

(11)

В многомерном случае итерационная формула (11) имеет вид

(12)

где — матрица, обратная матрице,

(13)

Схема метода приближенного решения задачи оптимального управления, использующего П-систему

1. Полагаем счетчик числа итераций .

2. Из каких либо соображений задаем вектор — начальное значение вектора.

3. Выполняем П-процедуру для вектора — вычисляем значение функциив точке:

4. Если условие окончание итераций не выполнено (см. ниже), то по формуле (12) вычисляем следующее приближение к , полагаеми переходим к п.3. Иначе переходим к следующему пункту.

5. В качестве приближения к оптимальному управлению принимаем где— решение системы (7) с начальными условиями

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

где — некоторая векторная норма, например, евклидова;— требуемая точность выполнения условия.

Рассмотрим в заключение основные трудности, возникающие при решении задачи оптимального управления данным методом:

1. Поскольку функция задана неявно, для вычисления- матрицы) приходится использовать численное дифференцирование. Для этого на каждой итерации, как минимум, приходитсяраз решать задачи Коши (6), (7).

2. Метод Ньютона сходится лишь в достаточно малой окрестности решения. Поэтому на практике приходится использовать различные модификации метода Ньютона, обеспечивающие ускорение сходимости.

3. Решение уравнения (10) может быть не единственно.

4. Содержательные соображения для выбора вектора практически отсутствуют. Иногда для выбора этого вектора используют приближенное решениезадачи оптимального управления (1), (2) каким-либо другим методом, дающим грубое приближение к .

Решение задачи оптимального управления методом вариаций в фазовом пространстве

Метод вариаций в фазовом пространстве разработан под руководством Н.Н. Моисеева в ВЦ АН СССР. Имеется несколько вариантов метода. Наиболее развитым является метод локальных вариаций Ф.Л. Черноусько.

Рассмотрим задачу оптимального управления

(1)

(2)

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

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

Элементарной операцией называется решение задачи (1), (2) для интервала , т.е. решение следующей задачи

(3)

(4)

Обозначим "цену" элементарной операции . Т.е.— это значениекритерия качества управления при оптимальном (в смысле минимума функционала (4)) переводе системы (1) из состоянияв состояние.

Заметим, что в связи с малостью интервала решатьзадачу оптимального управления (3), (4) не обязательно очень точно. Это обстоятельство позволяет во многих случаях достаточно просто получить цену элементарной операции .

Во введенных обозначениях функционал (2) на траектории равен

(5)

Локальной вариацией траектории (в фазовом пространстве) называется траектория, отличающаяся от данной траектории только значениемв точке. Обычно рассматриваются локальные вариации, в которых точкасмещается только вдоль координатных направлений (см.рис. 1):. Здесь—-я компонента вектора,—-й орт в-мерном пространстве,— шаг по-ой компоненте фазового вектора.

Рис. 1.  К определению локальной вариации в фазовом пространстве.

Отметим, что локальная вариация траектории в точкеприводит к изменению в сумме (5) только двух слагаемых —и.

Схема метода локальных вариаций.

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

2. Последовательно для на интервалевыполняемэлементарную операцию и определяем ее "цену" .

3. Для каждого последовательно для каждоговыполняем следующие действия:

• 3.1) выполняем локальную вариацию ;

• 3.2) если полученная в результате новая точка является допустимой (т.е.), то переходим к следующему пункту. Иначе переходим к п.3.4;

• 3.3) на интервалах ,выполняемэлементарные операции и определяем их "цены" ,. Если даннаялокальная вариация была успешной — привела к уменьшению критерия качества управления (5) то полагаеми переходим к следующему пункту;

• 3.4) выполняем локальную вариацию ;

• 3.5) если полученная в результате новая точка является допустимой (т.е.), то переходим к следующему пункту. Иначе, полагаемпереходим к п.3.1.

• 3.6) выполняем действия, указанные в п.3.3.

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

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

Действия, указанные в пункте 3 приведенной схемы метода локальных вариаций, будем называть основным циклом метода локальных вариаций. Легко видеть, что временная сложность основного цикла равна .

В изложенном виде метод локальных вариаций обладает рядом серьезных недостатков. Назовем основные из этих недостатков:

• Существование тупиковых ситуаций — во множестве локальных вариаций не оказывается удачной не потому, что данная траектория оптимальна, а потому, что исследуются не все возможные вариации траектории, а только чрезвычайно узкое множество соседних с данной.

• Медленная сходимость.

• Трудность построения элементарной операции.

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

Решение задачи оптимального управления методом вариаций в пространстве управлений

Метод разработан в ИПМ АН СССР Федоренко Р.П.

Рассмотрим задачу оптимального управления

(1)

(2)

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

Положим, что известно некоторое управление , которое мы будем называть невозмущенным управлением.

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

то называется функциональной производной в смысле Фреше функционалана невозмущенной траекториии обозначается

(3)

Здесь —-вектор-столбец,—-вектор-строка (транспонированный вектор),— некоторая векторная норма.

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

Заметим, что метод вариаций в пространстве управлений применим и к функционалам, отличным от функционала (2), например, к функционалу вида

По существу, при этом изменяется лишь техника вычисления функциональных производных.

В методе вариаций в пространстве управлений на каждой итерации вариация управленияопределяется путем минимизации линейной части приращения функционала, вызванного этой вариаций:

(4)

Здесь — некоторая малая окрестность невозмущенного управления.

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

При построении множества следует учитывать следующие требования:

1. Из того факта, что , должно следовать, что;

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

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

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

Общая схема метода вариаций в пространстве управлений.

1. Из каких либо соображений задаем начальное приближение к оптимальному управлению и полагаем счетчик числа итераций равным .

2. С управлением решаем задачу Коши для системы ОДУ (1) – получаем фазовую траекторию.

3. Вычисляем — значениекритерия качества управления (2) на невозмущенной траектории .

4. В окрестности невозмущенной траектории выполняем линеаризацию задачи – вычисляем функциональную производнуюи определяем окрестностьневозмущенной траектории.

5. Из условия

   (5)

6. находим приращение управления.

7. Полагаем .

8. Если условие окончания итераций выполнено (см. ниже), то в качестве приближения к оптимальному управлению принимаем управление и заканчиваем вычисления. Иначе – полагаеми переходим к п.2

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

где — некоторая функциональная норма,заданная константа.

Заметим, что задача (5) может быть сведена к задаче линейного программирования, что является значительным достоинством метода.

Метод динамического программирования Беллмана

Идею метода динамического программирования Беллмана рассмотрим на примере задачи оптимального быстродействия

(1)

(2)

Гипотеза 1. Какова бы ни была отличная от допустимая точка фазового пространства, существует оптимальная (в смысле быстродействия) траектория перехода динамической системы из точкив точку(см. рис. 1)

Рис. 1.  К гипотезе 1. (n = 2).

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

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

Гипотеза 2. Функция непрерывна и всюду, кроме, быть может, точки, имеет непрерывные частные производные

Пусть теперь (— оптимальный процесс перехода системы (1) из состоянияв состояниеи— отрезок времени, в течение которого этот переход происходит;. Другими словами, положим, что

Утверждение 1 (принцип оптимальности). Если процесс оптимален, то процесстакже оптимален.

Доказательство (см. рис. 2). Движение по рассматриваемой оптимальной траектории от точки до точкиосуществляется за время, а движение из точкидо точки— в течение времени. Быстрее, чем за это время из точкипопасть в точкуневозможно.

Рис. 2.  К утверждению 1. (n = 2).

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

Утверждение 2. Если процесс оптимален, то справедливо уравнение

где называется функцией Беллмана.

Доказательство. Из принципа оптимальности следует, что есть время оптимального движения из точкив точку, т.е.

(3)

Заменив в формуле (3) на, получим

или

(4)

Переходя в формуле (4) к пределу при , получим, что на оптимальной траектории выполняется равенство

(5)

По правилам дифференцирования сложной функции с учетом уравнения (1) из равенства (5) имеем

(6)

Из принципа оптимальности следует, что соотношение (6) верно для любых . Таким образом, окончательно имеем

Аналогично утверждению 2 можно доказать справедливость следующего утверждения.

Утверждение 3. Если процесс оптимален, то справедливоуравнение динамического программирования Беллмана для непрерывной системы

(7)

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

Подчеркнем следующие обстоятельства:

• уравнение динамического программирования Беллмана дает необходимое условие минимума;

• уравнение динамического программирования Беллмана требует выполнения гипотезы 12.6.2 относительно неизвестной функции Беллмана . Однако, даже в простейшихзадачах оптимального управления функция оказывается не всюду дифференцируемой. По этой причине при решении задач оптимального управления методом динамического программирования уравнение (7) в явном виде не используется — используетсяпринцип оптимальности.

Решение задачи оптимального управления методом динамического программирования Беллмана

Рассмотрим (только для простоты записи) задачу оптимального управления для стационарной динамической системы и критерием оптимальности управления, зависящим только от вектора управления:

(1)

(2)

Обратим внимание на то, что, в отличие от того, как это делалось ранее, для обозначения фазового вектора использована маленькая буква, а для обозначениявектора управления – маленькая буква.

Покроем интервал сеткойс шагом(см. рис. 1).

Рис. 1.  Равномерная временная сетка на интервале [0, T].

Систему ОДУ (1) заменим ее конечно-разностным аналогом

(3)

а функционал (2) заменим его приближенным значением, вычисленным по формуле прямоугольников

(4)

где есть-матрица.

Таким образом, задача оптимального управления (1), (2) в дискретной форме имеет вид (3), (4).

Аналогично матрице введем в рассмотрение-матрицуи сформулируемпринцип оптимальности (см. параграф 12.6) для задачи (3), (4).

Утверждение 1 (принцип оптимальности для дискретной системы). Пусть — оптимальное управление длязадачи оптимального управления (3), (4) и пусть — соответствующая оптимальная фазовая траектория. Тогда для любыхуправлениеи соответствующая траекториябудут оптимальными на интервале времени

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

Рис. 2.  К принципу оптимальности для дискретной системы. n = 2.

Обозначим значение функционала (4) на завершающих шагах

Тогда если на завершающих шагах управление оптимально, имеет место равенство

(5)

где — функция Беллмана для дискретной системы последнихшагов для дискретнойзадачи оптимального управления (3), (4).

Из утверждения 1 следует, что на последнем шаге (когда )

(6)

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

(7)

Уравнения (6), (7) позволяют последовательно найти функции и называютсяуравнениями динамического программирования Беллмана для дискретной системы (3), (4). Отметим, что одновременно с нахождением функций оказываются определенными и управления. Поскольку управлениезависит от состояния, это управление называется условно оптимальным управлением.

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

• поскольку состояние известно, находим управление; с этим управлением по формуле (3) находим состояние;

• поскольку состояние известно, находим управление; с этим управлением по формуле (3) находим состояние;

• ....

• поскольку состояние известно, находим управление; очевидно, что.

Схема метода приближённого решения задач оптимального управления методом динамического программирования Беллмана.

Этап 1

Шаг 1. Из условия (6) находим условно оптимальное управление и функцию Беллмана.

Шаг 2. Используя результаты предыдущего шага, из условия (7) находим условно оптимальное управление и функцию Беллмана.

...

Шаг N. Используя результаты предыдущего шага, из условия (7) находим условно оптимальное управление и функцию Беллмана

Этап 2.

Шаг 1. Находим управление и состояние;

Шаг 2. Находим управление и состояние;

...

Шаг N. Находим управление и состояние

Заметим, что при приближённом решении задач оптимального управления методом динамического программирования остается открытым вопрос о сходимости решения к решениюисходной непрерывной задачи оптимального управления (1), (2).

Решение задачи оптимального управления методом динамического программирования Беллмана. Тест 1

Решите методом динамического программирования Беллмана следующую задачу оптимального управления для дискретной динамической системы (n=1, m=1):

(1)

(2)

где— символ целой части числа (т.е. множествоесть множество целых числе от 0 до 4).

 Ответ 

Заменим ОДУ (1) его конечно-разностным аналогом

(3)

а критерий оптимальности управления (2) — его приближенным значением, вычисленным по формуле прямоугольников

(4)

Положим, что ,.

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

Этап 1.

Шаг 1 (. Из условия (4) находим условно оптимальное управлениеи функцию Беллмана. Поскольку, легко видеть,и. Сведем результаты вычисления значений функциив табл. 1

Таблица 1    

		4	3	2	1	0
		16	9	4	1	0

Шаг 2 (. Используя результаты предыдущего шага, из условия (4) находим условно оптимальное управлениеи функцию Беллмана. Сведем результаты вычисления значений функциив табл. 2, в которой прочерки соответствуют не допустимым управлениям, а значения управления и функции Беллмана, выделенные жирным шрифтом, соответствует оптимальной траектории.

Таблица 2    

			-	-	-	-
			-	-	-	-
		1		-	-	-
		10		-	-	-
		2	1		-	-
		8	5		-	-
		3	2	1		-
		10	5	2		-

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

Шаг 3 . Используя результаты предыдущего шага, из условия (4) находим условно оптимальное управлениеи функцию Беллмана. Сведем результаты вычисления значений функциив табл. 3, в которой прочерки соответствуют не допустимым управлениям, а значения управления и функции Беллмана, выделенные жирным шрифтом, соответствует оптимальной траектории.

Таблица 3    

		1
		10
		2
		8
		3
		10

Рассмотрим, для примера, схему получения значений ,, соответствующих переходу системы из состоянияв состояние. Из состояниясистема может перейти оптимально в состояниеили в состояниеПервому переходу соответствует оптимальное управление, второму переходу – оптимальное управление. Указанным переходам соответствует значение функции Беллмана, равное(см. табл. 2). Переход системы из состоянияв состояниеможет быть выполнен только под действием управления. Поэтому.

Этап 2.

Шаг 4. Из табл. 3 следует, что существует два равноценных (приводящих к значению функции Беллмана, равному ) оптимальных управления. По формуленаходим соответствующие значения переменной состояния:

Шаг 5. Из табл. 2 следует, что для существует два равноценных (приводящих к значению функции Беллмана, равному) управления,. Аналогично, из табл. 2 следует, что длясуществует одно оптимальное управление. По формуленаходим соответствующие значения переменной состояния:

Шаг 6. Из табл. 1 следует, что для существует одно оптимальное управление. Аналогично, из табл. 1 следует, что длясуществует одно оптимальное управление. По формуленаходим соответствующие значения переменной состояния:

.

Полученные оптимальные управления и соответствующие оптимальные фазовые траекториииллюстрирует рис. 1.

Рис. 1.  

Решение задачи оптимального управления методом сведения к задаче нелинейного программирования

Рассмотрим задачу оптимального управления

(1)

(2)

Обратим внимание на то, что так же, как в предыдущем параграфе, для обозначения фазового вектора использована маленькая буква, а для обозначениявектора управления – маленькая буква.

Метод решения задачи оптимального управления (1), (2) путем сведения этой задачи к задаче нелинейного программирования (метод сведения к задаче нелинейного программирования) рассматривался (на одном частном примере) в главе 1. Изложим общую схему этого метода.

Покроем интервал равномерной или неравномерной сеткойс шагом(см. рис. 1).

Рис. 1.  Временная сетка t_k, k ∈ [0, N] на интервале [0, T].

Систему ОДУ (1) заменим ее конечно-разностным аналогом

(3)

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

(4)

где есть-матрица.

Дискретная задача оптимального управления (3), (4) представляет собой задачу нелинейного программирования

(5)

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

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

• при управлениях по формуле (3) последовательно вычисляем значения компонент векторадля;

• с найденными векторами и управлениямипо формуле (5) вычисляем значениекритерия оптимальности управления .

Задача нелинейного программирования (5) может быть решена рассмотренными ранее методами условной оптимизации.

Изложенный метод создает впечатление тривиальности решения задач оптимального управления. Действительно, есть теоремы о том, что решение дискретной задачи (3), (4) сколь угодно точно (при ) аппроксимирует решение исходной задачи (1), (2). Есть теоремы о сходимости методов оптимизации, с помощью которых может быть найден минимум (4). Однако всегда остаются открытыми вопросы: можно ли данноесчитать достаточно большим?; можно ли ограничиться данным числом итераций при решении задачи (4)?. Т.е. необходим тщательный содержательный контроль результатов. Иначе легко получить решения, сколь угодно далекие от действительно оптимальных решений. В целом, данный метод (впрочем, как и любой другой) может быть рекомендован только в комбинации с другими методами.

Решение задачи оптимального управления путем сведения к задаче нелинейного программирования. Тест 1

Рассмотрим следующую двумерную (n = 2) задачу оптимального управления с одномерным (m = 1) вектором управления

(1)

(2)

где — заданные скалярные константы, а— заданная скалярная функция.

Сведите эту задачу оптимального управления к задаче условной оптимизации.

 Ответ 

Заменим систему ОДУ (1) ее конечно-разностным аналогом:

Заменим критерий качества управления (2) его приближенным значением, вычисленным по формуле прямоугольников:

где есть-вектор (поскольку— скалярная функция).

Таким образом, задача оптимального управления (1), (2) сведена к следующей -мернойзадаче условной оптимизации

где множество допустимых значений вектора варьируемых параметров .