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

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

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

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

УДК 519.6:514.1

АВТОРЕФЕРАТ

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

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

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

МАГДАЛІНА ІГОР ВАЛЕРІЙОВИЧ

Харків - 2001

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

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

Науковий керівник: доктор технічних наук, старший науковий співробітник Гіль Микола Іванович, Інститут проблем машинобудування ім. А.М. Підгорного НАН України (м. Харків), провідний науковий співробітник.

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

доктор технічних наук, професор Сіроджа Ігор Борисович, Національний аерокосмічний університет ім. М.Е. Жуковського “ХАІ”, завідувач кафедри програмного забезпечення.

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

Захист відбудеться “6” грудня 2001 р. о 14.00 годині на засіданні спеціалізованої вченої ради Д 64.180.01 в Інституті проблем машинобудування ім. А.М. Підгорного НАН України за адресою

61046, м. Харків, вул. Дм. Пожарського, 2/10.

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

61046, м. Харків, вул. Дм. Пожарського, 2/10.

Автореферат розісланий “2” листопада 2001 р.

Вчений секретар

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

кандидат технічних наук Б.П. Зайцев

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

опуклий багатогранник геометричний паралелепіпед

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана відповідно до тематики та загального плану досліджень, проведених у відділі математичного моделювання та оптимального проектування Інституту проблем машинобудування ім. А.М. Підгорного НАН України в період з 1996 по 2001 рр. згідно з планами науково-дослідних робіт за бюджетними темами:

_ № 187 “Розробка та дослідження інтелектуальної системи відображення геометричної інформації для оптимізації та моделювання фізико-механічних процесів і технічних систем” (№ 0197U012281);

_ № 2 “Розробка та дослідження математичних моделей задач оптимізації розміщення тривимірних геометричних об'єктів” (№ 0198U007627).

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

Задачами дослідження, зумовленими метою роботи, є:

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

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

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

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

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

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

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

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

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

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

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

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

Практичне значення отриманих результатів. На підставі розробленої методології розв'язання поставленої задачі створено програмну систему "Convex Polytopes Packing", що може бути застосована при проектуванні приладових та вантажних відсіків літальних апаратів, об'єктів будівництва, транспортних засобів, при розв'язанні проблеми раціонального розміщення обладнання в цехах. Розроблена програмна система використовується на ВАТ “ХТЗ” при моделюванні схем раціонального розміщення запасних частин та обладнання в контейнерах для їх транспортування.

Особистий внесок здобувача. Усі результати дисертаційної роботи отримані за особистої участі автора. У працях, опублікованих у співавторстві, дисертанту належать такі результати: у роботі [1] - дослідження просторових форм компонент лінійної зв'язності границі -об'єкта простору R²; у роботі [2] - формалізація умов розміщення багатогранників в області розміщення та умов їх взаємного неперетину, запропоновано підхід для побудови припустимого варіанту розміщення опуклих багатогранників у паралелепіпеді заданих розмірів; у роботі [3] - алгоритмічна та програмна реалізація побудови поверхні 0-рівня Ф-функціі двох довільних опуклих багатогранників; у роботі [4] - побудова поверхні 0-рівня Ф-функції для кола та багатокутника. У роботі [6] дисертантом запропонований спосіб представлення вихідної інформації про довільний -багатогранник.

Апробація результатів дисертації. Основні положення дисертаційної роботи доповідались та обговорювались на:

_ 3-му та 4-му міжнародних молодіжних форумах “Радіоелектроніка і молодь у XXI столітті” (м. Харків, 1999, 2000 рр.);

_ міжнародній конференції молодих вчених в області дослідження операцій “Euro Prime I” (м. Варшава, 1999 р.);

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

_ X міжнародному науково-технічному семінарі “Високі технології: розвиток та кадрове забезпечення” (м. Харків, 2000 р.);

_ 2-й міжнародній науково-технічній конференції “Фізичні і комп'ютерні технології в народному господарстві” (м. Харків, 2000 р.).

Публікації. Основні результати дисертаційної роботи опубліковані в 7 наукових працях, з них статей - 4, матеріалів конференцій - 3.

Структура та обсяг дисертації. Дисертація складається із вступу, п'яти розділів, висновків, додатку та списку використаних джерел. Повний обсяг дисертації становить 140 сторінок, серед них 123 сторінки основного тексту, 31 рисунок, 5 таблиць та 125 найменувань використаних літературних джерел (на 12 стор.).

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

У першому розділі наведено огляд літератури за темою дисертаційної роботи та обрано напрям досліджень. Розглядаються публікації, присвячені задачам геометричного проектування, зокрема задачам розміщення об'єктів довільної просторової форми і розмірів. Вивченню та розв'язанню задач такого класу присвячені роботи відомих вчених: Рвачова В.Л., Стояна Ю.Г., Гіля М.І., Комяк В.М., Яковлєва С.В., Мухачової Е.О., Новожилової М.В., Галати О.Я., Чорноморця А.О., Пономаренка Л.Д., Панкратова О.В., Dowsland W., Ferreira J.A.S., Terno I., Milencovic V. та ін.

Особлива увага приділяється науковим публікаціям, присвяченим розв'язанню задач нерегулярного розміщення тривимірних геометричних об'єктів довільної форми. Наведено коротку характеристику робіт зарубіжних вчених Bischoff E., Li K., Shykman S., Cagan J., Ikonen I. та ін. Інтерес до задач такого класу викликаний все більш зростаючим спектром їх практичного застосування та відсутністю ефективних методів для їх розв'язання.

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

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

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

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

Для опису математичних моделей матеріальних об'єктів, що розміщуються, використовується поняття -об'єкта простору R^k (k=2,3).

Точкова множина TR^k (k=2,3) називається -об'єктом, якщо виконуються наступні вимоги: _ канонічно замкнута чи канонічно відкрита множина; у будь-якій точці xclT існує окіл , такий, що та мають один і той же гомотопічний тип.

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

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

Геометрична інформація про довільний -об'єкт простору R^k (k=2,3) може бути зображена у вигляді g=(S, M, P), де S _ просторова форма -об'єкта, M _ метричні характеристики, що визначають “розміри” відповідного -об'єкта, P _ параметри розміщення, що визначають місце розташування -об'єкта у відповідному просторі.

Зауваження 1: Надалі будемо розглядати в якості багатокутника тільки _багатокутник, а в якості багатогранника - -багатогранник.

Нехай маємо n опуклих, орієнтованих (повороти не допускаються) довільних багатогранників T_i, i=1,2,…,n, та задано паралелепіпед D. Будемо вважати, що розміри A^*, B^* і C^* такі, що всі багатогранники можуть розміститися в паралелепіпеді D. Необхідно побудувати припустимий варіант розміщення багатогранників , i=1,2,…,n, у паралелепіпеді D таким чином, щоб багатогранники не перетиналися між собою, а висота зайнятої частини паралелепіпеда D була мінімальною.

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

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

a) умови взаємного неперетину об'єктів, що розташовуються;

б) умови розміщення об'єктів T_i, i=1,2,…,n, у паралелепіпеді D.

Для аналітичного опису умов а) та б) використовується математичний апарат Ф-функцій. Ф-функція дозволяє формально визначити міру близькості, а також міру перетину пари об'єктів T_i(u_i) і T_j(u_j).

Розглянемо довільні багатогранники T_i(u_i)R³ та T_j(u_j)R³. Неперервна та всюди визначена у просторі R⁶ функція вигляду називається Ф-функцією багатогранників T_i(u_i) і T_j(u_j), якщо вона має такі характеристичні властивості

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

Скористаємося поняттям поверхні -рівня Ф-функції: поверхня , яка описується рівнянням , називається поверхнею -рівня Ф-функції багатогранників T_i(u_i) і T_j(u_j).

Зауваження 2: Для зручності побудови поверхні -рівня Ф-функції багатогранників T_i(u_i) і T_j(u_j) та не порушуючи загальності, зафіксуємо параметри розміщення одного з багатогранників (наприклад, u_i^*=const).

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

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

У третьому розділі для моделювання умов взаємного неперетину опуклих орієнтованих багатогранників розроблений метод побудови поверхні 0-рівня Ф-функції пари багатогранників T_i, T_j.

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

Таким чином, будь-якій точці поверхні _ij відповідає деяке торкання багатогранників та, навпаки, будь-яке торкання багатогранників визначає принаймні одну точку поверхні _ij.

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

Розглянемо більш докладно процес побудови поверхні 0-рівня Ф-функції, який зводиться до послідовного формування граней поверхні _ij. Зазначимо, що елементами границі багатогранника є його вершини, ребра та грані. Очевидно, що при будь-якому торканні багатогранників T_i та T_j має місце один чи комбінація декількох варіантів торкання елементів їх границь:

_ вершина багатогранника T_j торкається грані багатогранника T_i;

_ ребро багатогранника T_j має спільні точки (торкається) із гранню багатогранника T_i;

_ грань багатогранника T_j має спільні точки з гранню багатогранника T_i;

_ вершина багатогранника T_i торкається грані багатогранника T_j;

_ ребро багатогранника T_i має спільні точки з гранню багатогранника T_j;

_ ребро багатогранника T_j має спільну точку з ребром багатогранника T_i.

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

Розглянуті варіанти охоплюють усі ситуації торкання багатогранників T_i та T_j. Очевидно, що грані поверхні 0-рівня Ф-функції утворюються:

_ кожною гранню багатогранника T_i та відповідним їй елементом границі багатогранника T_j (вершиною, ребром чи гранню);

_ кожною гранню багатогранника T_j та відповідним їй елементом границі багатогранника T_i (вершиною чи ребром);

_ парами відповідних ребер багатогранників T_i і T_j.

Тому процес побудови поверхні 0-рівня Ф-функції містить у собі такі етапи:

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

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

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

Таким чином, маємо багатогранну поверхню , максимальну кількість граней якої можна оцінити величиною , де () - кількість граней, а () - кількість ребер багатогранників T_i (T_j) відповідно.

Запропонований метод побудови поверхні _ij враховує питання чисельної стійкості при роботі з числами типу Real.

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

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

Нехай маємо деяку послідовність багатогранників T₁,T₂,…,T_n, відповідно до якої необхідно побудувати припустимий варіант розміщення. З урахуванням функції мети поставленої задачі (мінімізація висоти зайнятої частини паралелепіпеда) кожен багатогранник T_i будемо розміщати таким чином, щоб із усіх припустимих положень його полюса вибрати таке, при якому координата z мала б мінімальне значення. Якщо таких положень (точок) більше одного, то при рівних значеннях z вибирається положення з мінімальним значенням координати y. При рівних значеннях z та y вибирається положення полюса з мінімальним значенням координати x.

Відповідно до методу оптимізації за групами змінних полюс багатогранника розміщуємо у точці () (вершина паралелепіпеда P₁), тобто в якості параметрів розміщення багатогранника T₁ приймаємо координати цієї точки.

Нехай розміщені багатогранники T₁,T₂,…,T_l-1 (при цьому відомі їхні вектори параметрів розміщення , ,…,, а також поверхні , трансльовані на відповідні вектори). Тоді моделювання розміщення багатогранника T_l здійснюється в такий спосіб. Областю припустимих положень полюса O_l, за яких виконується умова T_lD, є паралелепіпед P_l.

Як можливі точки розміщення полюса O_l будемо розглядати:

вершину () паралелепіпеда P_l, якщо вона не належить областям intГ_rl (r=1,2,…,l-1);

точки перетину границі області P_l з поверхнею , які не належать областям intГ_sl (s=1,2,…,l-1, ), (r=1,2,…,l-1);

точки перетину поверхонь , та границі області P_l, які не належать областям intГ_sl (s=1,2,…,l-1, , ), (i=1,2,…,l-1, j=1,2,…,l-1, );

точки перетину трійок поверхонь , та , які належать області P_l та не належать областям intГ_sl (s=1,2,…,l-1, , , ), (i=1,2,…,l-1, j=1,2,…,l-1, , k=1,2,…,l-1, , ).

Як початкову припустиму точку розміщення полюса O_l вибираємо точку Q (). Якщо вершина () паралелепіпеда P_l не належить областям intГ_rl (r=1,2,…,l-1), то її координати є параметрами розміщення багатогранника T_l, тобто ; ; (вважається, що багатогранник T_l розміщений). У протилежному разі ( , ) переходимо до виконання наступних етапів:

_ послідовно знаходимо точки перетину ребер паралелепіпеда P_l з кожною з граней поверхні (r=1,2,…,l-1). Якщо чергова точка перетину ребра та грані (за умови, що вона існує) не належить областям intГ_sl (s=1,2,…,l-1 , ) та є переважнішою в порівнянні з раніше обраною точкою Q, то її приймаємо як чергову точку Q розміщення полюса багатогранника T_l;

_ послідовно знаходимо точки перетину (якщо вони існують) трійок граней: одна з граней є гранню поверхні (i=1,2,…,l-1), друга - гранню поверхні (j=1,2,…,l-1, ), третя - гранню паралелепіпеда P_l. Якщо чергова знайдена точка перетину такої трійки граней не належить ні одній області intГ_sl (s=1,2,…,l-1, , ) та є переважнішою в порівнянні з раніше знайденою точкою, то її приймаємо як чергову точку Q розміщення полюса O_l;

_ послідовно знаходимо точки перетину (якщо вони існують) трійок граней: одна з них є гранню поверхні (i=1,2,…,l-1), друга - гранню поверхні (j=1,2,…,l-1, ), третя - гранню поверхні (k=1,2,…,l-1, , ). Якщо чергова знайдена точка перетину трійки граней поверхонь , , належить області P_l, не належить областям intГ_sl (s=1,2,…,l-1 , , , ) та є переважнішою в порівнянні з раніше знайденою точкою, то її приймаємо як чергову точку Q розміщення полюса O_l.

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

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

Таким чином, використовуючи запропонований у роботі підхід, одержимо припустимий варіант розміщення багатогранників T_i, i=1,2,…,n, у паралелепіпеді заданих розмірів з мінімізацією висоти зайнятої частини паралелепіпеда. Очевидно, що при цьому кожен багатогранник належить області розміщення і не перетинається з іншими багатогранниками.

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

Програма “0-level surface” є складовою частиною програмної системи “Convex Polytopes Packing” та призначена для автоматизації процесу побудови поверхні 0-рівня Ф-функції двох довільних опуклих багатогранників.

Програмна система “Convex Polytopes Packing” являє собою інтегровану обчислювальну систему, призначену для моделювання та автоматизації процесу побудови припустимого варіанта розміщення опуклих багатогранників у паралелепіпеді заданих розмірів. У таблиці 1 наведені деякі результати чисельних експериментів роботи програмної системи “Convex Polytopes Packing”, які отримані на персональному комп'ютері з процесором типу Intel Celeron з тактовою частотою 300МГц, ОЗП - 64МБт, що працює під управлінням операційної системи Windows 98.

Розроблене програмне забезпечення реалізоване мовою високого рівня Object Pascal в об'єктно - орієнтованому середовищі Delphi версії 5.0 і може експлуатуватися на персональних комп'ютерах з операційною системою Windows 9x/2000.

У дисертаційній роботі наведено результат розв'язання прикладної задачі моделювання розміщення запасних частин та обладнання у контейнерах заданих розмірів для їх транспортування. Раніше запасні частини (обладнання) апроксимувалися паралелепіпедами та розглядалася задача розміщення набору паралелепіпедів у паралелепіпеді заданих розмірів. Використання розробленої програмної системи “Convex Polytopes Packing” дозволяє розглядати запасні частини (обладнання) як опуклі багатогранники та розв'язувати задачу розміщення їх у паралелепіпеді заданих розмірів. Це дозволяє зменшити витрати, пов'язані з транспортуванням запасних частин (збільшити ефективність використання об'єму контейнерів за рахунок збільшення кількості об'єктів, що розміщуються).

У додатку наведено довідку про використання розробленого програмного забезпечення на ВАТ “ХТЗ”.

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

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

Основні наукові і практичні результати:

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

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

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

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

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

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

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

1. Романова Т.Е., Магдалина И.В. Особенности представления геометрической информации о -объекте пространства // Радиоэлектроника и информатика. - 1999. _ № 1. - С.68-71.

2. Гиль Н.И., Магдалина И.В. Построение допустимого варианта размещения выпуклых многогранников в параллелепипеде заданных размеров // Автоматика и приборостроение. Вестн. ХГПУ. - Харьков, 2000. _ № 102.

3. Гиль Н.И., Магдалина И.В. Способ построения поверхности 0- уровня Ф-функции для двух выпуклых многогранников // Высокие технологии в машиностроении. Сб. науч. тр. ХГПУ. - Харьков, 2000. - Вып. 1(3). - С.52

4. Стоян Ю.Г., Шайтхауєр Г., Гиль Н.И., Романова Т.Е., Магдалина И.В. Класс поверхностей 0-уровня Ф-функций точечных множеств с границей - окружность или многоугольник. Проблемы машиностроения. - 2000. - Т3, № 1-2. - С.117-123.

5. Магдалина И.В. Представление исходной информации о материальных объектах при решении задач геометрического проектирования // Тез. докл. 3-го международного молодежного форума “Радиоэлектроника и молодежь в XXI веке”. ч.2, Харьков, 1999. - С.335-338.

6. Романова Т.Е., Магдалина И.В. Особенности представления геометрической информации о -объекте пространства // Вестник инженерной академии Украины. Информация по 2-й международной научно-технической конференции “Физические и компьютерные технологии в народном хозяйстве”. - Харьков, 2000. _ С.548-550.

7. Магдалина И.В. Условия касания двух множеств, индуцируемых компонентами связности границы -объекта // Тез. докл. 4-го международного молодежного форума “Радиоэлектроника и молодежь в XXI веке”. ч.2, Харьков, 2000. - С.30-31.

АНОТАЦІЯ

Магдаліна І.В. Математична модель та метод наближеного розв'язання задачі упакування опуклих багатогранників. - Рукопис.

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

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

Для розв'язання задачі розроблені нові ефективні методи.

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

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

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

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

АННОТАЦИЯ

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

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

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

Необходимо построить допустимый вариант размещения выпуклых ориентированных многогранников T_i, i=1,2,…,n, в параллелепипеде D таким образом, чтобы многогранники не пересекались между собой, а высота занятой части параллелепипеда D была минимальной.

Для описания области допустимых решений W используется понятие структуры линейных неравенств.

Для реализации условий взаимного непересечения многогранников и условий принадлежности размещаемых многогранников параллелепипеду D используется математический аппарат Ф-функций, разработанный в научной школе члена-корреспондента НАН Украины Ю.Г. Стояна. Ф-функция пары произвольных объектов позволяет формально определить меру близости, а также меру пересечения объектов в зависимости от значения их параметров размещения. В частности, для формализации условий взаимного непересечения многогранников используется понятие поверхности 0-уровня Ф-функции.

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

Для решения поставленной задачи разработана методология, основанная на принципе последовательно-одиночного размещения (модификация метода оптимизации по группам переменных), суть которого заключается в следующем. Все объекты размещаются последовательно по одному. Ранее размещенные объекты считаются неподвижными, т.е. их параметры размещения имеют вполне определенные фиксированные значения. Каждый объект размещается так, что из всех его возможных положений выбирается такое, при котором значение функции цели достигает наименьшего значения только по тем переменным, которые являются параметрами размещения размещаемого объекта. Учитывая постановку задачи (минимизация высоты занятой части параллелепипеда), каждый многогранник размещается таким образом, чтобы из всех его допустимых положений выбрать то, при котором значение z вектора параметров размещения было бы минимальным. Если таких положений (точек) больше одного, то при равных значениях z выбирается положение с минимальным значением координаты y. При равных значениях z и y выбирается положение многогранника с минимальным значением координаты x.

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

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

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

SUMMARY

Magdalina I.V. A mathematical model and method of approximate solution of a convex polytopes placement problem. - 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 National Academy of Sciences of Ukraine, Kharkov, 2001.

The thesis is a continuation of investigations of the three-dimensional placement problems. An optimization problem of convex polytopes packing into a parallelepiped of given sizes with minimizing occupied part of the parallelepiped is considered. The mathematical model of this problem is improved and features are investigated.

To solve this problem new effective methods are developed.

To realise the conditions of convex polytopes non-intersection the method of creating 0-level surface of Ф-function is developed. The method allows consecutively to form the faces of sought surface.

To search for an approximate solution of the problem a theoretical approach based on the method of optimisation by groups of variables developed. A decision obtained in such way can be used as initial possible points when realising exact methods to solve this problem.

Corresponding algorithms and software are development and can be used for solving the practical problems connected with modeling of allocation of three-dimensional geometric objects.

Key words: mathematical modeling, optimization, layout, packing, parallelepiped, polytope.

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

...