Реєстраційний номер
0414U001833, Кандидатська дисертація
На здобуття
к.ф.-м.н.
Дата захисту
25-04-2014
Статус
Захищена
Назва роботи
Комбінаторні задачі оптимізації потоку в мережі і методи їх розв’язування
Здобувач
Олексійчук Юрій Федорович,
Керівник Ємець Єлизавета Михайлівна
Опонент Донець Георгій Панасович
Опонент Заславський Володимир Анатолійович
Установа, організація, у вченій раді якої відбудеться/відбувся захист
Інститут кібернетики ім. В.М.Глушкова НАН України
Опис
Вперше розглянуто комбінаторні задачі оптимізації потоку в транспортних мережах. Доведено NP-важкість комбінаторної задачі знахо-дження максимального потоку та комбінаторної задачі знаходження потоку мінімальної вартості. Математичною моделлю розглянутих задач є задачі евклідової комбінаторної оптимізації. Для їх розв'язування запропонований і обґрунтований прямий метод комбі-наторного відсікання. Для наближеного розв'язування комбінаторної задачі знаходження максимального потоку запропонований жадібний метод. Зроблено оцінку його складності. Метод гілок та меж і метод імітації відпалу застосований для розв'язування комбінаторної задачі знаходження максимального потоку. Для запропонованих методів проведені обчислювальні експерименти.
Дата реєстрації
2014-05-08
Додано/оновлено в НРАТ
2020-04-04 / 2026-06-29