Размещено на http://www.allbest.ru/

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ ПРОБЛЕМ МАШИНОБУДУВАННЯ

ім. А.М. ПІДГОРНОГО

01.05.02 - математичне моделювання та обчислювальні методи

УДК 519.853.7

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

ПОБУДОВА МАТЕМАТИЧНОЇ МОДЕЛІ І РОЗВ'ЯЗАННЯ ЗАДАЧІ ПОКРИТТЯ КОМПАКТНОЇ БАГАТОГРАННОЇ МНОЖИНИ НАБОРОМ ПРЯМИХ ПАРАЛЕЛЕПІПЕДІВ

Сосюрка Олена Сергіївна

Харків 2010

Дисертацією є рукопис.

Робота виконана в Інституті проблем машинобудування ім. А.М. Підгорного НАН України.

Науковий керівник: член-кореспондент НАН України, доктор технічних наук, професор Стоян Юрій Григорович, Інститут проблем машинобудування ім. А.М. Підгорного НАН України, завідувач відділу математичного моделювання та оптимального проектування.

Офіційні опоненти:

доктор фізико-математичних наук, доцент Рубльов Богдан Владиславович, Київський національний університет ім. Тараса Шевченка, професор кафедри обчислювальної математики;

кандидат фізико-математичних наук, доцент Карташов Олексій Вікторович, Національний аерокосмічний університет ім. М.Є. Жуковського «ХАІ», доцент кафедри інформатики.

Захист відбудеться “28” квітня 2011 р. о 14 годині на засіданні спеціалізованої вченої ради Д 64.180.01 в Інституті проблем машинобудування ім. А.М. Підгорного НАН України за адресою: 61046, Харків, вул. Дм. Пожарського, 2/10.

З дисертацією можна ознайомитись в бібліотеці Інституту проблем машинобудування ім. А.М. Підгорного НАН України за адресою: 61046, Харків, вул. Дм. Пожарського, 2/10.

Автореферат розісланий “___” березня 2011 р.

Вчений секретар спеціалізованої вченої ради доктор технічних наук О.О. Стрельнікова

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

математичний покриття паралелепіпед

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

Задачі покриття виникають у різних галузях науки і техніки і полягають у пошуку покриття заданої області деякою множиною геометричних об'єктів. Зустрічаються задачі покриття в системах статичного інспектування та спостереження кількома видами сенсорів, при розпізнаванні форми або контуру у робототехніці та в багатьох інших галузях.

Розглянувши сучасний стан задач покриття, можна зробити висновок, що розроблено деякі точні та наближені методи розв'язання двовимірних задач покриття як сім'єю ідентичних об'єктів, так і сім'єю об'єктів, метричні характеристики яких відмінні, і тривимірних задач покриття набором ідентичних куль. Щодо компактних багатогранних множин покриття і набору покриваючих об'єктів з різними розмірами, то в цьому випадку використовуються або евристичні методи, або методи, основою яких є апроксимація форм геометричних об'єктів прямими паралелепіпедами, а отже, послаблення обмежень задачі. Взагалі ж клас тривимірних задач покриття є недостатньо вивченим. Тому виникає необхідність у більш поглибленому дослідженні та розробці конструктивних засобів математичного моделювання, побудові адекватної математичної моделі задачі, дослідженні її особливостей та розробці нових методів розв'язання наукових та практичних задач покриття, зокрема конкретного зазначеного класу, що і визначило тему даної дисертаційної роботи.

Дисертаційна робота є продовженням досліджень, які виконуються в Інституті проблем машинобудування ім. А.М. Підгорного НАН України та пов'язані з розробкою методів розв'язання задач покриття.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в період з 2007 по 2010 рр. у відділі математичного моделювання та оптимального проектування Інституту проблем машинобудування ім. А.М. Підгорного НАН України згідно з планами науково-дослідницьких робіт за держбюджетною темою III-24-07 “Розробка конструктивних засобів і обчислювальних методів для розв'язання оптимізаційних задач пакування та покриття” (№ ДР 0107U003665) і договором про наукове співробітництво між Інститутом проблем машинобудування ім. А.М. Підгорного НАН України та Дрезденським технічним університетом (Німеччина).

Мета і задачі дослідження. Метою роботи математичне та комп'ютерне моделювання покриття, розробка методу розв'язання задачі покриття компактної багатогранної множини скінченним набором прямих паралелепіпедів.

Для досягнення цієї мети у дисертації були сформульовані і вирішені такі основні наукові задачі:

· розробка конструктивних засобів моделювання теоретико-множинних відношень (перетину, належності) між компактною багатогранною множиною (надалі, множиною покриття) та множиною, що утворена об'єднанням скінченного набору прямих паралелепіпедів;

· побудова математичної моделі тривимірної задачі покриття компактної багатогранної множини скінченним набором прямих паралелепіпедів;

· дослідження особливостей математичної моделі задачі;

· розробка методу розв'язання тривимірної задачі покриття на основі подальшого розвитку існуючих методів геометричного проектування та математичного програмування;

· створення програмного забезпечення, що реалізує розроблені засоби математичного моделювання та розв'язання задачі покриття на основі побудованої математичної моделі та запропонованого методу.

Об'єкт дослідження. Об'єктом дослідження є процес покриття тривимірної багатогранної множини скінченним набором прямих паралелепіпедів.

Предмет дослідження. Предметом дослідження є математична модель і метод розв'язання задачі покриття компактної багатогранної множини скінченною сім'єю прямих паралелепіпедів.

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

Наукова новизна отриманих результатів полягає у такому:

– набув подальшого розвитку метод Г-функції (функції покриття) на випадок покриття тривимірної багатогранної множини набором прямих паралелепіпедів;

– вперше побудовано математичну модель тривимірної задачі покриття компактної багатогранної множини набором прямих паралелепіпедів та двох її реалізацій: задачі покриття скінченним набором прямих паралелепіпедів різних розмірів та задачі покриття мінімальною кількістю однакових прямих паралелепіпедів;

– вперше запропоновано метод розв'язання тривимірної задачі покриття скінченним набором прямих паралелепіпедів різних розмірів, що дозволяє звести задачу покриття до розв'язання послідовності задач лінійного програмування;

– вперше запропоновано метод розв'язання тривимірної задачі покриття мінімальною кількістю однакових прямих паралелепіпедів, який ґрунтується на зведенні задачі до послідовності задач лінійного програмування.

Практичне значення отриманих результатів. На підставі результатів дисертаційної роботи, розроблених методів і запропонованих алгоритмів розв'язання задачі покриття створено комп'ютерні програми: “3D covering problem” та “3D minimal covering problem”, що можуть бути використані для розв'язання як тривимірних задач покриття компактної багатогранної множини сім'єю паралелепіпедів, що виникають у різноманітних галузях науки та техніки: системах статичного інспектування, аеро- та космічних системах спостереження, розпізнавання форми або контуру у робототехніці, “art gallery problem”, так і задач, які до них зводяться.

Розроблені засоби математичного та комп'ютерного моделювання: моделі, методи, алгоритми, програмне забезпечення являють собою подальший розвиток теорії геометричного проектування та набувають важливого значення для розв'язання задач, що виникають у різних технічних та наукових процесах.

Особистий внесок здобувача. Всі основні наукові результати дисертаційної роботи отримані особисто автором.

У роботах, написаних у співавторстві, дисертанту належать такі результати: у роботі [4] - побудовано математичну модель та поширено стратегію розв'язання задачі трансляційного покриття на випадок тривимірного простору, [14] - запропоновано алгоритмічну та програмну реалізацію методу розв'язання тривимірної задачі мінімального покриття.

Апробація результатів дисертації. Результати дисертаційної роботи доповідалися та одержали схвалення на міжнародних конференціях і наукових семінарах: конференціях молодих вчених і фахівців “Сучасні проблеми машинобудування” (м. Харків, 2008 - 2010 рр.); всеукраїнській та міжнародній наукових конференціях молодих вчених “Фізика низьких температур” (м. Харків, 2009, 2010 рр.); II міжнародній науковій конференції “Математичне моделювання та диференціальні рівняння” (Білорусь, м. Мінськ, 2009 р.); 14-му міжнародному молодіжному форумі «Радиоэлектроника и молодежь в 21 веке» (м. Харків, 2010 р.); 12-й міжнародній науково-технічній конференції «Системный анализ и информационные технологии» (м. Київ, 2010 р.); міжнародній конференції «Problem of decision making under uncertainties» (м. Львів, 2010 р.); 5-й науково-практичній конференції з міжнародною участю «Математичне та імітаційне моделювання систем» (м. Київ, 2010 р.); міжнародній конференції з дослідження операцій «EURO XXIV» (Lisbon, 2010 р.); конференції молодих учених «Підстригачівські читання - 2010» (м. Львів, 2010 р.); на семінарах відділу математичного моделювання та оптимального проектування ІПМаш ім. А.М. Підгорного НАН України (м. Харків, 2007 - 2010 рр.).

Публікації. За темою дисертації опубліковано 16 наукових праць, у тому числі 4 статті в наукових спеціалізованих виданнях, що входять до переліку ВАК України, 12 тез доповідей на наукових конференціях (включаючи міжнародні).

Структура й обсяг дисертації. Дисертація складається зі вступу, п'яти розділів, висновків, списку використаних джерел зі 117 найменувань (12 с.) та одного додатку, що займає 21 с. Загальний обсяг роботи складає 179 сторінок, включаючи 77 рисунків та 4 таблиці.

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

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

У першому розділі наведено огляд літератури за темою дисертації та обрано напрям досліджень. Проведено аналітичний огляд методології математичного моделювання та сучасних засобів розв'язання класу задач, що розглядаються.

В рамках теорії геометричного проектування задачі покриття досліджуються у роботах Ю.Г. Стояна, С.В. Яковлева, О.М. Кісельової, В.М. Комяк, Т.Є. Романової, В.М. Пацука, Г.В. Кривулі та ін. Вивченню та розв'язанню задач покриття присвячено роботи і багатьох іноземних вчених: L. Toth, V. Milencovich, Z. Li, D. Hochbaum, W. Maass, K. Daniels та їх учнів. На підставі аналізу сучасного стану даної проблеми за матеріалами вітчизняної та зарубіжної наукової літератури можна зробити наступні висновки: більшість геометричних задач покриття належать до класу NP-повних задач; переважна кількість методик розв'язання задач означеного класу є евристичними. У випадку тривимірного простору відомі тільки дві роботи, що присвячені задачам покриття. Одна з них (Cao An Wang, Bo-Ting Yang, Binzhai Zhu) суттєво обмежує кількість покривних об'єктів до двох, а інша (K. Daniels, B. England) - вимагає, щоб множина покриття була прямим паралелепіпедом. Таким чином, на цей час клас тривимірних задач покриття з довільною множиною покриття та без обмежень на кількість покривних об'єктів потребує розробки методів розв'язання, що, в свою чергу, вимагає створення конструктивних засобів математичного та комп'ютерного моделювання відношень покривних об'єктів та множини покриття, що і визначило тему даної роботи.

В другому розділі наведено конструктивні засоби математичного та комп'ютерного моделювання задачі покриття (надано визначення та побудовано Г-функції покриття, досліджено їх властивості), сформульовано постановку основної задачі дослідження.

Нехай задана скінченна сім'я паралелепіпедів

де - тривимірний арифметичний евклідів простір, та компактна багатогранна множина , така, що

,

, - внутрішність множини .

Розташування і у просторі однозначно визначається векторами трансляції та , . Паралелепіпед , трансльований на вектор , позначимо через , а сім'ю трансльованих паралелепіпедів - через , де .

Визначення 1. Сім'я називається покриттям множини , якщо існує вектор , такий, що виконується співвідношення

.(1)

Тривимірна задача покриття. Необхідно визначити параметри розташування , якщо такі існують, за яких сім'я є покриттям множини у сенсі виконання умови (1).

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

Задача покриття заданою кількістю різних паралелепіпедів виникає, якщо параметри розташування множини покриття є фіксованими, а параметри розташування , покривних паралелепіпедів , - змінні, тобто , .

Задача 1. (задача покриття). Необхідно визначити, якщо такий існує, вектор , такий, що сім'я є покриттям множини у сенсі співвідношення (1).

У випадку, коли метричні характеристики (розміри) покривних паралелепіпедів (однакових) сталі і наперед задані, а кількість їх невідома, постає задача мінімального покриття.

Задача 2. (задача мінімального покриття). Необхідно визначити мінімальну кількість однакових прямих паралелепіпедів заданих розмірів та їх параметри розташування у просторі , за умови, що об'єднання трансльованих паралелепіпедів є покриттям множини , тобто виконання умови (1) при .

Розглянемо множину . Позначимо

,

де - замикання множини . Тоді умова (1) може бути записана в еквівалентному вигляді:

.(2)

Для аналітичного опису умови покриття в даному дослідженні використовується математичний апарат Ф-функцій.

Визначення 2. Безперервна, всюди визначена функція , називається Ф-функцією пари довільних об'єктів та , якщо вона задовольняє такі характеристичні властивості:

, якщо ; , якщо та ; , якщо ,

де - границя множини .

Як критерій покриття області сім'єю запропоновано умову

,(3)

де - Ф-функція множин

і , де - початок власної системи координат багатогранника .

Множину подамо у вигляді , де - кількість компонент зв'язності множини . В свою чергу, множину пропонується надати у вигляді об'єднання базових множин , де , а саме - напівпростори, - двогранні кути, - тригранні кути, - напівнескінченні циліндри з прямокутною основою, - нескінченні циліндри з прямокутною основою та - прямі паралелепіпеди, що описуються системами з не більш ніж шести нерівностей вигляду

, , , де , , , , , .

Теорема 1. Нехай - Ф-функція множин та , , , тоді

- Ф-функція множин і .

При цьому,

,

в свою чергу, функція набуває одного із таких виглядів:

,

,

,

,

,

,

.

Для аналітичного опису відношень (включення, перетин) між областю покриття та скінченною сім'єю покривних об'єктів досліджується взаємне розташування різноманітних пар паралелепіпедів сім'ї . Нехай , , - набори вершин, ребер та граней паралелепіпеда відповідно. Кожна пара і може бути в одному з таких типів взаємного розташування:

1) ;

2) та ,

при цьому для будь-якого вірно, що , та для будь-якого вірно, що (в залежності від номера вершини можливо вісім типів);

3) та для будь-якого вірно, що (в залежності від номера ребра можливо дванадцять типів);

4) але (в залежності від номера грані можливо шість типів);

5) для будь-яких вірно, що , при цьому (можливо чотири типи).

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

Доведено теорему про розбиття простору параметрів розміщення двох довільних паралелепіпедів на множини , такі, що, якщо , то взаємне розташування паралелепіпедів і буде -го типу, на підставі якої здійснено розбиття простору параметрів розміщення на підмножини .

Теорема 2. Розбиття простору для сім'ї прямих паралелепіпедів має вигляд:

, ,(4)

де ,

, ,

,

- прямий циліндр з основою ,

,

при цьому

, якщо

або , або , або ;

, якщо

де або , або ;

, якщо де або ;

, якщо де або .

З метою математичного та комп'ютерного моделювання відношень компактної багатогранної множини покриття та сім'ї покривних паралелепіпедів побудовано Г-функцію покриття. Для цього спочатку введено в розгляд функцію , , де -Ф-функція множин та . В свою чергу, . Таким чином, якщо при , то , тобто виконана умова покриття (2). На основі розбиття простору параметрів розміщення покриваючих паралелепіпедів на підмножини побудовано Г-функцію

(5)

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

Математичну модель основної задачі покриття наведемо у вигляді:

знайти, якщо існують, та , такі, що

.(6)

Зауваження 1. Якщо знайдуться такі , що , то виконана умова покриття (2) і сім'я є покриттям множини . Якщо ж , то покриття не існує.

Задача 1, як реалізація тривимірної задачі покриття, може бути подана у вигляді оптимізаційної задачі, де як функція цілі виступає значення Г-функції, яке відповідає на питання, чи є сім'я трансльованих паралелепіпедів покриттям множини , чи ні. Математична модель такої задачі має вигляд:

(7)

де визначається формулою (5).

Зауваження 2. Якщо знайдеться хоча б один вектор , при якому , тоді є покриттям множини , і процес розв'язання задачі завершується. Однак, якщо для будь-якого вектору , то покриття множини сім'єю не існує.

Відзначимо основні особливості математичної моделі (7).

1. Функція цілі - кусково-лінійна.

2. Задача (7) зводиться до послідовності задач

,(8)

,(9)

де - кількість функцій - Ф-функцій для множин та .

3. Як тільки виконається нерівність , покриття отримане.

4. Задача (8-9) зводиться до послідовності задач лінійного програмування вигляду

, (10)

де область ,

,

де - кількість базових об'єктів , , що беруть участь у формуванні множини , - кількість функцій, що беруть участь у формуванні Ф-функцій для та .

5. Задача (6) є багатоекстремальною, NP-складною.

Для розв'язання задачі 2 розглянемо наступну задачу. Ввівши коефіцієнт гомотетії в якості функції цілі, вважаємо розміри покривних паралелепіпедів змінними з точністю до коефіцієнта гомотетії. Тобто

.

Тоді розв'язання задачі 2 в вихідній постановці зводиться до розв'язання послідовності задач :

Задача . Необхідно визначити вектор , такий, що сім'я є покриттям множини , а значення коефіцієнта гомотетії - мінімальне.

Таким чином, якщо в результаті розв'язання задачі для паралелепіпедів виконується умова і коефіцієнт гомотетії при цьому , то кількість паралелепіпедів сім'ї , необхідних для покриття множини , дорівнює , інакше збільшуємо кількість паралелепіпедів і для них розв'язуємо задачу . Математичну модель задачі мінімального покриття подамо у вигляді

, (11)

де .

Основні особливості математичної моделі (11).

1. Функція цілі - лінійна.

2. Якщо , то .

3. Якщо і , то вектор , що відповідає , забезпечує покриття множини : .

4. Розв'язання задачі (11) зводиться до розв'язання послідовності задач лінійного програмування

, (12)

де

, .(13)

У четвертому розділі запропоновано методи та побудовано алгоритми розв'язання поставлених задач покриття на основі методу внутрішньої точки.

Стратегія розв'язання задачі покриття (задачі 1).

Беручи за основу властивості математичної моделі (7), пропонується загальна стратегія розв'язання задачі покриття компактної багатогранної множини сім'єю прямих паралелепіпедів, яка зводиться до наступних етапів:

1. Обчислення коефіцієнта

,

де ,

- об'єм , - об'єм . Якщо , то покриття не існує свідомо, в протилежному випадку йдемо до наступного етапу.

2. Побудова систем лінійних нерівностей, що однозначно визначають підмножини .

3. Побудова Ф-функцій для множин та .

4. Формування стартового вектора параметрів розміщення або методом випадкового вибору, або методом апроксимації прямим паралелепіпедом найменших розмірів. Нехай .

5. Формування системи нерівностей, що визначає множину .

6. Побудова та зображення її у вигляді .

7. Побудова функції для та . Перевірка критерію покриття (3): якщо умова (3) не виконана - йдемо до наступного кроку, інакше вектор - розв'язок задачі (1).

8. Побудова функції та виділення системи нерівностей вигляду , яку задовольняє .

9. Розв'язання задачі (8-9).

10. Нехай - розв'язок задачі, якому відповідає значення цільової функції . Якщо - покриття знайдено, інакше переходимо до наступного кроку.

11. Формування системи, що визначає , суміжну до , і містить .

12. Приймаємо за , формування множини .

13. Побудова функції для множин та . Перевірка критерію покриття (3). Якщо , тоді переходимо до наступного кроку. Інакше вектор - розв'язок задачі (1).

14. Побудова функції та виділення системи нерівностей вигляду , яку задовольняє .

15. Розв'язання задачі (8-9).

16. Нехай - розв'язок задачі, якому відповідає значення цільової функції . Якщо - покриття знайдено. Якщо , то переходимо до кроку 4, якщо , то - до кроку 11.

17. Перевірка критерію зупинки. За критерій зупинки беремо обмеження на час обчислення.

Стратегія розв'язання задачі покриття компактної багатогранної множини мінімальною кількістю однакових прямих паралелепіпедів заданих розмірів.

1. Побудова систем нерівностей, що визначають .

2. Побудова Ф-функцій для множин та .

3. Вибір стартової кількості паралелепіпедів .

4. Формування випадковим чином стартового вектора параметрів розміщення . Покладаємо .

5. Формування системи нерівностей, що визначає підмножину .

6. Формування множини та зображення її у вигляді об'єднання базових множин .

7. Побудова функції для та .

8. Побудова функції та виділення системи нерівностей вигляду , яку задовольняє .

9. Розв'язання задачі лінійного програмування (12-13).

10. Нехай розв'язок задачі, - відповідне значення цільової функції. Якщо , то , задача розв'язана ( - необхідна кількість паралелепіпедів, - параметри їх розміщення), в іншому випадку переходимо до наступного етапу.

11. Формування , яка суміжна до і містить , та системи, що її визначає.

12. Покладаємо , формування та зображення її у вигляді об'єднання базових множин.

13. Побудова функції для та .

14. Побудова функції та виділення системи нерівностей вигляду , яку задовольняє .

15. Розв'язання задачі (12-13).

16. Нехай - розв'язок задачі, якому відповідає значення цільової функції . Якщо , то , (необхідна кількість паралелепіпедів дорівнює , вектор - їх параметри розміщення). Якщо , то переходимо до кроку 11, якщо - до кроку 4, поклавши .

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

У п'ятому розділі наведено чисельні приклади розв'язання задачі покриття та задачі мінімального покриття для множини покриття довільної просторової форми, а саме: опуклий багатогранник (рис. 1, 2), неопуклий багатогранник (рис. 3, 4), багатозв'язна багатогранна множина (рис. 5, 6).

У додатках наведено опис розроблених комп'ютерних програм.

Рис. 1. Покриття опуклого багатогранника

Рис. 2. Мінімальне покриття опуклого багатогранника

Рис. 3. Покриття неопуклого багатогранника

Рис. 4. Мінімальне покриття неопуклого багатогранника

Рис. 5. Покриття багатозв'язної багатогранної множини

Рис. 6. Мінімальне покриття багатозв'язної багатогранної множини

ОСНОВНІ ВИСНОВКИ ПО РОБОТІ

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

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

На основі доведених теорем здійснено розбиття простору змінних в залежності від метричних характеристик та параметрів розміщення покривних паралелепіпедів.

Набув подальшого розвитку метод Г-функції (функції покриття) на випадок покриття тривимірної компактної багатогранної множини набором прямих паралелепіпедів.

Вперше побудовано математичні моделі тривимірної задачі покриття та таких її реалізацій, як тривимірна задача покриття скінченною сім'єю прямих паралелепіпедів різних розмірів та тривимірна задача мінімального покриття скінченною сім'єю однакових прямих паралелепіпедів. Досліджено основні особливості запропонованих математичних моделей, що дозволило застосувати ідеологічно близькі методики їх розв'язання.

Розроблено методи розв'язання трансляційної задачі покриття та задачі покриття мінімальною кількістю однакових прямих паралелепіпедів.

Створено програмні продукти “3D covering problem” та “3D minimal covering problem”, які реалізують запропоновані засоби, моделі і методи розв'язання тривимірних задач покриття.

СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

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.

АНОТАЦІЯ

Сосюрка О.С. Побудова математичної моделі і розв'язання задачі покриття компактної багатогранної множини набором прямих паралелепіпедів. - Рукопис.

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

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

Як конструктивний засіб математичного та комп'ютерного моделювання задач покриття використовується математичний апарат Ф-функцій (для аналітичного опису критерію покриття) і Г-функція (функція покриття) для аналітичного опису відношень сім'ї трансльованих покривних паралелепіпедів та множини покриття. Побудовано математичні моделі тривимірної задачі покриття та її реалізацій у вигляді оптимізаційних задач. Досліджено їх основні особливості. Задачі є багатоекстремальними та NP-складними. Запропоновано методи розв'язання тривимірної задачі покриття скінченним набором прямих паралелепіпедів різних розмірів та задачі покриття мінімальною кількістю однакових прямих паралелепіпедів. Запропоновано методи та розроблено алгоритми розв'язання, які реалізовано у відповідному програмному забезпеченні. Наведено числові результати розв'язання тривимірних задач покриття компактних багатогранних множин.

Ключові слова: математичне моделювання, покриття, мінімальне покриття, багатогранна множина, сім'я паралелепіпедів, критерій покриття, Ф-функція, Г-функція, оптимізація.

АННОТАЦИЯ

Сосюрка Е.С. Построение математической модели и решение задачи покрытия компактного многогранного множества набором прямых параллелепипедов. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Институт проблем машиностроения им. А.Н. Подгорного НАН Украины, Харьков, 2010.

Диссертация является продолжением исследований задач геометрического проектирования, а именно - задач покрытия компактных областей набором прямоугольных объектов и посвящена решению актуальной научной задачи покрытия компактного многогранного множества конечным семейством прямых параллелепипедов.

В работе рассматривается трехмерная задача покрытия в следующих реализациях: трехмерная задача покрытия конечным набором прямых параллелепипедов в общем случае различных размеров (переменными являются параметры размещения прямых параллелепипедов, а их количество и метрические характеристики, а также расположение покрываемого множества в пространстве фиксированы) и трехмерная задача покрытия минимальным количеством одинаковых прямых параллелепипедов (переменными являются параметры размещения и необходимое количество параллелепипедов покрывающего семейства, при условии, что параллелепипеды конгруэнтны, их размеры фиксированы, расположение покрываемого множества в пространстве фиксировано).

В качестве конструктивного средства математического и компьютерного моделирования задачи покрытия используется математический аппарат Ф-функций (для аналитического описания критерия покрытия) и Г-функция (функция покрытия, зависящая от параметров размещения параллелепипедов покрывающего семейства) для аналитического описания отношений семейства транслированных покрывающих параллелепипедов и покрываемого множества.

Построены математические модели трехмерной задачи покрытия, задачи трансляционного покрытия и задачи минимального покрытия. Исследованы их особенности. Выделены общие существенные свойства этих задач, что позволило применить идеологически близкие методы решения рассматриваемых многоэкстремальных и NP-трудных задач.

Метод решения двухмерной трансляционной задачи покрытия распространен на случай трехмерной задачи, разработан метод решения трехмерной задачи покрытия компактного многогранного множества минимальным количеством одинаковых прямых параллелепипедов, позволяющий свести решение исходной задачи к решению последовательности задач линейного программирования.

Построенные математические модели, предлагаемые методы и разработанные пошаговые алгоритмы решения рассматриваемых трехмерных задач покрытия реализованы в соответствующем программном обеспечении, которое обеспечивает визуализацию процесса покрытия в реальном времени.

Приведены результаты решения задач покрытия, когда покрываемое множество является выпуклым многогранником, невыпуклым многогранником, многосвязным компактным множеством.

Все теоретические результаты представлены в виде сформулированных теорем, математических моделей и методов, которые приводятся впервые или обобщают уже известные на случай большей размерности.

На основании разработанных и предложенных средств, моделей и методов созданы программные модули «3D covering problem» и «3D minimal covering problem», которые могут быть использованы при распознавании образов в робототехнике, системах воздушного и космического наблюдения, графике, при создании систем технического зрения робота, а также при решении таких прикладных задач покрытия, как «Art gallery problem».

Ключевые слова: математическое моделирование, покрытие, минимальное покрытие, многогранное множество, семейство параллелепипедов, критерий покрытия, Ф-функция, Г-функция, оптимизация.

ABSTRACT

Sosyurka O.S. A mathematical model and solution method for the covering problem of a compact polyhedral set with a family of a right parallelepipeds. - Manuscript.

Thesis for a Candidate of Physical and Mathematical Sciences degree in the speciality 01.05.02 - mathematical modelling and computational methods. - A.N. Podgorny Institute for Mechanical Engineering Problems National Academy of Sciences Ukraine, Kharkov, 2010.

The dissertation is an extension of studies in geometric design problems, in particular, covering problems of a compact polyhedral set with a finite family of rectangular objects and devoted to the solving an urgent scientific covering problem of a compact multiply connected set with a finite family of right parallelepipeds. Two realizations of the three-dimensional covering problem are discussed: the covering problem with the finite family of the different sized right parallelepipeds (when the placement parameters of the set to be covered and the number of covering parallelepipeds are fixed and the placement parameters of parallelepipeds are variable) and a minimal covering problem with the congruent right parallelepipeds (when the placement parameters of the set to be covered and sizes of covering parallelepipeds are fixed and the placement parameters of parallelepipeds and their number are variable).

The mathematical apparatus of Ф-functions are applied for analytical description of the covering criterion and -function (function coverage) for an analytical description of relations between a family of translated covering parallelepipeds and the area to be covered as a constructive tools of mathematical and computer modeling. Mathematical model of the three-dimensional covering problem and its two realizations are constructed. Characteristics of these models are investigated. The problem is multiextremal and NP-hard. The solution methods of a three-dimensional covering problem with the finite family of the different sized right parallelepipeds and a minimal covering problem with the family of the identical right parallelepipeds, allowing to reduce the original problems to solving a sequence of linear programming problems, are developed. The offered methods and the algorithms of solving, which are realized in the proper software, are provided. The results of solving covering problems of the compact polyhedral sets are presented.

Key words: mathematical modelling, covering, minimal covering, polyhedral set, a family of parallelepipeds, covering criterion, Ф-function, Г-function, optimization.

Размещено на Allbest.ru

...