Поиск Потока В Несовместных Транспортных Сетях

Работа посвящена проблеме поиска потока в несовместной транспортной сети с двусторонними пропускными способностями дуг. При исследовании несовместных потоковых моделей рассматривается задача минимизации суммарных штрафов за изменения пропускных способностей сети. Предлагаемый алгоритм решения рассматриваемой задачи основан на сводимости к задаче поиска потока минимальной стоимости. В случае древовидной структуры сети предлагается алгоритм решения задачи, основанный на методе приведенных границThe paper covers the problem of finding flow in infeasible transport type network with two-side arc capacities. Minimization problem of overall penalty for capacities modification was considered while investigating of infeasible network flow models. Proposed algorithm of solving the considered problem is based on reduction to min-cost network flow problem. In the case of tree-like network algorithm of solving the considered problem based on bounds reduction method is proposed