Динамическое программирование. 
Оптимальное управление в технических системах

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

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

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

Рассмотрим задачу минимизации критерия.

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

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

соответствующую минимуму (2.33). Интеграл времени [С, tj] разобьем на два интервала [С, С + б] и [С + 8, tj] и запишем.

Тогда, в соответствии с принципом оптимальности, траектории на интервале [С + б, tj] должны начинаться из состояний, а (б), полученных в результате действия управления и [С, С + б] и быть оптимальными относительно, а (б). Следовательно, по определению.

и последнее уравнение примет вид.

Уравнение (2.34) носит название функционального уравнения динамического программирования и эффективно используется для построения вычислительных процедур. Для достаточно малого интервала [С, С + б] справедливо приближенное выражение:

Тогда

После разложения полученного выражения в ряд Тейлора относительно а, С по приращениям 8/(а, п (С)) и 8 получим.

С учетом этого выражения уравнение (2.34) примет вид.

Так как по определению оо (а, С) = min ш (а, С), a 8 — величина конечная, то обозначая и [С, С + 8] = и © = о и проводя простейшие преобразования, получаем уравнение Веллмана

или, поскольку в выражении (2.35) С не зависит от и,.

Уравнение (2.35) дает необходимые и достаточные условия экстремума. Оно эквивалентно двум уравнениям:

Уравнение (2.37) получено из (2.35) подстановкой в него оптимального решения, а уравнение (2.38) —дифференцированием по переменной и.

Связь динамического программирования с классическим вариационным исчислением и принципом максимума. Решим основную задачу классического вариационного исчисления, задачу Эйлера, используя уравнение Веллмана. Требуется найти минимум функционала.

при начальном условии x (t₀) = х°. Сведем эту задачу к задаче минимизации (2.33). Обозначим и = х = /и подставим в уравнение (2.35), тогда.

Последнее эквивалентно, как и уравнение (2.35), двум уравнениям:

Вычислим частную производную (2.39) по х:

и полную производную (2.40) по С.

Раскрывая последнее слагаемое как.

после подстановки полученного результата в уравнение (2.43) и вычитания из уравнения (2.43) уравнения (2.42) получим уравнение Эйлера

Таким образом, можно рассматривать уравнение Эйлера как частный случай уравнения Веллмана. Кроме того, из уравнения Веллмана выводятся все другие уравнения и условия классического вариационного исчисления.

Рассмотрим процедуру получения условия Лежандра. Обозначим содержимое квадратных скобок в уравнение (2.39) в виде некоторой функции Ф (х), минимум которой необходимо отыскать,.

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

Условие F& >0 и есть необходимое условие Лежандра.

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

из состояния X;(t₀) = хр в состояние x,(t₁) = xp за наименьшее время. Разобьем интервал [t₀, t_x] на интервалы [t₀, t] и [t, tj. Введем функцию.

Минимизация (tj — t₀) соответствует максимизации со (х), поэтому функциональное уравнение динамического программирования будет иметь вид

За время (t —1₀) система из состояния x (t₀) перейдет в состояние x (t) — Так как интервал [t₀, t] мал, воспользуемся разложением со (х (0) в ряд Тейлора в окрестности точки t₀ по приращениям (t — t₀)/,(x (t₀), a (t₀)), полученным из условия Тогда

и, подставляя сюда x,(t), получим.

Последнее условие выполняется вдоль оптимальной траектории для любого значения t₀, поэтому заменим u[t₀, t] на и и перепишем уравнение в виде.

или

Сравним уравнение (2.44) с необходимым условием в форме прин;

5(0.

ципа максимума. Если — = ()/, и удовлетворяют уравнениям сопря;

дх,

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

и вычислим.

Выполним преобразование.

Подставляя у, в уравнение (2.45), получим

Уравнение (2.46) представляет собой уравнение импульсов в принципе максимума, a (f, [/) = Н (х, и, |/) является функцией Гамильтона. Таким образом, из уравнения Веллмана выведены необходимые условия принципа максимума.

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

да> д²ы

частных производных —, ——, однако во многих практических зада;

дх дх²

чах это требование невыполнимо.

Уравнение Веллмана, таким образом, представляет собой нелинейное уравнение в частных производных. Оно имеет аналитическое решение лишь в самых простейших случаях. Наиболее удобным методом решения такого типа уравнений является метод характеристик. Однако этот метод сложен и трудоемок. Для приближенного решения можно в ряде случаев пользоваться методом неопределенных коэффициентов, аппроксимируя оо (х) = С₀ + Срс + С^с² + … и разрешая уравнения Веллмана относительно неизвестных значений Q.

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