L.A. Pilipchuk, A.S. Pilipchuk, Y.H. Pesheva
Belarussian State University
4, Nezalezhnosti Ave., Minsk, 220050, BELARUS
e-mail: pilipchuk@bsu.by
State Scientific Institution
99, Academician A.K. Krasin Str., Minsk, 220109, BELARUS
e-mail: pilip74@rambler.ru
Department of Differential Equations
Faculty of Applied Mathematics and Informatics
Technical University of Sofia
P.O. Box 384, Sofia, 1000, BULGARIA
e-mail: yhp@vmei.acad.bg

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