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