Олексійчук Ю. Ф. Комбінаторні задачі оптимізації потоку в мережі і методи їх розв’язування

Вперше розглянуто комбінаторні задачі оптимізації потоку в транспортних мережах. Доведено NP-важкість комбінаторної задачі знахо-дження максимального потоку та комбінаторної задачі знаходження потоку мінімальної вартості. Математичною моделлю розглянутих задач є задачі евклідової комбінаторної оптимізації. Для їх розв'язування запропонований і обґрунтований прямий метод комбі-наторного відсікання. Для наближеного розв'язування комбінаторної задачі знаходження максимального потоку запропонований жадібний метод. Зроблено оцінку його складності. Метод гілок та меж і метод імітації відпалу застосований для розв'язування комбінаторної задачі знаходження максимального потоку. Для запропонованих методів проведені обчислювальні експерименти.