Властивості задач комбінаторної оптимізації з дробово-лінійними цільовими функціями. Методи та алгоритми їх розв’язання - Автореферат

Дисертаційна робота є продовженням досліджень областей визначення евклідових задач комбінаторної оптимізації на переставних множинах та їх опуклих оболонок, а також задач оптимізації, що виникають в геометричному проектуванні на цих множинах, та задач з дробово-лінійними функціями цілі, пошуків нових методів їх розвязання. Для цього в роботі були поставлені основні задачі: 1) побудова та аналіз математичних моделей нового класу задач комбінаторної оптимізації з дробово-лінійними функціями цілі на переставленнях; побудова моделей деяких прикладних задач що зводяться до комбінаторних задач нового класу; комбінаторний задача дробовий Методи дослідження: для одержання властивостей многогранника в евклідовій задачі комбінаторної оптимізації з дробово-лінійною функцією цілі на переставленнях використовуються методи поліедральної комбінаторики; для одержання розвязків задач оптимізації з дробово-лінійними функціями цілі на переставленнях, екстремальних властивостей цільових функцій в таких задачах, а також для розвинення методу відсікання в комбінаторних задачах з дробово-лінійною цільовою функцією використовуються методи математичного моделювання, евклідової комбінаторної оптимізації. Наукова новизна одержаних результатів: 1)вперше запропонована постановка евклідових комбінаторних задач з дробово-лінійними функціями цілі на загальній множині переставлень, сформульовані і доведені властивості многогранника - області допустимих розв?язків задачі з лінійною функцією цілі, до якої зводиться задача з дробово-лінійною функцією цілі на переставленнях (встановлені теореми про грані многогранника, суміжність граней, критерій вершини, одержано незвідну систему лінійних обмежень такого комбінаторного многогранника); У роботах, написаних у співавторстві дисертанту належить: [1]-встановлення властивостей многогранника в задачі з дробово-лінійною функцією цілі, формулювання та доведення теорем про грані цього многогранника, про суміжність граней цього многоранника, критерій його вершини; [2] - формулювання та доведення властивостей многоранника - області допустимих розв?язків задачі; [3] - формулювання та доведення теореми про незвідну систему обмежень комбінаторного многогранника в задачі з дробово-лінійною функцією цілі; [4; 11]-програмна реалізація алгоритму на ПЕОМ та проведення і аналіз числових експериментів; [5] - постановка задач та побудова їх моделей; [6] - формулювання та доведення твердження про відображення точок; [9] - формулювання та доведення теореми про незвідну систему обмежень многогранника; [10] - формулювання та доведення властивостей області допустимих розвязків задачі; [12] - нове доведення теореми про грані переставного многогранника; [13] - формулювання та доведення теореми.Зроблено висновки про актуальність дослідження задач евклідової комбінаторної оптимізації з дробово-лінійною функцією цілі на комбінаторній множині переставлень. Нехай Jk={1, ..., k} - множина перших k натуральних чисел, = JKE{0}, J0= , DIML - вимірність множини LIRN, CONVM - опукла оболонка множини M, VERTП - множина вершин многогранника П. Множина E, елементи якої є k-вибірки вигляду (1) з G, називається евклідовою комбінаторною множиною, якщо для довільних елементів e’=(a1, ..., ak), e? =(b1, ..., bk) цієї множини виконується умова: (e’? e?)U ($ JIJK : aj ? bj ). Відображення називається зануренням множини E в арифметичний евклідів простір, якщо f ставить множину E у взаємно однозначну відповідність множині EFI R k за правилом: для маємо xj = gi j "JIJK . Множина Ef називається спеціальною комбінаторною множиною, або с-комбінаторною множиною; с-множина є також e-множиною.Для розв?язування задачі (2), (3) зроблено перехід до задачі з лінійною функцією цілі за допомогою співвідношень: Співвідношення (4) задають відображення y( )=EI . Система, обмежень (7), (8), визначає опуклий многогранний конус з вершиною в точці О(0,...,0), a (9) - гіперплощину, яка перерізає конус і не проходить через його вершину. 1) Якщо F - m-грань многогранника , що визначається системою (7)-(9), то існують множини , де для яких нерівності в (7) перетворюються на рівності "YIF. Метод комбінаторного відсікання для задач з дробово-лінійними цільовими функціями полягає в наступному: 1)здійснюємо перехід від задачі (20)-(22) з дробово-лінійною функцією цілі до задачі з лінійною функцією цілі (24)-(26) за допомогою перетворень (23); згідно МППО на першому етапі при t=1: формуємо систему S1 лінійних обмежень, що визначає область D1: D1ED0 (S1IS), де в систему S1 входять обмеження (26), та обмеження (27) нульової спілки, першої, (k-1) та k спілок з (27)-(29) та (29);Задачі з дробово-лінійними цільовими функціями на комбінаторних множинах - новий клас задач комбінаторної оптимізації, який раніше не розглядався, а тому є не дослідженим. Результати дисертаційної роботи одержані на основі застосування теорії та підходів, розвинутих раніше в рамках евклідової комбінаторної оптимізації, можуть бути використані для дослідження та розвязування нових задач комбін

ОСНОВНИЙ ЗМІСТ