Диссертация (Математическое моделирование и оптимизация по быстродействию линейных дискретных систем с ограничениями), страница 11

Тоесть далее будем предполагать, что существуют 1 , . . . , ∈ R и 1 , . . . , ∈ Rтакие, чтоU=⋂︁{ ∈ R : (, ) 6 }.(3.1)=1Приведем некоторые свойства выпуклых многогранников в конечномерном пространстве R . Под многогранником будем понимать выпуклую оболочкулюбого конечного множества точекX = conv{1 , . .

. , }.Множество вершин или, что то же самое, множество крайних точек X обозначимследующим образом:Ext X = { ∈ X : ̸ ∃′ , ′′ ∈ X, ∈ (0; 1), 1 ̸= 2 : = ′ + (1 − )′′ }.Хотя выполнено равенствоX = conv Ext X = conv{1 , . . . , },—77—множества Ext X и { 1 , .

. . , } не всегда совпадают. В общем случае вернотолькоExt X ⊂ {1 , . . . , }.Приведем ряд вспомогательных утверждений, необходимых для решенияпоставленной задачи.Лемма 3.1 (Следствие 19.3.2 [69]). Пусть X, Y ⊂ R – многогранни-ки,X = conv{1 , . . . , }, Y = conv{ 1 , . . . , }.Тогда алгебраическая сумма Минковского X + Y тоже является многогранником, причемX + Y = conv{ + , = 1, , = 1, }.Лемма 3.1 гарантирует, что класс многогранников в R замкнут относительно операции сложения, и позволяет достаточно просто построить верхнююоценку множества крайних точек алгебраической суммы двух многогранников.Сформулируем этот факт в виде следующего следствия.Следствие 3.1.

Пусть X, Y ⊂ R – многогранники,X = conv{1 , . . . , }, Y = conv{ 1 , . . . , }.ТогдаExt(X + Y) ⊂ { + , = 1, , = 1, }.Лемма 3.2 (Следствие 19.5.1 [69]). Пусть X ⊂ R – многогранник, ∈ R× – невырожденная матрица.ТогдаExt(X) = (Ext X).Замечание 3.2. Хотя класс всех выпуклых многогранников в R за-мкнут относительно сложения и линейного невырожденного преобразования,он не является линейным пространством.Лемма 3.1 позволяет построить верхнюю оценку множества всех вершиналгебраической суммы двух многогранников. Но многие точки в построенной—78—оценке могут не являться вершинами, причем их количество будет накапливаться с экспоненциальной скоростью.

Для определения множества крайних точекможет быть использован алгоритм быстрой оболочки [80].Сформулируем критерий принадлежности произвольной точки выпуклому многограннику при помощи функционала Минковского:(, X) = inf{ > 0 : ∈ X}.Если множество X ⊂ R допускает представлениеX = conv{1 , . . . , },то из определения следует, что значение функционала Минковского может бытьвычислено как решение задачи линейного программирования→=min,,1 ,..., ∈R∑︁ ,(3.2)=1∑︁ = ,=10 6 , = 1, .Лемма 3.3.

Пусть X = conv{1 , . . . , } ⊂ R , 0 ∈ X, ∈ R . Тогда ∈ X в том и только в том случае, когда (, X) 6 1.Доказательство леммы 3.3. Пусть ∈ X. Тогда существуют1 , . . . , ∈ [0; 1] такие, что=∑︁=1 ,∑︁ = 1.=1То есть существует точка (1, 1 , . . . , ), удовлетворяющая ограничениям задачи (3.2). Тогда(, X) = * 6 1.Пусть (, X) 6 1. Тогда существует точка (* , *1 , . . . , * ) – решениезадачи (3.2), удовлетворяющее условию * 6 1.

То есть существуют *1 , . . . , * ∈—79—[0; 1] такие, что=∑︁* ,=1Обозначим* +1∑︁* = * .=1= 1 − . Тогда*=∑︁* + * +1 · 0,+1∑︁* = 1.=1=1Поскольку 0 ∈ X, верно включение ∈ X.На основе лемм 3.1 и 3.2 сформулируем еще одно свойство класса множеств 0-управляемости.Лемма 3.4. Пусть семейство множеств {X( )}∞ =0 определяется со-отношениями (1.2), множество допустимых значений управлений удовлетворяет (3.1).Тогда для каждого ∈ N множество X( ) – многогранник.Доказательстволеммы3.4.Согласно лемме 3.2 множества−1 U, . . . , − U – многогранники. Откуда в силу леммы 3.1 следует, что алгебраическая сумма−1 U + .

. . + − Uтакже является многогранником. Тогда согласно лемме 1.1 X( ) – многогранник.Используя алгоритм быстрой оболочки, следствие 1.1 и леммы 3.1, 3.2,для произвольного числа ∈ N возможно построить точное описание Ext X( ).Тогда на основании критерия оптимальности управления, базирующегося напонятии класса множеств 0-управляемости, и лемм 3.3 и 3.4 удается сформулировать критерий оптимальности управления в рассматриваемой задаче быстродействия для системы (, U).Для этого определим отображение () = arg min ( + , X( )).∈U—80—С учетом (3.2) и (3.1) вычисление значения () в любой точке ∈ R сводитсяк решению ЗЛП→min ,,1 , ,+=∑︁ ,=1∑︁ 6 ,=10 6 , = 1, ,(, ) 6 , = 1, ,где Ext X( ) = {1 , .

. . , }.Теперь сформулируем теорему, предлагающую вид оптимального управления в задаче быстродействия для системы (1.1) в случае (3.1).определяТеорема 3.1. Пусть траектория системы (1.1) {* ()}=0ется соотношениями* ( + 1) = * () + −−1 (* ()), = 0, − 1,* (0) = 0 .Тогда) * ( ) = 0,) оптимальное управление на -м шаге имеет вид* () = −−1 (* ()).Доказательство теоремы 3.1. Так как * (0) ∈ X( ), то существу-ет вектор ˜ ∈ U такой, что* (0) + ˜ ∈ X( − 1).Тогда в силу леммы 1.1(* (0) + ˜, X( − 1)) 6 1,Откуда согласно определению функционала ()(* (0) + −1 ((0)), X( − 1) 6 (* (0) + ˜, X( − 1) 6 1.—81—* (1) = * (0) + −1 (* (0)) ∈ X( − 1).Продолжая рассуждения по индукции, получим* ( ) ∈ X(0) = {0}.* ( ) = 0.3.2.Алгоритм решения задачи быстродействия в случае линейных ограниченийПостроим алгоритм решения поставленной задачи быстродействия длялинейной дискретной конечномерной автономной системы на основе лемм 3.1,3.2 и теоремы 3.1. Алгоритм состоит из трех этапов, начиная с нулевого.

Нанулевом этапе проверяется равенство 0 = 0 с целью исключить тривиальныеслучаи. На первом этапе посредством последовательного построения множеств0-управляемости определяется оптимальное значение критерия На второмэтапе, исходя из известного значения , последовательно на каждом шагеопределяется оптимальное управление согласно теореме 3.1.Алгоритм 3.1.Этап 0.0.1.

Проверить равенство 0 = 0. Если оно выполнено, то завершитьалгоритм. Иначе перейти к этапу 1.Этап 1.1.1. Положить равным 1.1.2. Построить верхнюю оценку множества крайних точек X( ) согласно леммам 3.1 и 3.2.1.3. Исключить из полученной в шаге 1.2 оценки некрайние точкисогласно алгоритму быстрой оболочки [80].1.4. Согласно лемме 3.3 проверить выполнение условия 0 ∈ X( ),решив ЗЛП (3.2).1.5. Если включение выполнено, то положить значение равным и перейти к этапу 2.

Иначе увеличить значение на единицу и перейти кшагу 1.2.Этап 2.2.1. Положить равным 0.—82—2.2. Вычислить значение оптимального управления на -м шаге * ()согласно теореме 3.1.2.3. Вычислить значение вектора состояния на последующем шаге* ( + 1) согласно рекуррентным соотношениям (1.1).2.4.

Увеличить значение на 1.2.5. Если выполнено равенство = , то завершить алгоритм.Иначе перейти к шагу 2.2.Разработанный алгоритм 3.1 позволяет решить задачу быстродействиядля случая линейных ограничений. При этом для его реализации достаточноисключительно средств линейного программирования.3.3.Модификация алгоритма для случая скалярного управленияВ данном разделе рассмотрим случай одномерного множества допустимых значений управлений, симметричного относительно начала координат:U = conv{−; }.(3.3)Существенным отличием (3.3) от (3.1) является тот факт, что оптимальноеуправление может быть представлено в явном виде, что позволит избежатьрешения ЗЛП на шаге 2.2 алгоритма 3.1.

Данный факт является следствиемтого, что фактически в случае (3.3) управление скалярно, а систему (1.1) можно представить в эквивалентном виде( + 1) = () + (),(0) = 0 ,() ∈ [−1; 1], ∈ N ∪ {0}.Для решения поставленной задачи быстродействия проведем вспомогательные построения.Лемма 3.5. Пусть семейство множеств {X( )}∞ =0 определяется со-отношениями (1.2), множество допустимых значений управлений удовлетворяет условию (3.3).Тогда для каждого ∈ N существуют 1 , . . . ( ) ∈ R такие, что( )X( ) =⋂︁=1{ ∈ R : |( , )| 6∑︁=1|( , − )|}.—83—Доказательство леммы 3.5. Пусть ∈ X( ). Тогда по определениюмножества 0-управляемости существуют (0), .

. . , ( − 1) ∈ [−1; 1] такие, что + −1 (0) + . . . + ( − 1) = 0, (−) + −1 (−(0)) + . . . + (−( − 1)) = 0.Откуда следует, что − ∈ X. То есть множество X симметрично относительноначала координат. С учетом леммы 3.4 множество X( ) представляет собойсимметричный относительно начала координат полиэдр, то есть сущетствуют 1 , . . . , ( ) ∈ R и 1 , . . . , ( ) ∈ [0; +∞) такие, что( )⋂︁X( ) ={ ∈ R : |( , )| 6 }.=1Определим числа , = 1, ( ).

Для этого вычислим макисмальное значение величины ( , ). Согласно лемме 1.1 и условию 3.3 для каждого ∈ X( )существуют 1 , . . . , ∈ [−1; 1] такие, что=∑︁− .=1Тогдаmax ( , ) =∈X( )max1 ,..., ∈[−1;1]( ,∑︁− ) =∑︁=1=1max ( , ) = ∈[−1;1]Таким образом 6∑︁|( , − )|.=1В силу леммы 1.1˜ =∑︁− sign( , − ) ∈ X( ).=1Причем( , ˜) =∑︁|( , − )|,=1то есть >∑︁=1−|( , − )|.∑︁=1|( , − )|.—84—Окончательно, =∑︁|( , − )|, = 1, ( ).=1Для построения оптимального управления определим следующий функционал:1 () =2[︃(︃min=1,( ) : ( ,)̸=0[︃+max=1,( ) : ( ,)̸=0[︃ ]︃]︃∑︁1|( , − )| − sign(( , ))( , ) +|( , )| =1[︃ ]︃]︃)︃∑︁−1|( , − )| + sign(( , ))( , ).|( , )| =1Теорема 3.2.

Пусть траектория системы (1.1) {* ()}=0определя-ется соотношениями* ( + 1) = * () + −−1 (* ()), = 0, − 1,* (0) = 0 .Тогда) * ( ) = 0,) оптимальное управление на -м шаге имеет вид* () = −−1 (* ()).Доказательство теоремы 3.2. Так как * (0) ∈ X( ), то существу-ет * ∈ [−1; 1] такой, что* (0) + * ∈ X( − 1).Согласно лемме 3.5 верно представление( −1)X( − 1) =⋂︁{ : ( , ) 6=1∑︁−1|( , − )|}.=1Тогда для всех = 1, ( − 1)|( , * (0) + * )| 6∑︁−1|( , − )|,=1−∑︁−1=1|( , − )| 6 ( , * (0)) + * ( , ) 6∑︁−1=1|( , − )|,—85—−∑︁−1−**|( , )| − ( , (0)) 6 ( , ) 6∑︁−1=1|( , − )| − ( , (0)),=1⎧[︃ −1]︃⎪∑︁1⎪⎪⎪|( , − )| − ( , * (0)) , ( , ) > 0,⎪⎨ ( , )=1* 6[︃ −1]︃⎪∑︁⎪−1⎪⎪|( , − )| + ( , * (0)) , ( , ) < 0,⎪⎩ ( , )=1⎧[︃ −1]︃⎪∑︁1⎪⎪⎪|( , − )| − ( , * (0)) , ( , ) < 0,⎪⎨ ( , )=1* >[︃ −1]︃⎪∑︁⎪−1⎪⎪|( , − )| + ( , * (0)) , ( , ) > 0,⎪⎩ ( , )=1⎧[︃ −1]︃⎪∑︁1⎪⎪⎪|( , − )| − sign(( , ))( , * (0)) ,* 6⎪⎨|( , )|=1]︃[︃ −1⎪∑︁⎪−1⎪*⎪|( , − )| + sign(( , ))( , * (0)) .⎪⎩ > |( , )|=1Введем обозначения−11 =max=1,( −1) : ( ,)̸=0 |( , )|[︃12 =min=1,( −1) : ( ,)̸=0 |( , )|[︃ −1∑︁]︃|( , − )| + sign(( , ))( , * (0)) ,=1 −1∑︁]︃−*|( , )| − sign(( , ))( , (0)) .=1Тогда управление * (0) будет оптимальным в том и только в том случае, когда * (0) ∈ [1 ; 2 ].

По определению функционала () −1 () =1 + 2∈ [1 ; 2 ],2Тогда* (1) = * (0) + −1 (* (0)) ∈ X( − 1).Продолжая рассуждения по индукции, получим, что * ( ) ∈ X(0) ={0}.При использовании теоремы 3.2 вместо теоремы 3.1 на шаге 2.2 алгоритма 3.1 удается избежать решения ЗЛП, что увеличивает скорость работыалгоритма.—86—3.4.Метод сведения решения задачи быстродействия для системы с выпуклым множеством допустимых значенийуправлений к случаю линейных ограниченийМетод сведения базируется на идее проведения полиэдральной аппроксимации выпуклого компактного множества допустимых значений управленийU системы (1.1).