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

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

Національна академія наук України

Інститут кібернетики ім. В.М. Глушкова

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

Автореферат

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

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

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

Романова Тетяна Євгеніївна

Київ 2003

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

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

Науковий консультантдоктор технічних наук, професор,

членкореспондент НАН України

Стоян Юрій Григорович,

Інститут проблем машинобудування

ім. А.М. Підгорного НАН України, завідувач відділу

Офіційні опоненти:доктор фізикоматематичних наук, професор,

членкореспондент НАН України,

Перевозчикова Ольга Леонідівна,

Інститут кібернетики ім. В.М. Глушкова НАН України,

завідувач відділу

доктор технічних наук, професор,

членкореспондент АПН України

Верлань Анатолій Федорович,

Інститут проблем моделювання в енергетиці

ім. Г.Є. Пухова НАН України, завідувач відділу

доктор технічних наук, професор,

Сазонов Костянтин Олександрович,

Київський національний університет технологій та дизайну, завідувач кафедри

Провідна установаХарківський національний університет ім. В.Н. Каразіна, кафедра моделювання і математичного забезпечення ЕОМ, м. Харків

Захист відбудеться " 17 " жовтня 2003 р. об 11 годині на засіданні

спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики ім. В.М. Глушкова НАН України за адресою:

03680, МСП, м. Київ 187, пр. Академіка Глушкова, 40.

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

03680, МСП, м. Київ 187, пр. Академіка Глушкова, 40.

Автореферат розісланий " 12 " вересня 2003 р.

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

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

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

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

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

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

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

Цій тематиці присвячені роботи академіка АН СРСР Канторовича Л.В., академіка НАН України Рвачова В.Л., членкореспондента НАН України Стояна Ю.Г., а також відомих учених Залгаллера В.А., Мухачевої Е.О. (Росія), Dowsland K.A. (Велика Британія), Terno J., Dychoff H., Scheithauer G.(Німеччина), Milenkovic V. (США), Ferreira J.A, Oliveira J.F. (Португалія), Ikonen I., Biles W.D. (Фінляндія) та ін.

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

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

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

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

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

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

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

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

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

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

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

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

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

6.4.1. "Інтегровані комп'ютерні технології проектування" за д/б темами:

"Інтегрована комп'ютерна технологія геометричного проектування складних технічних систем" (19921996 рр., N ДР 0193U020060); "Інтелектуальні системи геометричного проектування" (19921996 рр., N ДР 193U020061), (постанова ДКНТ України);

1.12.5 "Проблеми автоматизації проектування технічних систем" за д/б темами: "Математичне моделювання складних технічних систем модульного типу", (19901993 рр., N ДР 01900009448); "Розробка і дослідження інтелектуальної системи відображення геометричної інформації для оптимізації і моделювання фізикомеханічних процесів і технічних систем" (1994 1997 рр., N ДР 0197U012281); "Розробка і дослідження математичних моделей задач оптимізації розміщення тривимірних геометричних об'єктів" (19982001 рр., N ДР 0198U007627); "Розробка методів і алгоритмів оптимізації для розв'язання задач розміщення тривимірних опуклих геометричних об'єктів у заданих опуклих областях " (20012002 рр., N ДР 0102U001480);

а також згідно з:

проектом ДКНТ України (фонд фундаментальних досліджень) N 12.3/66 "Розробка нових методів загального збереження і перетворення складної аналітичної і геометричної інформації в математичному і комп'ютерному моделюванні" (19941997 рр.);

договором між Німецьким дослідним товариством (Deutsche Forschungsgemeinschaft) і НАН України, грант TE 207/7, 436 UKR 113/42/0.

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

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

1)побудувати засоби математичного моделювання відношень базових геометричних об'єктів у вигляді функцій і нормалізованих функцій базових орієнтованих 2D&3D геометричних об'єктів евклідових просторів за заданими кортежами геометричної інформації;

2)побудувати засоби математичного моделювання відношень геометричних об'єктів, що мають довільну просторову форму в евклідових просторах , , у вигляді функцій складених 2D&3D геометричних об'єктів;

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

4)визначити і дослідити інтервальні геометричні об'єкти інтервального простору , , як математичні моделі 2D&3D геометричних об'єктів, заданих з деякими похибками в евклідових просторах;

5)розробити єдиний підхід до побудови функцій 2D&3D інтервальних геометричних об'єктів як засіб математичного моделювання відношень геометричних об'єктів у інтервальному просторі , ;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Запропоновані засоби математичного моделювання задач оптимізаційного геометричного проектування впроваджені в навчальний процес у Харківському національному університеті радіоелектроніки в курсах: "Конструктивні засоби математики", "Загальна топологія"; в Інституті обчислювальної математики Дрезденського технічного університету в курсі "Cutting&Packing"; використані при розробці сучасних технічних і програмних засобів комплексних автоматизованих систем контролю і керування промисловими об'єктами та технологічними процесами в АТЗТ "Важпромавтоматика" (м. Харків); у Харківській міській галереї при комп'ютерному моделюванні оформлення виставочних залів на республіканських і міжнародних виставках; на державному науково виробничому підприємстві "Меридіан" при математичному моделюванні і розв'язанні задачі розміщення пожежних сповіщувачів у системах автоматичного протипожежного захисту; в науково виробничій фірмі "Інформаційні комп'ютерні системи" при створенні системи комплексної автоматизації проектування і виробництва швейних виробів (САПР "Грація").

Особистий внесок здобувача в роботах, що виконані в співавторстві, полягає в такому: у монографії [1] написано розділ 1; [2] інтервальна математична модель комбінаторної оптимізаційної задачі розміщення прямокутників; [3] математична модель оптимізаційної задачі розміщення правильних багатокутників у інтервальному вигляді; [4] побудова області припустимих розв'язків у інтервальному вигляді; [5] виділення топологічних і гомотопічних особливостей компонентів лінійної зв'язності 2D об'єктів; [6] моделювання відношень між інтервальними прямокутниками, програмна реалізація, чисельні експерименти; [7] побудова математичної моделі комбінаторної оптимізаційної задачі розміщення прямокутників у смузі з урахуванням похибок вихідних даних; [9] опис відношень інтервального дотику опуклих інтервальних багатокутників; [10] побудова повного класу поверхонь 0 рівня функцїї множин, що мають границю коло чи прямокутник; [11] класифікація видів інтервального дотику точок простору , ; [12] метод побудови поверхонь 0рівня функцій пар геометричних об'єктів, границя яких має просторову форму кола або опуклого багатокутника; [13] визначення інтервального добутку в просторі ; [14] аналітичний опис області припустимих розв'язків задачі покриття; [15] побудова області припустимих розв'язків оптимізаційної задачі покриття прямокутної області кругами; [16] застосування інтервальної арифметики для моделювання фактора невизначеності тимчасового параметра при керуванні проектами; [17] математична модель регулярного покриття прямокутної області конгруентними кругами; [18] інтервальна модель задачі покриття опуклої багатокутної області кругами; [19, 20] поняття множини інтервальних переставлень та її образу в просторі ; побудова відображень множини інтервальних переставлень в евклідів простір ; [21] застосування функцій при побудові математичної моделі відношень перетинання і дотику геометричних об'єктів у задачі покриття; [22] побудова поверхонь 0 рівня і рівня функції паралелепіпедів; замикання доповнення прямого кругового циліндра і паралелепіпеда; [23] поняття інтервальної належності елементів у просторі ; відображення довільних точок простору на множину точок в , через які можливо провести інтервальну гіперплощину в ; [25] побудова нормалізованих Ффункцій паралелепіпедів і циліндрів; [26] поняття опуклої в множини, теорема про опуклість в перетину довільної кількості опуклих в множин; [27] розробка стратегії побудови функцій базових 2D об'єктів; [28] метод побудови функції двох опуклих багатогранників; [30] формування кортежу просторової форми базового 2D об'єкта; [31, 32] методологічні аспекти та стратегія побудови комп'ютерної системи візуалізації відношень базових та складених 2D&3D геометричних об'єктів; [33] стратегія побудови системи розв'язання оптимізаційних 2D задач розміщення; [34] виділення класу складених об'єктів, побудова функцій складених об'єктів; [35] побудова нормалізованих функцій базових 3D об'єктів; [36] дослідження просторової форми та метричних характеристик геометричних об'єктів на належність до класу об'єктів; [37] математична модель смуги та прямокутника з урахуванням похибок вихідних даних, інтервальна функція цілі; [38] побудова інтервальної математичної моделі задачі розміщення інтервальних прямокутників; [39] опис особливостей математичних моделей оптимізаційних 2D задач розміщення; [40] інтервальна математична модель основної оптимізаційної задачі геометричного проектування; [41] метод розв'язання оптимізаційної задачі розміщення інтервальних прямокутників; [42] класифікація та дослідження просторових форм базових 2D об'єктів; [43] теорема про функцію складених геометричних об'єктів.

Апробація результатів дисертації. Основні результати роботи доповідалися та дістали схвалення на міжнародних конференціях і наукових семінарах: на міжнародній конференції Interval'96, International Conference on Interval Methods and Computer Aided Proofs in Science and Engineering, Wurzburg, Germany, 1996 р.; на міжнародній конференції 16th International Symposium on Mathematical Programming, Lausanne, Switzerland, 1997 р.; на міжнародній конференції International Conference on Interval Methods and Their Applications on Global Optimization, Nanjing, China, 1998 р.; на міжнародній конференції International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, Budapest, Hungary, 1998 р.; на міжнародній конференції International Symposium EURO PRIME, Warsaw, Poland, 1999 р.; на міжнародній конференції EURO XVII, 17th European Conference on Operational Research, Budapest, Hungary, 2000 р.; на міжнародній науково технічній конференції Artificial Intelligence, с. Кацивелі, Україна, 2002 р.; на 1 му міжнародному форумі "Прикладна радіоелектроніка. Стан і перспективи розвитку", м. Харків, Україна, 2002 р.; на постійно діючому семінарі "Математичні методи геометричного проектування" (м. Харків, 19912003 рр.) при науковій раді з проблеми "Кібернетика" НАН України; на семінарах відділу математичного моделювання і оптимального проектування Інституту проблем машинобудування ім. А.М. Підгорного НАН України (м. Харків, 19912003 рр.); на семінарі "Математичні моделі і методи оптимізації систем з дискретними джерелами фізичних полів" кафедри програмного забезпечення обчислювальної техніки Житомирського інженерно технологічного інституту (м. Житомир, 1998 р.); на семінарі кафедри прикладної математики Харківського державного технічного університету радіоелектроніки (м. Харків, 1998 р.); на семінарах Дрезденського технічного університету "Cutting and Packing" (м. Дрезден, Німеччина, 19992002 рр.); на семінарі кафедри математичного моделювання і забезпечення ЕОМ Харківського національного університету ім. В.Н. Каразіна (м. Харків, 2003 р.); на семінарі відділу автоматизації програмування Інституту кібернетики ім. В.М.Глушкова НАН України (м. Київ, 2003 р.).

Публікації. За темою дисертації опубліковані 43 наукові праці, у тому числі: 1 монографія, 27 статей у наукових фахових виданнях, що входять до переліку ВАК України, 2 статті в зарубіжних наукових журналах, 1 препринт Інституту проблем машинобудування ім. А.М. Підгорного НАН України, 2 препринти Дрезденського технічного університету, 2 депоновані роботи, 6 тез доповідей на міжнародних наукових конференціях та 2 свідоцтва про реєстрацію авторського права на твір.

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

Структура та обсяг дисертації. Дисертація містить вступ, п'ять розділів, висновки по роботі, 4 додатки (оформлених у вигляді окремої книги на 105 сторінках), 83 рисунки, 10 таблиць та список використаних джерел з 365 найменувань на 32 сторінках. Повний обсяг дисертації становить 324 сторінки, з них 292 сторінки основного тексту.

ЗМІСТ РОБОТИ

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

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

На цей час розроблені деякі підходи до розв'язання оптимізаційних задач розміщення, що ґрунтуються на модифікаціях методу оптимізації по групах змінних, методу гілок і границь, евристичних методах, методах локальної оптимізації, цілочисловому, лінійному і нелінійному програмуванні. Цій тематиці присвячені роботи професора Стояна Ю.Г. і його учнів, у тому числі Гіля М.І., Путятіна В.П., Яковлева С.В., Смелякова С.В., Комяк В.М., Новожилової М.В., Пономаренка Л.Д., Єщенка В.Г., Панкратова О.В., Пацука В.М., Яськова Г.М. і багатьох інших.

Досить повний огляд публікацій із проблем моделювання та розв'язання задач упакування і розкрою (Cutting& Packing), що належать до класу задач геометричного проектування, наведений в анотованій бібліографії Dychoff H., Terno J., Scheithauer G. Джерела останніх публікацій можна знайти на інтернет сайті SICUP (Special Interested Group on Cutting and Packing, http://www.apdio.pt/sicup/).

До класу задач геометричного проектування належать також деякі задачі покриття. Дослідження в області математичного моделювання класичних задач покриття, а також у створенні методів їхнього розв'язання здійснені в роботах таких відомих учених, як Fejes Toth L., Rogers C.A., Fary L., Bezdek K., Делоне Б.М та ін. В рамках теорії геометричного проектування задачі покриття розглядаються в роботах Стояна Ю.Г., Яковлева С.В. та їхніх учнів. У цьому класі задач найменш вивченими є методи розв'язання задач нерегулярного покриття. Подальший розвиток цього напряму вимагає конструктивного опису умов покриття геометричних об'єктів, побудови нових математичних моделей.

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

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

Перелік основних публікацій з інтервального аналізу включає роботи, присвячені побудові інтервальних арифметик (Moore R.E., Kaucher E., Markov S.M., Sendov B., Нестеров В.М., Зюзін В.С. та ін.), дослідженню інтервальних матриць (Kulish U., Hansen E., Alefeld G., Herzberger J. та ін.), методам розв'язання систем лінійних і нелінійних інтервальних рівнянь (Rohn J., Hansen E., Rump S.M., Neumaier R., Moore R.E., Калмиков С.А., Шарий С.П., Лакеєв А.В. та ін.), обчисленню інтервальних інтегралів і похідних (Ratschek H., Nickel K., Moore R.E. та ін.).

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

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

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

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

Обґрунтована необхідність створення нових конструктивних засобів побудови математичних моделей задач геометричного проектування.

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

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

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

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

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

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

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

Перераховані вище умови задовольняє введена професором Стояном Ю.Г. функція.

Визначення 1. Неперервна, усюди визначена функція , , називається функцією об'єктів і , якщо вона має такі властивості:

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

В роботі використовуються основні властивості функції :

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

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

Вводиться вимірний інтервальний простір = , де розширений простір центрованих інтервалів.

Розглянуто основні властивості простору , в тому числі такі.

Арифметичний евклідів простір є підпростором простору з введеними операціями додавання, віднімання і множення на число.

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

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

Вводиться визначення інтервальної гіперплощини в просторі .

Множина точок простору , що задовольняють (6), (7), називається інтервальною гіперплощиною.

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

Визначається поняття інтервальної належності: , , .

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

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

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

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

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

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

Визначення. Інтервальна функція називається нормалізованою, якщо функції і нормалізовані

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

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

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

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

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

Далі наводиться метод побудови функцій базових 2D& об'єктів, суть якого полягає в такому.

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

1. Не втрачаючи загальності, припускаємо, що .

2. Будуємо поверхню (криву) .

3. Задаємо рівняння , що описує поверхню (криву) . При цьому має бути неперервною функцією.

4. Орієнтуємо рівняння так, що для і для , , відповідно до визначення 12.

5. Будуємо та, змінюючи на , одержуємо функцію .

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

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

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

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

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

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

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

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

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

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

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

Оптимізаційна задача розміщення паралелепіпедів у циліндрі з урахуванням мінімально і максимально припустимих відстаней. Будується математична модель задачі на основі використання нормалізованих функцій. Наводяться особливості математичної моделі.

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

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

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

Запропоновані в роботі засоби математичного моделювання взаємодій довільних геометричних об'єктів евклідових просторів були використані при створенні системи "SC functions" побудови функцій базових та складених геометричних об'єктів та візуалізації їхніх відношень. Програмні коди написані в середовищі програмування Microsoft Visual C++ 6.0 з використанням бібліотеки Open GL.

Додатки дисертації містять: акти про впровадження в навчальний процес, акти про використання результатів дисертаційної роботи; опис інтерфейсу і можливості системи "SC functions", вигляд основних програмних вікон; результати програмних реалізацій (у середовищі програмування Microsoft Visual С++6.0, TURBO PASCAL 7.0, Delphi 5, C++Builder 5.0) розв'язку оптимізаційних задач розміщення, що використовують функції базових і складених орієнтованих геометричних об'єктів з використанням математичного забезпечення, розробленого під керівництвом професора Стояна Ю.Г. у відділі математичного моделювання та оптимального проектування Інституту проблем машинобудування ім. А.М. Підгорного НАН України.

ВИСНОВКИ

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

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

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

2. Створено методику побудови поверхонь 0рівня функцій базових геометричних об'єктів.

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

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

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

6. Побудовано інтервальну математичну модель основної оптимізаційної задачі геометричного проектування з урахуванням похибок метричних характеристик та параметрів розміщення 2D&3D геометричних об'єктів.

7. Запропоновано нові підходи до побудови математичних моделей комбінаторних задач геометричного проектування з урахуванням похибок вихідних даних.

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

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

10. Побудовано математичну модель оптимізаційної задачі покриття з урахуванням похибок вихідних даних з застосуванням інтервальних функцій.

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

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

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

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

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

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

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

...