Математичні моделі та методи комбінаторної оптимізації в геометричному проектуванні

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

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

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

Гребеннік Ігор Валерійович

УДК 519.859

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

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

Автореферат

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

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

Харків - 2006

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

Робота виконана в Харківському національному університеті радіоелектроніки, Міністерство освіти і науки України.

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

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

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

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

Офіційні опоненти:

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

Наконечний Олександр Григорович,

Київський національний університет ім. Тараса Шевченка, завідувач кафедри

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

Перепелиця Віталій Опанасович,

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

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

Комяк Валентина Михайлівна,

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

Провідна установа - Інститут кібернетики ім. В.М. Глушкова НАН України, відділ математичних систем моделювання проблем екології та енергетики, м. Київ

Вчений секретар спеціалізованої

вченої ради Д 64.180.01

доктор технічних наук О.О.Стрельнікова

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

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

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

Задачі геометричного проектування полягають у пошуку оптимального розміщення множини геометричних об'єктів відносно області розміщення з урахуванням технологічних обмежень згідно з критеріями якості розміщення. До класу задач геометричного проектування належать задачі компонування обладнання, керування складними технічними системами, побудови генеральних планів промислових підприємств, конструювання електронних пристроїв, оптимального розкрою промислових матеріалів, теорії розкладів та керування проектами, задачі покриття. Результати досліджень в цьому напрямі наведено в роботах Л.В. Канторовича, В.Л. Рвачова, Ю.Г. Стояна, В.А. Залгаллера, С.В. Яковлева, Е.О. Мухачової, М.І. Гіля, В.М. Комяк, J. Terno, G. Scheithauer, V. Milenkovich, J. Ferreira, J. Oliverra та ін.

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

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

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

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

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

Розвиток теорії геометричного проектування пов'язаний з появою нових наукових та прикладних задач. Внаслідок цього виникає необхідність розробки нових комбінаторних оптимізаційних моделей, як ідеалізованих, так і інтервальних. Ефективним засобом побудови математичних моделей задач цього класу є комбінаторні множини. Комбінаторні властивості нових задач є такими, що класичні комбінаторні множини не завжди дозволяють адекватно описувати відповідні математичні моделі задач геометричного проектування. Отже, необхідно вводити нові комбінаторні множини як засоби побудови математичних моделей задач геометричного проектування. При цьому властивості комбінаторних множин мають бути використані при розробці нових та реалізації відомих методів оптимізації. Класичні підходи до формалізації визначення комбінаторних множин належать до перелічувальної комбінаторики та пов'язані з конфігураціями К.Бержа (C. Berge) та теорією перерахування Дж. Пойа (G. Polya). Однак застосування вказаних підходів при математичному моделюванні задач геометричного проектування найчастіше призводить до громіздких результатів.

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційну роботу виконано в період з 1993 р. по 2006 р. на кафедрі системотехніки Харківського національного університету радіоелектроніки згідно з планами науково-дослідних робіт за програмами: за темою № 134 „Розробка інформаційно-аналітичної системи з розподіленим штучним інтелектом „Університет”” (№ ДР 0101U001763); за темою № 165 „Розробка теоретичних основ проектування систем підтримки прийняття рішень при управлінні соціально-економічним розвитком регіону”, розділ 6 „Розробка спеціалізованих моделей в системах підтримки прийняття рішень з дискретними параметрами в умовах невизначеності для застосування в задачах геометричного проектування та управління” (№ ДР 0103U001564); за темою № 196 “Розробка методів і інструментальних засобів структурно-параметричної ідентифікації моделей багатофакторного оцінювання і багатокритеріальної оптимізації”, розділ 4 “Розробка методології математичного моделювання комбінаторних оптимізаційних задач геометричного проектування в умовах невизначеності параметрів” (№ ДР 0106U003175). Автор брав участь у виконанні робіт за темою № 134 як виконавець, за темами № 165 та № 196 як науковий керівник розділу. В рамках виконаних робіт автором побудовано математичні моделі та розроблено методи розв'язання комбінаторних задач прийняття рішень в умовах невизначеності при інтервально заданих параметрах для систем підтримки прийняття рішень в задачах геометричного проектування.

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

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

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

2. Дослідити властивості образів виділених класів комбінаторних множин в евклідовому та інтервальному просторах.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

13. Вперше запропоновано метод розв'язання інтервальних задач комбінаторної оптимізації з квазілінійними обмеженнями у n-вимірному інтервальному просторі з подальшим зведенням до відомих класів задач комбінаторної оптимізації в евклідовому просторі.

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

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

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

Моделі, методи та алгоритми, запропоновані в дисертаційній роботі, впроваджено в держбюджетні науково-дослідні роботи (акт від 05.12.2005 р.) та в навчальний процес Харківського національного університету радіоелектроніки (акт від 09.11.2005 р.). Розроблені засоби математичного моделювання та розв'язання комбінаторних оптимізаційних задач геометричного проектування використано при розв'язанні задач ефективного планування робіт в комплексі програм проектування, експлуатації та розвитку мереж електрозв'язку у ВАТ „Укртелеком” (м. Київ) (акт від 10.09.2004 р.); на державному підприємстві „Укрпошта” (м. Київ) при розробці елементів системи автоматичної ідентифікації поштових відправлень (акт від 11.08.2005 р.); на державному науково-виробничому підприємстві „Меридіан” при розв'язанні задач компонування приладів та спеціального технологічного устаткування (акт від 10.12.2005 р.); при розробці комплексів бурового обладнання, при компонуванні геофізичних пристроїв орієнтування бурового інструменту у ВАТ завод „Потенціал” (акт від 08.11.2005 р.).

Особистий внесок здобувача. Всі наукові результати дисертаційної роботи одержані автором особисто. В роботах, що виконані в співавторстві, здобувачу належить таке: [1], [36] - побудова комбінаторної математичної моделі розробки символіки штрихового коду з урахуванням заданих вимог; [3] - розробка математичної моделі багатокритеріального оцінювання символіки штрихового коду; [6] - розробка підходу до оптимізації оцінок мінімуму опуклих та сильно опуклих функцій на евклідових комбінаторних множинах, доведення теореми про сильну опуклість функції; [7] - визначення поняття мінімуму з множини елементів інтервального простору, теорема про строгий мінімум лінійної функції на множині переставлень, опис множини інтервальних переставлень за допомогою множини підстановок; [8] - дослідження властивостей відображень множини інтервальних переставлень в евклідів простір; [9] - визначення поняття інтервальної гіперплощини в просторі, доведення необхідної та достатньої умови можливості проведення гіперплощини через n точок простору; [10] - доведення теореми про опуклість множини в просторі, введення понять інтервальної опуклої оболонки, інтервального симплексу та інтервального багатогранника в просторі; [12] - розробка та обґрунтування методу розв'язання задач оптимізації лінійних функцій з лінійними обмеженнями на множині переставлень на основі покриття області припустимих розв'язків; [13] -обґрунтування вигляду критерію та процедури оптимізації при переході від інтервальної моделі задачі оптимізації в просторі до еквівалентної двокритеріальної задачі оптимізації в евклідовому просторі; [14], [40] - визначення відношення переваги на множині елементів інтервального простору, формування схеми параметричного аналізу класу оптимізаційних задач геометричного проектування; [15] - розробка та обґрунтування способу обчислення оцінок мінімуму в задачах оптимізації опуклих функцій з лінійними обмеженнями на евклідових комбінаторних множинах; [16] - побудова та дослідження математичної моделі задачі планування робіт на заданий період; [18] - розробка та обґрунтування способів переходу від інтервальних оптимізаційних моделей з квазілінійними обмеженнями до задач евклідової комбінаторної оптимізації з лінійними обмеженнями; [19] - визначення поняття квазілінійної інтервальної поверхні та квазілінійного інтервального рівняння в просторі; [20], [41] - виконання класифікації комбінаторних оптимізаційних задач геометричного проектування в n-вимірному інтервальному просторі, визначення поняття інтервально опуклої функції; [21] - побудова математичної моделі основної оптимізаційної інтервальної задачі геометричного проектування, визначення поняття основної комбінаторної інтервальної задачі геометричного проектування; [24] - визначення поняття -околу точки в тривимірному інтервальному просторі та інтервальної кулі в тривимірному інтервальному просторі з евклідовою метрикою; [25], [42] - введення поняття, формування конструктивних засобів опису та дослідження властивостей композиційних образів комбінаторних множин; [26] - визначення поняття -околу точки в просторі, побудова інтервальної -функції пари куль в інтервальному просторі; [28] - побудова багатофакторної оцінки альтернатив при інтервально заданих коефіцієнтах важливості критеріїв; [29] -аналіз дискретних параметрів структури штрихкодового ідентифікатора для застосування в поштовому зв'язку; [30], [45] - побудова інтервальної математичної моделі задачі упакування куль в паралелепіпеді; [31] - модифікація методу околів, що звужуються, на основі властивостей комбінаторної множини переставлень кортежів для розв'язання задачі розміщення циліндрів та паралелепіпедів у призмі з урахуванням найкоротших відстаней та зон заборони; [34] - побудова математичної моделі задачі вибору оптимальної структури штрихових шкал перетворювачів переміщення; [43] - формалізація відношень покриття інтервальних геометричних об'єктів в заданій інтервальній області; [44] - виділення класів композиційних образів комбінаторних множин в математичних моделях задач геометричного проектування.

Апробація результатів дисертації. Основні результати роботи доповідалися та одержали схвалення на міжнародних конференціях та наукових семінарах: на Міжнародній конференції „Теорія і техніка передачі, прийому та обробки інформації” (Харків - Туапсе, 1996-1998, 2000, 2004 рр.), Міжнародній конференції "Контроль і управління в складних системах” (Вінниця, 1999 р.), Міжвузівській науково-методичній конференції „Експертні оцінки елементів навчального процесу” (Харків, Народна українська академія, 2000 р.), Міжнародній науково-технічній конференції „Інтелектуальні багатопроцесорні системи 2003” (Таганрог - Донецьк, 2003 р.), Міжнародній науково-технічній конференції „Штучний інтелект. Інтелектуальні багатопроцесорні системи” (Таганрог - Донецьк, 2004 р.), Міжнародній науково-технічній конференції „Інтелектуальні та багатопроцесорні системи” (Таганрог - Донецьк - Мінськ, 2005 р.), 2 Міжнародному радіоелектронному форумі “Прикладна радіоелектроніка. Стан та перспективи розвитку” МРФ_2005 (Харків: АН ПРЕ, ХНУРЕ, 2005 р.), на семінарах “Математичні методи геометричного проектування” при науковій раді з проблеми “Кібернетика” НАН України (Харків, 1993-2005 рр.), на семінарах “Системний аналіз, математичне моделювання та прийняття рішень в соціально-економічних та технічних системах” при науковій раді з проблеми “Кібернетика” НАН України (Харків, 1996-2005 рр.), на семінарах відділу математичного моделювання та оптимального проектування Інституту проблем машинобудування ім. А.М. Підгорного НАН України (Харків, 1993-2005 рр.), на семінарі кафедри обчислювальної математики Київського національного університету ім. Тараса Шевченка (Київ, 2006 р., керівник - чл.-кор. НАНУ, д.ф.-м. н., проф. Ляшко С.І.).

Публікації. За темою дисертації опубліковано 45 наукових праць, в тому числі: 33 статті в наукових журналах та збірниках наукових праць, які входять до переліку ВАК України, 12 доповідей та тез, опублікованих в матеріалах наукових конференцій.

Структура та обсяг дисертації. Дисертація містить вступ, шість розділів, висновки по роботі, 3 додатки (оформлених у вигляді окремої книги на 105 с.), 7 рисунків, 28 таблиць та список використаних джерел з 378 найменувань на 36 сторінках. Повний обсяг дисертації без додатків складає 321 с., з них 285 с. основного тексту.

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

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

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

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

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

3. Евклідові комбінаторні множини (-множини), досліджені в роботах Ю.Г.Стояна, С.В.Яковлева, О.О.Ємця та їх учнів, є ефективним засобом моделювання ідеалізованих комбінаторних задач геометричного проектування. Основою для дослідження властивостей евклідових комбінаторних множин, постановки й розв'язання задач евклідової комбінаторної оптимізації є відображення (занурення) комбінаторних множин в евклідів простір, опис та дослідження властивостей образів, побудова відповідних комбінаторних багатогранників. Однак поява нових все більш складних задач геометричного проектування потребує подальших досліджень евклідових комбінаторних множин. Ці дослідження мають включати як запровадження, класифікацію та вивчення нових класів евклідових комбінаторних множин, так і подальше вивчення властивостей існуючих евклідових комбінаторних множин.

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

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

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

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

На основі наведених висновків сформульовано постановку задачі досліджень:

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

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

, (1)

, (2)

де - комбінаторна множина, , - інтервальний простір.

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

З метою розробки конструктивних засобів опису нових комбінаторних множин введено поняття композиційного - образу комбінаторних множин.

Визначення 1. Комбінаторна множина називається композиційним - образом комбінаторних множин, породженим множинами, якщо

, (3)

Де - комбінаторна множина, породжена множиною, - множина всіх підмножин множини,

Множина називається множиною нульового рівня, множини - множинами -го рівня. Позначимо.

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

Як комбінаторні множини, можуть виступати переставлення, розміщення, сполучення з повтореннями й без повторень та інші відомі комбінаторні множини. Ці множини назвемо базовими комбінаторними множинами, а відповідні відображення - базовими відображеннями.

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

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

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

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

1. Композиційний образ комбінаторних множин, породжений множинами, який позначено відповідно, и. Побудовані комбінаторні множини названо: - множиною парних переставлень, - множиною парних розміщень, - множиною парних сполучень з повтореннями.

2. Композиційний образ комбінаторних множин, породжений множинами. Тут- кортеж, складений з елементів множини. При цьому серед множин є різними. Цей композиційний образ комбінаторних множин позначено через і названо множиною переставлень кортежів.

3. Композиційний образ комбінаторних множин, породжений множинами, одержав назву композиції переставлень та позначений через.

Нехай - композиційний образ комбінаторних множин. Здійснено відображення множини в арифметичний евклідів простір. Тут - кількість елементів, які складають впорядкований набір. Відповідно до робіт Ю.Г. Стояна зазначене відображення (називане зануренням) задано у вигляді

, , (4)

, , .

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

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

Математичну модель ідеалізованої оптимізаційної задачі геометричного проектування вигляду (1)-(2) подано таким чином:

, (5)

, (6)

де - функціонал, заданий на підмножині композиційного образу комбінаторних множин.

Здійснено занурення множини в простір вигляду (4). Сформульовано задачу комбінаторної оптимізації в арифметичному евклідовому просторі, еквівалентну задачі (5)-(6)

, (7)

, (8)

Для розв'язання задачі (7)-(8) необхідно розробити (обрати) метод розв'язання згідно з класом цільової функції та області припустимих розв'язків. Для цього в роботі дано класифікацію задач комбінаторної оптимізації вигляду (7)-(8).

Виконано дослідження переходу від задачі оптимізації (7) - (8) до еквівалентної задачі оптимізації з опуклою (сильно опуклою) на опуклій замкненій множині цільовою функцією. Тут еквівалентність двох задач оптимізації на множині розуміється таким чином, що значення функції цілі вихідної задачі та опуклої функції цілі еквівалентної задачі збігаються в точках множини. Для переходу до еквівалентної задачі використано методи побудови опуклих та сильно опуклих продовжень функцій, заданих на комбінаторних множинах, запропоновані в роботах проф. Яковлева С.В. Для розглянутих класів множин задачу оптимізації (7) - (8) перетворено до еквівалентної задачі з опуклою (сильно опуклою) цільовою функцією. Ця задача оптимізації називається опуклою - задачею.

Досліджено випадок, коли в задачі (7) - (8) функція лінійна та виконується умова, а як множина виступають різні композиційні образи комбінаторних множин, відображені в

, (9)

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

В роботі введені відношення порядку для базових комбінаторних множин. Ідею задання відношення порядку та його застосування при розв'язанні задачі (9) викладемо на прикладі множини переставлень кортежів.

Координати точок множини набувають значень всіх можливих переставлень кортежів. На множині кортежів, введено таке бінарне відношення:

Показано, що відношення (11) є відношенням лінійного порядку. Кортежі, , можна впорядкувати згідно з відношенням.

Теорема 1. Мінімум лінійної функції задачі (10) на множині, породженій множинами, досягається в точці, де, при а послідовність задовольняє (12).

На основі теореми 1 розв'язано задачі знаходження мінімуму норми різниці між довільною точкою простору та точками множини, визначення діаметру множини.

В ряді випадків опуклі задачі не містять додаткових обмежень на змінні. В роботах Ю.Г.Стояна, С.В.Яковлева, О.О.Ємця викладається загальний підхід до побудови та конкретні реалізації оцінок та достатніх умов мінімуму опуклих та сильно опуклих функцій на евклідових комбінаторних множинах. Наведемо співвідношення для оцінок мінімуму в загальному випадку. Нехай - опукла замкнена множина, де,. Тоді

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

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

Аналіз оцінок (13) - (15) дозволяє зробити такі висновки. Оцінки (13), (14) справедливі для довільної точки. Крім того, конструктивні методи побудови сильно опуклих продовжень на дозволяють отримати сильно опукле продовження з заданим значенням параметра. Тому співвідношення (14), (15) допускають вибір значення.

В розвиток підходу, описаного в роботах проф. Ємця О.О., розглянуто задачу оптимізації значень оцінок за цими параметрами. Задачу відшукання максимальних значень, можна розв'язати тільки після знаходження мінімумів в правих частинах співвідношень (13) - (15). Ці задачі вирішуються по-різному для різних множин. В роботі запропоновано та досліджено підхід до оптимізації оцінок вигляду (13) - (15) на прикладі множини.

Теорема 2. Для оцінки вигляду (15) при справедлива тотожність при всіх, де - параметр сильної опуклості функції, , - опукла замкнена множина, причому.

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

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

В роботі запропоновано та досліджено новий клас оцінок мінімуму опуклих функцій на евклідових комбінаторних множинах. Нехай функція має обмежену множину точок екстремуму на опуклій замкненій множині. Множину точок мінімуму на позначимо

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

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

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

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

В загальному випадку кортеж геометричної інформації про інтервальний об'єкт, де, - базовий інтервальний об'єкт, можна зобразити таким чином:

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

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

Сформульовано основну оптимізаційну інтервальну задачу геометричного проектування.

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

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

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

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

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

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

Введено композиційні - образи інтервальних комбінаторних множин.

Визначення 2. Композиційним - образом інтервальних комбінаторних множин називається множина вигляду (3), породжена множинами, які складені з елементів множин.

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

За аналогією з відображенням (4) здійснюється занурення множини у простір. Тут - кількість елементів, що складають один впорядкований набір.

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

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

З метою застосування відомих методів евклідової комбінаторної оптимізації здійснено відображення математичної моделі (20) - (21) в евклідів простір. Основну інтервальну задачу оптимізації на - множині вигляду (20) - (21) розглянуто для випадку.

Побудовано відображення, яке задає бієкцію між множиною та деякою множиною вигляду

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

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

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

...