11.2. Методы решения задач синтеза оптимального управления
Как следует из постановки задачи, при реализации оптимального управления и критерий оптимальности — функционал
— принимает экстремальное значение. Обычно критерий оптимальности составляется так, чтобы условием оптимальности был минимум, когда
можно трактовать как обобщенную «стоимость» достижения цели управления, показатель «потерь».
Задача определения оптимального управления и и оптимальной траектории х сводится к определению функции
которая придает функционалу
экстремальное значение. Если имеется несколько функций
и при одной из них функционал имеет экстремум, то эту функцию следует принять в качестве решения задачи.
В случае сравнительно простых задач с одним или двумя управляющими воздействиями определение управляющего воздействия возможно методом прямого поиска путем многократного нахождения процесса на вычислительной машине при вариации управляющего воздействия.
Метод динамического программирования Веллмана
В основу метода динамического программирования решения вариационных задач положен следующий принцип оптимальности: участок оптимальной траектории от любой ее промежуточной до конечной точки также является оптимальной траекторией между этими точками. Например, если траектория 1—2 между точками Н и К (рис. 11.11) является оптимальной, то оптимальным будет и любой
участок от произвольной точки I до точки К. Справедливость
Рис. 11.11. К принципу оптимальности.
принципа оптимальности очевидна: если траектория 1—2 оптимальна (на ней достигается минимум критерия оптимальности), то оптимальной будет и траектория 2. В противном случае, если бы оптимальной траекторией между точками I и К оказалась какая-то другая траектория 2, то оптимальной траекторией между точками Н и К была бы траектория 1—2, так как для нее критерий оптимальности имел бы меньшее значение, чем для траектории 1—2 за счет меньшего приращения критерия на участке 2. Данный принцип оптимальности справедлив для систем, у которых оптимальная траектория не зависит от предыстории системы, а определяется лишь ее начальным состоянием.
Суть метода динамического программирования поясним на следующем примере (рис. 11.12, а). Пусть требуется перевести некоторый объект из точки Н в точку К. Для этого необходимо сделать
шагов, каждый из которых, кроме последнего
шага, имеет I вариантов. Например, если в результате первого шага объект оказался в точке
1 вертикали 1, то для выполнения второго шага имеется I вариантов. Из точки 2 вертикали 1 второй шаг также может быть сделан в соответствии с одним из
вариантов и т. д. Для каждого варианта шага известна величина приращения
критерия оптимальности.
В данной задаче число возможных вариантов траектории перевода объекта из точки Н в точку К равно числу комбинаций
Из этого числа возможных траекторий требуется определить оптимальную траекторию (оптимальное управление движением объекта), соответствующую минимальному критерию оптимальности
Пусть, например, требуется выбрать маршрут автомобиля, проходящий через заданные точки, на котором достигается минимум расхода топлива или времени движения. Оптимальное решение можно найти перебором возможных вариантов на вычислительной машине, однако при больших значениях
и I, что имеет место при решении большинства реальных задач, это потребовало бы чрезвычайно большого объема вычислений. Решение этой задачи упрощается при использовании
Рис. 11.12. К методу динамического программирования: а — пример задачи; б — определение оптимальной траектории.
Таблица 11.1. К расчету оптимальной траектории
вании метода динамического программирования. Оптимальную траекторию этим методом, согласно сформулированному выше принципу, будем определять путем нахождения оптимальных участков траектории между точками некоторой промежуточной вертикали и конечной точкой К, постепенно переходя от точек одной вертикали к точкам другой в направлении от конечной точки К траектории к ее начальной точке Н. Сперва найдем оптимальные участки траекторий для перехода от каждой точки
вертикали в точку К. Из точки
вертикали, как отмечалось, имеется I вариантов перехода в точку
. Оптимальный участок траектории, дающий минимальное приращение
критерия оптимальности, можно найти перебором из I вариантов или любым другим методом (методом градиента, методом наискорейшего спуска, методом Гаусса-Зейделя и др., которые будут рассмотрены в гл. 12). Пусть оптимальной траекторией, которой соответствует наименьшее приращение
будет, например, траектория
(рис. 11.12, б). Результаты расчетов удобно занести в табл. 11.1.
Из точки
вертикали к точке К можно перейти также по I траекториям. Аналогично находится оптимальная траектория (пусть таковой будет, например, траектория
рис. 11.12, б), которой соответствует наименьшее приращение
критерия оптимальности. Оптимальные траектории от всех других точек
вертикали до точки К находятся таким же образом и результаты расчетов заносятся в таблицу или при использовании ЭВМ вводятся в память машины.
При определении оптимальных траекторий между точками
вертикали и точкой К учитываются полученные значения
для последних двух
и
шагов и найденные ранее оптимальные траектории. Благодаря этому задача нахождения оптимальных траекторий между каждой точкой
вертикали и точкой К упрощается и сводится к выбору оптимальной траектории из I траекторий. Случай, когда оптимальной между точками
и К является траектория
а между точками
— траектория
иллюстрируется на рис.
Аналогично определяются оптимальные траектории из точек
вертикали и т. д., вплоть до начальной точки Н. Для определения оптимальной траектории на последнем этапе необходимо найти минимальную сумму среди I сумм, составленных из приращений
Рис. 11.13. Пример оптимальной траектории.
за первый шаг и найденных перед этим значений
за последующие
шагов из каждой I точек вертикали 1. В результате находим оптимальную траекторию в целом, т. е. от начальной Н до конечной точки К.
Решение данной задачи возможно не только при обратном движении от конца к началу, но и при прямом движении от начала к концу [81].
Таким образом, с помощью метода динамического программирования задача выбора оптимальной траектории из
вариантов сведена к последовательному выбору из I вариантов. Например, если
то выбор из 107 вариантов сводится к последовательному выбору из 10 вариантов.
Для математической формулировки задачи динамического программирования предположим, что шаги в решении задачи представляют фиксированные интервалы времени, т. е. происходит квантование по времени. Требуется найти с учетом ряда ограничений закон управления и
переводящий объект из точки
фазового пространства в точку
при условии обеспечения минимума критерия оптимальности
Здесь и — текущий номер шага (относительное время). Оптимальное управление будем искать, как и раньше, с конечного момента
двигаясь обратно. Находим из I вариантов оптимальное управление и
для каждого дискретного значения
] (для каждой возможной точки
вертикали). Найденные оптимальные значения и
как функции
], фиксируются. Переходя затем к началу
шага, определяем варьированием
минимальное приращение
для каждого значения
(для каждой точки
вертикали) с учетом ранее найденных значений приращений
и т. д., вплоть до начальной точки
. В результате находим оптимальное управление и
сам оптимальный процесс
и суммарную величину критерия оптимальности
Управление записывается в виде последовательности значений и [0], и [1],
например: и
(рис. 11.13).
Таким образом, оптимизация функционала, зависящего от искомой функции управления и
заменяется последовательностью
оптимизаций более простой функции
одной переменной
Благодаря такому упрощению с помощью метода динамического программирования становится возможным решение задач оптимального управления, которые не решаются путем прямой оптимизации исходного функционала классическими методами вариационного исчисления. Метод динамического программирования по существу
Рис. 11.14. К принципу максимума: а — оптимальная по быстродействию траектория; б — оптимальные траектории, соответствующие различным начальным значениям функции
представляет собой метод составления программы для численного решения задачи на цифровых вычислительных машинах. Лишь в простейших случаях данный метод позволяет получить аналитическое выражение искомого решения и выполнять его исследование. С помощью метода динамического программирования возможно решение задач не только оптимального управления, но и многошаговых задач оптимизации из самых различных областей техники.