Математична модель та метод розв’язання задачі розміщення неорієнтованих складених геометричних 2d об’єктів

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

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

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

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

АВТОРЕФЕРАТ

МАТЕМАТИЧНА МОДЕЛЬ ТА МЕТОД РОЗВ'ЯЗАННЯ ЗАДАЧІ РОЗМІЩЕННЯ НЕОРІЄНТОВАНИХ СКЛАДЕНИХ ГЕОМЕТРИЧНИХ 2D ОБ'ЄКТІВ

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

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

Науковий керівник:

доктор технічних наук, професор Романова Тетяна Євгеніївна, Інститут проблем машинобудування ім. А.М. Підгорного НАН України, старший науковий співробітник відділу математичного моделювання та оптимального проектування.

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

доктор технічних наук, професор Комяк Валентина Михайлівна, Університет цивільного захисту України Міністерства України з питань надзвичайних ситуацій та у справах захисту населення від наслідків Чорнобильської катастрофи, професор кафедри фізико-математичних дисциплін;

доктор технічних наук, професор Тевяшев Андрій Дмитрович, Харківський національний університет радіоелектроніки, завідувач кафедри прикладної математики.

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

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

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

Загальна характеристика роботи

Актуальність теми. Задачі пакування та розкрою (в межах міжнародної класифікації: nesting problem, cutting-stock problem, irregular stock problem, multi-stock problem, irregular nesting problem), у подальшому задачі розміщення, виникають у багатьох галузях промисловості, у тому числі машинобудуванні, металургії, листовому розкрої, суднобудуванні, текстильній, паперовій, легкій промисловості. Ці задачі спрямовані на пошук раціонального розміщення об'єктів на промисловому матеріалі/листах з метою максимізування коефіцієнта використання матеріалу чи мінімізації відходів.

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

Цій тематиці присвячені роботи академіка АН СРСР Канторовича Л.В., академіка НАН України Рвачова В.Л., члена-кореспондента НАН України Стояна Ю.Г. та їх учнів, а також відомих вчених - Залгаллера В.А., Мухачевої Є.О. (Росія), Dowsland K., Kendal G., Bennell J. (Велика Британія), Terno J., Dychoff H., Scheithauer G. (Німеччина), Milenkovic V., Daniels K. (США), Gomes M., Fereira J. (Португалія), Ikonen I. (Фінляндія), Birgin E. (Бразилія) та ін.

У переважній частині задач, які виникають, наприклад, у металургії при листовому розкрої, текстильній промисловості, об'єкти мають довільну форму (irregular shaped objects). Окрім того, останнім часом найбільш поширеним є індивідуальне (ексклюзивне) виробництво. В зв'язку з цим з'являється необхідність у пошуку розташування невеликої кількості різноманітних об'єктів за мінімальних часових затрат та максимального використання промислового матеріалу. Задачі розміщення об'єктів у одній або декількох областях складеної конфігурації (multi-stock problems) можуть бути звичайним чином зведені до задач розміщення об'єктів у прямокутній смузі нескінченної довжини із зонами заборони.

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

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

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

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

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

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

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

проведено дослідження властивостей побудованих Ф-функцій;

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

проведено дослідження математичної моделі;

розроблено стратегію розв'язку основної оптимізаційної задачі розміщення;

створено програмне забезпечення.

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

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

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

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

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

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

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

набув подальшого розвитку метод розв'язання задач пакування неорієнтованих базових об'єктів на випадок розміщення неорієнтованих складених геометричних об'єктів у прямокутній області (rectangular stock-problems for irregular shaped objects) із урахуванням зон заборони (prohibited areas) у сенсі побудови дерева розв'язків для кожної Ф-нерівності пари складених об'єктів.

Практичне значення отриманих результатів. Наукові результати дисертаційної роботи є подальшим розвитком теорії геометричного проектування. На підставі розроблених засобів, моделей та методів розроблено програми “Packing of circles, rotating circular segments and polygons” (отримано свідоцтво про реєстрацію авторського права на твір), “Packing of non-oriented composed objects”. Сукупність розроблених засобів математичного та комп'ютерного моделювання, математичних моделей, методів, алгоритмів та програм можуть бути використані у машинобудуванні, текстильній, паперовій, легкій, взуттєвій, деревообробній промисловості, при лазерному розкрої в рекламі тощо.

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

Результати дисертаційних досліджень використовуються у науково-виробничому підприємстві ТОВ "ЕЛКОР КОМПЛЕКТ" (м. Харків) на етапі конструкторського проектування при розробці АСУ технологічних процесів оптимізації розміщення 2D неорієнтованих об'єктів на промисловому матеріалі, на виробничій базі в КП ХКБМ ім. О.О. Морозова. Запропоновані у роботі засоби, моделі і методи впроваджено в навчальному процесі у Харківському національному університеті внутрішніх справ і Харківському національному університеті радіоелектроніки, про що свідчать відповідні акти.

Особистий внесок здобувача. Всі основні наукові результати дисертаційної роботи отримані особисто автором. У працях, що написані у співавторстві, дисертантові належать такі результати: у [1] - f-функції для базових об'єктів та відрізків прямих; [2, 3, 9, 10] - Ф-функції розширеного класу орієнтованих базових об'єктів; [4-7, 13] - Ф-функції розширеного класу неорієнтованих базових об'єктів; [3, 12] - математична модель задачі розміщення орієнтованих об'єктів розширеного класу базових об'єктів; [5, 14, 15] - математична модель та стратегія розв'язання задачі розміщення розширеного класу неорієнтованих базових об'єктів; [6, 7, 16] - Ф-функції сім'ї неорієнтованих складених об'єктів, математична модель та стратегія розв'язання задачі розміщення сім'ї неорієнтованих складених об'єктів із урахуванням зон заборони; [8] - програмна реалізація методу розв'язання основної задачі розміщення.

Апробація результатів дисертації. Результати дисертаційної роботи доповідались і отримали схвалення на міжнародних конференціях і наукових семінарах: II міжнародній науковій конференції студентів, аспірантів та молодих вчених "Комп'ютерний моніторинг та інформаційні технології" (Донецьк, 2006); VII, VIII міжнародних науково-технічних конференціях "Искусственный интеллект. Интеллектуальные и многопроцессорные системы" (Донецк, 2006, 2007); конференції молодих вчених і спеціалістів "Современные проблемы машиностроения" (Харків, 2006-2008); XI, XI міжнародних молодіжних форумах "Радиоэлектроника и молодежь в XXI веке" (Харків, 2007, 2008); 5th ESICUP Meeting L'Aquila (Italy, 2008); на постійно діючих семінарах “Математичні методи геометричного проектування” при науковій раді з проблеми “Кібернетика” НАН України (Харків, 2005-2009); на семінарах відділу математичного моделювання та оптимального проектування Інституту проблем машинобудування ім. А.М. Підгорного НАН України (Харків, 2005-2009).

Публікації. За темою дисертації опубліковано 17 наукових робіт, у тому числі 7 статей у наукових спеціалізованих виданнях, які включені до переліку ВАК України, 9 тез доповідей на наукових конференціях і 1 свідоцтво про реєстрацію авторського права на твір.

Структура й обсяг дисертації. Дисертація складається зі вступу, п'яти розділів, висновків по роботі, чотирьох додатків (16с.) та списку використаної літератури зі 150 найменувань (14с.). Загальний обсяг роботи складає 148 сторінок , серед них 117 сторінок основного тексту, включаючи 71 рисунок та 5 таблиць.

Основний зміст роботи

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

У першому розділі на підставі вивчення літературних джерел проведено огляд літератури за темою дисертації та обрано напрями досліджень. Вивченню та розв'язанню 2D задач розміщення геометричних об'єктів присвячені роботи багатьох іноземних вчених: V. Milencovich, K. Daniels, J. Ferreira, J. Oliveira, M. Gomes, E. Burke, G. Kendall, E. Birgin, W. Huang, J. Bennell та ін. У публікаціях автори розглядають багатокутні та прямокутні об'єкти, при цьому дозволяється обертання об'єктів, що розміщуються на дискретний кут, або розміщують тільки круги. Для моделювання основних обмежень багатокутного розміщення використовуються No-Fit полігони або D-функції. Для розв'язання задач розміщення об'єктів з границею, що утворена об'єднанням дуг кіл та відрізків прямих, автори, як правило, здійснюють апроксимацію об'єктів багатокутниками, або пропонують алгоритми, які реалізують аналіз взаємного розміщення відрізків прямих та дуг кіл для границь кожної пари об'єктів, що розміщуються. В зв'язку з цим, як правило, використовуються евристичні підходи. Застосування сучасних методів оптимізації потребує побудування математичних моделей задач пакування та розкрою як задач математичного програмування.

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

В рамках теорії геометричного проектування у роботах Ю.Г. Стояна та його учнів, у тому числі М.І. Гіля, О.О. Панасенка, В.М. Комяк, С.В. Яковлева, В.П. Путятіна, М.В. Новожилової, О.К. Пандоріна, О.В. Панкратова, Т.Є. Романової, А.В. Карташова, Г.М. Яськова, А.М. Чугая, М.В. Злотника, розглядаються засоби математичного моделювання (годограф функції щільного розміщення, структури нерівностей, Ф-функція) та методи розв'язання задач розміщення базових орієнтованих та неорієнтованих 2D об'єктів. На цей час, є відкритим питання моделювання оптимальних розміщень однозв'язних або багатозв'язних об'єктів більш складної конфігурації, у тому числі об'єктів, границя яких подана об'єднанням дуг кіл та відрізків прямих. математичний моделювання геометричний розміщення

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

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

В якості базових неорієнтованих 2D об'єктів розглядається множина , де - множина однозв'язних, а - множина двозв'язних 2D базових неорієнтованих об'єктів. В межах даного дослідження, вважаємо, що , , де - круги , - опуклі багатокутники , - сегменти, , , - їх доповнення до всього двовимірного арифметичного евклідового простору .

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

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

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

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

, (1)

де , , , .

Геометрична інформація про об'єкт вигляду (1) задається кортежем

,

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

Об'єкти вигляду (1), які задовольняють властивості:

(2)

формують сім'ю складених -об'єктів.

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

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

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

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

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

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

Вважаємо, що об'єкти , .

Тоді є справедливим таке твердження.

Теорема. Функція

(3)

є Ф-функцією складених об'єктів та ,

де , , - Ф-функції об'єктів та ; та ; та відповідно.

У роботі доведено, що функція (3) задовольняє визначенню Ф-функції.

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

Ф-функція об'єктів и має вигляд

де , , , ,

тут , - радіуси та параметри розміщення об'єктів , , , відповідно; , - радіус та параметри розміщення об'єкта .

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

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

Основна задача розміщення. Розмістити об'єкти , , в області так, щоб виконувались співвідношення

, ,

, , (4)

та змінна набувала мінімального значення, де .

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

Математична модель основної задачі розміщення сім'ї неорієнтованих складених об'єктів має вигляд

, (5)

де , , , , тут , - Ф-функція та , - Ф-функція та , , - Ф-функція та , - Ф-функція та , , .

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

Задача (5) - нелінійна з лінійною функцією мети.

Область припустимих розв'язків - незв'язна з багатозв'язними компонентами зв'язності.

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

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

Область може бути подана у вигляді об'єднання , ,

, (6)

де - верхня оцінка числа всіх систем нелінійних нерівностей.

Верхня оцінка має вигляд

де , - число кругів, - число багатокутників, - число сегментів, що формують , - число вершин багатокутника.

Верхня оцінка числа нерівностей, що формують область

де

.

Враховуючи (6), задача (5) може бути перетворена до вигляду

(7)

Де

. (8)

Кожна задача (8) є багатоекстремальною задачею нелінійного програмування. У загальному випадку локальні мінімуми нестрогі. Задача (7)-(8) - NP-складна.

У п'ятому розділі розглядається стратегія та покроковий алгоритм розв'язання задачі (7)-(8). Наводяться результати чисельних експериментів у вигляді рисунків та графіків.

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

Для розв'язання задачі (7)-(8) пропонується стратегія, що дозволяє отримувати локально оптимальні розв'язки.

Далі наведена схема, яка ілюструє стратегію розв'язання задачі (7)-(8).

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

Алгоритм, який реалізує дану стратегію, полягає у такому.

1) Апроксимація області розміщення та складених об'єктів , , багатокутниками , , де - об'єднання елементарних прямокутників однакової ширини.

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

3) Формування множини .

4) Пошук точок локального мінімуму для кожної початкової точки модифікованим методом Зойтендейка.

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

5) Формування множини .

6) Пошук наближення до глобального мінімуму: , .

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

На рисунках 4-5 наводяться приклади пакування розширеного класу базових об'єктів та сім'ї складених об'єктів.

На рисунку 4 наведені розміщення n=32 базових неорієнтованих об'єктів у прямокутній смузі шириною h=12, які відповідають початковій точці (u⁰, l⁰=14.323) та локально-оптимальному розв'язку (u*, l^*=10.369).

На рисунку 5 наведені розміщення n=31 складених неорієнтованих об'єктів у прямокутній смузі шириною h=25 із урахуванням зон заборони , які відповідають початковій точці (u⁰, l⁰=29.88) та локально-оптимальному розв'язку (u*, l^*=23.78).

Наведені приклади розв'язання прикладних задач, які виникають у машинобудуванні та у рекламі.

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

Висновки

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

1) розроблені конструктивні засоби математичного та комп'ютерного моделювання відношень складених геометричних об'єктів, границя яких утворена об'єднанням дуг кіл та відрізків прямих:

побудовано повний клас Ф-функцій для розширеного класу орієнтованих і неорієнтованих базових об'єктів;

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

досліджено властивості побудованих Ф-функцій;

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

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

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

4) створено програмні продукти “Packing of circles, rotating circular segments and polygons”, “Packing of nonoriented composed objects”;

5) результати роботи використовуються у науково-виробничому підприємстві ТОВ "ЕЛКОР КОМПЛЕКТ" (м. Харків) і на виробничій базі в КП ХКБМ ім. О.О. Морозова (м. Харків) та впроваджені в навчальний процес у Харківському національному університеті радіоелектроніки й Харківському національному університеті внутрішніх справ.

Опубліковані роботи за темою дисертації

1. Романова Т.Е. Математическое моделирование взаимодействия отрезка прямой и базовых геометрических объектов / Т.Е.Романова, Е.А.Ступак // Радиоэлектроника и информатика. - 2006.- №2. - С.12-15.

2. Романова Т.Е. Полный класс Ф-функций для круговых сегментов и базовых объектов / Т.Е.Романова, Е.А.Ступак // Штучний інтелект. - 2006. - №4. - С.232-242.

3. Романова Т.Е. Математическая модель задачи размещения ориентированных круговых сегментов и кругов / Т.Е.Романова, Е.А.Ступак // Системи обробки інформації: зб. наук праць. - 2007. - № 5(63). - С. 149-153.

4. Ступак Е.А. Ф-функции для неориентированных круговых сегментов и базовых 2D объектов / Е.А.Ступак, Т.Е.Романова, М.В.Злотник // Бионика интеллекта. - 2007. - № 2(67). - С.27-32.

5. Stoyan Yu. Packing of circles, rotating circular segments and polygons / Yu. Stoyan, T. Romanova, M. Zlotnik, G. Scheithauer, E. Stupak // Проблемы машиностроения. - 2008. - №1(11). - С.56-62.

6. Романова Т.Е. Оптимизация упаковки неориентированных составных объектов с учетом зон запрета / Т.Е.Романова, М.В.Злотник, Е.А.Ступак // Проблемы машиностроения. -2008. - № 4(11). - С. 69-78.

7. Романова Т.Е. Математическая модель и метод решения задачи оптимизации упаковки произвольных двумерных объектов в прямоугольных областях / Т.Е. Романова, Е.А. Ступак, М.В. Злотник // Доповіді Національної академії наук України. - 2009. - № 1. -С.48-53.

8. Свідоцтво про реєстрацію авторського права на твір №24575 ДДІВ МОН України. Packing of circles, rotating circular segments and polygons: комп'ютерна програма / Т.Е. Романова, Е.А. Ступак, М.В. Злотник; заявл. 03.03.2008; зареєстр. 28.05.2008.

9. Гончаренко Е.Ю. Математическое моделирование взаимодействия круговых сегментов и базовых двумерных объектов / Е.Ю.Гончаренко, Е.А.Ступак // Комп'ютерний моніторинг та інформаційні технології: II Міжнародна наукова конференція студентів, аспірантів та молодих вчених, 15-17 травня 2006р.: тези доповідей. - Донецьк, 2006. - С.238-239

10. Романова Т.Е. Полный класс Ф-функций для круговых базовых объектов и сегментов / Т.Е. Романова, Е.А. Ступак // Искусственный интеллект. Интеллектуальные и многопроцессорные системы : Седьмая международная научно-техническая конференция, 25-30 сентября 2006г.: тезисы докл., - Таганрог- Донецк- Минск, 2006. - Т.1. - С.296-298.

11. Ступак Е.А. Математическая модель задачи размещения кругов и круговых сегментов в полубесконечной полосе / Е.А.Ступак // Современные проблемы машиностроения : конференция молодых ученых и специалистов, 2006г.: тезисы докл. -Харьков, 2006. - С.34.

12. Гончаренко Е.Ю. Математическое моделироавание размещения круговых сегментов / Е.Ю.Гончаренко, Е.А.Ступак // Радиоэлектроника и молодежь в XXI веке: XI Международный молодежный форум, 10-12 апреля 2007г.: тезисы докл. -Харьков, 2007. - С.165.

13. Ступак Е.А. Ф-функции для неориентированных круговых сегментов и базовых 2D объектов / Е.А. Ступак, Т.Е. Романова, М.В. Злотник // Искусственный интеллект. Интеллектуальные системы : VIII международная научно-техническая конференция, 24-29 сентября 2007г.: тезисы докл. - Донецк, 2007. - С.359-362.

14. Злотник М.В. Математическая модель задачи размещения неориентированных составных объектов с нелинейной границей / Е.А. Ступак, М.В. Злотник // Современные проблемы машиностроения : конференция молодых ученых и специалистов, 2007г.: тезисы докл. -Харьков, 2007. - С .20.

15. Romanova T. Packing of rotating circular segments and primary objects / T. Romanova, Yu. Stoyan, M. Zlotnik, E. Stupak // 5th ESICUP Meeting: междун. конф., April 20-22, 2008: тезисы докл. - L'Aquila, Italy, 2008. - P 24.

16. Блинова А.Н. Ф-функции для неориентированных объектов с нелинейными границами / А.Н. Блинова, Е.А. Ступак // Радиоэлектроника и молодежь в XXI веке: XII Международный молодежный форум, 1-3 апреля 2008г.: тезисы докл. - Харьков, 2008. - С.348.

17. Гиренко Е.А. Задача размещения неориентированных составных объектов с нелинейной границей с учетом зон запрета / Е.А. Гиренко // Современные проблемы машиностроения: конференция молодых ученых и специалистов, 2008г.: тезисы докл. -Харьков, 2008. - С .21.

Анотація

Гиренко К.А. Математична модель та метод розв'язання задачі розміщення неорієнтованих складених геометричних 2D об'єктів. - Рукопис.

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

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

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

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

Аннотация

Гиренко Е.А. Математическая модель и метод решения задачи размещения неориентированных составных геометрических 2D объектов. - Рукопись.

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

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

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

Строится математическая модель основной задачи размещения в виде задачи нелинейного программирования и исследуются ее особенности. Задача является многоэкстремальной и трудной.

Строится дерево решений для каждой пары Ф-неравенств объектов из семейства неориентированных составных объектов.

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

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

Создано соответствующее алгоритмическое и программное обеспечение.

Приведены результаты анализа численных экспериментов.

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

Abstract

Girenko E.A. Mathematical model and solution method for a placement problem of non-oriented composed geometric 2D objects. - Manuscript.

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

The thesis is an extension of the geometric design theory. An optimization placement problem of a class of arbitrary objects in a rectangular region taking into account rotations of the objects and prohibited areas in order to minimize a length of the region is considered within the research.

The complete class of Ф-functions for an extended class of non-oriented primary objects (circles, polygons, circular segments as well as their complements) and class of Ф-functions for a family of the non-oriented composed objects as the tools of mathematical and computer modeling of the basic placement constrains (non-intersecting of placement objects, belonging objects to the region, object rotations, prohibited areas) are constructed.

A mathematical model is presented as a constrained non linear optimization problem. Characteristics of the model are provided.

A solution tree for each Ф-inequality of a pair of objects from the family of non-oriented composed objects is constructed.

The problem is multiextremal and NP-hard.

A solution strategy is offered. The strategy involves a fast initial placement, local optimisation and searching for an approximation to a global minimum.

Analysis of numeral experiments is given.

The proposed tools, mathematical model and solution method are recommended for solving irregular packing and cutting problems in metal, textile, paper, wood, sheet, plastics and glass industries.

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

...