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

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

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

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

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

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

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

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

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

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

Ообраз інтервальної комбінаторної множини в просторі при відображенні, введеному в розд. 4.

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

Запропоновано метод розв'язання інтервальної задачі оптимізації з квазілінійними обмеженнями на - множині в такій постановці:

Інтервальна функція цілі, - інтервальна комбінаторна множина, породжена множиною.

Через складність розглядуваного класу задач геометричного проектування система обмежень (30), як правило, містить велику кількість нерівностей. Тому застосування методів класичного інтервального аналізу для розв'язання задачі (29)-(31) не є можливим. З метою розв'язання поставленої задачі в роботі здійснено перехід від інтервальної моделі (29)-(31) до математичної моделі задачі в евклідовому просторі. Математичну модель задачі (29)-(31) подано в за допомогою відображення виду (22):

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

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

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

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

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

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

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

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

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

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

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

ВИСНОВКИ

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

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

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

- поява нових складних задач геометричного проектування потребує подальших досліджень евклідових комбінаторних множин;

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

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

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

3. Введено нові класи задач комбінаторної оптимізації в евклідовому просторі.

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

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

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

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

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

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

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

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Голуб В.И., Гребенник И.В., Кузьменко В.М. Комбинаторный подход к построению технологических штриховых кодов минимальной длины // Радиоэлектроника и информатика. - 1998.- № 3.- С. 66 - 71.

2. Гребенник И.В. Решение некоторых задач условной оптимизации линейных функций на перестановочном многограннике // Радиоэлектроника и информатика. - 1999.- № 1.- С.55 - 59.

3. Голуб В.И., Гребенник И.В., Кузьменко В.М. Математическая модель многофакторного оценивания и выбора варианта технологического штрихового кода // Радиоэлектроника и информатика. - 1999.- № 2.- С. 71 - 73.

4. Гребенник И.В. Оценки минимума выпуклых функций с ограниченным множеством точек экстремума на евклидовых комбинаторных множествах // Радиоэлектроника и информатика. - 2001.- № 2.- С. 111 - 114.

5. Гребенник И.В. Декомпозиция множества допустимых решений и экстремальные свойства целевых функций в задачах оптимизации с булевыми переменными // Радиоэлектроника и информатика. - 2001.- № 3.- С. 93 - 99.

6. Гребенник И.В., Лапко Д.А. Исследование оценок минимума выпуклых продолжений функций, заданных на евклидовых комбинаторных множествах // Радиоэлектроника и информатика. - 2002.- № 1.- С. 109 - 113.

7. Гребенник И.В., Романова Т.Е. Учет погрешностей при построении математических моделей оптимизационных комбинаторных задач // Автоматизированные системы управления и приборы автоматики. - 2002. Вып. 119.- С. 64 - 69.

8. Гребенник И.В., Романова Т.Е. Отображение интервальных комбинаторных множеств в евклидово пространство // Пробл. машиностроения.- 2002.- т.5.- № 2.- С. 87-91.

9. Гребенник И.В., Романова Т.Е. Интервальная гиперплоскость в пространстве // Пробл. машиностроения.- 2002.- т.5.- № 3.- С. 52-56.

10. Гребенник И.В., Евсеева Л.Г., Романова Т.Е. Интервальное выпуклое множество в пространстве //Системи обробки інформації.- 2002.- Вып. 4 (20).- С. 255 - 261.

11. Гребенник И.В. Локализация точек минимума в некоторых экстремальных задачах с булевыми переменными // Радиоэлектроника и информатика. - 2002.- № 4.- С. 99 - 103.

12. Гребенник И.В., Лапко Д.А. Решение задач оптимизации линейных функций с линейными ограничениями на множестве перестановок, отображенном в // Радиоэлектроника и информатика. - 2003.- № 1.- С. 116 - 119.

13. Гребенник И.В., Романова Т.Е., Шеховцов С.Б. Синтез критерия оптимизации в задачах геометрического проектирования с учетом погрешностей исходных данных // Пробл. машиностроения. - 2003.- т.6.- № 3.- С. 69-78.

14. Гребенник И.В., Романова Т.Е., Шеховцов С.Б. Параметрический анализ некоторых оптимизационных задач геометрического проектирования // Искусств. интеллект. - 2003, № 3.- С. 329-337.

15. Гребенник И.В., Лапко Д.А. Оценки минимума функций в задачах условной оптимизации на евклидовых комбинаторных множествах // Радиоэлектроника и информатика. - 2003.- № 4.- С. 61 - 64.

16. Гребенник И.В., Хабаров А.Ю. Модель задачи эффективного планирования работ на заданный период // Автоматизированные системы управления и приборы автоматики. - 2003.- Вып. 123.- С. 44 - 53.

17. Гребенник И.В. Интервальные модели комбинаторной оптимизации квазилинейных функций в пространстве // Доповіді НАН України. - 2004. - № 9. - С. 60-64.

18. Гребенник И.В., Романова Т.Е., Шеховцов С.Б. Задачи комбинаторной оптимизации с квазилинейными ограничениями в интервальном пространстве // Пробл. машиностроения.- 2004.- т.7.- № 1.- С. 82-86.

19. Гребенник И.В., Евсеева Л.Г., Романова Т.Е. Интервальная прямая в пространстве // Радиоэлектроника и информатика.-2004.- № 2.- С. 57 - 63.

20. Гребенник И.В., Романова Т.Е., Шеховцов С.Б. Классы интервальных комбинаторных оптимизационных задач геометрического проектирования // Искусств. интеллект. - 2004. - № 4.- С. 321-327.

21. Гребенник И.В., Евсеева Л.Г., Романова Т.Е. Основная оптимизационная задача геометрического проектирования в интервальном виде // Радиоэлектроника. Информатика. Управление. - 2004. - № 2.- С. 68-72.

22. Гребенник И.В. Модели оптимизации на композиционных образах комбинаторных множеств в системах поддержки принятия решений // Бионика интеллекта. - 2004.- Вып.1(61).- С. 90 - 97.

23. Гребенник И.В. Свойства классов композиционных образов комбинаторных множеств, отображенных в евклидово пространство // Радиоэлектроника и информатика. - 2005. - № 1. - С. 66 - 70.

24. Гребенник И.В., Евсеева Л.Г., Романова Т.Е. Учет погрешностей при моделировании компоновки объектов с нелинейной границей в задачах синтеза технических систем // Пробл. машиностроения.- 2005.- т.8.- № 1.- С. 65-70.

25. Стоян Ю.Г., Гребенник И.В. Композиционные образы комбинаторных множеств и некоторые их свойства // Пробл. машиностроения.- 2005.- т.8.- № 3.- С. 56-62.

26. Гребенник И.В., Евсеева Л.Г., Романова Т.Е. Моделирование взаимодействий -мерных шаров в интервальных пространствах // Радиотехника: Всеукр. межвед. научно-техн. сб. 2005.- Вып. 140.- С. 167-171.

27. Гребенник И.В. Экстремальные свойства функций на композиционных образах комбинаторных множеств // Радиоэлектроника и информатика. - 2005.- № 2.- С. 36 - 44.

28. Гребенник И.В., Петров К.Э., Колесник Л.В. Ранжирование альтернативных решений на основе интервальной информации о важности их характеристик // Вестник Херсонского национального технического университета. - 2005.- №1(21).- С. 42 - 47.

29. Голуб В.И., Гребенник И.В., Кузьменко В.М. Оптимизация структуры штрихкодового идентификатора почтового отправления // Зв'язок. - 2005.- № 1.- С. 25 - 27.

30. Гребенник И.В., Романова Т.Е., Шеховцов С.Б., Яськов Г.Н. Упаковка шаров различных радиусов в параллелепипеде с учетом погрешностей // Искусств. интеллект. - 2005. - № 4. - C. 119-129.

31. Гребенник И.В., Чугай А.М. Оптимизационная задача размещения цилиндров и параллелепипедов в призме с учетом кратчайших расстояний и зон запрета // Збірник наукових праць Харківського університету повітряних сил. - 2005.- №6 (6).- С. 41 - 49.

32. Гребенник И.В. Классы композиционных образов комбинаторных множеств в математических моделях задач геометрического проектирования // Радиоэлектроника и информатика. - 2005.- № 3.- С. 69 - 73.

33. Гребенник И.В. Комбинаторное множество перестановок кортежей и его свойства // Радиоэлектроника. Информатика. Управление. - 2005. - № 1. - С. 92-98.

34. Гребенник И.В., Захаров Л.П. Оптимизация топологии штриховых шкал преобразователей перемещения // Труды 2-й Междунар. конф. "Теория и техника передачи, приема и обработки информации".- Харьков-Туапсе. - 1996.- С. 135-136.

35. Гребенник И.В. Об одном подходе к декомпозиции задач оптимизации с булевыми переменными // Труды 3-й Междунар. конф. "Теория и техника передачи, приема и обработки информации".- Харьков-Туапсе. - 1997.- С. 290.

36. Гребенник И.В., Кузьменко В.М. Построение технологических штриховых кодов на основе комбинаторного подхода // Труды 4-й Междунар. конф. "Теория и техника передачи, приема и обработки информации".- Харьков-Туапсе. - 1998.- С. 302-303.

37. Гребенник И.В. Оценки минимума линейных функций в задачах условной оптимизации на множестве перестановок // Труды 5-й Междунар. конф. "Контроль і управління в складних системах”. - Вінниця. - 1999. - С. 147-153.

38. Гребенник И.В. Оптимизация линейной функции на перестановочном многограннике с линейными ограничениями // Труды 6-й Междунар. конф. “Теория и техника передачи, приема и обработки информации”.-Харьков.-2000.- С. 257-259.

39. Гребенник И.В. Оптимизация линейной функции с линейными ограничениями на множестве перестановок, отображенном в // Труды межвузовской научно-методич. конф. “Экспертные оценки элементов учебного процесса”.- Харьков: Народная украинская академия.- 2000.- С. 68-70.

40. Гребенник И.В., Романова Т.Е., Шеховцов С.Б. Параметрический анализ некоторых экстремальных задач геометрического проектирования для учета погрешностей исходных данных // Труды Междунар. научно-технич. конф. “Интеллектуальные многопроцессорные системы 2003”. - Т.1. - Таганрог - Донецк. - 2003. - С. 96-98.

41. Гребенник И.В., Романова Т.Е., Шеховцов С.Б. Классы интервальных комбинаторных задач геометрического проектирования // Труды Междунар. научно-технич. конф. “Искусственный интеллект. Интеллектуальные многопроцессорные системы”. - Т.1. - Таганрог - Донецк. - 2004. - С. 157-159.

42. Стоян Ю.Г., Гребенник И.В. Специальные классы комбинаторных множеств в геометрическом проектировании // Труды 10-й Юбилейной междунар. конф. "Теория и техника передачи, приема и обработки информации". - Харьков-Туапсе - 2004. - С. 253-254.

43. Гребенник И.В., Евсеева Л.Г., Романова Т.Е. Аналитическое описание отношений интервальных геометрических объектов // Труды 10-й Юбилейной междунар. конф. "Теория и техника передачи, приема и обработки информации". - Харьков-Туапсе - 2004. - С. 34-35.

44. Стоян Ю.Г., Гребенник И.В. Классификация композиционных образов комбинаторных множеств в математических моделях задач геометрического проектирования // 2-й Междунар. радиоэлектронный форум “Прикладная радиоэлектроника. Состояние и перспективы развития” МРФ_2005: Сб. науч. тр. Т. 3. Междунар. конф. “Информационные системы и технологии” - Харьков: АН ПРЭ, ХНУРЭ, 2005. - С.161 - 164.

45. Гребенник И.В., Романова Т.Е., Шеховцов С.Б., Яськов Г.Н. Упаковка шаров в параллелепипеде с учетом погрешностей // Труды Междунар. научно-технич. конф. “Интеллектуальные и многопроцессорные системы”. - Таганрог - Донецк - Минск - 2005. - С. 180 -181.

АНОТАЦІЯ

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

Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 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.

Размещено на Allbest.ru