Об одном методе декомпозиции для решения задач синтеза коммуникационных сетей

Рассматривается алгоритм решения задачи о формировании коммуникационной сети для нахождения гарантированного плана перевозок заданного объема при наличии неопределенных факторов. Объемы производств и пропускные способности коммуникаций выражены линейными функциями от вложенных ресурсов. Для решения двойственной задачи, в силу ее ступенчатой блочной структуры, применяется известный алгоритм декомпозиции Данцига – Вулфа. Возникающие на итерациях линейные задачи предлагается решать, используя их специфику, на основе эффективных сетевых методов и методов теории графов, а именно: нахождения максимального потока, минимального разреза в сети, компонент связности и минимальных остовных деревьев графов. Существующие для этих задач алгоритмы имеют оценки сложности $O(mn^2)$, $O(n^2m)$ и $O(n+m)$, где $n$ — число вершин графа, $m$ — число ребер.