Перейти к основному содержанию

Моделирование и анализ данных
2025. Том 15. № 4. С. 104–121
doi:10.17759/mda.2025150407
ISSN: 2219-3758 / 2311-9454 (online)

Анализ сложности алгоритма решения задачи быстродействия для линейных дискретных систем с линейными ограничениями

 
Аудио генерируется искусственным интеллектом
  630 мин. чтения
11

,

PDF (RUS)
GS
Информация
в Google Scholar
Метрики

Резюме

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

Общая информация

Ключевые слова: оптимальное управление, задача быстродействия, выпуклая оболочка, задача линейного программирования, вычислительная сложность

Рубрика издания: Численные методы

Тип материала: научная статья

DOI: https://doi.org/10.17759/mda.2025150407

Поступила в редакцию 24.10.2025

Поступила после рецензирования 10.11.2025

Принята к публикации

Опубликована

Для цитаты: Камчиев, Н.А., Ибрагимов, Д.Н. (2025). Анализ сложности алгоритма решения задачи быстродействия для линейных дискретных систем с линейными ограничениями. Моделирование и анализ данных, 15(4), 104–121. https://doi.org/10.17759/mda.2025150407

© Камчиев Н.А., Ибрагимов Д.Н., 2025

Лицензия: CC BY-NC 4.0

Полный текст

Введение

Задача быстродействия – классическая проблема теории оптимального управления, обладающая естественным функционалом качества – числом шагов, необходимым для достижения системой начала координат. В дискретном времени при построении оптимальных по быстродействию процессов возникает ряд сложностей, из-за которых традиционные методы оптимального управления и выпуклого программирования оказываются неприменимыми. Одной из таких особенностей является дискретный функционал качества, значение которого в свою очередь определяет число управляющих воздействий. Этот факт вынуждает вычислять время быстродействия перебором, решая при каждом фиксированном временном горизонте двухточечную задачу. С другой стороны, даже если наименьшее число шагов, для которого систему можно перевести в нуль, вычислено, почти для всех начальных состояний множество оптимальных процессов является бесконечным, что делает проблематичным применение классических методов решения одноэкстремальных задач (Беллман, 1960; Пропой, 1973).

Известные результаты, посвященные задаче быстродействия для систем с дискретным временем, представлены крайне небольшим набором статей и в основном исследуют различные частные постановки. В (Мороз, 1965) обсуждаются только трёхмерные системы со скалярным управлением, (Desoer, Wing, 1961; Lin, 1986) рассматривают уже системы произвольной размерности, но всё ещё со скалярным управлением. Работы (Bashein, 1971; Vlieger, Verbruggen, Bruijn, 1982) сосредоточены на численных методах построения оптимального управления на основе линейного программирования. В статьях (Lasserre, 1993; Stamnes, Callafon, 2007) управление предполагается векторным, но исключительно с ограничениями в форме зонотопов. В свою очередь (Kolev, 1978; Scott, 1986) предлагают регуляризацию задачи быстродействия при помощи введения дополнительного критерия качества. Работы (Blanchini, 1991; Blanchini, Ukovich, 1993) допускают уже геометрические полиэдральные ограничения на управление. В (Keerthi, Gilbert, 1987) предполагают смешанные полиэдральные ограничения, накладываемые одновременно на управление и состояние. Из наиболее актуальных работ можно выделить статьи (Abdelhak, Rachik, 2010; Amato и др., 2022; Chen, Bako, Lecoeuche, 2012; Lee, Haddad, 2022; Yang, Xia, Geng, 2019), продолжающие ранее приведённые результаты.

Также в настоящее время вновь возник интерес к задаче быстродействия, в том числе и для систем с непрерывным временем, в связи с возросшими мощностями ЭВМ, что позволило эффективно проводить дискретизацию исходной системы, сводя её к эквивалентным конечно-разностным соотношениям. Такой подход нашёл отражение в статьях (Leomanni, Costante, Ferrante, 2022; Lini, Consolini, Piazzi, 2009; Краснощеченко, 2014; Сазанова, 2002).

Все описанные выше работы объединены общим подходом к решению, основанным на использовании аппарата множеств достижимости и 0-управляемости, где под множеством достижимости понимается совокупность тех терминальных состояний, в которые можно перевести систему из заданного начального за фиксированное время, а под множеством 0-управляемости – совокупность тех начальных состояний, из которых можно перевести систему в начало координат за фиксированное время. Данный подход в наиболее общем виде сформулирован в (Ибрагимов, Новожилкин, Порцева, 2021) и алгоритмически представлен в (Ибрагимов, Кибзун, 2025).

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

Постановка задачи

Рассматривается линейная дискретная система управления с линейными ограничениями на управление ( A , U ) :
x ( k + 1 ) = Ax ( k ) + u ( k ) ,
x ( 0 ) = x 0 , u ( k ) ∈ U , k ∈ N ∪ { 0 } , ( 1 )
U = conv { u 1 , … , u M } ,
где x ( k ) ∈ R n – вектор состояния системы, U – множество допустимых значений управлений системы, u ( k ) ∈ U – управление, A ∈ R n × n – матрица системы. Предполагается, что множество допустимых значений управлений U ⊂ R n является выпуклым и компактным, 0 является относительно внтуренней точкой U , det A ≠ 0 .
Для системы ( A , U ) решается задача быстродействия, т.е. требуется вычислить минимальное число шагов N min , за которое можно перевести систему из заданного начального состояния x 0 ∈ R n в начало координат, а также построить процесс { x ( k ) , u ( k − 1 ) , x 0 } k = 1 N min , удовлетворяющий условию x ( N min ) = 0 , который будем называть оптимальным. Предполагается, что N min < ∞ .
Множество состояний, из которых систему ( A , U ) можно перевести в 0 за N шагов посредством выбора допустимого управления называется множеством 0-управляемости за N шагов:
X ( N ) = { { x 0 ∈ R n : ∃ u ( 0 ) , … , u ( N − 1 ) ∈ U : x ( N ) = 0 } , N ∈ N , { 0 } , N = 0. ( 2 )
Тогда N min можно вычислить с помощью класса множеств 0-управляемости:
N min = min { N ∈ N ∪ { 0 } : x 0 ∈ X ( N ) } . ( 3 )

Известно аналитическое описание класса множеств 0-управляемости (2).

Лемма 1 (Ибрагимов, Сиротин, 2017, лемма 1). Пусть класс множеств { X ( N ) } N = 0 ∞ определяется соотношениями (2). Тогда для всех N ∈ N справедливо представление
X ( N ) = − ∑ i = 1 N A − i U , X ( N ) = A − 1 X ( N − 1 ) + ( − A − 1 U ) . ( 4 )
В (Ибрагимов, Новожилкин, Порцева, 2021) подробно рассмотрен подход к решению задачи быстродействия для системы (1) в случае, когда на управление на каждом шаге наложены только линейные ограничения, т.е. множество допустимых значений управлений U ⊂ R n представляет собой полиэдр. В этом случае задача быстродействия может быть сведена к ряду задач линейного программирования.
Функционалом Минковского для выпуклого и компактного X ⊂ R n называется
μ ( x , X ) = inf { t > 0 : x ∈ t X } . ( 5 )
Заметим, что по определению x ∈ X тогда и только тогда, когда μ ( x , X ) ≤ 1 .
Для произвольных N ∈ N и k = 0 , N − 1 ¯ определим отображение S N , k : R n → R n следующим образом:
S N , k ( x ) = arg min u ∈ U μ ( Ax + u , X ( N − k − 1 ) ) . ( 6 )

Как продемонстрировано в (Ибрагимов, Новожилкин, Порцева, 2021), если известно представление

X ( N − k − 1 ) = conv { x 1 ( N − k − 1 ) , … , x L ( N − k − 1 ) ( N − k − 1 ) } , ( 7 )
Ext X ( N − k − 1 ) = { x 1 ( N − k − 1 ) , … , x L ( N − k − 1 ) ( N − k − 1 ) } , ( 8 )
card Ext X ( N − k − 1 ) = L ( N − k − 1 ) , ( 9 )
то вычисление отображения S N , k для каждого x ∈ R n сводится к решению задачи линейного программирования:
min λ 1 , … , λ L ( N − k − 1 ) , μ 1 , … , μ M , u ∑ i = 1 L ( N − k − 1 ) λ i , Ax + u = ∑ i = 1 L ( N − k − 1 ) λ i x i ( N − k − 1 ) , u = ∑ i = 1 M μ j u j , λ i ≥ 0 , i = 1 , L ( N − k − 1 ) ¯ , μ j ≥ 0 , j = 1 , M ¯ . ( 10 )
Теорема 1 ((Ибрагимов, Новожилкин, Порцева, 2021). Пусть для системы (1) процесс { x ( k ) , u ( k − 1 ) , x 0 } k = 0 N min определяется соотношениями
x ( k + 1 ) = A x ( k ) + S N min , k ( x ( k ) ) , k = 0 , N min − 1 ¯ , x ( 0 ) = x 0 . ( 11 )

Тогда

  1. 1. x ( N min ) = 0 ;
  2. 2.оптимальное по быстродействию позиционное управление на k -м шаге имеет вид u ( k , x ( k ) ) = S N min , k ( x ( k ) ) .

Целью данной статьи является определение вычислительной сложности использования теоремы 1 для решения задачи быстродействия.

Алгоритм решения задачи быстродействия

Учтем, что в силу (3) и (5)

N min = min { N ∈ N ∪ { 0 } : μ ( x 0 , X ( N ) ) ≤ 1 } . ( 12 )

Теперь представить теорему 1 в виде следующего алгоритма решения задачи быстродействия.

Алгоритм 1 (решения задачи быстродействия).

Пусть задана матрица системы A , множество U = conv { u 1 , … u M } и начальное состояние x 0 .
  1. Положить  N = 1 и перейти к шагу 2.
  2. Построить множество 0-управляемости  X ( N ) = A − 1 X ( N − 1 ) + ( − A − 1 U ) .
  3. Вычислить функционал Минковского  t = μ ( x 0 , X ( N ) ) .
  4. Если  t > 1 , то увеличить N на 1 и перейти к шагу 2.
    Иначе N min = N и перейти к шагу 5.
  5. Положить  k = 0 , x ( 0 ) = x 0 .
  6. Построить оптимальное управление  u ( k ) .
  7. Применить управление:  x ( k + 1 ) = A x ( k ) + u ( k ) .
  8. Если  k = N min , то завершить цикл и алгоритм.
    Иначе увеличить k на 1 и перейти к шагу 6.

Подробно рассмотрим математические операции, исполняемые в алгоритме 1. Согласно теореме 1 нахождение оптимального управления на 6-м шаге алгоритма сводится к вычислению функционала Минковского:

u ( k , x ( k ) ) = arg min u ∈ U μ ( A x ( k ) + u , X ( N − k − 1 ) ) , ( 13 )
т.е. может быть представлено в качестве решения ряда задач линейного программирования (10). Вычисление функционала Минковского для определения N min на 3-м шаге также сводится к решению задачи линейного программирования (ЗЛП). Действительно μ ( x , X ) для X = conv { x 1 , … , x L } может быть найдено как решение следующей задачи:
∑ i = 1 L λ i → min , ∑ i i λ i x i = x , λ 1 , … , λ L ≥ 0. ( 14 )

В свою очередь в силу леммы 1 построение множеств 0-управляемости, а именно нахождение суммы по Минковскому, может быть выполнено с помощью алгоритма быстрой оболочки Quickhull (Barber, Dobkin, Huhdanpaa, 1996). На практике Quickhull часто показывает лучшие результаты по сравнению с другими алгоритмами.

Таким образом, применение алгоритма 1 предполагает многократное решение ЗЛП и сложение многогранников по Минковскому. Остановимся подробнее на оценки сложности данных математических операций.

Оценка сложности алгоритма

Обозначим через LPP ( k , n ) сложность решения ЗЛП с k неотрицательными переменными оптимизации и n ограничениями вида равенство, через CH ( n , M 1 , M 2 , M 3 ) – сложность алгоритма быстрой оболочки при сложении двух n -мерных многогранников с M 1 и M 2 вершинами соответственно, где в результате сложения получается многогранник с M 3 вершинами. В терминах леммы 1 и представления (7) –(9) верно, что M 1 = M , M 2 = L ( N − 1 ) , M 3 = L ( N ) .

В (Barber, Dobkin, Huhdanpaa, 1996) была сформулирована теорема о сложности алгоритма Quickhull.

Теорема 2 (Barber, Dobkin, Huhdanpaa, 1996). Пусть M 1 , M 2 , M 3 ∈ N . Тогда наихудшая сложность алгоритма не будет превышать
CH ( n , M 1 , M 2 , M 3 ) = { O ( M 1 ∙ M 2 ∙ log M 3 ) , n ≤ 3 , O ( M 1 ∙ M 2 ∙ M 3 [ n 2 ] − 1 [ n 2 ] ! ) , n ≥ 4. ( 15 )

В рамках алгоритма 1 теорема 2 позволит оценить сложность шага 2 следующей величиной:

CH ( n , M , L ( N − 1 ) , L ( N ) ) = { O ( L ( N − 1 ) ∙ M ∙ log L ( N ) ) , n ≤ 3 , O ( L ( N − 1 ) ∙ M ∙ L ( N ) [ n 2 ] − 1 [ n 2 ] ! ) , n ≥ 4. ( 16 )
Рассмотрим теперь сложность решения ЗЛП. Вообще говоря, LPP ( k , n ) существенно зависит от используемого метода линейного программирования. Так симплекс-метод (Схрейвер, 1991) теоретически предполагает LPP ( k , n ) = O ( 2 k ) , однако практически для большинства задач демонстрирует вычислительную сложность порядка O ( k 3 ) . Методы внутренней точки (Karmarkar, 1984) обладают сложностью LPP ( k , n ) = O ( k 3 ,5 ∙ L ) , где L – количество бит для представления задачи:
L = ( 1 + log ( 1 + n ) ) + ( 1 + log ( 1 + m ) ) + ∑ i = 1 m ∑ j = 1 d ( 1 + log ( | a ij | + 1 ) ) + + ∑ i = 1 m ( 1 + log ( | b i | + 1 ) ) + ∑ j = 1 d ( 1 + log ( | c j | + 1 ) ) . ( 17 ) Здесь a ij – коэффициенты матрицы ограничений, b i – коэффициенты вектора правых частей ограничений, c j – коэффициенты целевой функции. Метод эллипсоидов (Khachiyan, 1980) допускают сложность LPP ( k , n ) = O ( k 6 ∙ L ) .

В общем виде можно получить следующие утверждения о сложности алгоритма 1.

Лемма 2. Сложность этапов 2–4 алгоритма 1 решения задачи быстродействия не превышает

N min ∙ ( LPP ( L ( N min ) , n ) + O ( n 2 ∙ L ( N min − 1 ) ) + CH ( n , M , L ( N min − 1 ) , L ( N min ) ) ) . ( 18 )
Доказательство. На шаге 2 алгоритма 1 производится построение множеств 0-управляемости по формуле X ( N ) = A − 1 X ( N − 1 ) + ( − A − 1 U ) . Данное действие включает в себя перемножение матриц и сумму по Минковскому. Рассмотрим сложность каждой операции по отдельности:
  • сложность умножения множества  X ( N − 1 ) на матрицу A ∈ R n × n составляет O ( n 2 ∙ L ( N − 1 ) ) , множества U на матрицу A ∈ R n × n – O ( n 2 ∙ M ) ;
  • сумма по Минковскому состоит из сложения каждой вершины  A − 1 X ( N − 1 ) с каждой вершиной ( − A − 1 U ) , которое обладает сложностью O ( L ( N − 1 ) ∙ M ) , и применения алгоритма Quickhull к результирующему многограннику, что приводит к сложности CH ( n , M , L ( N − 1 ) , L ( N ) ) .

Таким образом, итоговая сложность шага 2 не будет превышать

O ( n 2 ∙ M ) + O ( n 2 ∙ L ( N − 1 ) ) + O ( L ( N − 1 ) ∙ M ) + CH ( n , M , L ( N − 1 ) , L ( N ) ) = = O ( n 2 ∙ L ( N − 1 ) ) + CH ( n , M , L ( N − 1 ) , L ( N ) ) . ( 19 )
На шаге 3 решается ЗЛП с L ( N ) переменными и n ограничениями вида равенство, что приводит к сложности LPP ( L ( N ) , n ) .
Этапы 2 и 3 повторяются N min раз. Значит, суммарная сложность цикла этапов 2 и 3, состоящего из N min итераций не будет превышать
∑ N = 1 N min ( LPP ( L ( N ) , n ) + O ( n 2 ∙ L ( N − 1 ) ) + CH ( n , M , L ( N − 1 ) , L ( N ) ) ) ≤ ≤ N min ∙ ( LPP ( L ( N min ) , n ) + O ( n 2 ∙ L ( N min − 1 ) ) + CH ( n , M , L ( N min − 1 ) , L ( N min ) ) ) . ( 20 )

Лемма 2 доказана.

□

Лемма 3. Сложность этапов 6–8 алгоритма 1 решения задачи быстродействия не превышает

N min ( LPP ( L ( N min − 1 ) + M , n + 1 ) + O ( n 2 ) ) . ( 21 )
Доказательство. На этапе 6 решается ЗЛП с ( L ( N min − k − 1 ) + M ) переменными и ( n + 1 ) ограничением, т.е. сложность этого шага составит LPP ( L ( N min − k − 1 ) + M , n + 1 ) .
На шаге 7 перемножается матрица с вектором со сложностью O ( n 2 ) . Этапы 6 и 7 так же повторяются N min раз. Суммарная сложность цикла шагов 6 и 7 не превышает

Лемма 3 доказана.

□

Теорема 3. (Оценка сложности алгоритма 1)

Пусть A ∈ R n × n , det A ≠ 0 , U = conv { u 1 , … , u M } – множество допустимых значений управлений, x 0 – начальное состояние. Тогда сложность алгоритма 1 решения задачи быстродействия для линейных дискретных систем с линейными ограничениями не превышает
N min ∙ ( LPP ( L ( N min ) , n ) + O ( n 2 ∙ L ( N min − 1 ) ) + CH ( n , M , L ( N min − 1 ) , L ( N min ) ) + LPP ( L ( N min − 1 ) + M , n + 1 ) ) . ( 23 )

Доказательство. Доказательство теоремы 1 вытекает непосредственно из лемм 2 и 3 в результате сложения представленных в них оценок сложности.

□

Замечание 1. Количество вершин многогранника на шаге N можно ограничить соотношением (Weibel, 2007)
L ( N ) ≤ ( 1 − 1 ( n + 1 ) N ) ∙ M N . ( 24 )
Можно учесть полученные ранее выражения для LPP ( k , n ) и CH ( n , M 1 , M 2 , M 3 ) , чтобы уточнить сложность алгоритма 1 при n ≤ 3 . Будем полагать, что для решения ЗЛП используется метод внутренней точки как один из наиболее распространенных в различных прикладных математических средах. Тогда можно принять LPP ( L ( N min ) , n ) = O ( L ( N min ) 4.5 n ) , LPP ( L ( N min − 1 ) + M , n + 1 ) = O ( ( L ( N min − 1 ) + M ) 4 ,5 ∙ ( n + 1 ) ) .

Теперь распишем сложность алгоритма Quickhull:

CH ( n , M , L ( N min − 1 ) , L ( N min ) ) = O ( n 2 ∙ L ( N min − 1 ) ) + O ( L ( N min − 1 ) ∙ M ∙ log L ( N min ) ) . ( 25 )
Тогда сложность алгоритма при n ≤ 3 оценивается следующим образом:
N min ∙ ( LPP ( L ( N min ) , n ) + CH ( n , M , L ( N min − 1 ) , L ( N min ) ) + + O ( n 2 ) + LPP ( L ( N min − 1 ) + M , n + 1 ) ) = = N min ( O ( L ( N min ) 4 ,5 ∙ n ) + O ( n 2 ∙ L ( N min − 1 ) ) + + O ( L ( N min − 1 ) ∙ M log L ( N min ) ) + O ( n 2 ) + + O ( ( L ( N min − 1 ) + M ) 4 ,5 ∙ ( n + 1 ) ) ) = = N min ( O ( n 2 ∙ L ( N min − 1 ) ) + O ( L ( N min − 1 ) ∙ M ∙ log L ( N min ) ) + O ( ( L ( N min − 1 ) + M ) 4 ,5 ∙ ( n + 1 ) ) ) . ( 26 )
Окончательно с учётом замечания 1 можно получить следующую оценку сложности:
N min ( O ( n 2 ∙ ( 1 − 1 ( n + 1 ) N min − 1 ) ∙ M N min − 1 ) + O ( ( 1 − 1 ( n + 1 ) N min − 1 ) log ( ( 1 − 1 ( n + 1 ) N min ) ∙ M N min ) M N min ) + O ( ( ( 1 − 1 ( n + 1 ) N min − 1 ) ∙ M N min − 1 + M ) 4 ,5 ∙ ( n + 1 ) ) ) .
Обозначим c 1 = ( 1 − 1 ( n + 1 ) N min ) и c 2 = ( 1 − 1 ( n + 1 ) N min − 1 ) . При M ≥ 4 , N min ≥ 1 доминирующим в данной оценке является член ( с 2 ∙ M N min − 1 + M ) 4 ,5 ∙ ( n + 1 ) . Остальные слагаемые лишь вносят небольшие поправки. Это определяет экспоненциальный рост сложности в зависимости от времени быстродействия и полиномиальный в зависимости от сложности ограничений.

Полученная верхняя граница задаёт необходимый запас вычислительной мощности при практическом планировании вычислительных экспериментов. В следующем разделе мы проверим адекватность этой оценки на серии задач размерностей 2 и 3, сравнив фактическое время работы программы с теоретической оценкой.

Численное моделирование

Рассмотрим пример решения задачи быстродействия по алгоритму 1 для n = 2 со следующими входными данными:
x 0 = ( 3 ,53 2 ,37 ) , A = ( 0 ,97 86 0,014 3 − 0 ,00 54 0,997 3 ) ,
U = conv { ( 0 , 651 0,608 ) , ( − 0,871 0,320 ) , ( − 0,774 − 0,364 ) , ( − 0,651 − 0,608 ) , ( 0,871 − 0 ,32 ) , ( 0,774 0,364 ) } .
На рис. 1 изображены множества 0-управляемости и траектория, по которой данная двумерная система перемещается в начало координат за N mi n = 5 шагов. Время решения составило 0 ,11 с. Для надёжности в дальнейшем анализе аналогичные эксперименты были повторены для ещё четырёх случайно сгенерированных 2-мерных систем, на массиве из 100 различных начальных состояний, что дало в сумме 500 решенных задач быстродействия. Такое количество экспериментов позволяет проследить влияние параметров M и N min на время работы алгоритма.
 
Рис. 1
Рис. 1. Пример решения задачи быстродействия при n = 2
Fig. 1. An example of solving a time-optimization problem for n = 2  
 
Алгоритм 1 был реализован в среде разработки Maple с использованием встроенных библиотек (LinearAlgebra, Optimization и др.). Расчеты проводились на случайно сгенерированных матрицах систимы  A , множествах ограничений на управление U и начальных состояниях x 0 . Многогранник U хранится в памяти ЭВМ в виде матрицы, столбцы которой представляют собой его вершины.
  • В программе реализованы следующие функции:
  • вычисление функционала Минковского (принимает на вход точку и множество);
  • вычисление суммы множеств по Минковскому (принимает на вход два множества);
  • генерация матрицы системы  A (принимает на вход размерность задачи);генерация множества управлений  U (принимает на вход размерность задачи);
  • генерация начального состояния  x 0 (принимает на вход размерность).

В рамках численного моделирования вычислялось время решения задач быстродействия для размерностей вектора состояния 2, 3 и 4.

На рис. 2 представлена зависимость времени решения двумерной задачи быстродействия от количества вершин M многогранника U и минимального числа шагов N min . Было сгенерировано 5 систем с различными A , U и по 100 начальных состояний в каждой системе. То есть было решено 500 задач быстродействия при n = 2 .
Рис. 2
Рис. 2. Зависимость времени решения от N_min и M при n=2
Fig. 2. The dependence of the decision time on N_min and M for n=2
 
и M при n = 2
Fig*. 2. The dependence of the decision time on  N min and M    n = 2
 
 
В трехмерном случае зависимость времени решения задачи быстродействия от параметров системы представлена на рис. 3. Было сгенерировано также 5 систем с различными  A , U , для каждой из которых было сгенерировано по 50 начальных состояний. То есть было решено 250 задач быстродействия при n = 3 .
Рис. 3
Рис. 3. Зависимость времени решения от N_min и M при n=3
Fig. 3. The dependence of the decision time on N_min and M for n=3

и

M

при

n = 3
Fig*. 3. The dependence of the decision time on  N min and M for n = 3
 
При  n = 4 расчет произведен только для случая, когда множество U является многогранником с M = 8 вершинами, начальных состояний было сгенерировано 20. Это связано с тем, что вычисление множеств 0-управляемости для задач размерности n = 4 весьма ресурсоемко. Данная ситуация может быть решена использованием более оптимизированного алгоритма вычисления выпуклой оболочки множества. График зависимости времени решения от N min представлен рис. 4.
Рис. 4
Рис. 4. Зависимость времени решения от N_min при n=4
Fig. 4. The dependence of the decision time on N_min for n=4

при

n = 4
Fig*. 4. The dependence of the decision time on  N min for n = 4
 
По графикам видно, что на временную сложность решения задачи быстродействия влияет не только размерность задачи  n , но и количество вершин многогранника U . Это закономерно, так как увеличение числа вершин  M увеличивает число вершин каждого множества 0-управляемости и, следовательно, все ключевые операции алгоритма требуют больше вычислительных ресурсов.
Во‑первых, при построении сумм Минковского на шаге 2 алгоритма количество точек в объединённом множестве пропорционально L ( N − 1 ) ∙ M , а последующая процедура Quickhull должна проверить и отфильтровать каждую из них. Поэтому даже при фиксированной размерности вычислительная нагрузка растёт.
Во‑вторых, рост M напрямую отражается и на сложности решения задач линейного программирования, к которой сводится вычислении функционала Минковского.
В совокупности эти факторы объясняют наблюдаемый на графиках эффект: кривые для разных M значительно расходятся, и при фиксированных n и N min время решения оказывается пропорционально числу вершин многогранника U .

Заключение

В проведен анализ вычислительной сложности алгоритма построения оптимального по быстродействию управления для линейных дискретных систем. В частности, реализован и протестирован алгоритм решения данной задачи, основанный на поэтапном построении множеств 0-управляемости, проведены численные эксперименты для систем размерности n = 2 , 3 , 4 при различных начальных условиях и множествах допустимых значений управлений. Эти эксперименты показали, что время решения задачи быстродействия существенно зависит от параметров системы: с ростом размерности n и сложности множества U (числа вершин M ) вычислительные затраты увеличиваются. Выявлено, что при относительно малых n (до 3–4) алгоритм выполняется за приемлемое время (доли секунды или несколько секунд), однако дальнейшее увеличение размерности приводит к экспоненциальному росту времени вычислений. Это соответствует теоретической оценке сложности.

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

Литература

  1. Беллман, Р. (1960). Динамическое программирование. М.: ИИЛ.
    Bellman, R. (1960). Dynamic programming. Moscow: IIL. (In Russ.).
  2. Ибрагимов Д.Н., Кибзун А.И. (2025). Программная реализация алгоритмов решения задачи быстродействия для линейных систем с дискретным временем. Вестник компьютерных и информационных технологий, 22(3), 12–20. 10.14489/vkit.2025.03.pp.012-020
    Ibragimov D.N., Kibzun A.I. (2025). Software implementation of algorithms for solving the performance problem for linear discrete-time systems. Herald of Computer and Information Technologies (Russia), 22(3), 12–20. 10.14489/vkit.2025.03.pp.012-020 (In Russ.).
  3. Ибрагимов Д.Н., Новожилкин Н.М., Порцева Е.Ю. (2021). О достаточных условиях оптимальности гарантирующего управления в задаче быстродействия для линейной нестационарной дискретной системы с ограниченным управлением. АиТ, (12), 48–72. 10.1134/S000511792112002X
    Ibragimov, D.N., Novozhilin, N.M., Portseva, E.Y. (2021). On Sufficient Optimality Conditions for a Guaranteed Control in the Speed Problem for a Linear Time-Varying Discrete-Time System with Bounded Control. Autom Remote Control, (82), 2076–2096. https://doi.org/10.1134/S000511792112002X
  4. Ибрагимов Д.Н., Сиротин А.Н. (2017). О задаче быстродействия для класса линейных автономных бесконечномерных систем с дискретным временем и ограниченным управлением. АиТ, (10), 3–32. 10.1134/S0005117917100010
    Ibragimov, D.N., Sirotin, A.N. (2017). On the problem of operation speed for the class of linear infinite-dimensional discrete-time systems with bounded control. Autom Remote Control, (78), 1731–1756. https://doi.org/10.1134/S0005117917100010
  5. Краснощеченко В.И. (2014). Симплекс-метод для решения задачи быстродействия при наличии ограничения на скалярное управление и фазовых ограничений. Инженерный журнал: наука и инновании. (6). URL: http://engjournal.ru/catalog/it/asu/1252.html
    Krasnoshchechenko V.I. (2014). The simplex method for solving the performance problem with scalar control and state constraints. Engineering Journal: Science and Innovation (Russia), (6). URL: http://engjournal.ru/catalog/it/asu/1252.html (In Russ.).
  6. Мороз А.И. (1965). Синтез оптимального по быстродействию управления для линейного дискретного объекта третьего порядка. I. АиТ, 26(2), 193–207.
    Moroz A.I. (1965). Synthesis of time-optimal control for a third-order linear discrete object. I.. Automation and Remote Control (Russia), 26(2), 193–207. (In Russ.).
  7. Мороз А.И. (1965). Синтез оптимального по быстродействию управления для линейного дискретного объекта третьего порядка. АиТ, 26(3), 410–426.
    Moroz A.I. (1965). Synthesis of time-optimal control for a third-order linear discrete object. II.. Automation and Remote Control (Russia), 26(3), 410–426. (In Russ.).
  8. Мороз А.И. (1965). Синтез оптимального по быстродействию управления для линейного дискретного объекта третьего порядка. АиТ, 26(8), 1324–1335
    Moroz A.I. (1965). Synthesis of time-optimal control for a third-order linear discrete object. III.. Automation and Remote Control (Russia), 26(8), 1324–1335. (In Russ.).
  9. Пропой А.И. (1973). Элементы теории оптимальных дискретных процессов. М.: Наука.
    Propoy A.I. (1973). Elements of the theory of optimal discrete processes. Moscow: Nauka. (In Russ.).
  10. Сазанова Л.А. (2002). Устойчивость оптимального синтеза в задаче быстродействия. Известия вузов. Математика, (2), 46–57.
    Sazanova L.A. (2002). Stability of optimal synthesis in the performance problem. University Proceedings. Mathematics (Russia), (2), 46–57. (In Russ.).
  11. Схрейвер А. (1991). Теория линейного и целочисленного программирования. М.: Мир.
    Schrijver A. (1986). Theory of Linear and Integer Programming. England: John Wiley & Sons Ltd.
  12. Abdelhak A., Rachik M. (2010). The Linear Quadratic Minimum-Time Problem for a Class of Discrete Systems. Math. Programming and Operations Research, 59(4), 575–587. 10.1080/02331930801954672
  13. Amato F., Cosentino C., Tommasi G. D., Pironti A., Romano M. (2022). Input–Output Finite-Time Stabilization of Linear Time-Varying DiscreteTime Systems. IEEE Transactions on Automatic Control, 67(9), 4438–4450. 10.1109/TAC.2022.3161374
  14. Barber C. B., Dobkin D. P., Huhdanpaa H. (1996). The Quickhull Algorithm for Convex Hulls. ACM Transactions on Mathematical Software. 10.1145/235815.235821
  15. Bashein G. (1971). A Simplex Algorithm for On-Line Computation of Time Optimal Controls. IEEE Transactions on Automatic Control, 16(5), 479–482. 10.1109/TAC.1971.1099776
  16. Blanchini F. (1991). Polyhedral Set Constrained Control for Discrete-Time Systems with Unknown Additive Disturbances. IFAC Proceedings Volumes. 24(8), 95–100. 10.1016/s1474-6670(17)54151-8
  17. Blanchini F., Ukovich W. (1993). Linear Programming Approach to the Control of Discrete-Time Periodic Systems with Uncertain Inputs. Journal of Optimization Theory and Applications, 78(3), 523–539. 1007/bf00939880
  18. Chen D., Bako L., Lecoeuche S. (2012). The Minimum-Time Problem for Discrete-Time Linear Systems: A Non-Smooth Optimization Approach. Proceedings of the IEEE International Conference on Control Applications, 196–201. 10.1109/CCA.2012.6402693
  19. Desoer C.A., Wing J. (1961). The Minimal Time Regulator Problem for Linear Sampled-Data Systems: General Theory. Franklin Inst, 272(3), 208–228. 10.1016/0016-0032(61)90784-0
  20. Karmarkar N. (1984). A new polynomial-time algorithm for linear programming.
  21. Keerthi S., Gilbert E. (1987). Computation of Minimum-Time Feedback Control Laws for Discrete-Time Systems with State-Control Constraints. IEEE Transactions on Automatic Control, 32(5), 432–435. 10.1109/tac.1987.1104625
  22. Khachiyan L. G. (1980). Polynomial algorithms in linear programming. S.S.R. Cornput. Maths. Math. Phys, 20(1), 53–72. https://doi.org/10.1016/0041-5553(80)90061-0
  23. Kolev L.V. (1978). Minimum-Fuel Minimum-Time Control of Linear Discrete Systems. International Journal of Control, 27(1), 21–29. 10.1080/00207177808922344
  24. Lasserre J.B. (1993). Reachable, Controllable Sets and Stabilizing Control of Constrained Linear Systems. Automatica, 29(2), 531–536. 1016/0005-1098(93)90152-J
  25. Lee J., Haddad W.M. (2022). Fixed Time Stability and Optimal Stabilisation of Discrete Autonomous Systems. International Journal of Control, 96(9), 2341–2355. 1080/00207179.2022.2092557
  26. Leomanni M., Costante G., Ferrante F. (2022). Time-Optimal Control of a Multidimensional Integrator Chain With Applications. IEEE Control Systems Letters, 6, 2371–2376. 1109/LCSYS.2022.3154351
  27. Lin W.-S. (1986). Time-Optimal Control Strategy for Saturating Linear Discrete Systems. J. Control, 43(5), 1343–1351. 10.1080/00207178608933543
  28. Lini G., Consolini L., Piazzi A. (2009). Minimum-Time Constrained Velocity Planning. IEEE 2009 17th Mediterranean Conference on Control and Automation, 748–753. 10.1109/med.2009.5164633
  29. Scott M. (1986). Time/Fuel Optimal Control of Constrained Linear Discrete Systems. Automatica, 22(6), 711–715. 1016/0005- 1098(86)90008-7
  30. Stamnes O.N., Callafon R.A. (2007). Time-Optimal Input Shaping for DiscreteTime LTI Systems with Application to Seek Profiles of a HDD System. ASME ISPS Conf, 146–148.
  31. Vlieger J.H., Verbruggen H.B., Bruijn P.M. (1982). A Time-Optimal Control Algorithm for Digital Computer Control. Automatica, 18(2), 239–244. 1016/0005-1098(82)90111-x
  32. Weibel C. (2007). Minkowski sums of polytopes: combinatorics and computation. Suisse: EPFL. 10.5075/epfl-thesis-3883
  33. Yang H., Xia Y., Geng Q. (2019). Stabilization on Null Controllable Region. In: Analysis and Synthesis of Delta Operator Systems with Actuator Saturation. Studies in Systems, Decision and Control, 193, 39–65. 10.1007/978-981-13-3660-7_3

Информация об авторах

Нурсейит Акимжанович Камчиев, студент кафедры «Компьютерное моделирование информационных и экономических систем», Московский авиационный институт (национальный исследовательский университет) (МАИ), Москва, Российская Федерация, ORCID: https://orcid.org/0009-0001-1044-7071, e-mail: nurseiitkamchiev@yandex.ru

Данис Наилевич Ибрагимов, кандидат физико-математических наук, доцент образовательного центра института №8 Компьютерные науки и прикладная математика, Московский авиационный институт (национальный исследовательский университет) (МАИ), Москва, Российская Федерация, ORCID: https://orcid.org/0000-0001-7472-5520, e-mail: rikk.dan@gmail.com

Вклад авторов

Камчиев Н.А. — доказательство лемм 2 и 3, теоремы 1; проведение численного моделирования; обработка статистики.

Ибрагимов Д.Н. — идеи исследования; формулирование основных теоретических положений; определение методики исследования.

Все авторы приняли участие в обсуждении результатов и согласовали окончательный текст рукописи.

Конфликт интересов

Автор заявляет об отсутствии конфликта интересов.

Метрики

 Просмотров web

За все время: 8
В прошлом месяце: 0
В текущем месяце: 8

 Скачиваний PDF

За все время: 3
В прошлом месяце: 0
В текущем месяце: 3

 Всего

За все время: 11
В прошлом месяце: 0
В текущем месяце: 11