Geodesic
Method for sequential activation of limitations in~linear programming
Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 110-125.

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

In this paper, we present an algorithm for solving a problem in linear programming by means of procedure of sequential activation of limitations (inclusions in calculation are made one after another) with retention of the optimality status in the generated sequence of nested polyhedrons. Due to compression of the admissible solutions area, the objective function decreases on each step at the “max” criterion of an optimality (the movement to a maximum “from above”) contrary to its growth in other methods (“from below”). Geometrically, the motion to the maximum starts from the trivially determined starting point and continues along the broken line outside of the polytope of admissible solutions. In the theoretical justification of the algorithm, the signs for the incompatibility of the system of conditions in the problem, for the uniqueness and nonuniqueness of the solution, and for its unboundedness are formulated and proved. Computer experiments demonstrate the advantages of the program implementation of this algorithm in speed and completeness of the output information over the simplex-method option of the MATLAB's library linprog program.
Keywords: linear programming, activation of limitation, MATLAB, computer experiment. 
@article{PDM_2018_3_a10,
     author = {V. S. Kolosov},
     title = {Method for sequential activation of limitations in~linear programming},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {110--125},
     publisher = {mathdoc},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2018_3_a10/}
}
TY  - JOUR
AU  - V. S. Kolosov
TI  - Method for sequential activation of limitations in~linear programming
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2018
SP  - 110
EP  - 125
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2018_3_a10/
LA  - ru
ID  - PDM_2018_3_a10
ER  - 
%0 Journal Article
%A V. S. Kolosov
%T Method for sequential activation of limitations in~linear programming
%J Prikladnaâ diskretnaâ matematika
%D 2018
%P 110-125
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2018_3_a10/
%G ru
%F PDM_2018_3_a10
V. S. Kolosov. Method for sequential activation of limitations in~linear programming. Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 110-125. http://geodesic.mathdoc.fr/item/PDM_2018_3_a10/

[1] Kantorovich L. V., Mathematical Methods in the Organization and Planning of Production, News of Leningrad State University, Leningrad, 1939, 67 pp. (in Russian)

[2] Dantzig J., Linear Programming, its Application and Generalizations, Progress Publ., Moscow, 1966, 600 pp. (in Russian)

[3] Yudin D. B., Golstein E. G., Linear Programming: Theory, Methods and Applications, Nauka Publ., Moscow, 1969, 424 pp. (in Russian) | MR

[4] Dikin I. I., “Iterative solution of problems of linear and quadratic programming”, Report AS USSR, 174 (1967), 747–748 (in Russian) | MR | Zbl

[5] Khachiyan L. G., “Polynomial algorithm in linear programming”, Report AS USSR, 244 (1979), 1093–1096 (in Russian) | Zbl

[6] Zorkaltsev V. I., “Dual algorithms of interior-points”, Iz. VUZ, Mathematics, 2011, no. 4, 33–53 (in Russian) | Zbl

[7] Zorkaltsev V. I., Medvejonkov D. S., “Computational experiments with variants of interior-point algorithms for nonlinear flow distribution problems”, Upravlenie bolshimi sistemami, 46, Institute of Energy Systems of SB RAS, 2013, 68–87 (in Russian)

[8] Medvejonkov D. S., “Experimental researches of interior- point algorithms for solution of flow distribution nonlinear problems”, Bulletin of the Buryat State University, 2013, no. 9, 12–16 (in Russian)

[9] Vylegzhanin O. N., Skatova G. I., “The solution of the linear programming problem using the operator-projector”, News Tomsk Polytechnic University, 314:5 (2009), 37–40 (in Russian)

[10] Bakhshiyan B. Ts., Gurianov A. V., “The skeletal algorithm for solving the linear programming problem and its application for solving estimation problems”, Bulletin MAI, 15:2 (2008), 5–16 (in Russian)

[11] Gordunovski V. M., The Method of Exponential Approximation for Linear Programming, Editus Publ., Moscow, 2013, 32 pp. (in Russian)

[12] Kolosov V. S., “The finite parametric method for solving linear programming problem”, Scientific Works MLTI, 103, 1978, 197–198 (in Russian)

[13] Kolosov V. S., “The role of dual estimates in the parametric method for solving the linear programming problem”, Scientific Works MLTI, 183, 1986, 51–54 (in Russian)

[14] Karmanov V. G., Mathematical Programming, FIZMATLIT Publ., Moscow, 2004, 264 pp.