|
DOI: 10.14489/vkit.2025.03.pp.012-020
Ибрагимов Д. Н., Кибзун А. И.
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ БЫСТРОДЕЙСТВИЯ ДЛЯ ЛИНЕЙНЫХ СИСТЕМ С ДИСКРЕТНЫМ ВРЕМЕНЕМ
(с. 12-20)
Аннотация. Рассмотрены вопросы разработки программного обеспечения для решения задачи быстродействия для линейных систем с дискретным временем и ограничениями первого порядка (геометрическими или суммарными). Сформулированы и обоснованы соответствующие алгоритмы. Оценена вычислительная сложность использования данных алгоритмов. Представлено описание программы для ЭВМ, а также всех ее структурных элементов и интерфейса, выполненных на языке MatLab. На примере решения задачи наискорейшей стабилизации уровня глюкозы и инсулина в плазме крови продемонстрирована работа программного обеспечения. Рассмотрены две математические модели с ограничениями на объем разовой инъекции инсулина и глюкозы и на суммарный допустимый объем всех инъекций.
Ключевые слова: линейные дискретные системы; задача быстродействия; задача линейного программирования; программа для ЭВМ.
Ibragimov D. N., Kibzun A. I.
SOFTWARE IMPLEMENTATION OF ALGORITHMS FOR SOLVING THE SPEED-IN-ACTION PROBLEM FOR LINEAR DISCRETE-TIME SYSTEMS
(pp. 12-20)
Abstract. The article discusses the development of software for solving the speed-in-action problem for linear systems with discrete time and first-order constraints (geometric or summary). Algorithms for constructing an optimal process are formulated and the main theoretical information necessary for their derivation is given. In particular, the discussed solution method is based on the apparatus of null-controllable sets, which was developed in previous theoretical works, and the dynamic programming method. The computational complexity of these algorithms is estimated. It is demonstrated that the solution of the speed-in-action problem can be performed in polynomial time depending on the minimum time (in the case of geometric constraints, this requires additional polyhedral approximations of null-controllable sets). A description of the computer program, all its structural elements and interface, composed using the programming language MatLab, is presented. The program uses the Quick Hull algorithm as its main tool when constructing null-controllable sets, and the interior point method for solving linear and quadratic programming problems when calculating optimal control and polyhedral approximation, respectively. The program output is provided in graphical and text formats. The operation of the software is demonstrated by the example of solving the problem of the fastest stabilization of glucose and insulin levels in blood plasma. Two mathematical models are considered: with restrictions on the volume of a singe injection of insulin and glucose and with restrictions on the total permissible volume of all injections. The first statement corresponds to geometric constraints on control, the second statement is described by summary constraints.
Keywords: Linear discrete system; Speed-in-action problem; Linear programming problem; Computer program.
Д. Н. Ибрагимов, А. И. Кибзун (Московский авиационный институт (национальный исследовательский университет), Москва, Россия) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
D. N. Ibragimov, A. I. Kibzun (Moscow Aviation Institute (National Research University), Moscow, Russia) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. Болтянский В. Г. Оптимальное управление дискретными системами. М.: Наука, 1973. 448 с.
2. Пропой А. И. Элементы теории оптимальных дискретных процессов. М.: Наука, 1973. 256 с.
3. Benvenuti L., Farina L. The geometry of the reachability set for linear discrete-time systems with positive controls // SIAM Journal on Matrix Analysis and Applications. 2006. V. 28, No. 2. P. 306–325. DOI: 10.1137/040612531
4. Colonius F., Cossich J. A. N., Santana A. J. Controllability properties and invariance pressure for linear discrete-time systems // Journal of Dynamics and Differential Equations. 2022. V. 34. No. 1. P. 5–28. DOI: 10.1007/s10884-021-09966-4
5. Darup M.S., Mönnigmann M. On general relations between null-controllable and controlled invariant sets for linear constrained systems // Proceedings of 53rd IEEE Conference on Decision and Control. 15–17 December 2014. Los Angeles, USA. P. 6323–6328. DOI: 10.1109/CDC.2014.7040380
6. Fucheng L., Mengyuan S. Usman Optimal preview control for linear discrete-time periodic systems // Mathematical Problems in Engineering. 2019. No. 1. P. 1–11. DOI: 10.1155/2019/8434293
7. Ge S. S., Zhendong S., Lee T. H. Reachability and controllability of switched linear discrete-time systems // IEEE Transactions on Automatic Control. 2001. V. 46, No. 9. P. 1437–1441. DOI: 10.1109/9.948473
8. Heemels W. P. M. H., Camlibel M. K. Null controllability of discrete-time linear systems with input and state constraints // Proceedings of 47th IEEE Conference on Decision and Control. 9–11 December 2008. Cancun, Mexico. P. 3487–3492. DOI: 10.1109/CDC.2008.4739333
9. Kaba M. D., Camlibel M. K. A spectral characterization of controllability for linear discrete-time systems with conic constraints // SIAM Journal on Control and Optimization. 2015. V. 53, No. 4. P. 2350–2372. DOI: 10.1137/140960967
10. Kostousova E. K. External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms // Mathematical Control and Related Fields. 2021. V. 11, No. 3. P. 625–641. DOI: 10.3934/mcrf.2021015
11. Ибрагимов Д. Н., Новожилкин Н. М., Порцева Е. Ю. О достаточных условиях оптимальности гарантирующего управления в задаче быстродействия для линейной нестационарной дискретной системы с ограниченным управлением // Автоматика и телемеханика. 2021. № 12. С. 48–72. DOI: 10.31857/S0005231021120047
12. Ибрагимов Д. Н., Осокин А. В., Сиротин А. Н., Сыпало К. И. О свойствах предельных множеств управляемости для класса неустойчивых линейных систем с дискретным временем и l1-ограничениями // Известия РАН. Теория и системы управления. 2022. № 4. С. 3–21. DOI: 10.31857/S0002338822040102
13. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. М.: Наука, 1981. 544 с.
14. Спутниковые системы мониторинга. Анализ, синтез и управление / В. В. Малышев, М. Н. Красильщиков, В. Т. Бобронников и др. М.: Московский авиационный институт, 2000. 568 с.
15. Ибрагимов Д. Н. О решении задачи быстродействия для линейной системы с дискретным временем и суммарным ограничением на векторное управление // Материалы международной конференции «Динамические системы: устойчивость, управление, дифференциальные игры (SCDG 2024). 9–13 сентября 2024 г. Екатеринбург, Россия. С. 137–141.
16. Свидетельство о государственной регистрации программы для ЭВМ № 2024687521 РФ. Программа для решения задачи быстродействия для линейных систем с дискретным временем и суммарными или геометрическими ограничениями первого порядка: Заявка № 2024686102 от 1 ноября 2024 г. / Ибрагимов Д. Н.; правообладатель: Федеральное государственное бюджетное образовательное учреждение Высшего образования «Московский авиационный институт (национальный исследовательский университет)». Опубл. 19.11.2024. Зарегистрировано в Реестре программ для ЭВМ.
17. Barber C. B., Dobkin D. P., Huhdanpaa H. The quickhull algorithm for convex hulls // ACM Transactions on Mathematical Software. 1996. V. 4, No. 22. P. 469–483. DOI: 10.1145/235815.235821
18. Weibel C. Minkowski sums of polytopes: combinatorics and computation. Lausanne: EPFL, 2007. 114 p. DOI: 10.5075/epfl-thesis-3883
19. Ибрагимов Д. Н., Герасимова К. В., Мохначева А. А. Методы численного моделирования множеств 0-управляемости линейной дискретной динамической системы с ограниченным управлением на основе алгоритмов полиэдральной аппроксимации // Моделирование и анализ данных. 2023. Т. 13, № 4. С. 84–110. DOI: 10.17759/mda.2023130405
20. Козлов М. К., Тарасов С. П., Хачиян Л. Г. Полиномиальная разрешимость выпуклого квадратичного программирования // Журнал вычислительной математики и математической физики. 1980. Т. 20, № 5. C. 1319–1323. DOI: 10.1016/0041-5553(80)90098-1
21. Fisher M. E. A Semiclosed-Loop Algorithm for the Control of Blood Glucose Levels in Diabetics // IEEE Transactions on Biomedical Engineering. 1991. V. 38, No. 1. P. 57–61. DOI: 10.1109/10.68209
1. Boltyanskiy V. G. (1973). Optimal control of discrete systems. Moscow: Nauka. [in Russian language]
2. Propoy A. I. (1973). Elements of the theory of optimal discrete processes. Moscow: Nauka. [in Russian language]
3. Benvenuti L., Farina L. (2006). The geometry of the reachability set for linear discrete-time systems with positive controls. SIAM Journal on Matrix Analysis and Applications, 28(2), 306 – 325. DOI: 10.1137/040612531
4. Colonius F., Cossich J. A. N., Santana A. J. (2022). Controllability properties and invariance pressure for linear discrete-time systems. Journal of Dynamics and Differential Equations, 34(1), 5 – 28. DOI: 10.1007/s10884-021-09966-4
5. Darup M.S., Mönnigmann M. (2014). On general relations between null-controllable and controlled invariant sets for linear constrained systems. Proceedings of 53rd IEEE Conference on Decision and Control, 6323 – 6328. Los Angeles. DOI: 10.1109/CDC.2014.7040380
6. Fucheng L., Mengyuan S. (2019). Usman Optimal preview control for linear discretetime periodic systems. Mathematical Problems in Engineering, (1), 1 – 11. DOI: 10.1155/2019/8434293
7. Ge S. S., Zhendong S., Lee T. H. (2001). Reachability and controllability of switched linear discrete-time systems. IEEE Transactions on Automatic Control, 46(9), 1437 – 1441. DOI: 10.1109/9.948473
8. Heemels W. P. M. H., Camlibel M. K. (2008). Null controllability of discretetime linear systems with input and state constraints. Proceedings of 47th IEEE Conference on Decision and Control, 3487 – 3492. Cancun. DOI: 10.1109/CDC.2008.4739333
9. Kaba M. D., Camlibel M. K. (2015). A spectral characterization of controllability for linear discrete-time systems with conic constraints. SIAM Journal on Control and Optimization, 53(4), 2350 – 2372. DOI: 10.1137/140960967
10. Kostousova E. K. (2021). External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms. Mathematical Control and Related Fields, 11(3), 625 – 641. DOI: 10.3934/mcrf.2021015
11. Ibragimov D. N., Novozhilkin N. M., Portseva E. Yu. (2021). On sufficient conditions for the optimality of guaranteeing control in the problem of speed of response for a linear non-stationary discrete system with bounded control. Avtomatika i telemekhanika, (12), 48 – 72. [in Russian language] DOI: 10.31857/S0005231021120047
12. Ibragimov D. N., Osokin A. V., Sirotin A. N., Sypalo K. I. (2022). On the properties of limit controllability sets for a class of unstable linear systems with discrete time and l1-constraints. Izvestiya RAN. Teoriya i sistemy upravleniya, (4), 3 – 21. [in Russian language] DOI: 10.31857/S0002338822040102
13. Kolmogorov A. N., Fomin S. V. (1981). Elements of the theory of functions and functional analysis. Moscow: Nauka. [in Russian language]
14. Malyshev V. V., Krasil'shchikov M. N., Bobronnikov V. T. et al. (2000). Satellite monitoring systems. Analysis, synthesis and control. Moscow: Moskovskiy aviatsionniy institut. [in Russian language]
15. Ibragimov D. N. (2024). On the solution of the speed problem for a linear system with discrete time and a total constraint on vector control. Proceedings of the International Conference "Dynamic Systems: Stability, Control, Differential Games" (SCDG 2024), 137 – 141. Ekaterinburg. [in Russian language]
16. Ibragimov D. N. (2024). A program for solving the problem of high-speed response for linear systems with discrete time and total or geometric constraints of the first order. Certificate of state registration of computer software No. 2024687521. Russian Federation. [in Russian language]
17. Barber C. B., Dobkin D. P., Huhdanpaa H. (1996). The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software, 22(4), 469 – 483. DOI: 10.1145/235815.235821
18. Weibel C. (2007). Minkowski sums of polytopes: combinatorics and computation. Lausanne: EPFL. DOI: 10.5075/epfl-thesis-3883
19. Ibragimov D. N., Gerasimova K. V., Mohnacheva A. A. (2023). Methods of numerical modeling of 0-controllability sets of a linear discrete dynamic system with limited control based on polyhedral approximation algorithms. Modelirovanie i analiz dannyh, 13(4), 84 – 110. [in Russian language] DOI: 10.17759/mda.2023130405
20. Kozlov M. K., Tarasov S. P., Hachiyan L. G. (1980). Polynomial solvability of convex quadratic programming. Zhurnal vychislitel'noy matematiki i matematicheskoy fiziki, 20(5), 1319 – 1323. [in Russian languge] DOI: 10.1016/0041-5553(80)90098-1
21. Fisher M. E. (1991). A Semiclosed-Loop Algorithm for the Control of Blood Glucose Levels in Diabetics. IEEE Transactions on Biomedical Engineering, 38(1), 57 – 61. DOI: 10.1109/10.68209
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 700 руб. (в том числе НДС 20%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа скопируйте doi статьи:
10.14489/vkit.2025.03.pp.012-020
и заполните форму
Отправляя форму вы даете согласие на обработку персональных данных.
.
This article is available in electronic format (PDF).
The cost of a single article is 700 rubles. (including VAT 20%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.
After depositing your payment on our bank account we send you file of the article by e-mail.
To order articles please copy the article doi:
10.14489/vkit.2025.03.pp.012-020
and fill out the form
.
|
Текущий номер
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»