Исследование сетевых оптимизационных моделей и разработка алгоритмов решения задач дискретной и многокритериальной оптимизации на графах

Abstract

Объектом исследования являются задачи оптимизации, которые допускают формулировку в терминах теории графов. Большинство известных алгоритмов решения таких задач связаны с метками вершины графа. Что предполагает его графическое представление. Это делает достаточно сложной программную реализацию таких алгоритмов. Целью работы является разработка алгоритмов решения задач сетевой оптимизации основанных на матричном представлении графа. В процессе работы были разработаны, на основе обобщения аппарата тернарных операций, алгоритмы решения задач о многополюсных максимальных потоках, задачи о назначениях, обобщенной транспортной задачи, а также задач многокритериальной потоковой оптимизации и сетевого планирования.