Математичні моделі і методи розв’язання нелінійних задач розміщення геометричних об’єктів

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

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

Автореферат

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

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

Математичні моделі і методи розв'язання нелінійних задач розміщення геометричних об'єктів

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Незважаючи на те, що оптимізаційні задачі геометричного проектування належать до класу 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. Дістав подальший розвиток апарат формалізації умов розміщення об'єктів в ізотропних і анізотропних областях довільної просторової форми у R², оснований на понятті ?-функції пари об'єктів.

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

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

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

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/Western 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] - застосування поняття ?-функції до задач геометричного проектування, якщо об'єкти розміщення є ніде не щільними; [14] - постановка задачі дослідження, розробка принципових основ застосування методики неперервної оптимізації, а саме, стратегії активного набору, до комбінаторної задачі прямокутного розміщення; [17] - порівняння, аналіз обчислювальної складності і застосування алгоритмів, що розглядаються, до розв'язання задачі розміщення неорієнтованих багатокутників; [18] - застосування стратегії активного набору до обробки інформації про кінцеві вершини дерева розв'язків задачі прямокутного розміщення, алгоритмічна та програмна реалізація; [19] - моделювання задачі розміщення скінченої множини гіперпаралелепіпедів у гіперпаралелепіпеді, засіб розв'язання задачі; [20] - моделювання і дослідження конструктивних властивостей області припустимих розв'язків задачі розміщення орієнтованих багатокутників у смузі з дефектними зонами; [21, 30] - моделювання і дослідження області припустимих розв'язків задачі розміщення неорієнтованого багатогранника в багатогранній області; [22] - побудова методу розв'язання, аналіз множників Лагранжа з точки зору геометричних особливостей задачі прямокутного розміщення; [23, 27] - алгоритмічна і програмна реалізація методу розв'язання задачі, що розглядається; [25] - дослідження властивостей симетрії області припустимих розв'язків задачі прямокутного розміщення; [26] - моделювання задачі, що розглядається, як задачі оптимального розміщення багатокутників у смузі; [27, 28] - модифікація стратегії активного набору для розв'язання 2D задач геометричного проектування.

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

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

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

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

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

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

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

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

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

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

g = (s₁, s₂ ,...,s_q , m₁ ,...,m_i ,..., m_q , v₁ ,...,v_i ,...,v_q, v),

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

s₁, s₂ ,...,s_q -сукупність просторових форм компонент зв'язності межі S;

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

v₁ ,...,v_i ,...,v_q - параметри розміщення компонент зв'язності межі S;

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

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

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

У розділі аналізуються існуючі засоби визначення неопуклого багатокутного (багатогранного) j*--об'єкта. У просторі R² метричні характеристики m₁, m₂,...,m_q можуть бути зображені координатами вершин відповідних багатокутних контурів у власній системі координат, параметри розміщення мають вигляд v=(x,y,фj*-).

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

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

Початковою інформацією про неопуклий багатогранний геометричний об'єкт S є множина граней j*-={фj*-_r}, r=1,2,…,N, де j*-_r - r-а грань об'єкта S, що визначається послідовністю вершин (x_r¹, y_r¹, z_r¹),...,(x_r^g, y_r^g, z_r^g),..., (x_r^lr, y_r^lr, z_r^lr), - кількість вершин грані j*_r, N - кількість граней. Вектор параметрів розміщення об'єкта S має вигляд: {v} = (X,Y, Z, j*-,фy,фq).

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

визначити вектор u^* і відповідний йому образ S_u R^t, що індукується геометричною інформацією g(u^*)=P(g₀(u⁰),g₁(u¹),...,g_n(uⁿ)), при якому

u* =,(1)

деg_i=(s_i, m_i, v_i) - геометрична інформація, що індукує обмежені однозв'язні j*-багатокутники (j*-багатогранники) S_i, i=0,1,...n в R^t;

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

g(u)-геометрична інформація про точкову множину S_u=B(S₀, S₁,...S_n),

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

S_u=S₀(S_i)

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

g(u)=P(g₀(u⁰), g₁(u¹),..., g_n(uⁿ))=({S₀(S_i)}, {m₀, m₁ ...m_n}, {v₀ v₁...v_n}),

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

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

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

а) умовами розміщення об'єктів S_j в області S₀

S₀S_j= S_j або S_jS₀ або S^₀ S_j = , j=1,2,...n,(2)

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

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

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

int S_i int S_j= , i < j =1,2,...n.(3)

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

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

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

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

У роботі розглядається частинний випадок афінного перетворення подібності - гомотетія G геометричного об'єкта S_j відносно центра його власної системи координат (або, коли це зручно, відносно іншої точки площини R²): G(S) = S^*, що характеризується коефіцієнтом гомотетії K. Тоді S_j^* =KS_j(v_j).

Далі розглядається відношення включення (2), якщо над областю розміщення - багатокутником S₀ - припустима гомотетія G(S₀) = S₀^*, причому багатокутник S_j має задані метричні характеристики, а параметри розміщення області S₀ фіксовані. У даному випадку як область S₀, так і об'єкт розміщення S_j мають непорожню внутрішність і умова (2) задається j*_0j(x_j,y_j,K)-функцією

j*_0j (x_j,y_j,K )>0, якщо S_j(x_j,y_j) S^₀(K) = ,

j*_0j ( x_j,y_j,K) = 0, якщо S_j(x_j,y_j) S^₀(K) ,

int S_j(x_j,y_j) int S^₀(K) =,

j*_0j (x_j,y_j,K) < 0, якщо int S_j(x_j,y_j) int S^₀(K) ,

У роботі наведено побудову аналітичного опису j*_0j(x_j,y_j,K)-функції структурою лінійних нерівностей.

Центральне місце у розділі займає побудова структури нелінійних нерівностей, що описує область невід'ємності j*-функції для об'єктів, які мають кутовий параметр розміщення. У цьому випадку j*_ij(x_i,y_i,фj*_i,x_j,фj*x_j,_j)-функція як функція, що дозволяє задавати неперетин, дотик і перетин замкнених j*-об'єктів S_i(x_i,y_i,_iфj*) і S_j(,x_j,x_jфj*,_j) розглядається у просторі R⁶ параметрів розмі-щення (x_i, y_i,_i,фj* x_j, x_j,фj*_j).

Поверхня T_ij^lk 0-рівня j*_ij(x_i,y_i,_iфj*,x_j,x_j,фj*_j) -функції в R⁶ є нелінійною, кусково-диференційовною і складається з набору гладких поверхонь {T_ij^lфj*^k},_{1,2, Н}.

При побудові структури нелінійних нерівностей використовується визначення області невід'ємності -функції пари орієнтованих багатокутників (параметри f_i, f_j є фіксованими) структурою лінійних нерівностей. При цьому неопуклі багатокутники S_i(x_i,y_i) і S_j(x_i,y_i) зображуються у вигляді об'єднання опуклих замкнених багатокутників:

S_i = S_i^l і S_j = S_j^k (4)

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

Покладемо x_i^l=0, y_i^l=0. Для довільної пари (S_i^l, S_j^k) поверхня 0-рівня f_ij(0, 0,0,x_j^k,y_j^k,0)-функції є замкненою ламаною T² у просторі R² параметрів (x_j^k, y_j^k). Кожна сторона T_p² кривої T², p=1,2,...P, P (N_j^k + N_j^k), де N_i^l і N_j^k - кількість вершин об'єктів S_i^l і S_j^k відповідно, породжується одним з трьох можливих випадків дотику об'єктів (S_j^k, S_i^l):

Дотик першого типу: g-а сторона об'єкта S_i^l і q-а вершина об'єкта S_j^k;

Дотик другого типу: q-а сторона об'єкта S_j^k і g-а вершина об'єкта S_i^l;

Дотик третього типу: g-а сторона об'єкта S_i^l і q-а сторона об'єкта S_j^k.

Умова f_ij (x_i^l ,y_i^l, x_j^k ,y_j^k) 0 (умова взаємного неперетину об'єктів S_i^l і S_j^k) зображується структурою лінійних нерівностей вигляду

(5)

де нерівності набору F_lk (x_i^l ,y_i^l , x_j^k ,y_j^k) кількістю P мають вигляд

A_p(x_i^l - x_j^k ) + B_p(y_i^l - y_j^k ) + C_p 0, p=1,2,...P,

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

Тоді умова взаємного неперетину об'єктів S_i і S_j у R⁴ з урахуванням (5) визначається структурою лінійних нерівностей:

У просторі R⁶ всіх параметрів розміщення координати вершин об'єктів S_i^l і S_j^k є функціями параметрів f_i i f_j. Тому при розгляді поверхні T_ij^lk в R⁶ коефіцієнти A, B, C стають нелінійними функціями даних параметрів.

Отже, поверхня T_ij^lf^k R⁶ належить поверхні, яка визначається рівнянням f_ijf=0, причому у випадку першого типу сторони T_p² функція f_ijf приймає вигляд

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

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

Зауваження 2. Аналітичний опис T_ijf^lk містить також визначення можливих меж змінювання кутових параметрів f_i і f_j. Нехай f_i[0,2], тоді параметр f_j повинен задовольняти обмеження:

(6)

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

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

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

Зауваження 3. Об'єкти S_i^l і S_j^k у R² мають довільну взаємну орієнтацію, тому поверхні T_ij?^lk, ?=1,2,...H, можуть породжуватися довільною парою вигляду "вершина S_i^l - сторона S_j^k " або "вершина S_j^k - сторона S_i^l", тобто H= 2(N_i^l x N_j^k).

При цьому, виконання однієї з тернарних систем нерівностей вигляду (7) задає умову взаємного неперетину об'єктів S_i^l і S_j^k в R⁶.

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

що визначає умови взаємного неперетину об'єктів S_i^l і S_j^k, об'єднує H тернарних систем нерівностей, які містять нерівності вигляду (6-7).

Подальший розвиток апарат структур нелінійних нерівностей дістає для опису відношення включення (3), якщо об'єкт S₁(x₁,y₁,?₁) розміщується в області S₀ (x₀, y₀, f ₀, К) з урахуванням перетворення гомотетії над областю. Відношення (3) задається структурою нелінійних нерівностей вигляду

f _0j = f (F_0k (x₀,y₀,фf ₀,К,x_j,y_j,фf _j), f,3H). (8)

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

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

1. Граньфg_{r r} об'єкта S₀ - вершина s^p=(x^p, y^p, z^p) об'єкта S₁,

2. Грань g_{r r} oб'єкта S₁ - вершина s^k=(x^k, y^k, z^k) об'єкта S₀ .

Гладка частина T^l, l=1,2....H, поверхні T 0-рівня Ф-функції, що розглядається, визначається системою 4 обмежень вигляду { f^l=0; , , }, (9)

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

f^l=a^l x₁+ b^l y₁+ c^l z₁+ d^l (K)+ a^l x^p(₁) + b^l y^p(₁)+ c^l z^p(₁),

f^l=a^l (₁)x₁+ b^l(₁) y₁+ c^l (₁)z₁+ d^l - K( a^l(₁) x^k + b^l (₁)y^k+ c^l(₁) z^k),

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

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

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

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

Отже, в кожній точці області S₀ напрям s_object найменшої тягучості об'єкта S_i, що розміщується, повинен збігатися з напрямом анізотропії s_point області розміщення, що означає зміну орієнтації власної системи координат X_iО_iY_i об'єкта в залежності від координати ? його полюса.

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

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

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

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

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

...