Романова Н. Г. Задачі евклідової комбінаторної оптимізації на поліпереставленнях та методи їх розв'язування

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