Недобачій С. І. Моделі, методи і алгоритми в задачах евклідової комбінаторної оптимізації.

Досліджуються опукі оболонки областей визначення задач, моделями яких є задачі евклідової оптимізації на переставних множинах. Мета роботи -- установлення нових властивостей зазначених множин та їх опуклих оболонок, розробка нового методу точного розв'зування задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів. Одержано незвідні системи лінійних обмежень загального переставного і загального поліпереставного многогранників. Для кожного із них визначено рівняння гіперграней, виражені через ненадлишкові обмеження, установлено їх кількість, зроблено опис вершин рівняннями гіперграней. Визначено кількість гіперграней, що збігаються в одній і тій же вершині. Викладено нове доведення збіжності вершин загального переставного многогранника з множиною переставлень із повтореннями, якою він індукується. Установлено залежність між кількістю гіперграней добутку многогранників і кількістю гіперграней многогранників, що утворюють цей добуток. Для переставного многогра нника визначено найменшу кількість ребер, що з'єднують дві довільні його вершини. Викладено алгоритм знаходження шляху між двома довільними вершинами, який складається знайменшої кількості ребер. Доведено властивості одного відображення множини переставлень перших n натуральних чисел у множину переставлень абсолютних величин їх різниць, яке виникає в задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів. Викладено новий метод точного розв'язування цієї задачі. Одержані результати можуть виористовуватися в теорії евклідової комбінаторної оптимізації при подальшому її розвитку та для одержання нових алгоритмів розв'язу вання практичних задач оптимізації.