Деменков Н.П. Вычислительные аспекты решения задач оптимального управления (2007) (1253737), страница 12
Текст из файла (страница 12)
Так, если на каждом шаге возможно k состояний и длякаждого состояния r управлений, то общее число подлежащих рассмотрению вариантов будет k·r·N или r·r·k, если считать, что r = k,т. е. что имеется управление, переводящее каждое состояние в любое новое. При r = N = 10 это дает всего 1000 вариантов.Несмотря на большие достоинства, метод динамического программирования имеет и свои недостатки.Эти недостатки заключаются в том, что для нахождения оптимального управления при некотором начальном состоянии объектаприходится идти от конца процесса к началу, определяя на каждомшаге оптимальные управления для всех возможных на этом шагесостояний объекта, причем до самого последнего момента остается неизвестным, каково же будет оптимальное управление для заданного начального состояния.При этом в конце концов оказывается, что большая часть вычислительной работы проделана напрасно, так как результаты определения оптимального управления для состояний, не лежащихна оптимальной траектории, не используются.3.1.2.
Синтез оптимального регулятораРассмотрим задачу синтеза оптимального управления дискретной системой регулирования. Пусть объект регулирования описывается разностным уравнением85x ( k + 1) = f ( x ( k ), u ( k )),(3.7)где x – n -мерный вектор координат состояния; u – m-мерныйвектор управления.Начальное состояние вектора состояния x задано:x(0) = x0 .Требуется найти такое управление u (k ) (k = 0, 1, 2,..., N − 1),чтобы на соответствующем ему решении уравнения (3.7) функционалJ (x, u ) =N −1∑ Lk ( x (k ), u (k )) + G ( x ( N ))(3.8)k =0достигал минимума.Относительно вектора управления u (k ) будем полагать, что онпринадлежит некоторой замкнутой области U пространства управлений.Рассматриваемая задача представляет собой задачу выбора оптимальной стратегии в многошаговом процессе, определяемомразностным уравнением (3.7).В общем случае поставленная задача может быть решена какзадача на условный экстремум функции mN переменных J ( x , u )при наличии условий (3.7). Однако такое решение очень громоздкоиз-за наличия большого числа переменных.
Метод динамическогопрограммирования позволяет свести задачу к последовательнойминимизации функции m переменных.Допустим, что все значения оптимального управления u (k ),кроме последнего, найдены и система находится в состоянииx ( N − 1) . Согласно принципу оптимальности управление u ( N − 1)должно быть также оптимальным. Это управление должно доставлять минимум функционалу, который для последнего участка траектории имеет видJ N* −1 ( x ( N − 1)) =minu ( N −1)∈UJ N −1 ( x ( N − 1), u ( N − 1)),(3.9)гдеJ N −1 ( x ( N − 1), u ( N − 1)) = LN −1[ x ( N − 1), u ( N − 1)] + G[ x ( N )].86(3.10)Подставив в (3.10) значение x ( N ) из разностного уравнения(3.7), получимJ N* −1 ( x ( N − 1)) =min {LN −1[ x ( N − 1), u ( N − 1)] +u ( N −1)∈U+ G[ f ( x ( N − 1), u ( N − 1))]}.Для определения J N* −1 ( x ( N − 1)) необходимо провести минимизацию функции J N −1 ( x ( N − 1), u ( N − 1)) по m переменнымu1 ( N − 1),..., um ( N − 1).
В процессе минимизации определяется оптимальное управление u ( N − 1) как функция состояния x ( N − 1).Перейдем к предпоследнему участку, для которого начальноезначение будет x ( N − 2). Для последнего и предпоследнего участка траектории функционал (3.9) имеет видJ N − 2 ( x ( N − 2), u ( N − 2)) = LN − 2 [ x ( N − 2), u ( N − 2)] ++ LN −1[ x ( N − 1), u ( N − 1)] + G ( x ( N )).Необходимо определить управления u ( N − 1) и u ( N − 2), которые доставляют минимум этому функционалу.
Согласно принятым обозначениям,J N* − 2 ( x ( N − 2)) ==minu ( N −1)∈Uu ( N − 2)∈UJ N −2 ( x , u ) =min {LN − 2 [ x ( N − 2), u ( N − 2)] +u ( N −1)∈Uu ( N − 2)∈U+ LN −1[ x( N − 1), u ( N − 1)] + G ( x ( N ))}.Минимум по u ( N − 1) для каждого x ( N − 1) был получен выше,а также было определено соответствующее оптимальное управлениеu ( N − 1). Поэтому, учитывая равенство (3.7), можно написатьJ N* − 2 ( x ( N − 2)) =min {LN − 2 [ x ( N − 2), u ( N − 2)] +u ( N − 2)∈U+ J N* −1 ( x ( N − 1))} =min {LN − 2 [ x ( N − 2), u ( N − 2)] +u ( N − 2)∈U+ J N* −1[ f ( x ( N − 2), u ( N − 2))]}.87На этом шаге также проводится минимизация функции m переменных, причем определяется оптимальное управление u ( N − 2).Действуя далее аналогичным образом, мы получим рекуррентнуюформулу для определения на k -м шаге минимального значенияфункционала J N − k ( x , u ) и соответствующего оптимального управления u ( N − k )J N* − k ( x ( N − k )) =+ J N* − k +1[min {LN − k [ x ( N − k ), u ( N − k )] +u ( N − k )∈U(3.11)f ( x ( N − k ), u ( N − k ))]}.Оптимальное управление u ( N − k ) определяется как функциякоординат состояния системы:u ( N − k ) = u ( x ( N − k )).Вычисляя по формуле (3.11) последовательно значения функцииN получим минимальное значениеJ N* − k для k = 1, 2,..., N , при k =J 0* функционала (3.8) для всейтраектории.
Одновременно с этимопределяется оптимальное управление u (0), u (1),..., u ( N − 1) , причемуправление, как указывалось выше, находится в функции координатсистемы, т. е. решается задача синтеза оптимального регулятора.Указанная процедура решения задачи может быть выполнена внекоторых случаях аналитически.
Если это невозможно, то решение проводится с помощью ЭВМ.Из изложенного следует, что применение принципа оптимальности позволяет существенно упростить вычисления по сравнениюс прямым методом решения задачи на условный экстремум. Минимизация функции большого числа переменных (число переменных равно N для скалярного управления и mN – для векторного)сводится к последовательной минимизации функции либо однойпеременной, если управление скалярное, либо m переменных, если управление является n -мерной векторной величиной.Однако этот «одношаговый перебор» осуществляется для всевозможных состояний x и требует значительных объемов памятиЭВМ. Поэтому при большом числе шагов проявляет себя так называемое «проклятие размерности», заключающееся в переполне88нии памяти ЭВМ.
Так, если имеется 4 переменных состояния икаждая переменная представлена значениями 100 = 102, то нужнатаблица 108 данных.В этом отношении имеет преимущества принцип максимума,который открывает путь для построения одной отдельно взятойоптимальной траектории.3.1.3. Оптимизация статических задачМетод динамического программирования как метод оптимизации динамических систем, т. е.
процессов, развивающихся вовремени и описываемых тройкой показателей ( x , u , t), можетприменяться и для оптимизации статических задач, если роль параметра t будет играть некоторый другой параметр, допускающий разбиение задачи оптимизации на последовательность этапов (метод нахождения кратчайшего пути в графе).Рассмотрим задачу распределения ресурсов.В распоряжении инвестора имеется какой-то запас средств (ресурсов) Р, который должен быть распределен между К предприятиями П1, П2,...,Пk. Каждое из предприятий Пi при включении внего каких-то средств X приносит доход, зависящий от X, т.
е.представляющий собой какую-то неубывающую функцию Li(X).Все функции Li(X) (i = 1,2,...,k) заданы. Спрашивается, как нужнораспределить средства Р между предприятиями, чтобы в суммеони дали максимальный доход?Эта задача легко решается методом динамического программирования. Хотя в своей постановке она не содержит упоминанияо времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первыйшаг вложение средств в предприятие П1, за второй – в П2 и т. д.Объект управления в данном случае – средства или ресурсы,которые распределяются. Состояние объекта перед каждым шагом характеризуется одним числом S – наличным запасом еще невложенных средств.
В этой задаче «шаговыми управлениями»являются средства Х1, X2,...,Xk, выделяемые предприятиям. Требуется найти оптимальное управление, т. е. такую совокупность чисел Х1, X2,...,Xk, при которой суммарный доход максимален:kJ = ∑ Li ( X i ) = > max.(3.12)i =189Найдем для каждого i-го шага условный оптимальный выигрыш Ji(S) (от этого шага и до конца), если мы подошли к данномушагу с запасом средств S. Соответствующее этому выигрышу условное оптимальное управление Хi(S) есть средства, вкладываемыев i-е предприятие.Начнем оптимизацию с последнего (k-го) шага.
Пусть мы подошли к этому шагу с остатком средств S. Что нам делать? Очевидно, что нужно вложить всю сумму S целиком в предприятие Пk.Поэтому условное оптимальное управление на k-м шаге – отдатьпоследнему предприятию все имеющиеся средства S, т. е. Xk(S) == S, а условный оптимальный выигрыш Jk(S) = Lk(S).Задаваясь диапазоном значений S (располагая их достаточнотесно), мы для каждого значения S будем знать Xk(S) и Jk(S). Последний шаг оптимизирован.Перейдем к предпоследнему (k – 1)-му шагу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
