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

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

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

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

УДК 519.859

МАТЕМАТИЧНА МОДЕЛЬ І МЕТОД РОЗВ'ЯЗАННЯ ОПТИМІЗАЦІЙНОЇ ЗАДАЧІ РОЗМІЩЕННЯ ЦИЛІНДРІВ І ПАРАЛЕЛЕПІПЕДІВ У ПРИЗМІ З УРАХУВАННЯМ СПЕЦІАЛЬНИХ ОБМЕЖЕНЬ

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

АВТОРЕФЕРАТ

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

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

Чугай Андрій Михайлович

Харків - 2006

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

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

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

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

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

Провідна установа: Харківський національний університет радіоелектроніки, кафедра прикладної математики, Міністерство освіти і науки України, м. Харків

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3) провести дослідження особливостей зазначених математичних моделей;

4) розробити ефективні методи та алгоритми розв'язання поставлених задач;

5) створити програмні системи, що реалізують запропоновані методи розв'язання задач.

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

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

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

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

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

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

– розроблено модифікацію методу гілок та меж, яка полягає у побудові спеціального дерева розв'язків;

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

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

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

Практичне значення отриманих результатів. Наукові результати дисертаційної роботи є подальшим розвитком теорії геометричного проектування. На підставі розроблених методологій розв'язання поставлених задач створені програмні системи “Placement of cylinders and parallelepipeds into prism with given shortest distances” та “Packing of equal circles into multiconnected domain”. Сукупність розроблених математичних моделей, методів, алгоритмів та програмних комплексів може використовуватися у вигляді оптимізаційного ядра в системах автоматизованого проектування різних технічних систем та пристроїв у машинобудуванні, в задачах перевезення вантажів, в задачах зберігання запасів на складах, в задачах проектування генеральних планів підприємств і т.п.

Зокрема, результати дисертаційних досліджень використовуються на етапі проектування при розробці комплексів бурового устаткування та при компонуванні геофізичних пристроїв орієнтування бурового інструмента у ВАТ завод “Потенціал” (м. Харків) та на Державному науково-виробничому підприємстві “Меридіан” (м. Харків) при розробці приладів електросинтезу озона “Озон 2-20”, про що свідчать акти про впровадження результатів досліджень.

Особистий внесок здобувача. Усі основні наукові результати дисертаційної роботи отримані особисто автором. У роботах, написаних у співавторстві, дисертанту належать такі результати: у роботі [1] - запропонований підхід для побудови спеціального дерева розв'язків задачі, а також модифікація методу околів, що звужуються, та методу можливих напрямків; у роботі [4] - запропонована математична модель задачі та метод її розв'язання; у роботі [5] - програмна реалізація алгоритму розв'язання задачі; у роботі [9] - методологія швидкого пошуку локальних мінімумів; у роботі [10] - алгоритмічна і програмна реалізація методу локальної оптимізації, у роботі [11] - модифікація методу околів, що звужуються.

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

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

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

· 2-й міжнародній науково-технічній конференції “2^nd ESICUP Meeting” (University of Southampton, UK, 2005);

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

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

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

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

Структура й обсяг дисертації. Дисертація складається зі вступу, п'яти розділів, висновків, списку використаних джерел iз 131 найменуванням (14 с.) та одного додатку (3 с.). Загальний обсяг роботи складає 140 сторінок, включаючи 46 рисунків та 14 таблиць.

математичний моделювання тривимірний геометричний

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

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

У першому розділі виконаний огляд літератури за темою дисертації та обраний напрям досліджень. Розглянуто вітчизняну та зарубіжну літературу, яка присвячена задачам розміщення тривимірних геометричних об'єктів. Вивченню даного класу задач присвячені роботи багатьох учених, у тому числі Ю.Г. Стояна, М.І. Гіля, В.М. Комяк, С.В. Яковлева, М.В. Новожилової, Е.О. Мухачової, W. Dowsland, J.A.S. Ferreira, I. Terno, Ikonen I., Bischoff E.E., Cagan J., Birgin E.G., George J.A. та ін.

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

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

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

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

Визначення 1. Безперервна, всюди визначена функція , , називається Ф-функцією об'єктів T₁(u₁) та T₂(u₂), якщо вона задовольняє таким характеристичним властивостям:

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

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

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

Нехай є циліндри

, ,

паралелепіпеди

,

, та множина :

,

де - замикання множини А, - пряма призма з багатокутною основою P, границя якої frP=H складається з q-2 сторін (q- кількість граней призми), K_j- циліндри, основи яких є кола L_j, що задаються нерівностями , j=1,2,…,.

Задані мінімально припустимі відстані d_ij, i<j=2,3,…,n=n₁+n₂, між кожною парою об'єктів, що розміщуються. Крім того, задані мінімально припустимі відстані d_i^k, k=1,2,…,q, між кожним циліндром C_i, i=1,2,…,n₁, і кожною гранню призми B, між кожним паралелепіпедом P_i, i=n₁+1, n₁+2, n=n₁+n₂, і кожною гранню призми B (q-кількість граней призми), а також мінімально припустимі відстані між кожним циліндром K_l, l=1,2,…,, і циліндром C_i, i=1,2,…,n₁, кожним циліндром K_l, l=1,2,…,, та кожним паралелепіпедом P_i, i=n₁+1, n₁+2, n=n₁+n₂.

Висота h призми є змінною. Циліндри і паралелепіпеди не можуть повертатися, а можуть лише транслюватися на вектори , i=1,2,…,n. Назвемо u_i=(x_i,y_i,z_i) вектором параметрів розміщення. Циліндр C_i із параметрами u_i позначимо C_i(u_i), а паралелепіпед P_i з параметрами u_i позначимо P_i(u_i). Позначимо вектор змінних задачі через .

Задача. Необхідно знайти вектор такий, що циліндри C_i, i=1,2,…,n₁, та паралелепіпеди P_i, i=n₁+1, n₁+2, n=n₁+n₂, розміщуються в T з урахуванням мінімально припустимих відстаней d_ij, i<j=2,3,…,n=n₁+n₂, d_i^k, k=1,2,…,q та , i=1,2,…,n, l=1,2,…,, , і h досягає мінімуму.

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

, (1)

де F(X)=h,

- нормалізована Ф-функція для C_i і C_j; - нормалізована Ф-функція для і ; - нормалізована Ф-функція для C_i і P_j; функції і забезпечують розміщення відповідно циліндрів C_i і паралелепіпедів P_i у B з урахуванням заданих мінімально припустимих відстаней , функції і забезпечують знаходження на відстанях відповідно циліндрів C_i і паралелепіпедів P_i із K_l.

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

При n₂=0 отримуємо задачу розміщення тільки циліндрів. Якщо у циліндрів радіуси та висоти рівні, то виникає задача розміщення однакових циліндрів у призмі із зонами заборони. Специфіка цієї задачі вимагає деякої модифікації побудованої математичної моделі (1)-(2). Особливості задачі упакування однакових циліндрів у призмі з зонами заборони дозволили звести її до двовимірної задачі розміщення однакових кіл в опуклому багатокутнику із зонами заборони. Математичну модель даної задачі можна побудувати таким чином. Нехай є однакові кола С_i (i=1,2,…,N) радіуса r і задана багатозв'язна область розміщення P:

,

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

Задача. Необхідно розмістити у області P максимальну кількість однакових кіл Сi.

Розв'язання даної задачі зводиться до розв'язання послідовності задач

, n=1,2,…,N,

де , u=(u1,u2,…,un), ui=(xi,yi,ri), (xi,yi) - координати центру кола Ci(ui), ri- змінний радіус кола Ci(ui); D описується системою нерівностей:

(4)

де - Ф-функція кола Ci(ui) та , - Ф-функція кіл Ci(ui) та Cj(uj).

Якщо , а , то розв'язок задачі досягається в точці .

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

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

1. Будуються множини, де - оператор суми Мінковського, - куля радіуса.

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

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

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

5. У процесі пошуку за методом околів, що звужуються, формується деяка множина Г початкових точок типу , в яких функція мети (1) приймає мінімальні значення.

6. Кожна точка береться як початкова точка для пошуку локального мінімуму.

7. Отриманий кращий локальний мінімум , , приймається як деяке наближення до глобального мінімуму.

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

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

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

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

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

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

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

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

,

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

,

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

,

де , ,

.

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

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

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

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

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

Усі наступні етапи модифікованого методу околів, що звужуються, реалізуються за таким алгоритмом.

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

У п'ятому розділі наведено короткий опис створеного алгоритмічного та програмного забезпечення. Створені програмні системи “Placement of cylinders and parallelepipeds into prism with given shortest distances” та “Packing of equal circles into multiconnected domain” можуть використовуватися у вигляді оптимізаційного ядра в системах автоматизованого проектування.

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

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

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

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

Вперше побудовано математичну модель задачі розміщення різних циліндрів і паралелепіпедів у призмі з урахуванням мінімально припустимих відстаней і зон заборони.

Вперше побудовано математичну модель задачі розміщення однакових циліндрів у призмі з урахуванням зон заборони.

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

Досліджено особливості побудованих математичних моделей.

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

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

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

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

Створено програму “Placement of cylinders and parallelepipeds into prism with given shortest distances” для розміщення різних циліндрів і паралелепіпедів з урахуванням мінімально припустимих відстаней та программу “Packing of equal circles into multiconnected domain” для розміщення однакових циліндрів у призму з зонами заборони.

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

Результати роботи впроваджені у ВАТ завод “Потенціал” (м. Харків) та на Державному науково-виробничому підприємстві “Меридіан” (м. Харків).

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

1. Стоян Ю.Г., Чугай А.М. Оптимизация упаковки одинаковых кругов в многосвязную область // Докл. НАН Украины.- 2004.- № 12.- С. 64-68.

2. Чугай А.М. Метод поиска локальных экстремумов в задаче упаковки одинаковых цилиндров в многоугольной призме с зонами запрета // Радиоэлектроника. Информатика. Управление. - ЗНТУ.-2004. -№2.-С.94-101.

3. Чугай А.М. Решение задачи упаковки кругов в выпуклый многоугольник с помощью модифицированного метода сужающихся окрестностей // Радиоэлектроника и информатика.-2005. -№1.- С.58-63.

4. Гребенник И.В., Чугай А.М. Оптимизационная задача размещения цилиндров и параллелепипедов в призме с учетом кратчайших расстояний и зон запрета // Збірник наукових праць Харківського університету Повітряних сил. - 2005. -№6. -С. 41-50.

5. Стоян Ю.Г., Чугай А.М. Свідоцтво про реєстрацію авторського права на твір № 11504. Комп'ютерна програма "Packing of equal circles into multiconnected domain".

6. Чугай А.М. Упаковка одинаковых кругов в многосвязную область // Тезисы докладов конференции молодых ученых и специалистов "Современенные проблемы машиностроения". -Харьков. - ИПМаш им. А.Н. Подгорного НАНУ. - 2003. - С.20.

7. Чугай А.М. Математическая модель и способ решения оптимизационной задачи размещения различных цилиндров в параллелепипеде с учетом кратчайших расстояний // Тезисы докладов конференции молодых ученых и специалистов "Современные проблемы машиностроения". - Харьков. - ИПМАШ им. А.Н. Подгорного НАНУ. - 2004. - С.22.

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

9. Yu. Stoyan and A. Chugay. Packing cylinders and parallelepipeds with given shortest distances between them into a prism // “2^nd ESICUP Meeting”. -University of Southampton. -UK. April 14-16. -2005. - P.25.

10. G. Yaskov, Yu. Stoyan and A. Chugay. Packing a great number of identical spheres into a composed domain // “2^nd ESICUP Meeting”. -University of Southampton. -UK. April 14-16. - 2005. - P.24.

11. Yu. Stoyan, A. Chugay, A. Pankratov, M. Zlotnick. 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 15-18. - 2005. - P.13.

АНОТАЦІЯ

Чугай А.М. Математична модель і метод розв'язання оптимізаційної задачі розміщення циліндрів і паралелепіпедів у призмі з урахуванням спеціальних обмежень. - Рукопис.

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

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

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

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

Ключові слова: математичне моделювання, оптимізація, розміщення, мінімально припустимі відстані, зони заборони, циліндр, паралелепіпед, призма.

АННОТАЦИЯ

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

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

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

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

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

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

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

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

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

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

Ключевые слова: математическое моделирование, оптимизация, размещение, минимально допустимые расстояния, зоны запрета, цилиндр, параллелепипед, призма.

ABSTRACT

Chugay A.M. A mathematical model and method for solving packing optimization problem of cylinders and parallelepipeds into a prism with account of special restrictions.- Manuscript.

Thesis for a candidate's degree (technical sciences) by speciality 01.05.02 - mathematical modeling and computational methods. - The A.M. Pidgorny Institute for Problems in Machinery of NAS of Ukraine, Kharkiv, 2006.

The dissertation is a continuation of investigation of geometric design problems, namely non-linear 3D packing problems with account restrictions on admissible distances.

It is necessary to pack cylinders and parallelepipeds into a prism so that height of the occupied part of the prism reaches a minimum and restrictions on admissible distances between each pair of objects and between objects and the frontier of the prism are fulfilled.

For the first time a mathematical model of the packing optimization problem of cylinders and parallelepipeds into the prism with account restrictions on admissible distances is built. A class of geometrical objects which can be placed is extended. For the first time a mathematical model of the problem of packing of identical cylinders into the prism with account prohibited areas is built. A new integrated approach for solving problems is offered. This approach consists in a combination of a method of searching for initial approximations of local extremums, modified method of decremental neighborhood and modified method of possible directions. Algorithm and software to solve problems are developed. Numerical examples are given.

Key words: mathematical modeling, optimization, placement, minimal distances, prohibited areas, cylinder, parallelepiped, prism.

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