Деменков Н.П. Вычислительные аспекты решения задач оптимального управления (2007) (1253737), страница 11
Текст из файла (страница 11)
Обозначим их соответственночерез x и u , а последующее состояние x j +1 = xN −i +1 – через x ′.Тогдаx ′ = T( x , u );(3.2)J i∗ ( x ) = min [L( x , u ) + J i∗−1 ( x ′ )](3.3)uДинамическое программирование является численным методом решения задачи оптимизации управления и поэтому связано сдовольно громоздкими вычислениями.Оптимальное управление на произвольном i-м шаге, отсчитываемом от момента окончания процесса, определяется на основании соотношений (3.2) и (3.3), которые для удобства проведениячисленных расчетов можно записать в несколько иной форме:Ji ( x , u ) = L ( x , u ) + J i*−1 ( x ′ );(3.4)J i* ( x ) = min Ji( x , u ).(3.5)uПеременные x , u могут рассматриваться как элементы конечных множествX = { x (1) , ... , x ( k ) } и U = { u (1) , ... , u ( r ) }.Такое представление упрощает поиск оптимального управления.793.1.1.
Табличный способ оптимизацииЗначение L ( x , u ) удобно вычислить заранее и задать в видетабл. 3.1 на прямом произведении множеств X·U. Эта таблицадолжна храниться в памяти ЭВМ. Таблицу заполняют по ходу вычислений по формулам (3.4) и (3.5). В первых двух столбцах перечислены все возможные комбинации x ∈ X и u ∈ U.
В последнихстолбцах таблицы для каждого значения x ∈ X записывается минимальное значение Ji ( x , u ), т. е. определяется J i* ( x ) иоптимальное управление u ∗ .Таблица 3.1xx (1)ux' = T( x , u )u1T( x 1, u 1 )…T( x 1, u r )T( x 2 , u 1 )…T( x 2 , u r )…urx(2)u1…u…x (k )r…u1…ur…kJi( x , u )J ∗i ( x )u∗L( x 1, u 1 ) Ji–1*( x 1, u 1 )……L( x 1, u r ) Ji–1*( x 1, u r )Ji( x , u 1 )…Ji( x 1, u r )J i∗ ( x 1 )u 1∗L( x 2 , u 1 ) Ji–1*( x 2 , u 1 )……2*rL( x , u ) Ji–1 ( x 2 , u r )Ji( x 2 , u 1 )…Ji( x 2 , u r )J ∗i ( x 2 )u ∗2………L( x , u )Ji – 1*( x′ )…1T( x , u )…T( x k , u r )k…1Ji–1*(kJ i∗1k1(x , u )x , u )L( x , u )…J i∗ ( x k )……kk∗k*rrrL( x , u ) Ji–1 ( x , u ) J i ( x , u )u ∗kПодобные расчеты нужно провести для каждого шага многошагового процесса.
При этом следует учесть, что для определенияJ i∗ ( x ) необходимо предварительно составить таблицу для J i∗−1 ( x ),аналогичную табл. 3.1, так как с ее помощью находят значенияJ i∗−1 ( x′ ) при заполнении таблицы. Следовательно, значения J i∗−1 ( x )должны быть вычислены раньше, чем значения J i∗ ( x ). Отсюда следует, что вычисления функций J i∗ ( x ) нужно начинать с последнегошага многошагового процесса. Замечая при этом, что J0( x ) = 0, заначальный этап расчета нужно взять значение i = 1, для которогоJ1( x , u ) = L( x , u ); J1∗ ( x ) = min L( x , u ).u80(3.6)Далее расчет проводят обычным путем для i = 2, 3, …, N.После того, как выполнены расчеты и составлены таблицы для∗J i ( x ) и u ∗ при i = 1, ...
, N, можно приступить к поиску оптимального управления для всего процесса при данных начальныхусловиях x0 .По таблице для J ∗N ( x ) находим управление u ∗0, соответствующеезаданному вектору x0 , и подсчитываем: x = T( x0 , u0 ). Далее по таблице для JN–1( x ) находим оптимальное управление u 1∗, соответствующее найденному вектору x′, и подсчитываем x2′ = T( x1 , u 1∗ ) и т. д.В результате получаем оптимальное управление u ∗ = ( u ∗0, u 1∗,... , u ∗N −1 ).Рассмотрим процедуру динамического программирования напримере оптимизации задачи набора высоты.Самолет летит со скоростью V0 на высоте h0.
Нужно изменитьего скорость до V1 и высоту до h1 так, чтобы расход горючего наРис. 3.2. Траектория в задаче набора высотыэто изменение был минимальным. Процесс изменения V и h будемизображать на плоскости (V, h) (рис. 3.2).81Проведем дискретизацию переменных, разбив диапазоны изменения V и h на четыре интервала каждый.
При этом дискретныесостояния объекта управления будут представляться узлами сетки.Считаем, что в каждом узле сетки возможно применение толькодвух управлений: Ui = 0 – изменение скорости V; Ui = 1 – изменение только высоты h. Таким образом, множеством допустимыхуправлений будет множество U = {0, 1}.Для того чтобы оценить траекторию, нужно знать расход топливана каждом шаге.
Это и будет целевой функцией L(x, u), значения которой зададим в виде условных чисел на каждом переходе. Для однойиз возможных траекторий, которая соответствует управлению U == (01011001) (на рис. 3.2 траектория отмечена звездочками), суммарный расход топлива, т. е. значение критерия эффективности управления, будет равен L(x, u) = 4 + 4 + 7 + 5 + 7 + 8 + 9 + 8 = 52 .Для того чтобы представить рассматриваемый процесс какмногошаговый, введем подходящий способ описания состоянийсамолета. Дискретные значения V отметим числами от 0 до 4, начиная с конечного значения.
Так же поступим в отношении h. Тогда параметр xij будет означать состояние при V = i и h = j, из которого до конца процесса остается сделать i + j шагов.Обозначим через Xn множество состояний, из которых процессзаканчивается за n шагов. В это множество войдут все те значенияxij, для которых i + j = n. Полагая n = 0, 1, 2,..., получаем X0 = x00;X1 = {x10, x01}; X2 = {x20, x11, x02} и т. д.Теперь можно приступать к решению задачи.
Двигаясь последовательно от конечной точки к начальной и фиксируя в узлах оптимальные для каждого промежуточного состояния затраты, найдем оптимальный маршрут движения самолета.При n = 1 имеем X1 = {x10, x01}; J1 = L(X, U), J1∗ ( x ) = min J1(X, U).UЭти соотношения используем для составления таблицы расчетаоптимального управления на последнем шаге (табл. 3.2) .Таблица 3.2xx10x0182ux'=T(x, u)L(x, u)J ∗0 (x')J1(x, u)J 1∗ (x)U 1∗0101x00––x009––80––09––89––80––1При n = 2 имеем: X2 = {x20, x11, x02}; J2(x, u) = L(x, u) + J1∗ (x);J 2∗ = min J2(x, u).uЭти соотношения используем для составления таблицы расчетаоптимального управления на предпоследнем шаге (табл.
3.3) .Таблица 3.3xux' = T(x, u)L(x, u)J1∗ (x)J2(x, u)J 2∗ (x)U2x10–x01x10–x019–97–69–89–818–1716–1418–16––140–1––1010101x20x11x02Аналогичные расчеты проводятся при n = 3, 4, ... .Расчет оптимального управления за 3 шага до конца приведенв табл. 3.4.Таблица 3.4xx30x21x12x03u01010101x' = T(x, u)L(x, u)J 2 (x, u) = J 2∗ (x)J3(x, u)J 3∗ (x)u3∗x20–x11x20x02x11–x026–8896–318–16181416–1424–24262322–1724–24––22–170–0––1–1В рассматриваемом примере данные, содержащиеся в табл.3.2–3.4, можно изображать непосредственно на плоскости (V, h),указывая значения J ∗n (x) в виде числа в соответствующем узлесетки, а u* – стрелкой в направлении следующего узла (рис. 3.3).Двигаясь последовательно от конечной точки к начальной,фиксируем в узлах оптимальные для каждого промежуточногосостояния затраты.
После того, как значения J ∗n (x) и u* определены для всех узлов сетки, находим оптимальную траекторию83перемещения самолета (на рис. 3.3 траектория отмечена звездочками), двигаясь от начального узла в направлении стрелок, иминимальные затраты, относительная величина которых дляРис. 3.3. Оптимальная траектория в задаче набора высотыданного примера равна J n∗ (x, u ) = 37. Оптимальное управлениеимеет вид u* = (1 1 0 0 0 1 1 0) и состоит из 8 шагов. В самихузлах показана стоимость минимальных затрат при перемещении самолета между соответствующими узлами и конечной точкой (Xk, Yk).Рассмотренный пример хорошо иллюстрирует достоинства метода динамического программирования.Как следует из примера, суть метода динамического программирования заключается в сокращении перебора путем отбрасывания заведомо неоптимальных решений, что выполняется на основепринципа оптимальности.Этот метод, во-первых, снимает проблему абсолютного и относительного минимума, так как из самой процедуры вычисленийясно, что всегда находится абсолютный минимум.Во-вторых, ограничения вида |Ui| ≤ Mi, явившиеся серьезнымпрепятствием для применения вариационных методов, только об84легчают процесс вычислений по методу динамического программирования, так как сужают область допустимых управлений U.Наконец, метод динамического программирования несравненно упрощает поиск оптимального решения по сравнению с методом простого перебора вариантов.
Это можно проиллюстрироватьрасчетом. Если на каждом шаге возможны r различных управлений, то при прямом переборе каждое из этих управлений должнорассматриваться в сочетании со всеми возможными управлениямина всех остальных шагах, что при N-шаговом процессе дает r Nвариантов. Даже при r = 10 и N = 10 получается огромное числовариантов: 1010.В методе динамического программирования при выборе управления на каком-либо шаге для состояния x рассматривают не всевозможные продолжения, а только те, которые соответствуют оптимальным шагам из состояния x '= T( x , u ). Это позволяет исключить из рассмотрения огромное число не представляющих интересавариантов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
