Registration Number
0412U006642, Candidate dissertation
Status
к.ф.-м.н.
Date
23-11-2012
popup.evolution
.
Title
Exact and approximate cut-off methods for solving linear optimization problems on permutations
Author
Olhovsky Dmitriy Mykolayevich,
popup.head Iemets Elizaveta Mikhaylovna
popup.opponent Донець Георгій Панасович
popup.opponent Ляшенко Ігор Миколайович
popup.opponent Гребеннік Ігор Валерійович
popup.rada
V.M.Glushkov Institute of Cybernetics of NASU
Description
Запропоновано та обґрунтовано другий метод комбінаторного відсікання в умовних лінійних задачах на вершинно розташованих множинах з виключенням виродженості в допоміжних задачах лінійного програмування, що, на відміну від першого методу відсікання, дозволяє проводити відсікання тільки на многограннику переставлень. Одержано симплексну форму переставного многогранника, що дозволяє застосовувати алгоритм Кармаркара в методі комбінаторного відсікання. Розроблено та обґрунтовано метод комбінаторного відсікання на основі алгоритму Кармаркара для умовних лінійних задач комбінаторної оптимізації на переставленнях, що дозволяє для розв'язування допоміжних задач лінійного програмування застосовувати поліноміальні алгоритми. Розроблено метод відсікання вершин графа переставного многогранника для умовних лінійних задач комбінаторної опти-мізації на переставленнях, що дозволяє більш ефективно враховувати властивості комбінаторної множини. Розроблено наближений поліноміальний метод аналізу графа переставного многогранника з реалізацією для багатопроцесорної системи, що дозволяє на практиці отримувати наближений розв'язок задач з використанням переваг багатопроцесорних систем.
Registration Date
2012-12-26
popup.nrat_date
2020-04-04 / 2026-06-30