КіСА | Зміст

Том 62 >>> № 2 БЕРЕЗЕНЬ — КВІТЕНЬ 2026

-->

УДК 519.85

Н.В. СЕМЕНОВА
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
nvsemenova@meta.ua

Л.М. КОЛЄЧКІНА
Лодзький університет, Лодзь, Польща, lkoliechkina@gmail.com

О.А. ДВІРНА
Національний університет «Полтавська політехніка імені Юрія Кондратюка», Полтава, Україна, lenadvirna@gmail.com

РОЗВ’ЯЗУВАННЯ БАГАТОКРИТЕРІЙНОЇ ЗАДАЧІ ОПТИМІЗАЦІЇ
НА КОМБІНАТОРНИХ ТОЧКОВИХ КОНФІГУРАЦІЯХ

Анотація. Запропоновано математичну модель багатокритерійної задачі на комбінаторних конфігураціях поліперестановок та проаналізовано її особливості з урахуванням властивостей комбінаторних конфігурацій та їхніх графів. Розроблено новий алгоритм горизонтального методу розв’язування таких задач знаходження множини оптимальних за Парето розв’язків, що базується на адаптивних алгоритмах комбінаторного пошуку та евристичних методах. Роботу запропонованого алгоритму проілюстровано розв’язуванням тестової задачі. На підставі проведених числових експериментів обґрунтовано ефективність алгоритму на Евклідових конфігураціях поліперестановок та перестановок з повтореннями з урахуванням сучасних підходів у комбінаторній та векторній оптимізації.

Ключові слова: багатокритерійна оптимізація, комбінаторні точкові конфігурації, конфігурації перестановок, поліперестановки, лінійна функція, структурний граф.

повний текст

СПИСОК ЛІТЕРАТУРИ

1. Papadimitriou C.H., Steiglitz K. Combinatorial optimization: Algorithms and complexity. Mineola, N.Y.: Dover Publications, Inc., 1998. 496 p.
2. Bóna M. Combinatorics of permutations. Boca Raton: Chapman & Hall/CRC, 2004. 337 р.
3. Berge C. Principes de combinatoire. Paris: Dunod, 1968. 146 p.
4. Sergienko I.V., Hulianytskyi L.F., Sirenko S.I. Classification of applied methods of combinatorial optimization. Cybernetics and Systems Analysis. 2009. Vol. 45, N 5. P. 732–741. https://doi.org/10.1007/s10559-009-9134-0.
5. Gulyanitskii L.F., Sergienko I.V. Metaheuristic downhill simplex method in combinatorial optimization. Cybernetics and System Analysis. 2007. Vol. 43, N 6. P. 822–829. https://doi.org/10.1007/s10559-007-0106-y.
6. Сергієнко І.В., Шило В.П., Рощин В.О. Дискретна оптимізація. Алгоритми та їхнє ефективне використання. Київ: Наук. думка, 2020. 219 с.
7. Shor N.Z., Setstyuk P.I. Lagrangian bounds in multiextremal polynomial and discrete optimization problems. Journal of Global Optimization. 2002. Vol. 23. P. 1–41. https://doi.org/10.1023/A:1014004625997.
8. Onwubolu G.C., Davendra D. (Eds.) Differential evolution: A handbook for global permutation-based combinatorial optimization. Studies in Computational Intelligence. Berlin; Heidelberg: Springer, 2009. Vol. 175. 213 p. https://doi.org/10.1007/978-3-540-92151-6.
9. Korte B., Vygen J. Combinatorial optimization: Theory and algorithms. 5th ed. Berlin; Heidelberg: Springer, 2012. https://doi.org/10.1007/978-3-642-24488-9.
10. Pardalos P.M., Du D., Graham R.L. Handbook of combinatorial optimization. New York: Springer, 2013. 648 p.
11. Стецюк П.І., Донець Г.П., Ненахов Е.І. та ін. Субградієнтні алгоритми та задачі на комбінаторних конфігураціях. Київ: Пульсари, 2019. 234 с.
12. Згуровський М.З., Павлов О.А. Важкорозв’язувані задачі комбінаторної оптимізації в плануванні і прийнятті рішень. Київ: Наук. думка, 2016. 716 с.
13. Aardal K., Hoesel S. Polyhedral techniques in combinatorial optimization II: Theory. Statistica Neerlandica. 1999. Vol. 59, N 2. P. 131–177. https://doi.org/10.1111/1467-9574.00104.
14. Стоян Ю.Г., Ємець. О.О. Теорія і методи евклідової комбінаторної оптимізації. Київ: Ін-т систем. досліджень освіти, 1993. 188 с.
15. Семенова Н.В., Колєчкіна Л.М. Векторні задачі дискретної оптимізації на комбінаторних множинах: Методи дослідження та розв’язання. Київ: Наук. думка, 2009. 266 с.
16. Донець Г.П., Колєчкіна Л.М. Екстремальні задачі на комбінаторних конфігураціях. Полтава: РВВ ПУЕТ, 2011. 309 с.
17. Grebennik I.V., Chorna O.S. Special transpositions of permutation elements and properties of their composition. Cybernetics and Systems Analysis. 2017. Vol. 53, N 1. P. 67–77. https://doi.org/10.1007/s10559-017-9907-9.
18. Grebennik I., Chorna O. Elements transpositions and their impact on the cyclic structure of permutations. Econtechmod: An International Quarterly Journal on Economics of Technology and Modelling Processes. 2015. Vol. 4, N 3. P. 33–38.
19. Semenova N.V., Kolechkina L.N., Nagornaya A.N. Solution and investigation of vector problems of combinatorial optimization on a set of polypermutations. Journal of Automation and Information Sciences. 2008. Vol. 40, N 12. P. 27–42. https://doi.org/10.1615/JAutomatInfScien.v40.i12.30.
20. Semenova N.V., Kolechkina L.N. A polyhedral approach to solving multicriterion combinatorial optimization problems over sets of polyarrangements. Cybernetics and Systems Analysis. 2009. Vol. 45, N 3. P. 438–445. https://doi.org/10.1007/s10559-009-9110-8.
21. Stoyan Y.G., Yakovlev S.V. Theory and methods of Euclidean combinatorial optimization: Current status and prospects. Cybernetics and Systems Analysis. 2020. Vol. 56, N 3. P. 366–379. https://doi.org/10.1007/s10559-020-00253-6.
22. Yakovlev S., Pichugina O., Koliechkina L. Combinatorial point configurations and polytopes. Lodz University Press. 2023. 232 p. https://doi.org/10.18778/8331-391-7.
23. Emmerich M.T.M., Deutz A.H. A tutorial on multiobjective optimization: fundamentals and evolutionary methods. Natural Computing. 2018. Vol. 17, N 1–2. P. 585–609. https://doi.org/10.1007/s11047-018-9685-y.
24. Ehrgott M., Wiecek M.M. Mutiobjective programming. In: Multiple Criteria Decision Analysis: State of the Art Surveys. International Series in Operations Research & Management Science. Springer, New York, 2005. Vol. 78. P. 667–708. https://doi.org/10.1007/0-387-23081-5_17.
25. Steuer R. Multiple criteria optimization: Theory, computation and application. New York: John Wiley, 1986. 546 p.
26. Sergienko I.V., Lebedeva T.T., Semenova N.V. Existence of solutions in vector optimization problems. Cybernetics and Systems Analysis. 2000. Vol. 36, N 6. P. 823–828. https://doi.org/10.1023/A:1009401209157.
27. Lebedeva T.T., Semenova N.V., Sergienko T.I. Regularization of the vector problem with quadratic criteria of Pareto optimization. Cybernetics and Systems Analysis. 2023. Vol. 59, N 4. P. 561–566. https://doi.org/10.1007/s10559-023-00591-1.
28. Lebedeva T.T., Semenova N.V., Sergienko T.I. Stability and regularization of vector optimization problems under possible criteria disturbances. Cybernetics and Systems Analysis. 2022. Vol. 58, N 5. P. 721–726. https://doi.org/10.1007/s10559-022-00505-7.
29. Donec G.A., Kolechkina L.M. Construction of Hamiltonian paths in graphs of permutations polyhedral. Cybernetics and Systems Analysis. 2010. Vol. 46, N 1. P. 7–13. https://doi.org/10.1007/s10559-010-9178-1.
30. Koliechkina L.N., Dvirna O.A. Solving extremum problems with linear fractional objective functions on the combinatorial configuration of permutations under multicriteriality. Cybernetics and Systems Analysis. 2017. Vol. 53, N 4. P. 590–599. https://doi.org/10.1007/s10559-017-9961-3.
31. Pichugina O., Yakovlev S. Functional and analytic representations of the general permutations. Eastern-European Journal of Enterprise Technologies. 2016. Vol. 1, N 4. P. 27–38. https://doi.org/10.15587/1729-4061.2016.58550.
32. Yakovlev S. Convex extensions in combinatorial optimization and their applications. In: Springer Optimization and its Applications. 2017. Vol. 130. P. 567–584. https://doi.org/10.1007/978-3-319-68640-027.
33. Yakovlev S.V., Pichugina O.S. Properties of combinatorial optimization problems over polyhedral-spherical sets. Cybernetics and Systems Analysis. 2018. Vol. 54, N 1. P. 99–109. https://doi.org/10.1007/s10559-018-0011-6.
34. Berge C. Graphs. 2nd ed. Amsterdam: Elsevier Science, 1985. 413 p.
35. Bondy J.A., Murty U.S.R. Graph theory with applications. New York: Springer, 2008. 264 p.

УДК 519.85

РОЗВ’ЯЗУВАННЯ БАГАТОКРИТЕРІЙНОЇ ЗАДАЧІ ОПТИМІЗАЦІЇ НА КОМБІНАТОРНИХ ТОЧКОВИХ КОНФІГУРАЦІЯХ

СПИСОК ЛІТЕРАТУРИ

РОЗВ’ЯЗУВАННЯ БАГАТОКРИТЕРІЙНОЇ ЗАДАЧІ ОПТИМІЗАЦІЇ
НА КОМБІНАТОРНИХ ТОЧКОВИХ КОНФІГУРАЦІЯХ