Search academic texts

Information × Registration Number 0499U003282, Candidate dissertation Status к.ф.-м.н. Date 09-12-1999 popup.evolution o Title Models, methods and algorithms in Euclidean combinatorial optimization problems. Author Nedobachij Stanislav Ivanovych, popup.head Ємець Олег Олексійович popup.opponent Яковлев Сергій Всеволодович popup.opponent Гребеннік Ігор Валерійович Description Досліджуються опукі оболонки областей визначення задач, моделями яких є задачі евклідової оптимізації на переставних множинах. Мета роботи -- установлення нових властивостей зазначених множин та їх опуклих оболонок, розробка нового методу точного розв'зування задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів. Одержано незвідні системи лінійних обмежень загального переставного і загального поліпереставного многогранників. Для кожного із них визначено рівняння гіперграней, виражені через ненадлишкові обмеження, установлено їх кількість, зроблено опис вершин рівняннями гіперграней. Визначено кількість гіперграней, що збігаються в одній і тій же вершині. Викладено нове доведення збіжності вершин загального переставного многогранника з множиною переставлень із повтореннями, якою він індукується. Установлено залежність між кількістю гіперграней добутку многогранників і кількістю гіперграней многогранників, що утворюють цей добуток. Для переставного многогра нника визначено найменшу кількість ребер, що з'єднують дві довільні його вершини. Викладено алгоритм знаходження шляху між двома довільними вершинами, який складається знайменшої кількості ребер. Доведено властивості одного відображення множини переставлень перших n натуральних чисел у множину переставлень абсолютних величин їх різниць, яке виникає в задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів. Викладено новий метод точного розв'язування цієї задачі. Одержані результати можуть виористовуватися в теорії евклідової комбінаторної оптимізації при подальшому її розвитку та для одержання нових алгоритмів розв'язу вання практичних задач оптимізації. Registration Date 2001-04-04 popup.nrat_date 2021-03-17 Close