МЕТОД ГЕОМЕТРИЧНОГО МОДЕЛЮВАННЯ МАКСИМАЛЬНОГО ПОКРИТТЯ ЗАДАНИХ ОБЛАСТЕЙ З УРАХУВАННЯМ ОБМЕЖЕНЬ СПЕЦІАЛЬНОГО ВИДУ
DOI:
https://doi.org/10.32347/0131-579x.2020.98.139-149Ключові слова:
метод геометричного моделювання, модель, максимальне покриття, обмеження спеціального виду.Анотація
Дану роботу присвячено розробці методу геометричного моделювання максимального покриття заданих областей з урахуванням обмежень спеціального виду. Задачі оптимального покриття є складовою частиною класу задач оптимізаційного геометричного проектування, до якого у своїх постановках може бути зведеною велика кількість важливих практичних задач з різних галузей діяльності людини. Незважаючи на розвиток методів оптимального покриття, існують актуальні задачі, які до теперішнього часу є не розв’язаними. Саме до таких відноситься задача максимального покриття заданих областей з урахуванням обмежень спеціального виду. При цьому обмеження спеціального виду є різними для відповідних галузей діяльності людини. Наприклад, для сфери цивільного захисту це можуть бути обмеження, що пов’язані з: часом реагування оперативно-рятувальних підрозділів на пожежі; наявними ресурсами на створення підрозділів; необхідністю реалізації заданого номеру виклику підрозділів; ризиком для людини загинути внаслідок пожежі в одиницю часу, який має не перевищувати значення, що має бути обґрунтованим, виходячи з існуючих соціально-економічних умов.
Перш за все, було сформульовано постановку задачі та розроблено модель максимального покриття заданих областей з урахуванням обмежень спеціального виду. Досліджено характеристики моделі максимального покриття, до яких відносяться наступні: цільова функція є алгоритмічною, тобто обчислюється в процесі розв’язання задачі; обмеження задачі складаються з нелінійних, дискретних та кусково-лінійних виразів. Виходячи з моделі максимального покриття було зроблено висновок, що дана задача відноситься до класу задач комбінаторної оптимізації. У зв’язку з цим, для її розв’язання було розроблено метод геометричного моделювання максимального покриття заданих областей з урахуванням обмежень спеціального виду, основою якого є метод направленого перебору припустимих місць розміщення початків локальних систем координат об’єктів покриття. Одержано оцінку складності розробленого методу. Подальші дослідження будуть направлені на здійснення комп’ютерної реалізації розробленого методу.
Посилання
Stoyan Y.G., Yakovlev Y.G. Configuration space of geometric objects. Cybernetics and Systems Analysis. USA, 2018. Vol. 54, № 5, P. 716–726.
Yakovlev S., Kartashov O., Korobchynskyi K. The informational analytical technologies of synthesis of optimal spatial configuration. Computer Sciences and Information Technologies : IEEE 13th Intern. Scientific and Technical Conf. c. Lviv, LPNU, September 11–14 2018, Lviv. P. 140–143.
Andronov V.A. , Komyak V.M. , Sobol A.N. , Komyak V.V. , Popova A.V. Problem of geometric design: placement, coverage, рartition and defining optimal routes. Годишник на техническия университет във Варна. Варна, 2013. Т. 3. С. 9–13.
Киселева Е.М., Шор Н.З. Непрерывные задачи оптимального разбиения множеств: монографія. Киев: наук. думка, 2005. – 564 с.
Komyak V., Sobol O., Kartashov O., Yakovleva I., Komyak V., Danilin A., Lyashevskaya О. Computer simulation of the partitioning by mutually orthogonal lines. Experience of Designing and Application of CAD Systems : IEEE 15th International Conference,v. Polyana, LPTU, February 26 – March 2 2019, Polyana, P. 16–19.
Stoyan Yu., Romanova T., Scheithauer G., Krivulya A. Covering a polygonal region by rectangles. Computational Optimization and Applications. 2011. Vol. 48, № 3, P. 675–695. DOI:
https://doi.org/10.1007/s10589-009-9258-1.
Yakovlev S., Kartashov O., Komyak V., Shekhovtsov S., Sobol O., Yakovleva I. Modeling and Simulation of Coverage Problem in Geometric Design System. Experience of Designing and Application of CAD Systems : IEEE 15th International Conference,v. Polyana, LPTU, February 26 – March 2 2019, Polyana, P. 20–23.
Yakovlev S.V. On a class of problems on covering of a bounded set. Acta Mathematica Hungarica. 1989. Vol. 53, № 3, P. 253–262. DOI: https://doi.org/10.1007/BF01953365.
Kiseleva E.M., Lozovskaya L.I., Timoshenko E.V. Solution of continuous problems of optimal covering with spheres using optimal set-partition theory. Cybernetics and Systems Analysis. 2009. Vol. 45, № 3, P. 421–437. DOI: https://doi.org/10.1007/s10559-009-9113-5.
Stoyan Y.G., Patsuk V.M. Covering a convex 3D polytope by a minimal number of congruent spheres. International Journal of Computer Mathematics. 2014. Vol. 91, № 9, P. 2010–2020. DOI: https://doi.org/10.15587/1729-4061.2018.140722.
Yakovlev S., Kartashov O., Korobchynskyi K. The informational analytical technologies of synthesis of optimal spatial configuration Computer Sciences and Information Technologies : IEEE 13th Intern. Scientific and Technical Conf. c. Lviv, LPNU, September 11–14 2018, Lviv. P. 374–377.
Комяк В.М., Соболь О.М. , Собина В.О. , Лісняк А.А. Оптимізація покриття заданих областей геометричними об’єктами зі змінними метричними характеристиками: монографія. Харків: НУЦЗУ, 2013. – 124 с.
Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев.: наук. думка, 1986. – 268 с.
Соболь О.М., Собина В.О., Тур О.М. Побудова ω-функцій в задачах покриття заданої області геометричними об’єктами зі змінними метричними характеристиками. Прикладна геометрія та інженерна графіка: міжвідомчий науково-технічний збірник. Київ, 2010. Вип. 86 С. 118–122.
Кравців С.Я., Соболь О.М., Тютюник В.В. Оцінювання параметрів впливу на інтегральний пожежний ризик за допомогою факторного аналізу. Пожежна безпека. Технічні науки. Львів, 2017. № 30. С. 99–104.
Комяк В. М., Соболь О. М., Кравців С. Я., Чуб І. А. Моделювання покриття опуклими багатокутниками заданої області з дискретними елементами. Вісник Херсонського національного технічного університету. Технічні науки. Херсон, 2018. № 3 (66), Т. 2. С. 147–152.
Кравців С.Я. Метод мінімізації інтегрального пожежного ризику за допомогою оптимізації покриття пожежних депо. Наукові вісті КПІ. Технічні науки. Київ, 2018. № 4. С. 30–37.
Комяк В.М., Соболь О.М., Кравців С.Я. Модель та метод оптимального покриття неопуклими багатокутниками заданої області з дискретними елементами. Науковий вісник Таврійського державного агротехнічного університету. Мелітополь, 2018. Вип. 8, Т. 1. С. 11–22.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2020 Oleksandr Sobol, Svitlana Кravtsiv
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
