Geodesic
Algorithm for finding of a non-negative solution for linear system of equations
Čelâbinskij fiziko-matematičeskij žurnal, Tome 1 (2016) no. 2, pp. 68-77 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The new algorithm for finding of the exact solution for the linear programming problem is constructed. The method is based on the converting of the linear programming problem to the problem of solving in nonnegative numbers for a system of linear equations with an incomplete rank. This problem is solved by successive approximations in specially constructed subspaces. The convergence of the algorithm for a finite number of the steps is proved. The algorithm has been tested on the data of the Klee–Minty problem and on a set of random tests.
Keywords: algorithm of linear programming, non-negative solution of linear system of equations, linear inequality. 
@article{CHFMJ_2016_1_2_a6,
     author = {Y. N. Sevostyanov and M. G. Leptchinski},
     title = {Algorithm for finding of a non-negative solution for linear system of equations},
     journal = {\v{C}el\^abinskij fiziko-matemati\v{c}eskij \v{z}urnal},
     pages = {68--77},
     year = {2016},
     volume = {1},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHFMJ_2016_1_2_a6/}
}
TY  - JOUR
AU  - Y. N. Sevostyanov
AU  - M. G. Leptchinski
TI  - Algorithm for finding of a non-negative solution for linear system of equations
JO  - Čelâbinskij fiziko-matematičeskij žurnal
PY  - 2016
SP  - 68
EP  - 77
VL  - 1
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CHFMJ_2016_1_2_a6/
LA  - ru
ID  - CHFMJ_2016_1_2_a6
ER  - 
%0 Journal Article
%A Y. N. Sevostyanov
%A M. G. Leptchinski
%T Algorithm for finding of a non-negative solution for linear system of equations
%J Čelâbinskij fiziko-matematičeskij žurnal
%D 2016
%P 68-77
%V 1
%N 2
%U http://geodesic.mathdoc.fr/item/CHFMJ_2016_1_2_a6/
%G ru
%F CHFMJ_2016_1_2_a6
Y. N. Sevostyanov; M. G. Leptchinski. Algorithm for finding of a non-negative solution for linear system of equations. Čelâbinskij fiziko-matematičeskij žurnal, Tome 1 (2016) no. 2, pp. 68-77. http://geodesic.mathdoc.fr/item/CHFMJ_2016_1_2_a6/

[1] I. I. Dikin, “Iterative solving of linear and quadratic programming problems”, USSR Academy of Science Reports, 174:4 (1967), 745–747 (In Russ.) | MR

[2] A. Schrijver, Theory of Linear and Integer Programming, Wiley–Interscience series in discrete mathematics, John Wiley Sons, Chichester, 1986, xi+471 pp. | MR | Zbl

[3] N. Mollaverdi, Methods for solving of linear optimization problems with large dimension, Thesis, Moscow, 2005, 96 pp. (In Russ.)

[4] N. Karmarkar, “A new polynomial-time algorithm for linear programming”, Combinatorica, 1984, no. 4, 373–395 | DOI | MR | Zbl

[5] B. A. Rozenfel'd, Multidimensional spaces, Nauka Publ., Moscow, 1966, 648 pp. (In Russ.) | MR

[6] V. Klee, G. J. Minty, How good is the Simplex algorithm?, Inequalities: III, ed. O. Shisha, Academic Press, New York, 1972, 158–175 | MR

[7] E. Nikolaevskaya, A. Khimich, T. Chistyakova, Programming with Multiple Precision, Studies in Computational Intelligence, 397, Springer, Richmond, USA, 2012, 234 pp.