RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы управления // Архив

Пробл. управл., 2023, выпуск 3, страницы 3–11 (Mi pu1313)

Математические проблемы управления

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

О. А. Косоруковa, Д. В. Лемтюжниковаbc

a МГУ им. М.В. Ломоносова, г. Москва
b Институт проблем управления им. В.А. Трапезникова РАН, г. Москва
c МАИ (национальный исследовательский университет), г. Москва

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

Ключевые слова: задача о спросе и предложении, коммуникационные сети, линейный синтез, методы декомпозиции, максимальный поток, минимальный разрез, минимальное остовное дерево.

УДК: 519.863

Поступила в редакцию: 23.03.2023
Исправленный вариант: 13.05.2023
Принята в печать: 15.05.2023

DOI: 10.25728/pu.2023.3.1


 Англоязычная версия: Control Sciences, 2023:3, 2–8


© МИАН, 2024