Анотація до роботи:

Кривуля Г.В. Математична модель та метод розв’язання задачі покриття багатокутної області сім’єю прямокутників. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи. – Інститут проблем машинобудування ім. А.М. Підгорного НАН України, Харків, 2008.

Дисертаційна робота присвячена розв’язанню актуальної наукової задачі покриття незв’язної багатокутної компактної канонічної області скінченною сім’єю орієнтованих прямокутників (основної задачі покриття).

У роботі розглядаються дві реалізації основної задачі: трансляційне покриття (якщо параметри розміщення області покриття фіксовані, а змінними є параметри розміщення прямокутників) і трансляційне включення (якщо параметри розміщення та метричні характеристики області покриття є змінними, а параметри розміщення покриваючих об’єктів фіксовані).

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

У дисертації розроблено конструктивні засоби математичного та комп’ютерного моделювання задач прямокутного покриття і розроблено методи їх розв’язання, у тому числі:

1. вперше формалізовано критерій покриття методом Ф-функцій для складених -багатокутників, що дозволяє описати в аналітичному вигляді відношення між областю покриття та скінченною сім’єю прямокутників;

2. набув подальшого розвитку метод Г-функцій на основі доведеної теореми про розбиття простору параметрів розміщення покриваючих об’єктів, що дозволяє моделювати відношення між скінченною сім’єю трансльованих прямокутників та -багатокутними областями покриття;

3. вперше побудовано математичну модель задачі трансляційного багатокутного включення для області покриття зі змінними параметрами розміщення та метричними характеристиками, що дозволяє побудувати дерево розв’язків і забезпечує отримання глобального максимуму;

4. вперше побудовано математичну модель задачі покриття на основі Г-функції, що дозволяє використовувати методи локальної і глобальної оптимізації;

5. набув подальшого розвитку метод розв’язування задачі трансляційного багатокутного включення, побудований на комбінації симплекс-методу і методу гілок та меж;

6. вперше запропоновано підхід, який дозволяє звести задачу покриття до розв’язання послідовності задач лінійного програмування;

7. вперше запропоновано ефективні правила відтинання безперспективних вершин дерева розв’язків, що дозволяє знаходити розв’язки задач покриття сім’єю трансльованих прямокутників та забезпечує отримання глобального максимуму в задачі трансляційного багатокутного включення;

8. розроблено відповідне алгоритмічне та програмне забезпечення у вигляді програм, які реалізують розроблені засоби, моделі і методи;

9. результати досліджень дисертаційної роботи впроваджені в навчальний процес у Харківському національному університеті радіоелектроніки і Харківському національному університеті внутрішніх справ.

Публікації автора:

1. Злотник М.В. Аналитическое описание условия покрытия прямоугольной области прямоугольными объектами / М.В. Злотник, А.В. Кривуля, Т.Е. Романова // Штучний інтелект. – 2006. – №4. – С. 175–183.

2. Stoyan Yu. Translational polygonal containment in packing and covering problems / Yu. Stoyan, T. Romanova, A. Krivulya, G. Scheithauer // Проблемы машиностроения. – 2007. – Т.10, №3. – С. 67–75.

3. Кривуля А.В. Средства математического моделирования в задачах прямоугольного покрытия произвольных многоугольных областей / А.В. Кривуля, М.В. Злотник, Т.Е. Романова // Радиоэлектроника и информатика. – 2007. – №4(39). – С. 31–36.

4. Романова Т.Е. Покрытие компактной многоугольной области конечным семейством прямоугольников / Т.Е. Романова, А.В. Кривуля // Журнал вычислительной и прикладной математики. – 2007. – №2(95). – С. 99–108.

5. Кривуля А.В. Математическая модель задачи покрытия многоугольной области семейством прямоугольников / А.В. Кривуля // Системи обробки інформації : зб. наук. праць. – Харків, 2007. – №8(66). – С. 143–145.

6. Злотник М.В. Стратегия решения задачи покрытия многосвязной многоугольной области / М.В. Злотник, А.В. Кривуля, А.В. Панкратов, Т.Е. Романова // Бионика интеллекта. – 2007. – № 2(67). – С. 51–55.

7. Романова Т.Е. Трансляционное прямоугольное покрытие / Т.Е. Романова, А.В. Кривуля // Доповіді Національної академії наук України. – 2008. – №7. – С. 48–53.

8. Романова Т.Е. Средства математического моделирования задач покрытия / Т.Е. Романова, А.В. Кривуля // Доповіді Національної академії наук України. – 2008. – №9. – С. 48–52.

9. Романова Т.Е. Математическая модель и метод решения задачи покрытия многоугольной области прямоугольными объектами / Т.Е. Романова, А.В. Кривуля, М.В. Злотник // Проблемы машиностроения. – 2008. – Т.11, №3. – С. 58–68.

10. Свідоцтво про реєстрацію авторського права на твір №24580 ДДІВ МОН України. Translational polygonal containment : комп’ютерна програма / Ю.Г. Стоян, Т.Є. Романова, Г.В. Кривуля, М.В. Злотник; заявл. 03.03.2008; зареєстр. 28.05.2008.

11. Свідоцтво про реєстрацію авторського права на твір №24581 ДДІВ МОН України. Translational polygonal covering : комп’ютерна програма / Ю.Г. Стоян, Т.Є. Романова, Г.В. Кривуля, М.В. Злотник; заявл. 03.03.2008; зареєстр. 28.05.2008.

12. Кривуля А.В. Критерий покрытия в задаче покрытия прямоугольной области прямоугольными объектами / А.В. Кривуля, А.В. Злотник // Комп’ютерний моніторинг та інформаційні технології : II Міжнародна наукова конференція студентів, аспірантів та молодих вчених, 15-17 травня 2006 р. : тези доповідей.– Донецьк, 2006. –С.248-249.

13. Злотник М.В. Математическое моделирование взаимодействий геометрических объектов в задаче покрытия прямоугольной области прямоугольными объектами / М.В. Злотник, А.В. Кривуля, Т.Е. Романова // Искусственный интеллект. Интеллектуальные и многопроцессорные системы : Седьмая международная научно-техническая конференция, 25–30 сентября 2006 г. : тезисы докл. –Таганрог – Донецк – Минск, 2006. –С. 293–295.

14. Кривуля А.В. Математическая модель задачи покрытия многоугольной области прямоугольными объектами / А.В. Кривуля // Современные проблемы машиностроения : конференция молодых ученых и специалистов, 2006 г. : тезисы докл. – Харьков, 2006. – С .27.

15. Romanova T. Cover criterion of polygonal region by polygons / T. Romanova Yu. Stoyan, G. Scheithauer, A. Krivulya // EURO XXII : 22^nd European conference on Operational Research, 8–11 July, 2007 : book of abstracts. – Prague, Czech Republic, 2007.–P.142.

16. Гончаренко Е.Ю. Трансляционное многоугольное включение / Е.Ю. Гончаренко, М.В. Злотник, А.В. Кривуля // Радиоэлектроника и молодежь в ХХI веке : ХI Международный молодежный форум, 10–12 апреля 2007 г. : тезисы докл.– Харьков, 2007.– С.164.

17. Кривуля А.В. Задача покрытия многоугольной области семейством прямоугольных объектов / А.В. Кривуля, Т.Е. Романова, М.В. Злотник // Искусственный интеллект. Интеллектуальные системы : международная научно-техническая конференция, 24–29 сентября 2007 г. : тезисы докл. – Донецк, 2007.–С. 327-329.

18. Кривуля А.В. Стратегия решения задачи покрытия многоугольной области прямоугольными объектами / А.В. Кривуля // Современные проблемы машиностроения : конференция молодых ученых и специалистов, 2007 г. : тезисы докл. – Харьков, 2007. – С .21.

19. Romanova T. Covering of a polygonal region by rectangles / T. Romanova, Yu. Stoyan, A. Krivulya, M. Zlotnik, G. Scheithauer // 18^th Workshop on Discrete Optimization : conference, 18–21 May, 2008 : book of abstracts.– Knigstein, Dresden, Germany, 2008.–P. 142.

20. Безденежных Ю.В. Особенности моделирования и решения задачи покрытия произвольной многоугольной области / Ю.В Безденежных, А.В. Кривуля // Радиоэлектроника и молодежь в ХХI веке : ХII Международный молодежный форум, 1–3 апреля 2008 г. : тезисы докл. – Харьков, 2008.– С. 347.

21. Кривуля А.В. Задача трансляционного покрытия произвольной многоугольной области / А.В. Кривуля // Современные задачи прикладной статистики, промышленной, актуарной и финансовой математики : Четвертая всеукраинская научно-практическая конференция студентов, аспирантов и молодых ученых, 23–25 апреля 2008 г.: тезисы докл. – Донецк, 2008. – С. 27–28.

22. Scheithauer G. Covering a polygonal region by rectangles /Scheithauer G., Stoyan Y. G., Romanova T., Krivulya A. – Technische Univarsitt Dresden, 2008. – P. 18. – (Preprint / Technische Univarsitt Dresden; MATH-NM-05-2008).