Об одном методе декомпозиции для решения задач синтеза коммуникационных сетей
| Jazyk: | ruština |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| DOI: | 10.25728/pu.2023.3.1 |
| Popis: | Рассматривается алгоритм решения задачи о формировании коммуникационной сети для нахождения гарантированного плана перевозок заданного объема при наличии неопределенных факторов. Объемы производств и пропускные способности коммуникаций выражены линейными функциями от вложенных ресурсов. Для решения двойственной задачи, в силу ее ступенчатой блочной структуры, применяется известный алгоритм декомпозиции Данцига – Вулфа. Возникающие на итерациях линейные задачи предлагается решать, используя их специфику, на основе эффективных сетевых методов и методов теории графов, а именно: нахождения максимального потока, минимального разреза в сети, компонент связности и минимальных остовных деревьев графов. Существующие для этих задач алгоритмы имеют оценки сложности О( mn2 ), О(n2m ) и О(n+m), где n – число вершин графа, m – число ребер. This paper presents a communication network design algorithm for finding a guaranteed transportation plan of a given volume under uncertain factors. The volumes of production and the capacities of communication lines are expressed as linear functions of invested resources. The well-known Dantzig–Wolfe decomposition algorithm is applied to solve the dual problem due to its stepped block structure. In view of their specifics, the linear problems arising in iterations are solved using effective network and graph theory methods: the maximum flow, the minimum cutset in the network, the connectivity components, and the minimum spanning trees of the graphs are found. The existing algorithms for these problems have the complexity estimates О(mn2), О(n2m), and O(n + m), where n is the number of graph vertices and m is the number of edges. Проблемы управления, Выпуск 3 2023, Pages 3-11 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|