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

ІНСТИТУТ ПРОБЛЕМ МАШИНОБУДУВАННЯ ім. А. М. Підгорного

НОВОЖИЛОВА МАРИНА ВОЛОДИМИРІВНА

УДК 519.859

МАТЕМАТИЧНІ МОДЕЛІ І МЕТОДИ РОЗВ’ЯЗАННЯ

НЕЛІНІЙНИХ ЗАДАЧ РОЗМІЩЕННЯ

ГЕОМЕТРИЧНИХ ОБ’ЄКТІВ

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

АВТОРЕФЕРАТ

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

доктора фізико-математичних наук

Харків - 1999

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

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

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

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

Офіційні опоненти: доктор фізико-математичних наук, професор Кісельова Олена Михайлівна, Дніпропетровський державний університет, завідувач кафедри обчислювальної математики і математичної кібернетики;

доктор фізико-математичних наук, професор Литвин Олег Миколайович, Українська інженерно-педагогічна академія (м. Харків), завідувач кафедри прикладної математики

доктор фізико-математичних наук, професор Ємець Олег Олексійович, Полтавський державний технічний університет ім. Ю.Кондратюка, завідувач кафедри прикладної математики і математичного моделювання.

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

відділ методів розв’язання складних задач оптимізації, м. Київ.

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

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

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

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

Автореферат розісланий "23" жовтня 1999 р.

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

спеціалізованої вченої ради Б.П.Зайцев

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

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

Одним із основних інструментів вивчення і оптимізації таких систем є теорія дослідження операцій, зокрема, моделі і методи математичного програмування. В останні десятиріччя апарат математичного програмування як засіб вибору оптимальної конфігурації або множини параметрів для досягнення певної мети дістав подальший суттєвий розвиток значною мірою завдяки фунда-ментальним роботам таких відомих українських учених, як академік Михалевич В.С., академік НАН України Сергієнко І.В., академік НАН України Шор Н.З., академік НАН України Рвачов В.Л., академік НАН України Пшеничний Б.М., член-кореспондент НАН України Бублик Б.М., академік НАН України Єрмольєв Ю.М., член-кореспондент НАН України Стоян Ю.Г., професор Кісельова О.М. та інші.

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

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

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

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

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

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

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

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

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами.

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

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

--"Інтегрована комп'ютерна технологія геометричного проектування складних технічних систем" (1992-1996рр., NГР0193И020060);

--"Інтелектуальні системи геометричного проектування" (1992-1993 рр., N ГР0193V020061), (Постанова ДКНТ України);

-1.12.5 "Проблеми автоматизації проектування технічних систем" за д/б темами:

--"Математичне моделювання складних технічних систем модульного типу", (1990-1993 рр., N ГР 01900009448);

--"Розробка і дослідження інтелектуальної системи відображення геометричної інформації для оптимізації і моделювання фізико-механічних процесів і технічних систем" (1994 - 1997 рр., N ГР 0197V012281);

--1.7.2.2 "Розробка і дослідження математичних моделей задач оптимізації розміщення тривимірних геометричних об'єктів" (1998-2001 pp.);

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

-- Договору з Міністерством у справах науки і технологій України N 2/847-97 "Аналiтико-геометричне та комп’ютерне моделювання високих технологій виготовлення та експлуатації об’єктів складної конфігурації, що піддаються висoкоградiентним впливам".

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

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

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

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

3. Проаналізувати методи і алгоритми з точки зору їхньої обчислювальної складності.

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

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

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

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

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

4. Вперше застосовано апарат F-функцій для опису умов взаємного розміщення двох неорієнтованих багатогранників у R3.

5. Побудовано нові точні і наближені засоби розв’язання нових класів оп-тимізаційних задач розміщення у областях розміщення зі змінними метрични-ми характеристиками.

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

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

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

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

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

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

Теоретичне значення роботи. Всі теоретичні результати подані у вигляді визначень, теорем, властивостей, описів алгоритмів, що в значній частині приводяться вперше або узагальнюють вже відомі.

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

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

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

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

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

Основні засоби математичного моделювання, запропоновані методи

розв’язання задач оптимізаційного геометричного проектування впроваджені до навчального процесу Харківського державного технічного університету будів-ництва і архітектури під час підготовки та викладання таких лекційних курсів: “Технічні засоби в архітектурному проектуванні“, “Дискретний аналіз“, “Методи дослідження операцій“ (1997-1999 рр.).

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

-Всесоюзному семінарі "Моделювання регіональних систем" (Уфа, 1990 р.); -Всесоюзній школі "Системи програмного забезпечення розв'язку задач оптимального планування" (Кострома, 1990 р.); Міжнародній конференції "Mathematical Optimization" (Берлін, Німеччина, 1990 р.); Республіканській науково-технічній конференції "САПР технологічної і конструкторської підготовки виробництва в машинобудуванні" (Харків, 1990 р.); - Всесоюзній школі "Питання оп-тимізації обчислень" (Крим, 1991 р.); - 12-й Всесоюзній конференції "Системи програмного забезпечення розв'язання економічних задач" (Нарва-Йиєссуу, 1992 р.); - Міжнародній школі "Проектування АСК і АСУ складними об'єктами" (Туапсе, Росія, 1992 р.); - 46-й науковій конференції професорів і викладачів Полтавського державного технічного університету (Полтава, 1994 р.); - 17-й Міжнародній конференції "System Modeling and Optimization" (Прага, Чехія , 1995 р.); - Міжнародній конференції "Combinatorial Optimization'-96" (Лондон, Велика Британія, 1996 р.); - Міжнародній конференції "Математика і мистецтво" (Суздаль, Росія, 1996 р.); - 18th International Conference on Software Engineering (Берлін, Німеччина, 1996 р.); - Міжнародній науково-технічній конференції "Прогресивні технології машинобудування і сучасність" (Севастополь, 1996 р.); - Міжнародній конференції "Cooperation and Business Opportunities for Eastern/European countries in the IT field" (Будапешт, Угорщина, 1997 р.); - 15-й Міжнародній конференції "Математика. Комп'ютер, Освіта", (Пущіно, Росія, 1997 р.);- 1-му Міжнародному Форумі "Електроніка і молодь в ХХI сторіччі" (Харків, 1997 р.); - 53-й науково-практичній і навчально-методичній конференції професорів і викладачів Харківського державного університету будівництва і архітектури (Харків, 1998 р.); - 16th European Conference on Operational Research (Брюссель, Бельгія, 1998 р.); - постійно діючому семінарі "Математичні методи геометричного проектування" (Харків, 1991-1999 рр.) при науковій Раді за проблемою "Кібернетика" НАН України, науковому семінарі відділу № 120 Інституту кібернетики ім. В. М. Глушкова НАН України (Київ, 1999 р.).

Публікації. За темою дисертації опубліковано 30 наукових робіт, в тому числі: 1 монографія, 17 статей у наукових виданнях (журналах та збірниках наукових праць), 2 депонованих роботи, 3 доповіді в матеріалах міжнародних наукових конференцій, 5 тез доповідей на міжнародних і національних наукових конференціях, 2 препринта Інституту проблем машинобудування ім. А. М. Підгорного НАН України.

У 1997 році Президія НАН України присудила автору премію Національної академії наук України за серію кращих наукових робіт.

Особистий внесок здобувача. Всі результати дисертаційної роботи одержані за особистою участю автора. У монографії [1] автором особисто написані розділи 4.1, 4.2, 4.3.

У працях, що написані у співавторстві, дисертанту належать: [2] - концепція побудови системи, що орієнтована на розв'язання задач прямо-кутного розміщення з можливістю моделювання різних технологічних обме-жень; [6] - аналіз алгоритмів внутрішньої точки з точки зору їхньої обчислю-вальної складності і можливості застосування до розв'язання задач геометрич-ного проектування; [8] - моделювання і дослідження області припустимих роз-в'язків задачі розміщення орієнтованих багатокутників у багатозв'язній області розміщення; [9] - побудова математичної моделі оптимізаційної задачі розмі-щення неорієнтованого багатогранника у багатограннику зі змінними метричними характеристиками; [10, 24] - аналіз ефективності алгоритмів розв'язання оптимізаційних задач розміщення; [11] - моделювання задачі оптимального розміщення неорієнтованих багатокутників у багатозв'язній області розміщен-ня і вилучення умов локальної збіжності; [13] - застосування поняття F-функції до задач геометричного проектування, якщо об'єкти розміщення є ніде не щіль-ними; [14] - постановка задачі дослідження, розробка принципових основ за-стосування методики неперервної оптимізації, а саме, стратегії активного набо-ру, до комбінаторної задачі прямокутного розміщення; [17] - порівняння, аналіз обчислювальної складності і застосування алгоритмів, що розглядаються, до розв'язання задачі розміщення неорієнтованих багатокутників; [18] - застосу-вання стратегії активного набору до обробки інформації про кінцеві вершини дерева розв’язків задачі прямокутного розміщення, алгоритмічна та програмна реалізація; [19] - моделювання задачі розміщення скінченої множини гіперпаралелепіпедів у гіперпаралелепіпеді, засіб розв'язання задачі; [20] - моделювання і дослідження конструктивних властивостей області припус-тимих розв'язків задачі розміщення орієнтованих багатокутників у смузі з дефектними зонами; [21, 30] - моделювання і дослідження області припустимих розв'язків задачі розміщення неорієнтованого багатогранника в багатогранній області; [22] - побудова методу розв'язання, аналіз множників Лагранжа з точки зору геометричних особливостей задачі прямокутного розміщення; [23, 27] - алгоритмічна і програмна реалізація методу розв'язання задачі, що розгля-дається; [25] - дослідження властивостей симетрії області припустимих розв'язків задачі прямокутного розміщення; [26] - моделювання задачі, що розглядається, як задачі оптимального розміщення багатокутників у смузі; [27, 28] - модифікація стратегії активного набору для розв'язання 2D задач геометричного проектування.

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

Структура і обсяг роботи. Дисертація містить вступ, п'ять розділів, ви-

сновки з роботи, 2 додатки, повний обсяг дисертації - 281 стор., з них 251 стор.

машинописного тексту, 71 рисунок, 1 таблиця, список використаних джерел з 204 найменувань на 20 стор.

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

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

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

Аналіз сучасного стану даної проблеми за матеріалами вітчизняної і зару-біжної наукової преси та вивчення праць таких відомих вчених у галузі роз-в'язання задач розміщення, як проф. Мухачова Е. О. (Росія), проф. Dowsland W. (Велика Британія), проф. J.A.S. Ferreira (Португалія), проф. J. Terno (Німеччина), проф. V. Milenkovic (США) та ін. показали, що найбільш розпов-сюдженим способом є або послаблення обмежень задачі, аж до повного ігнору-вання просторової форми об'єктів, що розміщуються, шляхом зведення задачі до задачі одновимірного розміщення, тобто до задачі лінійного програмування, або фіксування параметрів розміщення об'єктів. Внаслідок цього розв'язок задачі ли-ше випадково може виявитися оптимальним. Найбільш дослідженими є задачі лінійного (одновимірного) розміщення, та задачі гільйотинного прямокутного розміщення. Кожна окрема задача розміщення розглядається лише у контексті своєї неформальної постановки. Брак фундаментальних досліджень в даній предметній області призводить до того, що майже зовсім не розглядаються за-дачі розміщення неорієнтованих геометричних об’єктів у багатокутних ізотроп-них та анізотропних областях зі змінними метричними характеристиками. В роботі показано, що цей недолік можна ліквідувати на основі єдиного підходу, єдиної математичної моделі задач розміщення, яка розглядається в рамках теорії геометричного проектування і розробляється у науковій школі члена-корес-пондента НАН України професора Стояна Ю.Г.

Основні результати розділу опубліковано в працях [8, 6, 7, 21, 23].

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

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

g = (s1, s2 ,...,sq , m1 ,...,mi ,..., mq , v1 ,...,vi ,...,vq, v),

де: q - число компонент зв’язності межі об’єкта S.

s1, s2 ,...,sq -сукупність просторових форм компонент зв’язності межі S;

m1, m2 ,..., mq - метричні характеристики, котрі, зокрема, визначають розміри точкових множин, що мають просторові форми {s};

v1 ,...,vi ,...,vq - параметри розміщення компонент зв’язності межі S;

v - параметри розміщення об’єкта S.

Отже, геометрична інформація g індукує S у певному метричному просто-рі H. У роботі взагалі розглядаються арифметичні евклідови простори R2 і R3, хоча окремі результати розповсюджуються і на простори більшої вимірності.

Основна задача даної роботи орієнтована на певний клас точкових мно-жин, а саме клас j*-багатокутників (j*-багатогранників).

У розділі аналізуються існуючі засоби визначення неопуклого багатокут-ного (багатогранного) j*-об’єкта. У просторі R2 метричні характеристики m1, m2,...,mq можуть бути зображені координатами вершин відповідних багато-кутних контурів у власній системі координат, параметри розміщення мають вигляд v=(x,y,f).

Якщо покласти параметр f - кут повороту власної системи координат j*-об’єкта відносно нуля простору - фіксованим, багатокутна область також може бути задана аналітично за допомогою апарату структур лінійних нерівностей (F(x),,m), де F(x) - упорядкований набір лінійних нерівностей, які задають лінійні частини межі j*-багатокутника S, = qgmm- матриця відношень, m- кількість нерівностей.

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

Початковою інформацією про неопуклий багатогранний геометричний об’єкт S є множина граней G={gr}, r=1,2,…,N, де gr - r-а грань об'єкта S, що визначається послідовністю вершин (xr1, yr1, zr1),...,(xrg, yrg, zrg),..., (xrlr, yrlr, zrlr), - кількість вершин грані gr, N - кількість граней. Вектор параметрів розміщення об’єкта S має вигляд: {v} = (X,Y, Z, f, y, q).

Математична модель Еk(Rt) (t=2,3) - оптимізаційної задачі геометричного проектування, що розглядається у роботі, має вигляд:

визначити вектор u* і відповідний йому образ Su Rt, що індукується геометричною інформацією g(u*)=P(g0(u0),g1(u1),...,gn(un)), при якому

u* =, (1)

де gi=(si, mi, vi) - геометрична інформація, що індукує обмежені однозв’язні j*-багатокутники (j*-багатогранники) Si, i=0,1,...n в Rt;

S0-область розміщення;

g(u)-геометрична інформація про точкову множину Su=B(S0, S1,...Sn),

В - оператор, що є композицією теоретико-множинних операцій вигляду

Su=S0(Si)

P- оператор вигляду:

g(u)=P(g0(u0), g1(u1),..., gn(un))=({S0(Si)}, {m0, m1 ...mn}, {v0 v1...vn}),

ui - вектор змінних giGi, i=0,1,...n;

D - область припустимих розв’язків.

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

а) умовами розміщення об’єктів Sj в області S0

S0Sj= Sj або SjS0 або S^0 Sj = , j=1,2,...n, (2)

де - відношення включення,

S^0=R2\int S0 - доповнення точкової множини S0 до всього простору, в якому розглядається точкова множина S0.

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

int Si int Sj= , i < j =1,2,...n. (3)

Основні результати розділу опубліковано в працях [1, 2, 7, 20, 21].

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

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

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

У роботі розглядається частинний випадок афінного перетворення подібності - гомотетія G геометричного об’єкта Sj відносно центра його власної системи координат (або, коли це зручно, відносно іншої точки площини R2): G(S) = S*, що характеризується коефіцієнтом гомотетії K. Тоді Sj* =KSj(vj).

Далі розглядається відношення включення (2), якщо над областю розмі-щення - багатокутником S0 - припустима гомотетія G(S0) = S0*, причому багато-кутник Sj має задані метричні характеристики, а параметри розміщення області S0 фіксовані. У даному випадку як область S0, так і об'єкт розміщення Sj мають непорожню внутрішність і умова (2) задається F0j(xj,yj,K)-функцією

F0j (xj,yj,K )>0, якщо Sj(xj,yj) S^0(K) = ,

F0j ( xj,yj,K) = 0, якщо Sj(xj,yj) S^0(K) ,

int Sj(xj,yj) int S^0(K) =,

F0j (xj,yj,K) < 0, якщо int Sj(xj,yj) int S^0(K) ,

У роботі наведено побудову аналітичного опису F0j(xj,yj,K)-функції струк-турою лінійних нерівностей.

Центральне місце у розділі займає побудова структури нелінійних нерів-ностей, що описує область невід’ємності F-функції для об'єктів, які мають куто-вий параметр розміщення. У цьому випадку Fij(xi,yi,fi,xj,xj,fj)-функція як функ------ція, що дозволяє задавати неперетин, дотик і перетин замкнених j*-об’єктів Si(xi,yi,fi) і Sj(,xj,xj,fj) розглядається у просторі R6 параметрів розмі-щення (xi, yi, fi, xj, xj, fj).

Поверхня Tijlk 0-рівня Fij(xi,yi,fi,xj,xj,fj) -функції в R6 є нелінійною, кус-ково-диференційовною і складається з набору гладких поверхонь {Tijhlk},h=1,2, Н.

При побудові структури нелінійних нерівностей використовується визна-чення області невід’ємності -функції пари орієнтованих багатокутників (пара-метри fi, fj є фіксованими) структурою лінійних нерівностей. При цьому нео-пуклі багатокутники Si(xi,yi) і Sj(xi,yi) зображуються у вигляді об’єднання опук-лих замкнених багатокутників:

Si = Sil і Sj = Sjk (4)

У роботі розглядаються і порівнюються засоби зображення однозв’язного неопуклого багатокутника у вигляді (4). Методи, що реалізують теоретико-мно-жинну операцію (4), поряд із засобами реалізації операції суми Мінковського і теоретико-множинного віднімання відіграють дуже важливу роль у множині методів геометричного проектування. Тому засоби зображення (4) порівню-ються не тільки з точки зору мінімізації обсягу геометричної інформації про множини об’єктів {Sil} і {Sjk} (4), обчислювальної складності алгоритмів, але і з точки зору уникнення зайвих методологічних ускладнень на етапі розв’язання конкретної оптимізаційної задачі геометричного проектування, що можуть по-роджуватися певним засобом зображення (4).

Покладемо xil=0, yil=0. Для довільної пари (Sil, Sjk) поверхня 0-рівня Fij(0, 0,0,xjk,yjk,0)-функції є замкненою ламаною T2 у просторі R2 параметрів (xjk, yjk). Кожна сторона Tp2 кривої T2, p=1,2,...P, P (Njk + Njk), де Nil і Njk - кількість вер-шин об’єктів Sil і Sjk відповідно, породжується одним з трьох можливих випадків дотику об’єктів (Sjk, Sil):

Дотик першого типу: g-а сторона об'єкта Sil і q-а вершина об'єкта Sjk;

Дотик другого типу: q-а сторона об'єкта Sjk і g-а вершина об'єкта Sil;

Дотик третього типу: g-а сторона об'єкта Sil і q-а сторона об'єкта Sjk.

Умова Fij (xil ,yil, xjk ,yjk) 0 (умова взаємного неперетину об’єктів Sil і Sjk )

зображується структурою лінійних нерівностей вигляду

s(Flk (xil ,yil , xjk ,yjk), D, P), (5)

де нерівності набору Flk (xil ,yil , xjk ,yjk) кількістю P мають вигляд

Ap(xil - xjk ) + Bp(yil - yjk ) + Cp 0, p=1,2,...P,

а коефіцієнти Ap, Bp, Cp є функціями координат вершин, що складають відповід-ну пару "вершина - сторона" першого, другого або третього типу.

Тоді умова взаємного неперетину об’єктів Si і Sj у R4 з урахуванням (5) ви-значається структурою sij лінійних нерівностей:

sij = s(Flk (xil, yil, xjk, yjk), D, Р).

У просторі R6 всіх параметрів розміщення координати вершин об'єктів Sil і Sjk є функціями параметрів fi i fj. Тому при розгляді поверхні Tijlk в R6 коефі-цієнти A, B, C стають нелінійними функціями даних параметрів.

Отже, поверхня Tijhlk R6 належить поверхні, яка визначається рівнянням fijh=0, причому у випадку першого типу сторони Tp2 функція fijh приймає вигляд

(Ahcosfi-Bhsinfi)(xil-xjk)+(Bhcosfi+Ahsinfi)(yil-yjk)+C1hcos(fi-fj) C2hsin(fi-fj)+ C3_h

а у випадку другого типу сторони Tp2 -

(Ah cosfj - Bh sinfj)(xil - xjk)+ (Bhcosfj +Ahsinfj)(yil -yjk)+

+C1_h cos(fi - fj) C2_hsin(fi - fj) + C3_h , h=1,2,...H.

Випадок третього типу зводиться до одного з цих типів.

Зауваження 2. Аналітичний опис Tijhlk містить також визначення можли-вих меж змінювання кутових параметрів fi і fj. Нехай fi[0,2], тоді параметр fj повинен задовольняти обмеження:

fi - fj -f ijhlk_2 , fj- fi fijhlk_1 , (6)

де {fijhlk_1, fijhlk_2} - певні константи, що залежать від обраної пари "вершина - сторона" (дотик першого, другого і третього типу).

Тоді в залежності від типу сторони Tp2 множина Tijhlk є частиною гіпер-по-верхні, яка описується системою обмежень

{fijh1=0; fi - fj -f ijhlk_2 , fj - fi fijhlk_1 } (7)

{fijh4=0; fi - fj -f ijhlk_2 , fj - fi fijhlk_1 }

для сторони Tp2 першого і другого типу відповідно.

Зауваження 3. Об’єкти Sil і Sjk у R2 мають довільну взаємну орієнтацію, то-му поверхні Tijhlk, h=1,2,...H, можуть породжуватися довільною парою вигляду "вершина Sil - сторона Sjk " або "вершина Sjk - сторона Sil", тобто H= 2(Nil x Njk).

При цьому, виконання однієї з тернарних систем нерівностей вигляду (7) задає умову взаємного неперетину об’єктів Sil і Sjk в R6.

Тоді структура нелінійних нерівностей

s(Flk (xil, yil,fi, xjk, yjk, fj), D , m3H) ,

що визначає умови взаємного неперетину об’єктів Sil і Sjk, об’єднує H тернарних систем нерівностей, які містять нерівності вигляду (6-7).

Подальший розвиток апарат структур нелінійних нерівностей дістає для опису відношення включення (3), якщо об’єкт S1(x1,y1,f1) розміщується в області S0 (x0, y0, f0, К) з урахуванням перетворення гомотетії над областю. Відношення (3) задається структурою нелінійних нерівностей вигляду

s0j = s(F0k (x0,y0,f0,К,xj,yj,fj), D,3H). (8)

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

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

1. Грань gr об'єкта S0 - вершина sp=(xp, yp, zp) об'єкта S1,

2. Грань gr oб'єкта S1 - вершина sk=(xk, yk, zk) об'єкта S0 .

Гладка частина Tl, l=1,2....H, поверхні T 0-рівня F-функції, що розгляда-ється, визначається системою 4 обмежень вигляду

{ fl=0; , , }, (9)

де функція fl у випадку дотику першого і другого типу має вигляд відповідно

fl=al x1+ bl y1+ cl z1+ dl (K)+ al xp(1) + bl yp(1)+ cl zp(1),

fl=al (1)x1+ bl(1) y1+ cl (1)z1+ dl - K( al(1) xk + bl (1)yk+ cl(1) zk),

а обмеження , , , g{k, p}, визначають діапазон зміни кутових параметрів 1=(f1, y1, q1) на найбільші можливі кути повороту з поточного положення.

У розділі розглянуто аналітичний опис умови взаємного неперетину об'єк-тів у випадку анізотропної області S0 розміщення, яка є анізотропною внаслідок наявності в кожній точці області свого напряму найменшої тягучості spoint, що розподілений, наприклад, за еліпсом напружень, тобто координати (x,y) до-вільної точки області S0 задовольняють співвідношення

x=atcosf, y=btsinf,

де t - коефіцієнт гомотетії,

a, b - значення довжин півосей певного базового еліпса.

Отже, в кожній точці області S0 напрям sobject найменшої тягучості об'єкта Si, що розміщується, повинен збігатися з напрямом анізотропії spoint області роз-міщення, що означає зміну орієнтації власної системи координат XiОiYi об'єкта в залежності від координати f його полюса.

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

Рис.1 - Проекція 0-рівня F-функції двох опуклих багатокутників (показана товстою лінією) у анізотропній області.

Основні результати третього розділу опубліковані у роботах [1, 3, 5, 7-9, 12, 13, 18, 19, 21, 22, 24].

У четвертому розділі розглядається реалізація задачі (1-3) на множині неорієнтованих багатокутних об'єктів розміщення, а саме оптимізаційна задача нерегулярного розміщення скінченого набору неопуклих неорієнтованих багатокутників S={Si}, i=1,2,...,n у багатокутній багатозв’язній області розмі-щення S0 з дефектними зонами Wс, с=1,2,...K. Аналізуються особливості області припустимих розв'язків задачі, пропонується метод локальної оптимізації за-дачі, що враховує можливість оптимізації за групами змінних, тобто за групами параметрів трансляції об'єктів і кутових параметрів розміщення. Розглядається також моделювання задачі розміщення неорієнтованого багатокутника в об-меженій багатокутній області з метою мінімізації площі області, задача розмі-щення неорієнтованого неопуклого багатогранника в багатограннику з метою мінімізації об'єму останнього, а також задача розміщення орієнтованих багато-кутників у смузі.

Математична модель реалізації основної задачі (1-3), що розглядається на множині неорієнтованих багатокутників, має вигляд:

визначити: min z, (10)

(X,f) DR3n+1

де Х = (x1, y1, x2, y2, ..., xn, yn, z),

f=( f1, f2, ...,fn),

область D= D1 D2 D3 визначається структурою нерівностей

{ si0} { sk} {sij}, (11)

умова (2) визначається структурою вигляду

s i0(F(X,f), mi, Di)=skt(F(X,f), 3, D1), i=1,2,...,n,

умова взаємного неперетину об’єктів Si та Sj визначається структурою

sij = sgl (Flk (xil ,yil , fi, xjk ,yjk, fj), 3H, D),

умова взаємного неперетину об’єктів Sj і Wс описується структурою

sg =skl(F (xjk, yjk, fj, (acl, bcl),0), (Njk x Nсl), D).

Вилучено такі основні характерні властивості області D.

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

2. Область D може бути зображена у вигляді об’єднання скінченого числа

неопуклих областей Ds_nonlinear, кожна з яких задається системою нелінійних і лі-нійних обмежень структури (11):

D=Ds_nonlinear. (12)

3. Покриття (12) не є розбиттям, тому для деяких точок X області D має місце співвідношення:

(X, f) Dg_nonlinear, Е .

4. Область D в загальному випадку є незв’язною множиною і кожна її компонента зв’язності має “яружний” характер.

5.У перерізі області D гіперплощиною fconst={fi}i=1,2,...,n=const маємо певну багатогранну неопуклу множину

Dlinear =Dg_linear= Dg_s_linear R2n+1,

де Dg_linear - компонента лінійної зв’язності області Dlinear,

Dg_s_linear - опукла багатогранна підмножина.

6. Область Dlinear є областю припустимих розв’язків задачі вигляду

знайти: z. (13)

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

Через властивості 1-4 області D, задача (10-11) класифікується як багато-вимірна багатоекстремальна оптимізаційна задача з лінійною функцією мети і, в загальному випадку, нелінійними неопуклими обмеженнями.

У розділі розглядаються кілька підходів до побудови початкового набли-ження Х0 (fconst=const), які аналізуються з точки зору якості Х0 і обчислювальної складності алгоритмів. На підставі поглибленого аналізу вибір робиться на користь для методу локальної оптимізації задачі (12). Точка Х0 є вершиною області Dlinear і визначається системою рангу (2n+1) активних у точці. лінійних обмежень

F(fconst)Х0+ C(fconst)=0, (14)

де ліві частини рівнянь системи (14) приймають вигляд

{Ag( -) + Bg( -)+Cg; Aq(-) + Bq(-)+Cq; z- -Ck (15)

-Cl; -Cw; -+Ce },

g=1,2,...m1; k= m1+1, ...,m2, l= m2+1,..., m3, w= m3 +1,..., m4, e= m4 +1,...,2n+1.

В загальному випадку точка Х0 є виродженою і належить більш ніж одній області Dg_s_linear, що визначається системою нерівностей порядку n(n-1)/2 +4n +(К-1)n

G(f const)X+C(f const) 0, (16)

де ліві частини рівнянь системи (16) мають вигляд (15).

Метою розв'язання задачі (10-11) є знаходження одного локального мі-німуму, тому обираються певна підобласть Dg_s_linearDlinear, яка містить Х0 і визначається системою (16), певна система рівнянь (14), що задає Х0, і здійс-нюється занурення у простір всіх змінних R3n+1, у якому розглядається задача

визначити (X*,f*) = arg min z ,

Ds_nonlinearD R3n+1

де множина Dnonlinear, задається системою обмежень вигляду

, (17)

де система G(f)X-C(f) 0 породжується системою (16),

система містить n(n-1)+8n+2(К-1)n нерівностей вигляду (6).

Розглядається також підобласть Dequation межі області D, що задається сис-темою обмежень порядку (2n+1), .... (3n) вигляду

(18)

де система F(f)Х+ C(f)=0 породжується системою (14).

Загальна схема метода локальної оптимізації задачі (10-11) є ітераційним процесом, k-а ітерація якого полягає в сукупності таких дій:

1. У околі певної початкової точки (Xk, fk) розв’язати задачу:

знайти (Xk*, fk*) = arg min z , (19)

(X, f) Ds_nonlinear

де підобласть Ds_nonlinear описується системою вигляду (17).

2. Перевірити умову

(Xk*, fk*) = arg min z , (20)

(Xk*, fk*)Dg_nonlinear =1,2,...,.

Якщо умова (20) виконана, точка (Xk*, fk*)