IJPAM: Volume 54, No. 2 (2009)

ALGORITHMS FOR CONSTRUCTION OF OPTIMAL AND
SUBOPTIMAL SOLUTIONS IN NETWORK
OPTIMIZATION PROBLEMS

L.A. Pilipchuk$^1$, A.S. Pilipchuk$^2$, Y.H. Pesheva$^3$
$^1$Belarussian State University
4, Nezalezhnosti Ave., Minsk, 220050, BELARUS
e-mail: [email protected]
$^2$State Scientific Institution
99, Academician A.K. Krasin Str., Minsk, 220109, BELARUS
e-mail: [email protected]
$^3$Department of Differential Equations
Faculty of Applied Mathematics and Informatics
Technical University of Sofia
P.O. Box 384, Sofia, 1000, BULGARIA
e-mail: [email protected]


Abstract.For a distributive flow programming optimization problem of a special structure direct and dual algorithms are constructed. These algorithms are based on a research of the theoretical and graph properties of the solution space bases. Optimality conditions are received, that allow to calculate a part of the components of the Lagrange vector. Algorithms that decompose calculation systems for pseudo-plans of the problem are presented. Suitable directions for change of the dual criterion function are constructed.

Received: October 10, 2008

AMS Subject Classification: 05C50, 15A03, 15A06, 65K05, 90C08, 90C35

Key Words and Phrases: sparse linear system, underdetermined system, direct method, dual method, basis of a solution space of a homogeneous linear system, decomposition of a system, network, network support, spanning tree, fundamental system of cycles, characteristic vector, optimality and suboptimality plan, pseudo-plan

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2009
Volume: 54
Issue: 2