AUTHORS: Oleg Kosorukov
Download as PDF
ABSTRACT: A new efficient algorithm for linear separable problem of synthesis of communication network, titled 'method of generalized potentials', has been developed and validated. It is close to the wellknown method of potentials for solving the classical transportation problem. The proposed algorithm has been developed for the Gale problem on demand and supply. The finiteness of the algorithm and the inability of the looping situations have been proved.
KEYWORDS: supply and demand problem, distribution of resources, linear programming, duality theory, method of potentials, spanning subtree
REFERENCES:
[1] Romanovsky I.V. Algorithms for solving extremal problems. - Moscow: Science, 1977.
[2] Lemeshko B.Yu., Optimization Methods: Lecture notes. - Novosibirsk: Publishing house of NSTU, 2009.
[3] Gale D. the Theory of linear economic models. – M.: IL, 1963. – 418 p
[4] Davydov E.G. Games, graphs, resources. – M.: Radio and communication, 1981, -112 p.
[5] Adelson-Velskiy, G.M., dinic E. A., Karzanov A.V. Streaming algorithms. - M.: Nauka, 1975. – 118 p
[6] Kosorukov O.A., Davydov E. G. Some Questions of Nonlinear Synthesis of Communication Networks - Moscow University Computational Mathematics and Cybernetics (Vestnik Moskovskogo Universiteta. Seriya 15. Vychislitel'naya Matematika i Kibernetika) Allerton Press Inc. (USA). – 1986. - № 2. - pp. 31- 36.
[7] O.A. Kosorukov Optimization Problems of Transportation in Communication Networks with Variable Capacities - Journal of Computer and Systems Sciences International, 2016, Vol. 55, No. 6, pp. 1010-1015.
[8] O.A. Kosorukova, A.G. Belov The Problem of Controlling Resources on Network Graphs as an Optimal Control Problem. Moscow University Computational Mathematics and Cybernetics, 2014, Vol. 38, No. 2, pp. 59–63.
[9] Solmaz S. Kia, Distributed optimal in-network resource allocation algorithm design via a control theoretic approach, Systems & Control Letters, Volume 107, September 2017, Pages 49-57.
[10] Lasdon LS Optimization of large systems. -M .: Science, 1975. - 432 p
[11] Tsurkov V.I. Decomposition in problems of large dimension. –M.: Science, 1981, -352p.