Geodesic
A simple algorithm for finding a non-negative basic solution of a system of linear algebraic equations
Modelirovanie i analiz informacionnyh sistem, Tome 28 (2021) no. 3, pp. 234-237.

Voir la notice de l'article provenant de la source Math-Net.Ru

This article describes an algorithm for obtaining a non-negative basic solution of a system of linear algebraic equations. This problem, which undoubtedly has an independent interest, in particular, is the most time-consuming part of the famous simplex method for solving linear programming problems. Unlike the artificial basis Orden's method used in the classical simplex method, the proposed algorithm does not attract artificial variables and economically consumes computational resources.The algorithm consists of two stages, each of which is based on Gaussian exceptions. The first stage coincides with the main part of the Gaussian complete exclusion method, in which the matrix of the system is reduced to the form with an identity submatrix. The second stage is an iterative cycle, at each of the iterations of which, according to some rules, a resolving element is selected, and then a Gaussian elimination step is performed, preserving the matrix structure obtained at the first stage. The cycle ends either when the absence of non-negative solutions is established, or when one of them is found. Two rules for choosing a resolving element are given. The more primitive of them allows for ambiguity of choice and does not exclude looping (but in very rare cases). Use of the second rule ensures that there is no looping.
Keywords: linear equation systems, linear programming, the rule of choosing a resolving element.
Mots-clés : nonnegative solution 
@article{MAIS_2021_28_3_a1,
     author = {G. D. Stepanov},
     title = {A simple algorithm for finding a non-negative basic solution of a system of linear algebraic equations},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {234--237},
     publisher = {mathdoc},
     volume = {28},
     number = {3},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2021_28_3_a1/}
}
TY  - JOUR
AU  - G. D. Stepanov
TI  - A simple algorithm for finding a non-negative basic solution of a system of linear algebraic equations
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2021
SP  - 234
EP  - 237
VL  - 28
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2021_28_3_a1/
LA  - ru
ID  - MAIS_2021_28_3_a1
ER  - 
%0 Journal Article
%A G. D. Stepanov
%T A simple algorithm for finding a non-negative basic solution of a system of linear algebraic equations
%J Modelirovanie i analiz informacionnyh sistem
%D 2021
%P 234-237
%V 28
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2021_28_3_a1/
%G ru
%F MAIS_2021_28_3_a1
G. D. Stepanov. A simple algorithm for finding a non-negative basic solution of a system of linear algebraic equations. Modelirovanie i analiz informacionnyh sistem, Tome 28 (2021) no. 3, pp. 234-237. http://geodesic.mathdoc.fr/item/MAIS_2021_28_3_a1/

[1] S. I. Gass, Linear programming: methods and applications, McGraw-Hill, New York, 1958 | Zbl

[2] D. B. Yudin, E. G. Holstein, Linear programming, Nauka, M., 1963

[3] G. Dantzig, Linear programming, its applications and generalizations, Princeton University Press, 1963

[4] T. Hu, Integer programming and network flows, Addison-Wesley, 1969 | Zbl

[5] S. Ashmanov, Linear programming, Nauka, M., 1981 | Zbl

[6] C. H. Papadimitriou, K. Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, 1982 | Zbl

[7] A. Schrijver, Theory of linear and integer programming, Mir, M., 1991

[8] F. P. Vasiliev, A. Y. Ivanitsky, Linear programming, MCCME, 2020

[9] V. Klee, G. J. Minty, How good is the simplex algorithm?, Inequalities, 3:3 (1972), 159–175