Побудова математичної моделі і розв’язання задачі покриття компактної багатогранної множини набором прямих паралелепіпедів - Автореферат

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ АВТОРЕФЕРАТ дисертації на здобуття наукового ступеня кандидата фізико-математичних наукРобота виконана в Інституті проблем машинобудування ім. Науковий керівник: член-кореспондент НАН України, доктор технічних наук, професор Стоян Юрій Григорович, Інститут проблем машинобудування ім. Підгорного НАН України, завідувач відділу математичного моделювання та оптимального проектування. Офіційні опоненти: доктор фізико-математичних наук, доцент Рубльов Богдан Владиславович, Київський національний університет ім. Захист відбудеться “28” квітня 2011 р. о 14 годині на засіданні спеціалізованої вченої ради Д 64.180.01 в Інституті проблем машинобудування ім.Розглянувши сучасний стан задач покриття, можна зробити висновок, що розроблено деякі точні та наближені методи розвязання двовимірних задач покриття як сімєю ідентичних обєктів, так і сімєю обєктів, метричні характеристики яких відмінні, і тривимірних задач покриття набором ідентичних куль. Щодо компактних багатогранних множин покриття і набору покриваючих обєктів з різними розмірами, то в цьому випадку використовуються або евристичні методи, або методи, основою яких є апроксимація форм геометричних обєктів прямими паралелепіпедами, а отже, послаблення обмежень задачі. Тому виникає необхідність у більш поглибленому дослідженні та розробці конструктивних засобів математичного моделювання, побудові адекватної математичної моделі задачі, дослідженні її особливостей та розробці нових методів розвязання наукових та практичних задач покриття, зокрема конкретного зазначеного класу, що і визначило тему даної дисертаційної роботи. Для досягнення цієї мети у дисертації були сформульовані і вирішені такі основні наукові задачі: · розробка конструктивних засобів моделювання теоретико-множинних відношень (перетину, належності) між компактною багатогранною множиною (надалі, множиною покриття) та множиною, що утворена обєднанням скінченного набору прямих паралелепіпедів; На підставі результатів дисертаційної роботи, розроблених методів і запропонованих алгоритмів розвязання задачі покриття створено компютерні програми: “3D covering problem” та “3D minimal covering problem”, що можуть бути використані для розвязання як тривимірних задач покриття компактної багатогранної множини сімєю паралелепіпедів, що виникають у різноманітних галузях науки та техніки: системах статичного інспектування, аеро-та космічних системах спостереження, розпізнавання форми або контуру у робототехніці, “art gallery problem”, так і задач, які до них зводяться.У вступі обґрунтовано актуальність теми дисертаційної роботи, визначено мету й дослідницькі завдання, вказано обєкт та предмет дослідження, зазначено теоретичне та практичне значення дослідження, його наукову новизну, наведено відомості щодо апробації здобутих результатів, а також інформацію стосовно публікацій з теми. Таким чином, на цей час клас тривимірних задач покриття з довільною множиною покриття та без обмежень на кількість покривних обєктів потребує розробки методів розвязання, що, в свою чергу, вимагає створення конструктивних засобів математичного та компютерного моделювання відношень покривних обєктів та множини покриття, що і визначило тему даної роботи. У роботі розглядаються дві реалізації тривимірної задачі покриття: задача покриття заданою кількістю різних прямих паралелепіпедів та задача покриття мінімальною кількістю однакових прямих паралелепіпедів. Задача 1, як реалізація тривимірної задачі покриття, може бути подана у вигляді оптимізаційної задачі, де як функція цілі виступає значення Г-функції, яке відповідає на питання, чи є сімя трансльованих паралелепіпедів покриттям множини , чи ні. Таким чином, якщо в результаті розвязання задачі для паралелепіпедів виконується умова і коефіцієнт гомотетії при цьому , то кількість паралелепіпедів сімї , необхідних для покриття множини , дорівнює , інакше збільшуємо кількість паралелепіпедів і для них розвязуємо задачу .

ОСНОВНИЙ ЗМІСТ РОБОТИ

1. Сосюрка Е.С. Аналитическое описание взаимного расположения прямых параллелепипедов в задаче покрытия компактного многогранного множества / Е.С. Сосюрка // Вестник Харьковского национального университета, серия «Математическое моделирование. Информационные технологии. Автоматизированные системы управления»: - Харьков: ХНУ, - 2008. - №833, вып. 10. - С.247-257.

2. Сосюрка Е.С. Построение гамма-функции и ее использование для решения задачи покрытия компактного многогранного множества набором прямых параллелепипедов / Е.С. Сосюрка // Вестник Харьковского национального университета, серия «Математическое моделирование. Информационные технологии. Автоматизированные системы управления»: - Харьков: ХНУ, - 2009. - №847, вып. 11. - С.314-323.

3. Сосюрка Е.С. Математическая модель и стратегия решения задачи покрытия выпуклого многогранного множества семейством прямых параллелепипедов / Е.С. Сосюрка // Вестник Харьковского национального университета, серия «Математическое моделирование. Информационные технологии. Автоматизированные системы управления»: - Харьков: ХНУ, - 2009. - №863, вып. 12. - С.252-263.

4. Сосюрка Е.С. Задача покрытия компактного многогранного множества набором прямых параллелепипедов / Е.С. Сосюрка, Ю.Г. Стоян // Доповіді Національної академії наук України. - 2010. - №8. - С.43-48.

5. Сосюрка Е.С. Задача покрытия прямого параллелепипеда семейством прямых параллелепипедов / Е.С. Сосюрка // Тезисы докладов конференции молодых ученых и специалистов "Современные проблемы машиностроения". - ИПМАШ им. А.Н. Подгорного НАН України. - Харьков. - 2008. - С.28.

6. Сосюрка Е.С. Математическая модель и метод решения задачи покрытия прямого параллелепипеда семейством прямых параллелепипедов / Е.С. Сосюрка // Тезисы докладов 2-ой всеукраинской научной конференции молодых ученых «Физика низких температур». - ФТИНТ им. Б.И. Веркина НАН Украины - Харьков. - 2009. - С.62.

7. Сосюрка Е.С. Математическая модель и метод решения задачи покрытия выпуклого многогранника семейством прямых параллелепипедов / Е.С. Сосюрка // Тезисы докладов второй международной научной конференции «Математическое моделирование и дифференциальные уравнения» - белорусский Государственный Университет. - Минск. - 2009. - С.76-77.

8. Сосюрка Е.С. Задача покрытия выпуклого многогранника семейством прямых параллелепипедов / Е.С. Сосюрка // Тезисы докладов конференции молодых ученых и специалистов "Современные проблемы машиностроения". - ИПМАШ им. А.Н. Подгорного НАН України. - Харьков. - 2009. - С.36.

9. Сосюрка Е.С. Задача покрытия многогранной области семейством прямых параллелепипедов / Е.С. Сосюрка // Тезисы докладов конференции 14-го международного молодежного форума «Радиоэлектроника и молодежь в 21 веке». - Харьков. - 2010.- С.276.

10. Сосюрка Е.С. Математическая модель и метод решения задачи покрытия многогранной области семейством прямых параллелепипедов / Е.С. Сосюрка // Тезисы докладов конференции 12-ой международной научно-технической конференции «Системный анализ и информационные технологии». - Киев. - 2010. - С.319.

11. Сосюрка Е.С. Особливості моделювання і стратегія розвязку задачі покриття компактної багатогранної множини мінімальною кількістю конґруентних прямих паралелепіпедів / Е.С. Сосюрка // Тези доповідей міжнародної конференції «Problem of decision making under uncertainties». - Львів. - 2010. - С.156-157.

12. Sosyurka O. A method of covering a compact polyhedral set by a minimal number of identical right parallelepipeds / O. Sosyurka // International conference for young scientists “Low temperature physics”: book of abstracts. - Kharkiv. - 2010. - P.185.

13. Сосюрка Е.С. Особенности моделирования и решения задачи покрытия компактного многогранного множества / Е.С. Сосюрка // Тезисы докладов пятой научно-практической конференции с международным участием «Математичне та імітаційне моделювання систем». - Киев. - 2010. - С.254-255.

14. Stoyan Yu. Covering a non-convex polytope by minimal number of congruent parallelepipeds // Yu. Stoyan, E.S. Sosurcka // EURO XXIV: European conference on Operational Research, 11-14 July, 2010: book of abstracts. - Lisbon, 2010. - P.75.

15. Сосюрка Е.С. Задача покрытия компактного многогранного множества семейством прямых параллелепипедов / Е.С. Сосюрка // Тезисы докладов Всеукраинской научной конференции для студентов и аспирантов «Современные проблемы машиностроения». - Харьков. - 2010. - С.45.

16. Сосюрка О.С. Математична модель і метод розвязання задачі покриття опуклої багатогранної множини мінімальною кількістю конґруентних прямих паралелепіпедів [Електронний ресурс] / О.С. Сосюрка // Тези докладів конференції молодих учених «Підстригачівські читання - 2010». - Львів. - 2010. - Режим доступу до журн.: http://www.iapmm.lviv.ua/chyt2010/materials/pc2010-02-S-29.pdf.