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

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

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

УДК 519.859

ЗАСОБИ ПОБУДОВИ МАТЕМАТИЧНИХ МОДЕЛЕЙ ОПТИМІЗАЦІЙНИХ

ЗАДАЧ РОЗМІЩЕННЯ ГЕОМЕТРИЧНИХ ОБ'ЄКТІВ ТА ЇХ

ЗАСТОСУВАННЯ

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).

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

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

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

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

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

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

1. = = , .

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

,

.

3. Поверхні і центрально симетричні, тобто

=,

а також .

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

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

У просторі визначена метрика, де, , ,

, ,.

У просторі вводяться інтервальні операції додавання, віднімання

(2)

операція множення на число

=, (3)

операція множення на інтервальне число

(4)

де , операція інтервального множення в ,

операція ділення на інтервальне число

, (5)

,.

Сформульовано властивості безперервності та стійкості операцій (2)(5).

Введено поняття спряження елементів простору .

Визначення 3. Спряженням точки називається точка

Визначення 4. Частковим спряженням точки називається точка , така, що

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

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

Простір гомеоморфний арифметичному евклідовому простору , а відображення

є гомеоморфізмом, де , , , .

Простори і ізометричні.

Вводяться деякі форми відображень з в .

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

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

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

Визначення 5. Інтервальне рівняння

(6)

називається інтервальним рівнянням інтервальної гіперплощини,

де , , , ,

. (7)

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

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

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

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

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

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

Визначення 6. Точки , інтервально дотикаються, якщо виконується умова

. (8)

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

, (9)

де .

Визначення 8. Інтервальна пряма L: та інтервальна точка , , , інтервально дотикаються, якщо

(10)

Інтервальна відстань між інтервальною прямою L і точкою , що інтервально дотикаються, визначається виразом

(11)

де

.

Визначення 9. Інтервальні прямі : , , інтервально дотикаються, якщо виконується умова

. (12)

Інтервальна відстань між інтервальними прямими і , що інтервально дотикаються, обчислюється за формулою

(15)

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

На підставі визначень 6 9 та співвідношень (8) (15) вводиться визначення інтервального дотику опуклих інтервальних багатокутників і .

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

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

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

Поверхня є інтервальною поверхнею 0 рівня функції и .

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

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

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

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

Інтервальна математична модель поставленої задачі має вигляд

, (16)

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

(17)

В (21) нормалізована інтервальна функція об'єктів і , нормалізована інтервальна функція об'єктів і , ( ) мінімально (максимально) припустима відстань між об'єктами і = , ( ) мінімально (максимально) припустима відстань між об'єктами і . У випадку = = та = = досить побудови ненормалізованих інтервальних функцій відповідних пар об'єктів.

Якщо всі похибки вихідних даних дорівнюють нулю, тоді математична модель (16) (17) буде описувати ідеалізовану оптимізаційну задачу розміщення.

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

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

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