Про динамічну задачу оптимального розбиття множин з відшуканням координат центрів підмножин
Анотація
Актуальність. Оптимальне розбиття множин є однією з ключових проблем сучасної прикладної математики та теорії оптимізації, яка знаходить широке застосування в логістиці, інформатиці, біоінженерії, моделюванні складних систем та штучному інтелекті. Особливий інтерес становлять динамічні варіанти задач оптимального розбиття, коли умови задачі змінюються у часі, а розбиття має адаптуватися відповідно до динаміки системи. Оптимальне розбиття множин, в переважній більшості прикладних задач, безпосередньо пов’язано з мінімізацією цільового функціоналу, невід’ємною складовою якого є не тільки контури підмножин але й інші визначальні параметри, що є ключовими для шуканих підмножин. В класичних постановках такими параметрами є, наприклад, центри підмножин. Прикладне застосування задач в такій постановці знаходять своє застосування в економіці, логістиці, медицині, архітектурі та інших галузях.
Мета. Основною метою роботи є постановка однопродуктової динамічної задачі оптимального розбиття множин з відшуканням координат центрів таких підмножин, розробка алгоритму розв’язання динамічної задачі, постановка чисельного експерименту та аналіз отриманих результатів з метою підтвердження їх достовірності.
Методи дослідження. До основних методів дослідження роботи слід віднести методи теорії оптимізації, якісну теорію диференціальних рівнянь та чисельні методи розв’язання задач оптимізації.
Результати. До основних результатів роботи віднесено постановка однопродуктової динамічної задачі оптимального розбиття множин з відшуканням координат центрів таких підмножин, розроблений алгоритм розв’язання задачі, результати чисельного експерименту та результати аналізу отриманих результатів.
Висновки. В статті розглянута нова динамічна задача оптимального розбиття множин з відшуканням координат центрів, розроблено алгоритм розв’язання такої задачі, проведено чисельний експеримент за результатами якого можна вважати отримані результати достовірними та використати для розв’язання практичних задач.
Завантаження
Посилання
/Посилання
E. M. Kiseleva, “The emergence and formation of the theory of optimal set partitioning for sets of the n-dimensional Euclidean space. Theory and application,” J. Autom. Inf. Sci., vol. 50, no. 9, pp. 1–24, 2018. doi: 10.1615/jautomatinfscien.v50.i9.10
O. M. Kiselova, Stanovlennia ta rozvytok teorii optymalnoho rozbyttia mnozhyn. Teoretychni i praktychni zastosuvannia: monohrafiia. Dnipro, Ukraine: Lira, 2018. [in Ukrainian]
E. M. Kiseleva, L. S. Koriashkina, and T. A. Shevchenko, “Solving the dynamic optimal set partitioning problem with arrangement of centers of subsets,” Cybern. Syst. Anal., vol. 50, no. 6, pp. 842–853, 2014. doi: 10.1007/s10559-014-9675-8
E. Kiseleva, O. Prytomanova, and L. Hart, “Solving a two-stage continuous-discrete problem of optimal partitioning-allocation with the subsets centers placement,” Open Comput. Sci., vol. 10, pp. 124–136, 2020. Available: https://www.degruyter.com/view/journals/comp/10/1/article-p124.xml
E. M. Kiseleva and N. Z. Shor, Continuous Problems of Optimal Set Partitioning: Theory, Algorithms, Applications. Kyiv, Ukraine: Naukova Dumka, 2005.
E. M. Kiseleva, O. M. Prytomanova, and S. A. Us, “Solving a two-stage continuous-discrete optimal partitioning-distribution problem with a given position of the subsets centers,” Cybern. Syst. Anal., vol. 56, no. 1, pp. 3–15, 2020. doi: 10.1007/s10559-020-00215-y
E. M. Kiseleva, “Solution of the problem of optimal partitioning including allocation of the centers of gravity of the subsets,” Comput. Math. Math. Phys., vol. 29, no. 3, pp. 47–56, 1989. doi: 10.1016/0041-5553(89)90146-8
E. Kiseleva, L. Hart, O. Prytomanova, and O. Kuzenkov, “An algorithm to construct generalized Voronoi diagrams with fuzzy parameters based on the theory of optimal partitioning and neuro-fuzzy technologies,” in Proc. 8th Int. Conf. Mathematics. Information Technologies. Education (MoMLeT&DS-2019), Shatsk, Ukraine, Jun. 2–4, 2019, pp. 148–162. [Online]. Available: https://ceur-ws.org/Vol-2386/paper12.pdf
G. Buttazzo and G. Dal Maso, “An existence result for a class of shape optimization problems,” Arch. Ration. Mech. Anal., 1993.
L. Caffarelli and F.-H. Lin, “An optimal partition problem for eigenvalues,” J. Sci. Comput., 2007.
M. Conti, S. Terracini, and G. Verzini, “On a class of optimal partition problems related to the Fucik spectrum and to the monotonicity formulae,” Calc. Var. Partial Differ. Equ., 2005.
M. Burger, B. Hackl, and W. Ring, “Incorporating topological derivatives into level set methods,” J. Comput. Phys., 2004.
S. Amstutz and A. A. Novotny, Topological Optimization of Structures. Berlin, Germany: Springer, 2010.
R. T. Rockafellar, Convex Analysis. Princeton, NJ, USA: Princeton Univ. Press, 1973. doi: 10.1017/S0013091500010142
A. Dumas and F. Santambrogio, “Optimal trajectories in L1 and under L1 penalizations,” Comptes Rendus Math., vol. 362, no. G6, pp. 657–692, 2024.
Kiseleva E. M. The emergence and formation of the theory of optimal set partitioning for sets of the n-dimensional Euclidean space. Theory and application // Journal of Automation and Information Sciences. – 2018. – Vol. 50, № 9. – P. 1–24. – DOI: 10.1615/jautomatinfscien.v50.i9.10.
Кісельова О. М. Становлення та розвиток теорії оптимального розбиття множин. Теоретичні і практичні застосування : монографія / О. М. Кісельова. – Дніпро : Ліра, 2018. – 532 с.
Kiseleva E. M., Koriashkina L. S., Shevchenko T. A. Solving the dynamic optimal set partitioning problem with arrangement of centers of subsets // Cybernetics and Systems Analysis. – 2014. – Vol. 50, № 6. – P. 842–853. – DOI: 10.1007/s10559-014-9675-8.
Kiseleva E., Prytomanova O., Hart L. Solving a Two-stage Continuous-discrete Problem of Optimal Partitioning-Allocation with the Subsets Centers Placement // Open Computer Science. – 2020. – Vol. 10. – P. 124–136. –URL: https://www.degruyter.com/view/journals/comp/10/1/article-p124.xml.
Kiseleva E. M., Shor N. Z. Continuous problems of optimal set partitioning: theory, algorithms, applications / E. M. Kiseleva, N. Z. Shor. – К. : Наукова думка, 2005. – 564 p.
Kiseleva E. M., Prytomanova O. M., Us S. A. Solving a two-stage continuous-discrete optimal partitioning-distribution problem with a given position of the subsets centers // Cybernetics and Systems Analysis. – 2020. – Vol. 56, № 1. – P. 3–15. – DOI: 10.1007/s10559-020-00215-y.
Kiseleva E. M. Solution of the problem of optimal partitioning including allocation of the centers of gravity of the Subsets // Computational Mathematics and Mathematical Physics. – 1989. – Vol. 29, № 3. – P. 47–56. – DOI: 10.1016/0041-5553(89)90146-8.
Kiseleva E., Hart L., Prytomanova O., Kuzenkov O. An algorithm to construct generalized Voronoi diagrams with fuzzy parameters based on the theory of optimal partitioning and neuro-fuzzy technologies // Workshop Proceedings of the 8th International Conference on “Mathematics. Information Technologies. Education”, MoMLeT&DS-2019, Shatsk, Ukraine, June 2–4, 2019. – P. 148–162. – URL: https://ceur-ws.org/Vol-2386/paper12.pdf.
Buttazzo G., Dal Maso G. An existence result for a class of shape optimization problems // Archive for Rational Mechanics and Analysis. – 1993.
Caffarelli L., Lin F.-H. An optimal partition problem for eigenvalues // Journal of Scientific Computing. – 2007.
Conti M., Terracini S., Verzini G. On a class of optimal partition problems related to the Fucik spectrum and to the monotonicity formulae // Calculus of Variations and Partial Differential Equations. – 2005.
Burger M., Hackl B., Ring W. Incorporating topological derivatives into level set methods // Journal of Computational Physics. – 2004.
Amstutz S., Novotny A. A. Topological optimization of structures. – Berlin : Springer, 2010.
Rockafellar R. T. Convex Analysis / R. T. Rockafellar. – Princeton University Press, 1973. – DOI: 10.1017/S0013091500010142.
Dumas A., Santambrogio F. Optimal trajectories in L1 and under L1 penalizations // Comptes Rendus. Mathématique. – 2024. – Vol. 362, Issue G6. – P. 657–692.
