Search academic texts

Registration Number

0499U003282, Candidate dissertation

Status

к.ф.-м.н., 01.05.02, Математичне моделювання та обчислювальні методи

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