Колєчкіна Людмила Миколаївна. Властивості задач комбінаторної оптимізації з дробово-лінійними цільовими функціями. Методи та алгоритми їх розв'язання: Дис... канд. фіз.-мат. наук: 01.05.02 / Полтавський національний технічний ун-т ім. Юрія Кондратюка. - Полтава, 2002. - 170арк. - Бібліогр.: арк. 130-144.
Анотація до роботи:
Колєчкіна Л. М. Властивості задач комбінаторної оптимізації з дробово-лінійними цільовими функціями. Методи і алгоритми їх розвязання. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи. – Інститут проблем машинобудування імені А. М. Підгорного, Харків, 2002.
В дисертації викладено дослідження властивостей задач евклідової комбінаторної оптимізації з дробово-лінійними цільовими функціями на переставних множинах. Розвинуто метод комбінаторного відсікання та вперше побудовані алгоритми розв’язування таких задач. Зроблено перехід від задачі з дробово-лінійною функцією цілі до задачі з лінійною функцією цілі. Для останньої сформульовані та доведені властивості області допустимих розв’язків задачі, опукла оболонка якої представляє собою многогранник: теорема про грані многогранника, критерій вершини, критерій суміжності граней. Встановлено незвідну систему лінійних обмежень цього многогранника. Алгоритми, побудовані по методу комбінаторного відсікання, програмно реалізовані на ПЕОМ. Зроблено аналіз алгоритмів на основі числових експериментів. Побудовано моделі прикладних задач з дробово-лінійною цільовою функцією на переставних множинах.
Задачі з дробово-лінійними цільовими функціями на комбінаторних множинах – новий клас задач комбінаторної оптимізації, який раніше не розглядався, а тому є не дослідженим.
Дисертаційна робота присвячена побудові та аналізу математичних моделей класу задач з дробово-лінійними цільовими функціями на переставних множинах. Результати дисертаційної роботи одержані на основі застосування теорії та підходів, розвинутих раніше в рамках евклідової комбінаторної оптимізації, можуть бути використані для дослідження та розв’язування нових задач комбінаторної оптимізації.
Серед основних результатів роботи слід зазначити такі:
вперше виділено та побудовано новий клас задач евклідової комбінаторної оптимізації з дробово-лінійними цільовими функціями та додатковими лінійними обмеженнями на переставленнях;
вперше побудовані моделі прикладних задач, що зводяться до задач розглядуваного класу, і можуть бути використані при розв’язуванні практичних задач з аналогічною структурою;
вперше одержано властивості комбінаторного многогранника в задачі з лінійною функцією цілі, до якої зводиться безумовна задача з дробово-лінійною цільовою функцією на переставленнях, які можуть бути використані для встановлення нових властивостей такого многогранника, а також для розробки та побудови інших методів та алгоритмів розвязування задач з дробово-лінійними цільовими функціями на переставленнях;
розвинуто метод комбінаторного відсікання для розв’язування нового класу задач евклідової комбінаторної оптимізації з дробово-лінійними функціями цілі та додатковими лінійними обмеженнями на переставних множинах;
вперше побудовано та обгрунтовано скінченний алгоритм цього методу відсікання для розглянутого класу задач. Проведені числові експерименти, які показали практичну ефективність запропонованого методу відсікання для розв’язування такого класу задач. Метод може бути застосований для розвязування практичних задач, які мають математичну модель у вигляді евклідових комбінаторних задач оптимізації з дробово-лінійними функціями цілі на переставній множині.
Публікації автора:
Ємець О.О., Колєчкіна Л.М., Недобачій С.І. Дослідження областей визначення задач евклідової комбінаторної оптимізації на переставних множинах. – Полтава: ПДТУ, Легат.- 1999. - 64с.
Ємець О.О., Колєчкіна Л.М. Задача оптимізації на переставленнях з дробово-лінійною цільовою функцією: властивості множини допустимих розвязків // Український математичний журнал. – 2000. – Т. 52, №12. – С. 1630-1640.
Емец О.А., Недобачий С.И., Колечкина Л.Н. Неприводимая система ограничений комбинаторного многогранника в дробно-линейной задаче оптимизации на перестановках // Дискретная математика. – 2001. – Т.13, №1. – С.110-118.
Емец О.А., Емец Е.М., Колечкина Л.Н. Использование метода отсечений при раскрое // Радиоэлектроника и информатика. – 1998, №3, С.114 –117.
Ємець О.О., Колєчкіна Л.М. Моделювання деяких прикладних задач оптимізаційними задачами з дробово-лінійною функцією цілі на переставленнях // Волинський математичний вісник. – 2000. – № 7 - С.116-119.
Ємець О.О., Колєчкіна Л.М. Розвязування оптимізаційних задач з дробово-лінійною цільовою функцією на загальній множині переставлень // Вісник державного університету “Львівська політехніка” – 1998. – № 337 – С.317-320.
Колєчкіна Л.М. Про одну задачу оптимізації з дробово-лінійною функцією цілі // Збірник наукових праць Полтавського державного пед. ін.-ту ім. В.Г.Короленка. – 1998 – Випуск 3. – С.32-35.
Колєчкіна Л.М. Задачі з дробово-лінійною функцією цілі та додатковими лінійними обмеженнями на загальній множині переставлень // Проблеми праці, економіки та моделювання: Збірник наук. праць – 1998. – С.116-117.
Колєчкіна Л. М., Недобачій С. І. Дослідження області визначення задачі комбінаторної оптимізації з дробово-лінійною функцією цілі на переставленнях // Збірник наукових праць Полтавського державного пед. ін.-ту ім. В.Г.Короленка – 1998. – Випуск 3 – С.18-24.
Ємець О.О., Колєчкіна Л.М. Дробово-лінійна задача оптимізації на загальній множині переставлень, та властивості області її допустимих розвязків. / Полт. тех. ун-т. – Полтава, 1997. – 25с. – Деп. в УкрІНТЕІ 30.12.97, №575 - Уі 97.
Емец О.А., Емец Е.М., Колечкина Л.Н. Отсечения при решении задачи раскроя как оптимизации на перестановках. Полт. гос. тех. универ. – Полтава, 1998 – 22с., Деп. в ГНТБ 10.09.98, №409 – Ук98.
Ємець О. О., Колєчкіна Л. М. Про нове доведення теореми про грані загального переставного многогранника. // В кн.: Матеріали конференції. Шоста Міжнародна конференція імені академіка М. Кравчука ( 15-17 травня 1997р.). – Київ. – 1997. – С.160.
Ємець О.О., Колєчкіна Л.М., Недобачий С.І. Незвідна система обмежень многогранника допустимих розвязків дробово-лінійної задачі оптимізації на переставленнях // В кн.: Матеріали конференції. VIII Міжнародна наукова конференція імені академіка М.Кравчука ( 11-14 травня 2000р.). – Київ. – 2000. – С. 300-301.
Колєчкіна Л.М. Властивості задач комбінаторної оптимізації з дробово-лінійнимицільовими функціями. Методи і алгоритми їх розв’язання.// В кн.: Матеріали конференції. Дев’ята Міжнародна наукова конференція імені академіка М.Кравчука ( 16-19 травня 2002р.). – Київ. – 2002. – С. 431-432.
