Registration Number
0499U003282, Candidate dissertation
Status
к.ф.-м.н.
Date
09-12-1999
popup.evolution
.
Title
Models, methods and algorithms in Euclidean combinatorial optimization problems.
Author
Nedobachij Stanislav Ivanovych,
popup.head Ємець Олег Олексійович
popup.opponent Яковлев Сергій Всеволодович
popup.opponent Гребеннік Ігор Валерійович
popup.rada
A. Podgorny's Institute of Mechanical Engeneering Problems of the National Academy of Science of Ukraine
Description
Досліджуються опукі оболонки областей визначення задач, моделями яких є задачі евклідової оптимізації на переставних множинах. Мета роботи -- установлення нових властивостей зазначених множин та їх опуклих оболонок, розробка нового методу точного розв'зування задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів. Одержано незвідні системи лінійних обмежень загального переставного і загального поліпереставного многогранників. Для кожного із них визначено рівняння гіперграней, виражені через ненадлишкові обмеження, установлено їх кількість, зроблено опис вершин рівняннями гіперграней. Визначено кількість гіперграней, що збігаються в одній і тій же вершині. Викладено нове доведення збіжності вершин загального переставного многогранника з множиною переставлень із повтореннями, якою він індукується. Установлено залежність між кількістю гіперграней добутку многогранників і кількістю гіперграней многогранників, що утворюють цей добуток. Для переставного многогра нника визначено найменшу кількість ребер, що з'єднують дві довільні його вершини. Викладено алгоритм знаходження шляху між двома довільними вершинами, який складається знайменшої кількості ребер. Доведено властивості одного відображення множини переставлень перших n натуральних чисел у множину переставлень абсолютних величин їх різниць, яке виникає в задачі мінімізації зваженої довжини зв'язуючої сітки при лінійному розташуванні прямокутних елементів. Викладено новий метод точного розв'язування цієї задачі. Одержані результати можуть виористовуватися в теорії евклідової комбінаторної оптимізації при подальшому її розвитку та для одержання нових алгоритмів розв'язу вання практичних задач оптимізації.
Registration Date
2001-04-04
popup.nrat_date
2021-03-18 / 2026-06-30