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