Search academic texts

Information × Registration Number 0412U006642, Candidate dissertation Status к.ф.-м.н. Date 23-11-2012 popup.evolution o 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 Гребеннік Ігор Валерійович Description Запропоновано та обґрунтовано другий метод комбінаторного відсікання в умовних лінійних задачах на вершинно розташованих множинах з виключенням виродженості в допоміжних задачах лінійного програмування, що, на відміну від першого методу відсікання, дозволяє проводити відсікання тільки на многограннику переставлень. Одержано симплексну форму переставного многогранника, що дозволяє застосовувати алгоритм Кармаркара в методі комбінаторного відсікання. Розроблено та обґрунтовано метод комбінаторного відсікання на основі алгоритму Кармаркара для умовних лінійних задач комбінаторної оптимізації на переставленнях, що дозволяє для розв'язування допоміжних задач лінійного програмування застосовувати поліноміальні алгоритми. Розроблено метод відсікання вершин графа переставного многогранника для умовних лінійних задач комбінаторної опти-мізації на переставленнях, що дозволяє більш ефективно враховувати властивості комбінаторної множини. Розроблено наближений поліноміальний метод аналізу графа переставного многогранника з реалізацією для багатопроцесорної системи, що дозволяє на практиці отримувати наближений розв'язок задач з використанням переваг багатопроцесорних систем. Registration Date 2012-11-23 popup.nrat_date 2020-04-04 Close