Черненко Оксана Олексіївна. Властивості математичних моделей задач з дробово-лінійною цільовою функцією на розміщеннях та методи їх розв'язування : дис... канд. фіз.-мат. наук: 01.05.01 / Полтавський ун-т споживчої кооперації України. — Полтава, 2006. — 167арк. : рис., табл. — Бібліогр.: арк. 132-148.
Анотація до роботи:
Черненко О.О. Властивості математичних моделей задач з дробово-лінійною цільовою функцією на розміщеннях та методи їх розв'язування. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики. – Інститут кібернетики ім. В. М. Глушкова НАН України, Київ, 2006.
У дисертації досліджено властивості математичних моделей задач евклідової комбінаторної оптимізації з дробово-лінійною цільовою функцією на множині розміщень. Побудовано математичні моделі прикладних задач такого типу. Сформульовані і доведені властивості многогранника в задачі з лінійною функцією цілі, до якої зводиться задача на розміщеннях з дробово-лінійною цільовою функцією. Виявлено надлишкові обмеження в системі лінійних нерівностей цього многогранника й встановлено його незвідну систему обмежень. Обґрунтовано аналітичний метод розв’язування безумовних задач на множині розміщень з дробово-лінійною функцією цілі. Розвинуто метод побудови лексикографічної еквівалентності та вперше запропоновано алгоритм розв’язування умовних задач на розміщеннях з дробово-лінійною цільовою функцією. Проведені оцінки та досліджена практична ефективність алгоритму шляхом числових експериментів.
Результати дисертаційної роботи є теоретичною основою вирішення важливої наукової проблеми розв’язування оптимізаційних задач з дробово-лінійною цільовою функцією на розміщеннях. У дисертації вперше досліджені властивості математичних моделей задач евклідової комбінаторної оптимізації на множині розміщень з дробово-лінійною цільовою функцією, що є необхідними для побудови алгоритмів розв’язування таких задач.
У роботі проведено аналіз сучасного стану теорії евклідової комбінаторної оптимізації, теорії дробово-лінійного програмування та їх застосування при розв’язуванні комбінаторних оптимізаційних задач на розміщеннях. У результаті огляду літературних джерел встановлено, що множина розміщень є ефективним засобом математичного моделювання задач оптимізації; задачі з дробово-лінійною цільовою функцією на розміщеннях ще не розглядалися, а тому залишаються не дослідженими. Проведений аналіз властивостей дробово-лінійних функцій та відомих методів розв’язування задач з дробово-лінійною цільовою функцією показав, що задачі з аналогічною структурою на загальній множині розміщень потребують розробки спеціальних методів та алгоритмів розв’язування.
Уперше сформульовані постановки безумовної та умовної задач евклідової комбінаторної оптимізації з дробово-лінійною цільовою функцією на множині розміщень, а також побудовано математичні моделі деяких прикладних задач як задач такого типу, що ілюструють їх існування та актуальність дослідження.
Уперше сформульовані і доведені властивості многогранника – області допустимих розв’язків задачі з лінійною функцією цілі, до якої зводиться безумовна задача на розміщеннях з дробово-лінійною цільовою функцією. Зокрема, визначено критерій вершини многогранника в задачі з лінійною цільовою функцією, встановлено незвідну систему обмежень цього многогранника, описано його грані, доведено критерій суміжності вершин многогранника. Досліджено властивості відображення, з допомогою якого зводиться задача з дробово-лінійною функцією цілі до задачі з лінійною цільовою функцією, а саме, доведено твердження про взаємнооднозначну відповідність між точками многогранника розміщень та многогранника – області допустимих розв’язків лінійної задачі. Одержані властивості використовуються при побудові алгоритмів розв’язування безумовних та умовних задач оптимізації з дробово-лінійними функціями цілі на розміщеннях.
Уперше на основі властивостей комбінаторного многогранника доведено критерій оптимальності для евклідової комбінаторної задачі на розміщеннях з дробово-лінійною цільовою функцією без додаткових обмежень.
Запропоновано метод розв’язування умовних задач з дробово-лінійною функцією цілі на загальній множині розміщень, як подальший розвиток методу розв’язування лінійних задач на розміщеннях. Проведені оцінки роботи допоміжних алгоритмів, складових алгоритму розв’язування задачі, та числові експерименти, які показали його практичну ефективність.
Результати дисертації впроваджено в держбюджетну тему „Евклідова комбінаторна оптимізація” (№ 213/04) та в навчальний процес Полтавського університету споживчої кооперації України Укоопспілки.
Результати дисертаційних досліджень одержані на основі застосування теорії та підходів, розвинутих раніше в рамках евклідової комбінаторної оптимізації, їх достовірність випливає з коректності математичних доведень лем, теорем, коректності застосувань методів досліджень.
Публікації автора:
Ємець О. О., Барболіна Т. М., Черненко О. О. Розв’язування умовних задач з дробово-лінійною функцією цілі на множині розміщень // Доповіді НАН України. – 2006. – №11. – С. 15-18.
Емец О. А., Черненко О. А. Неприводимая система ограничений комбинаторного многогранника в дробно-линейной задаче оптимизации на размещениях // Кибернетика и системный анализ. – 2005. – №2. – С. 107-116.
Емец О. А., Барболина Т. Н., Черненко О. А. Решение задач оптимизации с дробно-линейными целевыми функциями и дополнительными ограничениями на размещениях // Кибернетика и системный анализ. – 2006. – №5. – С. 79-85.
Ємець О. О., Черненко О. О. Оптимізація дробово-лінійної функції на розміщеннях: властивості допустимої області // Наукові вісті НТУУ “КПІ”. 2006. № 5. С. 22-29.
Ємець О. О., Черненко О. О. Математичне моделювання економічних проблем задачами оптимізації на розміщеннях з дробово-лінійною функцією цілі // Волинський математичний вісник. – Рівне: РДГУ. – 2004. – Вип. 2. – С. 107-113.
Емец О. А., Черненко О. А. Некоторые свойства области допустимых решений задачи с дробно-линейной функцией цели на размещениях // Динамические системы (межведомственный научный сборник). – Симферополь: ТНУ. – 2005. – Вып. 19. – С. 122-129.
Ємець О. О., Черненко О. О. Розв’язування безумовної задачі з дробово-лінійною функцією цілі на загальній множині розміщень // Радиоэлектроника и информатика. – 2005. – №4. – С. 144-149.
Ємець О. О., Черненко О. О. Дробово-лінійна задача оптимізації на розміщеннях: незвідна система обмежень комбінаторного многогранника // Матеріали VII Міжнародної науково-практичної конференції „Наука і освіта ‘2004” (10-25 лютого 2004 р.). – Дніпропетровськ: Наука і освіта, 2004. – С. 43-46.
Ємець О. О., Черненко О. О. Одна нова модель максимізації рентабельності як комбінаторна задача на розміщеннях // Економіко-математичні методи прийняття управлінських рішень на сучасному етапі: Матеріали II Всеукраїнської науково-практичної конференції (24 березня 2004 р.). – Дніпропетровськ: Наука і освіта, 2004. – С. 81-83.
Черненко О. О. Властивості множини допустимих розв’язків дробово-лінійної задачі на розміщеннях // Молодь, освіта, наука, культура і національна самосвідомість: Зб. матеріалів VII всеукр. наук.-практ. конф. (15-16 квітня 2004 р.). – К.: Вид-во Європ. ун-ту, 2004. – Т.5.– С. 21-25.
Черненко О. О. Дослідження множини допустимих розв’язків задачі оптимізації дробово-лінійної функції на евклідовій комбінаторній множині розміщень // X міжн. наук. конф. ім. ак. М. Кравчука: Матеріали конференції (13-15 травня 2004 р.). – К.: Задруга, 2004. – С. 548.
Ємець О. О., Черненко О. О. Лексикографічний метод розв’язування дробово-лінійної умовної задачі на розміщеннях // Праці II міжн. школи-семінару „Теорія прийняття рішень”(27 вересня-2 жовтня 2004 р.).– Ужгород: УжНУ, 2004. – С. 41.
Черненко О. О. Оптимізація на розміщеннях з дробово-лінійною цільовою функцією без додаткових обмежень // Матеріали IV Міжнародної науково-практичної конференції „Динаміка наукових досліджень ‘2005” (20 – 30 червня 2005 р.). – Дніпропетровськ: Наука і освіта, 2005. – С. 31-34.
Емец О. А., Барболина Т. Н., Черненко О. А. Оптимизация дробно-линейной функции на размещениях при дополнительных ограничениях // Проблемы теоретической кибернетики: Тезисы докладов XIV Международной конференции (Пенза, 23-28 мая 2005 г.). – Москва: МГУ, 2005. – С. 45.
Черненко О. О. Комбінаторна модель задачі про перевезення вантажу // XI міжн. наук. конф. ім. ак. М. Кравчука: Матеріали конференції (18-20 травня 2006 р.). – К.: Задруга, 2006. – С. 757.
