Задачі евклідової комбінаторної оптимізації на поліпереставленнях та методи їх розв’язування - Автореферат

Цей напрямок дослідження дозволив отримати нові класи моделей дискретних задач геометричного проектування та ефективні методи їх розвязання. При цьому такі дослідження базуються з одного боку на властивостях самих евклідових комбінаторних множин, а з іншого - на властивостях функцій, що задані на цих множинах. Для досягнення поставленої мети були сформульовані наступні задачі: 1) Розробка нових математичних моделей комбінаторних задач геометричного проектування та дослідження їх властивостей. вперше запропоновано комбінований метод розвязування задач оптимізації лінійних функцій з лінійними обмеженнями на евклідовій множині поліпереставлень, що дозволяє отримати точний розвязок таких задач; отримала подальший розвиток математична модель комбінаторної оптимізаційної задачі кольорового упакування в досить довгій смузі із зонами заборони з урахуванням похибок початкових даних, що дає можливість враховувати поліпереставні властивості допустимої області та похибки метричних характеристик і застосововувати відомі оптимізаційні методи розвязування цієї задачі;У першому розділі наведено необхідні поняття, означення та теореми, щодо властивостей загальної множини поліпереставлень, інтервального аналізу, опуклих та дробово-лінійних функцій та повязаних з ними оптимізаційних задач. Розглянемо поліпереставну множину, яка є евклідовою комбінаторною множиною. Тоді відображення називають зануренням в арифметичний евклідів простір, якщо ставить множину у взаємно однозначну відповідність множині . Якщо, розвязавши задачу (4), (6) і отримавши мінімаль, маємо виконання умови (5) для неї, то задача (4)-(6) розвязана. У третьому розділі розглядається задача про визначення порядку обслуговування замовлень для максимізації рентабельності системи обслуговування, для якої побудована математична модель на поліпереставленні з дробово-лінійною функцією цілі, виконано зведення до лінійної умовної задачі на спеціальній комбінаторній множині, досліджено властивості її комбінаторного многогранника.В результаті виконання дисертаційної роботи отримано результати, які в сукупності є подальшим розвитком теорії евклідової комбінаторної оптимізації в геометричному проектуванні шляхом дослідження властивостей спеціальних класів цільових функцій на множині поліпереставлень, побудовано та досліджено математичні моделі, розроблено та обгрунтовано методи розвязання вказаного класу задач. Показано необхідність використоання множини поліпереставлень як апарату математичного моделювання для задач комбінаторної оптимізації з дробово-лінійною цільовою функцією. Доведено теорему про еквівалентність розвязків задачі з дробово-лінійною функцією на поліпереставленнях та побудованої умовної задачі оптимізації з лінійною цільовою функцією на евклідовій комбінаторній множині спеціального вигляду. Досліджено властивості комбінаторної множини та комбінаторного многогранника задачі оптимізації з лінійною цільовою функцією на та одним лінійним обмеженням, до якої зводиться безумовна задача оптимізації на множині поліпереставлень. Запропоновано та обґрунтовано комбінований метод розвязування лінійних умовних евклідових комбінаторних задач оптимізації на множинах, що збігаються з множинами вершин своїх опуклих оболонок, на основі поєднання ідей відсікання та перебору, доведено теорему про точність та скінченність методу.

2. Основний зміст роботи

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

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

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

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

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

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

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

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

1. Емец О.А., Евсеева Л.Г., Романова Н.Г. Задача цветной упаковки прямоугольников с учетом погрешностей исходных данных и ее решение // Экономика и матем. методы.-2000.-Т.36, - №3.-С.149-152.

2. Емец О.А., Евсеева Л.Г., Романова Н.Г. Интервальная математическая модель комбинаторной задачи цветной упаковки прямоугольников // Кибернетика и системный анализ. - 2001. - №3. - С.131 - 138.

3. Валуйская О.А., Емец О.А., Романова Н.Г. Выпуклое продолжение многочленов, заданных на полиперестановках, модифицированным методом Стояна-Яковлева // Журн. вычислит.математ и матем. физики. - 2002. - Т. 42, - №4. - С.591- 596.

4. Ємець О.О., Романова Н.Г., Чілікіна Т.В. Задачі оптимізації на вершинно розташованих евклідових комбінаторних множинах // Математичне моделювання. - 2003. - №2 (10). - С. 13-15.

5. Ємець О.О., Романова Н.Г. Безумовна задача оптимізації дробово-лінійної цільової функції на поліпереставленнях: зведення до лінійної умовної на спеціальній комбінаторній множині // Радиоэлектроника и інформатика.- 2005. - №1. - С. 70-74.

6. Ємець О.О., Романова Н.Г. Комбінований метод розвязування лінійних комбінаторних задач оптимізації на вершинно розташованих евклідових комбінаторних множинах //Динамические системы (межвед. науч. сб.) - Симферополь: Тавр. нац. ун-т., 2004. Вып. 17. - С. 166-170.

7. Ємець О., Євсеєва Л., Романова Н. Результати численних експериментів по розвязуванню задачі кольорового упакування прямокутників з урахуванням похибок початкових даних// Зб. наук. праць: Вісник Полтав. держ. пед. ін-ту ім. В.Г. Короленка. - Сер. "Фіз.-матем. науки" - 1998 - Вип. 3.- С.16-18.

8. Ємець О.О., Романова Н.Г., Роскладка О.В. Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розвязування // Вісник Львів. нац. ун-ту . Сер. приклад. математика та інформатика. - 2002. - Вип. № 5. - С. 89 - 94.

9. Ємець О.О., Романова Н.Г. Моделювання задачами оптимізації з дробово-лінійною цільовою функцією на поліпереставленнях // Вісник нац. ун-ту “Львівська політехніка” Сер. Фіз.-мат. науки. - 2005. - Вип. № 540. - С. 65 - 68.

10. Романова Н.Г. Задача оптимізації дробово-лінійної цільової функції на поліпереставленнях: властивості її комбінаторного многогранника // Журн.”Волинський математичний вісник” Сер. Прикладна математика. - 2004. - Вип. № 2 (11). - С. 223-233.

11. Ємець О.О., Романова Н.Г., Чілікіна Т.В. Задачі оптимізації на вершинно розташованих евклідових комбінаторних множинах // В кн.: Міждержавна науково-методична конференція “Проблеми математичного моделювання” (28 -30 травня 2003 р.). - Дніпродзержинськ, 2003.- С. 32-33.

12. Ємець О.О., Євсеєва Л.Г., Романова Н.Г. Реалізація інтервальной моделі задачі кольорового упакування // Матеріали VII міжнар. наук. конф. ім. ак. М. Кравчука (14-16 травня 1998р.).- К., 1998.- С. 166.

13. Ємець О.О., Пічугіна О.С., Романова Н.Г. Про поширення на поліпереставлення методу Стояна-Яковлева опуклого продовження функції та його ефективність // Матеріали VIII міжнар. наук. конференції ім. ак. М.Кравчука (11-14 травня 2000 р.).- К., 2000. - С. 278

14. Романова Н.Г. Властивості множини допустимих розвязків в дробово-лінійній задачі оптимізації на поліпереставленнях // Матеріали VIII міжнар. наук.-практ. конференція “Наука і освіта’2005”. . - Дніпропетровськ: Наука і освіта, 2005, Том 23. Математичне моделювання, - С. 57-58.

15. Ємець О.О., Євсеєва Л.Г., Романова Н.Г. Розвязування задачі кольорового упакування прямокутників з урахуванням похибок початкових даних/ -Київ, 1998.- 19 с.-Укр.- Деп. в ДНТБУ 02.02.1998, №90.