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

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

Злотник Михайло Вікторович

УДК 519.859

МАТЕМАТИЧНА МОДЕЛЬ І МЕТОД РОЗВ’ЯЗАННЯ ОПТИМІЗАЦІЙНОЇ ЗАДАЧІ РОЗМІЩЕННЯ НЕОРІЄНТОВАНИХ БАГАТОКУТНИКІВ ТА КРУГІВ

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

АВТОРЕФЕРАТ

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

кандидата технічних наук

Харків – 2007

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

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

Науковий керівник: член-кореспондент НАН України, доктор технічних наук,

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

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

кандидат технічних наук, доцент Шеховцов Сергій

Борисович, Харківський національний університет внутрішніх справ, начальник кафедри прикладної математики

Провідна установа: Харківський національний університет радіоелектроніки,

кафедра прикладної математики, Міністерство

освіти і науки України, м. Харків

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

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

Автореферат розісланий “_5_” __травня__2007р.

Учений секретар спеціалізованої вченої ради

д.т.н. О.О. Стрельнікова

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практичне значення отриманих результатів. На підставі результатів дисертаційної роботи створені комп’ютерні програми “F-function for polygons with rotations”, “ Ф-functions for primary non-oriented objects” та “Packing of circles and non-oriented non-convex polygons” (одержано авторське право на програму “F-function for polygons with rotations”). Наукові результати дисертаційної роботи, що охоплюють розроблені засоби математичного та комп’ютерного моделювання, математичну модель, методи, алгоритми та програмні комплекси, є подальшим розвитком теорії геометричного проектування, та можуть використовуватися у якості оптимізаційного ядра в системах автоматизованого проектування карт розкрою у легкій та важкій промисловості, при проектуванні генеральних планів підприємств і таке інше.

Зокрема, результати дисертаційних досліджень використовуються у “ЕТЦ “Діагностика” при експертизі планів ліквідації аварійних ситуацій на об’єктах підвищеної небезпечності для оцінки варіантів компонування будинків, споруд та технологічного обладнання на промплощадці з урахуванням зон дії вражаючих факторів можливих аварій, та в учбовому процесі в Харківському національному університеті внутрішніх справ, про що свідчать акти про використання результатів досліджень.

Особистий внесок здобувача. Усі основні наукові результати дисертаційної роботи отримані особисто автором. У роботах, написаних у співавторстві, дисертанту належать наступні результати: у роботі [1] – побудована Ф-функція, [3] – побудовано алгоритм розрахунку Ф-функції, [5] – запропонована математична модель задачі та метод її розв’язання, алгоритмічна і програмна реалізація методу локальної оптимізації, [6] – запропоновано метод зображення неопуклих багатокутників у вигляді об’єднання опуклих багатокутників, алгоритмічну реалізацію побудови Ф-функції, [9] – запропонована математична модель задачі, засоби математичного моделювання, алгоритмічна і програмна реалізація методу локальної оптимізації, [13] – програмна реалізація методу локальної оптимізації, [14] – програмна реалізація побудови Ф-функції.

Апробація результатів дисертації. Основні результати роботи доповідалися та одержали схвалення на міжнародних конференціях і наукових семінарах:

· конференціях молодих вчених і фахівців “Сучасні проблеми машинобудування” (м. Харків, ІПМаш ім. А.М. Підгорного НАНУ, 2003–2006р.р.);

· міжнародній науково-технічній конференції “Proc. Workshop on Cutting Stock Problems” (Sapientia University, Miercurea-Ciuc, Romania, 2005);

· XIII міжнародній науково-практичній конференції “Інформаційні технології: наука, техніка, технологія, освіта, здоров'я” (м. Харків, 2005 р.);

· II міжнародній науковій конференції студентів, аспірантів та молодих вчених “Комп’ютерний моніторинг та інформаційні технології” (м. Донецьк, 2006р.)

· міжнародній конференції АППММ’06 (м. Харків, 2006р.);

· постійно діючому семінарі Математичні методи геометричного проектування при науковій раді з проблем Кібернетика (м.Харків, 2002–2006 рр.)

· на семінарах відділу математичного моделювання та оптимального проектування ІПМаш ім. А.М. Підгорного НАН України (м. Харків, 2002–2007 рр.).

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

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

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

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

У першому розділі наведено огляд літератури за темою дисертації та обрано напрям досліджень. Розглянуто публікації вітчизняних та зарубіжних авторів, що присвячені задачам розміщення геометричних об'єктів. Вивченню та розв’язанню даного класу задач присвячені роботи багатьох учених: Ю.Г. Стояна, М.І. Гіля, В.М. Комяк, С.В. Яковлева, М.В. Новожилової, Т.Є. Романової, А.А. Панасенка, О.К.Пандоріна, О.В. Панкратова, Е.О. Мухачової, W.V., J.A.S.I.G. Scheithauer, J. Benell, J.F.S. Oliveira та ін.

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

Деякі підходи до моделювання та розв’язання задач розміщення неорієнтованих багатокутників запропоновані, наприклад, у роботах V. Milencovich, Стояна Ю.Г. та його учнів.

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

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

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

Визначення 1. Безперервна, всюди визначена функція, називається Ф-функцією об'єктів T1(u1) та T2(u2), якщо вона задовольняє таким характеристичним властивостям: більше за нуль, якщо clT1(u1)  clT2(u2) ; дорівнює нулю, якщо frT1(u1)  frT2(u2) ?  , та intT1(u1)  intT2(u2) ; менше за нуль, якщо intT1(u1)  intT2(u2) ? .

де Tі(uі) – об’єкт трансльований на вектор vі=(xі, yі), та повернутий на кут , і = ,2, відносно початку власної системи координат.

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

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

Базуючись на методі побудови Ф-функцій для орієнтованих об’єктів, у роботі запропоновано наступний метод побудови Ф-функцій неорієнтованих об’єктів, який полягає у такому:

· вважаємо, що один з об’єктів зафіксовано, та всі його параметри розміщення дорівнюють нулю;

· будуємо рівняння ч(u) = 0 нульового рівня Ф-функції, яке залежить від параметрів розміщення другого об’єкту при умові, що параметри розміщення першого об’єкту фіксовані;

· задаємо орієнтацію рівняння ч(u) = 0 таким чином, що ч(u*) < 0, якщо та ч(u*) > 0, якщо , де T12(и) T12(0,0,0) ;

· вважаємо Ф12(0,u2)=ч(u);

· заміною змінної u на відповідні різниці параметрів розміщення, залежних від кутових параметрів, отримуємо необхідну Ф-функцію Ф12(u1,u2)=ч(), де , , .

Де 2а1, 2b1 – довжина та ширина прямокутника, r2 – радіус круга, (x1,1, и1) – параметри розміщення прямокутника, (x2,2) – параметри розміщення круга.

На рис. 1 зображено проекцію поверхні нульового рівня Ф-функції неорієнтованого прямокутника та круга, для випадку R1(0,0,и1=const) та C2(x2,2) (рис. 1а), R1(0,0,и1) та C2(x2,2) (рис. б)

а б

Рис.1. Проекція поверхні нульового рівня Ф-функції круга та неорієнтованого прямокутника

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

У роботі побудовано повний клас Ф-функцій та нормалізованих Ф-функцій неорієнтованих однозв’язних і двозв’язних -об’єктів із границею коло та багатокутник.

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

· неперервні;

· кусково-гладкі;

· періодичні відносно кутових змінних (рис. 2);

· майже всюди диференційовані;

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

· поверхні, визначені цими Ф-функціями, носять яружний характер (рис. 3).

Рис. 2 Проекція поверхні нульового Рис. 3 Проекція поверхні Ф-функції

рівня Ф-функції K1 та K2 K1 та K2

Під час дослідження Ф-функцій неорієнтованих об’єктів було встановлено, що Ф-функцію двох опуклих багатокутників запропоновану чл.-кор. НАНУ Стояном Ю.Г., можна спростити до наступного вигляду:

, (1)

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

Нехай є круги Ci радіуса ri i=1,2,…,n1, та, у загальному випадку неопуклі, багатокутники Pj, j= n1+1, n1+2,…,n, що задані послідовністю своїх вершин у власній системі координат.

Нехай область розміщення – прямокутник.

Положення круга Ci визначаємо вектором параметрів розміщення – координатами його центру (рис. а). Положення багатокутника Pj визначаємо вектором параметрів розміщення, тобто координатами початку власної системи координат та кутом повороту власної системи координат відносно нерухомої (рис. б). Об’єкт Ti з вектором руху ui надалі Ti(ui). Позначимо вектор параметрів розміщення усіх об’єктів через u = (u1,1,…, um), , q = 2n1+ 3n2. Відповідно вектор усіх змінних задачі позначимо, як X = (u, l)Rq+1.

а б

Рис. 2. Параметри розміщення

Задача. Необхідно знайти вектор X такий, що круги Ci, i=1,2,…,n1, та багатокутники Pi, i =1+1,1+2,…,n, розміщуються у прямокутнику S, не перетинаючись між собою, та його параметр l приймає мінімальне значення.

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

, (2)

де ;

(3)

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

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

Для швидкого отримання початкових точок із області припустимих розв’язків (припустимих варіантів розміщення) використовуємо метод оптимізації по групах змінних для геометричних об’єктів, що апроксимовані елементарними прямокутниками, як запропоновано у роботах Стояна Ю.Г. та Панкратова О.В.

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

У результаті отримуємо початкову точку, що належить області припустимих значень.

Пошук локального мінімуму ґрунтується на розв’язанні задачі нелінійного програмування однією з модифікацій методу можливих напрямків. Основна ідея методу пошуку локального мінімуму полягає у наступному.

Нехай X0 – початкова точка, що отримана у відповідності до описаного вище методу. Ітеративний процес пошуку локального мінімуму може бути представлено як Xk+1=k + tZk, k=0,1,2,…,з, де Zk =( – вектор найкращого спуску з точки Xk, точка X0D є стартовою точкою, t?0. Для того, щоб визначити вектор Zk, насамперед обираємо всі е–активні нерівності із системи (3), тобто ті функції Шkj(X), які задовольняють умові 0?Шkj(Xk)?е. Застосовуємо наступну модифікацію методу можливих напрямків

, (4)

де область припустимих розв’язків Gk визначається наступною системою нерівностей:

(5)

Задачу лінійного програмування (4)-(5) в роботі розв’язуємо за допомогою модифікованого симплекс-методу зображеного у роботі Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. – М.: Мир, 1985. – 509 с.

Для того, щоб отримати різні наближення до локальних мінімумів та здійснити їх направлений перебір, у відповідності до модифікації методу околів, що звужуються (зображеного у роботах Стояна Ю.Г. та Чугая А.М.), генеруємо випадкові послідовності Щj. Модифікація методу околів для задачі розміщення кругів та багатокутників полягає у наступному. Кожному кругу Ci та багатокутнику Pj ставимо у відповідність вектори ci=(сi, si), де сi = ri, i=1,2,…,n1, та pi =(сi, si), де si=/(2сi), i =1+1,1+2,…,n, сi – радіус описаного навколо багатокутника кола, – площа об’єкту (круга чи багатокутника). Тоді кожній випадковій послідовності , де i=1,2,…,n, – круг або багатокутник, можна поставити у взаємооднозначну відповідність вектор , де може бути або ci, або pi, i{1,2,…,n}. Якщо ci ?k, i < k=2,3,…,n1, pi ?k, n1 < i < k = n1+2, n1+3,…,n, ci ?k, i=1,2,…,n1, k =1+1,1+2,…,n, тоді кількість векторів дорівнює n!

Таким чином, різним послідовностям об'єктів, що розміщуються, відповідають різні вектори. Множина усіляких векторів являє собою комбінаторну множину переставлень vj, j=1,2,…,ф.

Для реалізації методу околів, що звужуються, зроблено оцінку діаметра множини V, а також визначено мінімальну відстань між двома різними точками vj та vi.

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

У п'ятому розділі наведено короткий опис створеного алгоритмічного та програмного забезпечення. Створено комп’ютерні програми “F-function for polygons with rotations”, “F-functions for primary non-oriented objects” та “Packing of circles and non-oriented non-convex polygons”, що можуть використовуватися у вигляді оптимізаційного ядра в системах автоматизованого проектування.

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

а б

в г

Рис. 3. Приклади розв’язання тестових задач

Проведено порівняння результатів, отриманих за розглянутим методом (рис. 4б, рис. 4г, рис. 4е), з результатами, отриманими:

· простим випадковим пошуком послідовностей з подальшою локальною оптимізацією розміщення об’єктів (рис. 4а);

· для орієнтованих об’єктів (наприклад Jakobs "On genetic algorithms for the packing of polygons" рис. 4в);

· неорієнтованих об’єктів (рис. 4д).

Результати розв’язання задач, що були отримані у відповідності з розробленим методом кращі (5% – 10%) за результати, що були отримані іншими способами.

а б в г

д е

Рис. 4. Порівняння результатів

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

У додатку наведено довідки про впровадження результатів дисертаційної роботи у виробництво та учбовий процес.

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

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

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

1. Стоян Ю.Г., Шайтхауэр Г., Романова Т.Е., Злотник М.В. Моделирование взаимодействий пересечения круговых двухсвязных -объектов и выпуклого многоугольника в задачах геометрического проектирования // Проблемы машиностроения. – 2004. – Т. 7, № 4. – С. 82-87.

2. Злотник М.В. Полный класс Ф-функций для кругов и прямоугольников с поворотами // Радиоэлектроника и информатика. – 2006. – №1. – С. 36–40.

3. Романова Т.Е., Кривуля А.В., Злотник М.В. Математическое моделирование взаимодействий геометрических объектов в задаче покрытия прямоугольной области прямоугольными объектами // Искусственный интеллект. – 2006. – №4. – С. .

4. Злотник М.В. Полный класс Ф-функций для кругов и многоугольников с поворотами // Радиоэлектроника и информатика. – 2006. –№3. – С. 29–33.

5. Стоян Ю.Г., Злотник М.В. Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины // Докл. НАН Украины. _2007. _№ 2. _С. 37-42.

6. Стоян Ю.Г., Злотник М.В. Свідоцтво про реєстрацію авторського права на твір № 11503. Комп'ютерна програма "F-function for polygons with rotations".

7. Злотник М.В. Построение Ф-функций неориентированных объектов // Тезисы докладов конференции молодых ученых и специалистов "Современные проблемы машиностроения". – ИПМаш им. А.Н. Подгорного НАНУ. – Харьков. – 2003. – С.12.

8. Злотник М.В. Размещение неориентированных прямоугольников и кругов в полосе минимальной длины // Тезисы докладов конференции молодых ученых и специалистов "Современные проблемы машиностроения". – ИПМаш им. А.Н. Подгорного НАНУ. – Харьков. – 2004. – С.15.

9. Yu. Stoyan, A.AM.Placement optimization problem of various-sizes circles and rectangles with rotations into a strip // “Proc. Workshop on Cutting Stock Problems”. – Sapientia University, Miercurea-Ciuc, Romania, September, 2005. – P.13.

10. Злотник М.В. Размещение неориентированных многоугольников и кругов в полосе минимальной длины // Тезисы докладов конференции молодых ученых и специалистов "Современные проблемы машиностроения". – ИПМаш им. А.Н. Подгорного НАНУ. – Харьков. – 2005. – С.25.

11. Злотник М.В. Построение математической модели и решение задачи размещения невыпуклых многоугольников с поворотами и кругов в полосе минимальной длины // Тезисы докладов конференции молодых ученых и специалистов "Современенные проблемы машиностроения". – ИПМаш им. А.Н. Подгорного НАНУ. – Харьков. – 2006. – С.25.

12. Злотник М.В. Построение полного класса нормализованных Ф-функций для кругов и прямоугольников с поворотами // Збірка тез доповідей II Міжнародної наукової конференції студентів, аспірантів та молодих вчених “Комп’ютерний моніторінг та інформаційні технології”. – Донецьк. –2006. – С.244-245.

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

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

15. Злотник М.В. Размещение кругов и неориентированных невыпуклых многоугольников в прямоугольнике минимальной длины // Тезисы докладов Международной конференции АППММ’06, ИПМаш им. А.Н. Подгорного НАН Украины. – Харьков. – 2006. – С. 9.

АНОТАЦІЯ

Злотник М.В. Математична модель і метод розв’язання оптимізаційної задачі розміщення неорієнтованих багатокутників та кругів. – Рукопис.

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

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

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

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

АННОТАЦИЯ

Злотник М.В. Математическая модель и метод решения оптимизационной задачи размещения неориентированных многоугольников и кругов. – Рукопись.

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

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

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

Рассматривается задача размещения кругов и неориентированных многоугольников в прямоугольной области с целью минимизации ее длины. Строится математическая модель поставленной задачи. Исследуются особенности математической модели. Метод Ф-функций позволяет представить область допустимых решений в виде объединения подобластей, каждая из которых определяется системой в общем случае нелинейных неравенств. Задача является многоэкстремальной и трудной.

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

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

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

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

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

ABSTRACT

Zlotnick M.V. A mathematical model and method of solving the optimization problem of packing non-oriented polygons and circles. – Manuscript.

Thesis for a candidate’s degree (technical science) by speciality 01.05.02 – mathematical modelling and computational methods. – A.M. Pidgorny Institute for Mechanical Engineering Problems NAS of Ukraine, Kharkiv, 2007.

The dissertation is an extension of studies in geometric design problems, in particular, nonlinear packing problems of 2D objects with account of possible object rotation.

A complete class of Ф-functions has been built first for circles and non-oriented geometric objects (rectangles, convex and nonconvex polygons), as well as their complements as a tool for mathematically modelling constraints on belonging of objects to the packing region, and for non-intersection of packed objects. A complete class of normalized Ф-functions has been built first for the above objects as a tool for mathematically modelling constraints on the minimal and maximal feasible distances between geometric objects. A mathematical model has been built first for the problem of packing non-oriented polygons and circles in a rectangular packing region. An integrated approach to solving problems, which consists in combining local and global optimization methods, has been further developed. Algorithms and software has been developed for solving these problems. The results of solving test problems are presented.

Key words: mathematical modelling, non-oriented object (objects with rotations), optimization, placement, Ф-function, circle, convex polygon, nonconvex polygon.