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

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

Р. Веллман так объясняет название метода [5]: «Название принято на основании следующих соображений. Пользуясь популярной ныне терминологией, можно сказать, что рассматриваемые нами задачи являются задачами программирования (т. е. задачами принятия решений). При этом прилагательное «динамический» указывает на то, что мы интересуемся процессами, в которых существенную роль играет время и в которых порядок выполнения операций может оказаться решающим».

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

Будем полагать, что для любой точки х фазового пространства, отличающейся от точки хк, существует оптимальное управление uk(t), под действием которого объект попадает в хк. Время, за которое происходит переход из ,v в хк оптимальным образом, обозначим через 7’(,v), причем переход за время, меньшее, чем мх), невозможен, т. к. это противоречило бы предположению об оптимальности ик (/). Если положить = const, то это уравнение определяет в фазовом пространстве *„) геометрическое место точек, из которых время оптимального перехода в хк постоянно. Такие геометрические места точек называют изохронами.

Введем в рассмотрение функцию 5(дг), которая отличается от функции Г(*) только знаком:

Предположим, что функция S(x) является непрерывной и всюду имеет не-

ds as

прерывные частные производные —,...,-, за исключением точкихк.

дх1 дхп

Если объект начал движение из точки х0 в момент /0 по произвольной фазовой траектории, то для попадания в некоторую точку дг(/) было затрачено время (/ -/0). Если от точки .*(/) объект движется к хк по оптимальной траектории, то на движение затратится время Г[л:(/)]. В результате на переход из х0 в хк затратится время (f-f0) + 7Tjc(f)]. Учитывая, что оптимальное время перехода от*0 до хк равно 7'[.v(/0)], то

Заменив функцию Г на 5 [см. формулу (1.38)] и поделив обе части равенства на величину (t -/0), которая является положительной, получим

или, переходя к пределу при / —> /0, найдем

Производная в левой части этого неравенства существует, поскольку функции 5’(х) и х(У) дифференцируемы, и вычисляется по формуле полной производной:

Полагая, что движение объекта описывается системой уравнений первого порядка вида х] = f, (x9 и), перепишем (1.39):

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

Пусть м(/), *(/) - оптимальный процесс перехода объекта из начального фазового состояния х0 в конечное состояние хк за интервал времени t0k. Тогда л;(/0) = д;0; x(tk) = xk и tk =t0 + Г(;с0). Оптимальная траектория находится по уравнениям объекта х] = /(х,и). Движение по этой траектории от фазовой точки х0 до фазовой точки лг(/) происходит в течение времени (/-f0), а движение от фазовой точки а(/) до фазовой точки хк - в течение времени Г[а(/)]. Поскольку общее время движения от а0 до хк по оптимальной траектории равно Г(а0), то можно записать:

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

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

Переход из точки хо в точку хк

Рис. 1.50. Переход из точки хо в точку хк

Отсюда следует равенство (1.41): если а(/) - оптимальная траектория для t0k, то для любой промежуточной точки t0 k заключительный участок траектории на отрезке /, tk также является оптимальной траекторией. Принцип оптимальности и равенство (1.41), в частности, легко доказываются от противного. Действительно, пусть существует траектория (штриховая линия на рис. 1.50), для которой переход из точки а(/) в точку хк осуществляется за время, меньшее, чем Г(а0)-(/-/0). Тогда, переместившись из х() в a(V) за время (/-/0), а из x{t) в хк> быстрее, чем за время r(x0)-(t-/0) = Г[а(/)], осуществился бы переход из точки а0 в точку хк за время, меньшее, чем Г(а0), что противоречит оптимальности процесса.

Итак, равенство (1.41) доказано. Заменяя Т на S в (1.41):

и дифференцируя по времени, находим

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

с учетом которого запишем соотношения (1.40) и (1.41):

Н(х, и) < 1 - для произвольного допустимого процесса; Н(х,и) = 1 - для оптимального допустимого процесса. Сопоставляя эти условия, запишем

max#(*,w) = 1,

иеП

или с учетом обозначений (1.42):

- для любой ТОЧКИ Л' Ф хк.

Это выражение называют уравнением Веллмана.

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

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

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

ПО

Характерные особенности алгоритмов динамического программирования удобно рассматривать на примере дискретной задачи. Представим себе прямоугольное поле из (п т) клеток: т - по горизонтали

и п - по вертикали. На рис. 1.51 для наглядности показано поле при т = 5 и п — 4. Пусть для каждой клетки задана «стоимость» перехода в любую клетку соседнего справа столбца. Требуется найти оптимальную по «стоимости» траекторию перехода из заданной клетки крайнего левого столбца в заданную клетку крайнего правого столбца.

Если искать оптимальный путь простым перебором, то придется сравнивать между собой п~2) возможных путей, а это очень большое число. При больших т и п прямой перебор нереален. Рассмотрим теперь, что может в этой ситуации дать динамическое программирование. Пусть начальной будет клетка 3, а заданной конечной клетка 18. На последнем шаге в эту клетку можно попасть из клеток 13, 14, 15, 16.

Поиск оптимального пути

Рис. 1.51. Поиск оптимального пути

Запишем «стоимости» перехода из каждой из этих клеток в клетку 18 как характеристики клеток (на рис. 1.51 характеристики указаны в кружках), после чего перейдем к выбору решения на последнем шаге. Из клетки 9 можно перейти в любую из клеток четвертого столбца, а из нее в клетку 18, всего возможны четыре пути. Сравним их между собой и выберем путь с наименьшей стоимостью (с учетом и стоимости движения из клетки четвертого столбца в конечную клетку 18). Стоимость перехода в клетку 18 по наилучшему пути запишем как характеристику клетки 9. Повторим эту процедуру для каждой из клеток третьего столбца. На рис. 1.51 выписаны характеристики всех клеток третьего столбца и для каждой клетки показан оптимальный путь.

Переходя ко второму столбцу, убеждаемся, что для каждой из клеток этого столбца нужно сравнить между собой только четыре варианта пути. Действительно, если, например, находясь в клетке 5, мы избрали путь в клетку 9, то над дальнейшим выбором пути задумываться уже не надо - оптимальный путь из клетки 9 был определен на предыдущем шаге исследования, а согласно принципу оптимальности, этот путь не зависит от того, каким образом мы попали в клетку 9. Заполнив характеристики второго столбца, переходим к последнему шагу решения - складываем стоимости перехода из заданной клетки 3 с характеристиками клеток второго столбца и выбираем наименьшую из сумм. Пусть наименьшая сумма соответствует переходу в клетку 5. Тогда оптимальной траекторией будет последовательность 3-5-9-13-18.

Подсчитаем теперь, сколько сравнений возможных путей необходимо провести при решении общей задачи выбора траектории на поле из т х п клеток. В каждом из столбцов кроме крайних, необходимо сделать п2 сравнений путей (по п путей в каждой из п клеток), в крайних столбцах (исключая последний) по п сравнений, т. с. всего будет л2(/и-3) + 2л сравнений, а это гораздо меньше, чем /7(w-2) путей при прямом переборе. Так, при п = т = 10 при прямом переборе надо сравнить 100000000 путей, а при использовании динамического программирования 720. В сокращении числа кривых сравнения заключается основное достоинство алгоритмов, основанных на идеях динамического программирования.

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >