Об одном методе декомпозиции для решения задач синтеза коммуникационных сетей
- Авторы: Косоруков О.А1, Лемтюжникова Д.В2,3
-
Учреждения:
- МГУ им. М.В. Ломоносова
- Институт проблем управления им. В.А. Трапезникова РАН
- МАИ (национальный исследовательский университет)
- Выпуск: № 3 (2023)
- Страницы: 3-11
- Раздел: Математические проблемы управления
- URL: https://bakhtiniada.ru/1819-3161/article/view/286628
- DOI: https://doi.org/10.25728/pu.2023.3.1
- ID: 286628
Цитировать
Полный текст
Аннотация
Рассматривается алгоритм решения задачи о формировании коммуникационной сети для нахождения гарантированного плана перевозок заданного объема при наличии неопределенных факторов. Объемы производств и пропускные способности коммуникаций выражены линейными функциями от вложенных ресурсов. Для решения двойственной задачи, в силу ее ступенчатой блочной структуры, применяется известный алгоритм декомпозиции Данцига – Вулфа. Возникающие на итерациях линейные задачи предлагается решать, используя их специфику, на основе эффективных сетевых методов и методов теории графов, а именно: нахождения максимального потока, минимального разреза в сети, компонент связности и минимальных остовных деревьев графов. Существующие для этих задач алгоритмы имеют оценки сложности О( ), О( ) и О(n+m), где n – число вершин графа, m – число ребер.
Об авторах
О. А Косоруков
МГУ им. М.В. Ломоносова
Email: kosorukovoa@mail.ru
г. Москва, Россия
Д. В Лемтюжникова
Институт проблем управления им. В.А. Трапезникова РАН; МАИ (национальный исследовательский университет)
Email: darabbt@gmail.com
г. Москва, Россия
Список литературы
- Давыдов Э.Г. Игры, графы, ресурсы. – М.: Радио и связь, 1981. – 112 с. [Davydov, E.G. Games, Gaphs, Resources. – M.: Radio and svyaz, 1981. – 112 s. (In Russian)]
- Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы. – М.: Наука, 1975. – 118 с. [Adelson-Velsky, G.M., Dinits, E.A., Karzanov, A.V. Streaming Algorithms. – Moscow: Nauka, 1975. – 118 p. (In Russian)]
- Гейл Д. Теория линейных экономических моделей. – М.: Изд-во иностр. лит., 1963. – 418 с. [Gale, D. Theory of Linear Economic Models. – N.-Y.: McGraw-Hill, 1960.]
- Романовский И.В. Алгоритмы решения экстремальных задач. – М.: Наука, 1977. – 352 с. [Romanovsky, I.V. Algorithms for Solving Extreme Problems. – Moscow: Nauka, 1977. – 352 p. (In Russian)]
- Лемешко В.Ю. Методы оптимизации: лекции. – Новосибирск: Изд-во НГУ, 2009. – 126 с. [Lemeshko, V.Yu. Optimization Methods: Lectures. – Novosibirsk: Publishing House of NSU, 2009. – 126 p. (In Russian)]
- Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования. – М.: Радио и связь, 1982. – 240 с. [Raskin, L.G., Kirichenko, I.O. Multi-index Problems of Linear Programming. – Moscow: Radio and Communication, 1982. – 240 p. (In Russian)]
- Серая О.В. Многомерные модели логистики в условиях неопределенности: монография. – Харьков: ФОП Стеценко И.И., 2010. – 512с. [Seraya, O.V. Multidimensional Models of Logistics Under Uncertainty: monograph. – Kharkov: FOP Stetsenko, I.I., 2010. – 512p. (In Russian)]
- Конюховский П.В. Математические методы исследования операций в экономике. – СПб: Питер, 2000. – 208 с. [Konyukhovsky, P.V. Mathematical Methods for Researching Operations in Economics. – St. Petersburg: Peter, 2000. – 208 p. (In Russian)]
- Kosorukov, O. The Algorithm of the Method of Generalized Potentials for the Problem of Optimal Synthesis of Communication Network // International Journal of Communications. – 2017. – Vol. 2. – P. 77–85.
- Kosorukov, O.A. Algorithm of the Method of Generalized Potentials for Problems of the Optimum Synthesis of Communication Networks with Undefined Factors // Moscow University Computational Mathematics and Cybernetic. – 2019. – Vol. 43, no. 3. – P. 138–142.
- Майника Э. Алгоритмы оптимизации на сетях и графах. Пер. с англ. – М.: Мир, 1981. – 324 c. [Minieka, E. Optimization Algorithms for Networks and Graphs. – N.-Y.: M. Dekker, 1978.]
- Лэсдон Л. С. Оптимизация больших систем. Пер. с англ. – М.: Наука, 1975. – 432 c. [Lasdon, L. S. Optimization Theory for Large Systems. – London: Macmillan & Co., 1970.]
- Берж К. Теория графов и ее применения. – М.: Изд-во иностр. лит. – 1967. – 320 с. [Berge, C. Theory of Graphs and Its Applications. – London : Methuen, 1962.]
- Берзин Е.А. Оптимальное распределение ресурсов и элементы синтеза систем. – М.: Сов. радио, – 1974. – 303 с. [Berzin, E.A. Optimal Distribution of Resources and Elements of Systems Synthesis. – Moscow: Sov. Radio. – 1974. – 303 p. (In Russian)]
- Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании // ДАН СССР. – 1979. – T. 244. – С. 1093–1096. [Khachiyan, L. A Polynomial Algorithm in Linear Programming // Soviet Mathematics Doklady – 1979. – Vol. 20. – P. 191–194.]
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – М.: Вильямс. – 2005. – 1296 с. [Cormen, T.H., Leiserson, Ch.E., Rivest, R.L, and Stein, C. Introduction to Algorithms, 3rd ed. Cambridge: MIT Press, 2009.]
- Седжвик P. Алгоритмы на графах. – Россия, Санкт-Петербург: «ДиаСофтЮП». – 2002. – 496 с. [Sedgwick, R. Algorithms on Graphs. – Boston: Addison-Wesley Professional, 2002. – 496 p.]
- Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. Пер. с англ. – М.: Мир, 1966. – 277 с. [Ford, L.R., Fulkerson, D.R. Flows in Networks. – Princeton, N.J.: Princeton University Press, 1962.]
- Hanaka, T., Kanemoto, K., Kagawa, S. Multi-perspective Structural Analysis of Supply Chain Networks // Economic Systems Research. – 2022. – Vol. 34, iss. 2. – P. 199–214.
- Turken, N., Cannataro, V., Geda, A., Dixit, A. Nature Inspired Supply Chain Solutions: Definitions, Analogies, and Future Research Directions // International Journal of Production Research. – 2020. – Vol. 58, iss. 15. – P. 91–102.
Дополнительные файлы
