Романова Наталія Гавриілівна. Задачі евклідової комбінаторної оптимізації на поліпереставленнях та методи їх розв'язування : дис... канд. фіз.-мат. наук: 01.05.02 . — Полтава, 2006. — 168арк. — Бібліогр.: арк. 121-143.
Анотація до роботи:
Романова Н.Г. Задачі евклідової комбінаторної оптимізації на поліпереставленнях та методи їх розв’язування. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи (фіз.-мат. науки). – ХНУРЕ, Харків, 2007.
В дисертації досліджені та розроблені математичні моделі: для задачі кольорового упакування прямокутників та задачі про визначення порядку обслуговування замовлень для максимізації рентабельності системи обслуговування. Реалізована математична модель кольорового упакування, проведено числові експерименти. Для розв’язування лінійних комбінаторних задач оптимізації на вершинно розташованих евклідових комбінаторних множинах розроблено та обгрунтовано новий комбінований метод.
Поширено на множину поліпереставлень та модифіковано метод Стояна-Яковлева опуклого продовження функцій з переставлень, проведена оцінка числа арифметичних операцій при цьому.
Для задачі оптимізації з лінійною цільовою функцією на та одним лінійним обмеженням, до якої зводиться безумовна задача оптимізації на множині поліпереставлень, розглянуто властивості комбінаторної множини та комбінаторного многогранника. Доведено теорему про грані цього многогранника, отримано та обгрунтовано критерій його вершин; критерій суміжності вершин многогранника та підрахована їх кількість.
Доведена теорема про еквівалентність розв'язків для задачі з дробово-лінійною цільовою функцією на поліпереставленнях та побудованої в роботі умовної задачі оптимізації з лінійною цільовою функцією на евклідовій комбінаторній множині спеціального вигляду.
В результаті виконання дисертаційної роботи отримано результати, які в сукупності є подальшим розвитком теорії евклідової комбінаторної оптимізації в геометричному проектуванні шляхом дослідження властивостей спеціальних класів цільових функцій на множині поліпереставлень, побудовано та досліджено математичні моделі, розроблено та обгрунтовано методи розв’язання вказаного класу задач.
Показано необхідність використоання множини поліпереставлень як апарату математичного моделювання для задач комбінаторної оптимізації з дробово-лінійною цільовою функцією. Обгрунтовано потрібність подальшого дослідження задач оптимізації з дробово-лінійною цільовою функцією, комбінаторними обмеженнями у вигляді належності множині поліпереставлень та додатковими некомбінаторними обмеженнями. Доведено теорему про еквівалентність розв'язків задачі з дробово-лінійною функцією на поліпереставленнях та побудованої умовної задачі оптимізації з лінійною цільовою функцією на евклідовій комбінаторній множині спеціального вигляду. Досліджено комбінаторний многогранник побудованої лінійної задачі на спеціальній комбінаторній множині, а саме: вигляд системи, що його описує, її сумісність. Досліджено властивості комбінаторної множини та комбінаторного многогранника задачі оптимізації з лінійною цільовою функцією на та одним лінійним обмеженням, до якої зводиться безумовна задача оптимізації на множині поліпереставлень. Доведено теорему про грані многогранника , отримано та обгрунтовано критерій вершини цього многогранника; доведено вершинну розташованість множини , критерій суміжності вершин многогранника , підрахована їх кількість.
Досліджені властивості комбінаторного многогранника дають фундамент для розвитку методів розв’язування задач евклідової комбінаторної оптимізації розглянутого вигляду з дробово-лінійними функціями на .
При розв’язуванні задач кольорового упакування та інших лінійних комбінаторних задач оптимізації на переставленнях та поліпереставленнях (взагалі на вершинно розташованих множинах) пропонується поєднання в рамках комбінованого методу ідей методу відсікання та методу гілок та меж (і переборних методів взагалі). Запропоновано та обґрунтовано комбінований метод розв’язування лінійних умовних евклідових комбінаторних задач оптимізації на множинах, що збігаються з множинами вершин своїх опуклих оболонок, на основі поєднання ідей відсікання та перебору, доведено теорему про точність та скінченність методу.
Для методу Стояна-Яковлева опуклого продовження многочленів з перестав-лень в арифметичний евклідів простір в роботі розроблена та обґрунтована модифікація для випадку опуклого продовження з поліпереставлень, проведена оцінка числа арифметичних операцій.
Побудована в роботі інтервальна математична модель задачі кольорового упакування прямокутників з урахуванням похибок початкових даних показує, як можна застосувати елементи інтервального аналізу для врахування поліпереставних властивостей допустимої області та похибок метричних характеристик. При цьому введено та використано поняття інтервального поліпереставлення.
Доведені властивості комбінаторних множин одержано вперше, розроблені методи є поширенням та модифікацією відомих. Це є гарантією їх практичної ефективності.
Доведені факти стосовно властивостей комбінаторних множин в дисертації є підґрунтям подальшого розвитку теорії моделювання оптимізаційними задачами на евклідових комбінаторних множинах. Розроблені методи можуть використовуватись в практичних задачах в різних галузях, зокрема в задачах, що зводяться до задачі кольорового упакування та задачі максимізації рентабельності системи з застосуванням евклідової комбінаторної оптимізації. Результати дисертаційної роботи впроваджено в навчальний процес Полтавського університету споживчої кооперації Украни.
Публікації автора:
Емец О.А., Евсеева Л.Г., Романова Н.Г. Задача цветной упаковки прямоугольников с учетом погрешностей исходных данных и ее решение // Экономика и матем. методы.–2000.–Т.36, - №3.–С.149-152.
Емец О.А., Евсеева Л.Г., Романова Н.Г. Интервальная математическая модель комбинаторной задачи цветной упаковки прямоугольников // Кибернетика и системный анализ. - 2001. - №3. - С.131 - 138.
Валуйская О.А., Емец О.А., Романова Н.Г. Выпуклое продолжение многочленов, заданных на полиперестановках, модифицированным методом Стояна-Яковлева // Журн. вычислит.математ и матем. физики. – 2002. – Т. 42, - №4. – С.591- 596.
Ємець О.О., Романова Н.Г., Чілікіна Т.В. Задачі оптимізації на вершинно розташованих евклідових комбінаторних множинах // Математичне моделювання. – 2003. – №2 (10). – С. 13-15.
Ємець О.О., Романова Н.Г. Безумовна задача оптимізації дробово-лінійної цільової функції на поліпереставленнях: зведення до лінійної умовної на спеціальній комбінаторній множині // Радиоэлектроника и інформатика.– 2005. - №1. – С. 70-74.
Ємець О.О., Романова Н.Г. Комбінований метод розв’язування лінійних комбінаторних задач оптимізації на вершинно розташованих евклідових комбінаторних множинах //Динамические системы (межвед. науч. сб.) – Симферополь: Тавр. нац. ун-т., 2004. Вып. 17. - С. 166-170.
Ємець О., Євсеєва Л., Романова Н. Результати численних експериментів по розв'язуванню задачі кольорового упакування прямокутників з урахуванням похибок початкових даних// Зб. наук. праць: Вісник Полтав. держ. пед. ін-ту ім. В.Г. Короленка. - Сер. "Фіз.-матем. науки" - 1998 - Вип. 3.- С.16-18.
Ємець О.О., Романова Н.Г., Роскладка О.В. Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв’язування // Вісник Львів. нац. ун-ту . Сер. приклад. математика та інформатика. – 2002. - Вип. № 5. - С. 89 – 94.
Ємець О.О., Романова Н.Г. Моделювання задачами оптимізації з дробово-лінійною цільовою функцією на поліпереставленнях // Вісник нац. ун-ту “Львівська політехніка” Сер. Фіз.-мат. науки. – 2005. - Вип. № 540. - С. 65 – 68.
Романова Н.Г. Задача оптимізації дробово-лінійної цільової функції на поліпереставленнях: властивості її комбінаторного многогранника // Журн.”Волинський математичний вісник” Сер. Прикладна математика. – 2004. - Вип. № 2 (11). - С. 223-233.
Ємець О.О., Романова Н.Г., Чілікіна Т.В. Задачі оптимізації на вершинно розташованих евклідових комбінаторних множинах // В кн.: Міждержавна науково-методична конференція “Проблеми математичного моделювання” (28 -30 травня 2003 р.). - Дніпродзержинськ, 2003.- С. 32-33.
Ємець О.О., Євсеєва Л.Г., Романова Н.Г. Реалізація інтервальной моделі задачі кольорового упакування // Матеріали VII міжнар. наук. конф. ім. ак. М. Кравчука (14-16 травня 1998р.).- К., 1998.- С. 166.
Ємець О.О., Пічугіна О.С., Романова Н.Г. Про поширення на поліпереставлення методу Стояна-Яковлева опуклого продовження функції та його ефективність // Матеріали VIII міжнар. наук. конференції ім. ак. М.Кравчука (11-14 травня 2000 р.).- К., 2000. – С. 278
Романова Н.Г. Властивості множини допустимих розв’язків в дробово-лінійній задачі оптимізації на поліпереставленнях // Матеріали VIII міжнар. наук.-практ. конференція “Наука і освіта’2005”. . – Дніпропетровськ: Наука і освіта, 2005, Том 23. Математичне моделювання, – С. 57-58.
Ємець О.О., Євсеєва Л.Г., Романова Н.Г. Розв’язування задачі кольорового упакування прямокутників з урахуванням похибок початкових даних/ -Київ, 1998.- 19 с.-Укр.- Деп. в ДНТБУ 02.02.1998, №90.
