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

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

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

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

УДК 519.859

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

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

Автореферат

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

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

Харків - 2006

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

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

Науковий консультант

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Провідна установа

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

Захист відбудеться " 2 " листопада 2006 р. о 14 годині на засіданні

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

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

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

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

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

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

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

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

АНОТАЦІЯ

Гребеннік І.В. Математичні моделі та методи комбінаторної оптимізації в геометричному проектуванні. - Рукопис.

Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 01.05.02 - математичне моделювання та обчислювальні методи. - Інститут проблем машинобудування ім. А.М. Підгорного НАН України, Харків, 2006.

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

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

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

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

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

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

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

АННОТАЦИЯ

Гребенник И.В. Математические модели и методы комбинаторной оптимизации в геометрическом проектировании. - Рукопись.

Диссертация на соискание ученой степени доктора технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Институт проблем машиностроения им. А.Н. Подгорного НАН Украины, Харьков, 2006.

Диссертация посвящена построению математических моделей и разработке методов решения комбинаторных оптимизационных задач геометрического проектирования.

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

Построены описания классов композиционных образов комбинаторных множеств. Проведено их отображение в евклидово пространство. Исследованы свойства образов построенных комбинаторных множеств в евклидовом пространстве.

Дана классификация задач комбинаторной оптимизации в евклидовом пространстве, которая является развитием известных ранее классификаций.

На множестве элементов композиционных образов комбинаторных множеств задано отношение линейного порядка. На основе заданного отношения предложен общий подход к оптимизации линейных функций и норм разности без дополнительных ограничений на композиционных образах комбинаторных множеств. Получены решения указанных задач на классах композиционных образов комбинаторных множеств.

На основе известного подхода исследованы экстремальные свойства и получены оценки минимума выпуклых и сильно выпуклых продолжений функций на основных классах композиционных образов комбинаторных множеств. Получил дальнейшее развитие метод оптимизации оценок минимума выпуклых и сильно выпуклых функций на евклидовых комбинаторных множествах.

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

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

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

Построены различные виды отображений интервальных комбинаторных множеств в евклидово пространство для перехода от задачи оптимизации на интервальном комбинаторном множестве к эквивалентной задаче оптимизации в евклидовом пространстве.

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

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

Предложен приближенный метод решения задач евклидовой комбинаторной оптимизации с линейной целевой функцией и линейными ограничениями на основе случайного поиска. Осуществлена локализация точек минимума для класса задач оптимизации с булевыми переменными.

Решены базовые задачи оптимизации квазилинейных функций в интервальном пространстве без дополнительных ограничений на классах интервальных комбинаторных множеств.

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

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

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

ABSTRACT

Grebennik I.V. Mathematical models and methods of combinatorial optimization in geometric design. - Manuscript.

A Thesis for a Doctor of Technical Sciences degree in the speciality 01.05.02 - mathematical modeling and computational methods. - A. M. Pidgorny Institute of Problems in Machinery of the National Academy of Sciences of Ukraine, Kharkiv, 2006.

The thesis is devoted to construction of mathematical models and development of solution methods for the combinatorial optimization problems of geometric design.

New combinatorial sets being composition k-images of combinatorial sets are introduced. Means for description and a classification of such sets are offered. On the set of elements of the composition images of combinatorial sets the linear order relationship is assigned. An approach to linear function optimization on the composition images of combinatorial sets is proposed. The extreme properties and estimations of minimum of convex functions on the classes of the composition images of combinatorial sets are investigated.

A mathematical model of the basic geometric design problem is constructed in an interval form. The classification of optimization problems on interval combinatorial sets is constructed.

A method for the combinatorial optimization problems with a linear objective function and linear constraints, based on covering feasible region is proposed.

The basic optimization problems on interval combinatorial sets classes are solved. A solution method of the interval combinatorial optimization problems with quasilinear constraints, which based on transformation of ones to the combinatorial optimization problems in the Euclidean space is proposed. A solution method of the interval combinatorial optimization problems as two-criterion optimization problems in the Euclidean space is developed.

The results are used to solve of problems of packing, placement, design, team planning and educational process.

Key words: combinatorial set, combinatorial optimization, geometric design, optimization placement problems, geometric information, -function, interval analysis.

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

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

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

Задачі геометричного проектування полягають у пошуку оптимального розміщення множини геометричних об'єктів відносно області розміщення з урахуванням технологічних обмежень згідно з критеріями якості розміщення. До класу задач геометричного проектування належать задачі компонування обладнання, керування складними технічними системами, побудови генеральних планів промислових підприємств, конструювання електронних пристроїв, оптимального розкрою промислових матеріалів, теорії розкладів та керування проектами, задачі покриття. Результати досліджень в цьому напрямі наведено в роботах Л.В. Канторовича, В.Л. Рвачова, Ю.Г. Стояна, В.А. Залгаллера, С.В. Яковлева, Е.О. Мухачової, М.І. Гіля, В.М. Комяк, 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) викладемо на прикладі множини переставлень кортежів.

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

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

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

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

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

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

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

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

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