Solving linear programming problems by reducing to the form with an obvious answer

G. D. Stepanov

Modelirovanie i analiz informacionnyh sistem, Tome 28 (2021) no. 4, pp. 434-451.

Résumé

The article considers a method for solving a linear programming problem (LPP), which requires finding the minimum or maximum of a linear functional on a set of non-negative solutions of a system of linear algebraic equations with the same unknowns. The method is obtained by improving the classical simplex method, which when involving geometric considerations, in fact, generalizes the Gauss complete exclusion method for solving systems of equations. The proposed method, as well as the method of complete exceptions, proceeds from purely algebraic considerations. It consists of converting the entire LPP, including the objective function, into an equivalent problem with an obvious answer. For the convenience of converting the target functional, the equations are written as linear functionals on the left side and zeros on the right one. From the coefficients of the mentioned functionals, a matrix is formed, which is called the LPP matrix. The zero row of the matrix is the coefficients of the target functional, $a_{00}$ is its free member. The algorithms are described and justified in terms of the transformation of this matrix. In calculations the matrix is a calculation table. The method under consideration by analogy with the simplex method consists of three stages. At the first stage the LPP matrix is reduced to a special 1-canonical form. With such matrices one of the basic solutions of the system is obvious, and the target functional on it is $ a_{00}$, which is very convenient. At the second stage the resulting matrix is transformed into a similar matrix with non-positive elements of the zero column (except $a_{00}$), which entails the non-negativity of the basic solution. At the third stage the matrix is transformed into a matrix that provides non-negativity and optimality of the basic solution. For the second stage the analog of which in the simplex method uses an artificial basis and is the most time-consuming, two variants without artificial variables are given. When describing the first of them, along the way, a very easy-to-understand and remember analogue of the famous Farkas lemma is obtained. The other option is quite simple to use, but its full justification is difficult and will be separately published.

Détail

Keywords: linear programming, simplex method, resolving element, choice rule, Farkas lemma, systems of linear equations, non-negative solution.
Mots-clés : Gauss method, LPP matrix

Bibliographie

[1] S. I. Gass, Linear Programming: Methods and Applications, McGraw-Hill, New York, 1958 | Zbl

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

[3] D. B. Yudin, E. G. Holstein, Linear Programming: theory and finite methods, Fizmatlit, M., 1963

[4] G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, 1963 | Zbl

[5] T. S. Hu, Integer programming and networkows, Addison-Wesley, 1969

[6] S. A. Ashmanov, Linear Programming, Nauka, M., 1981 | Zbl

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

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

[9] E. Stiefel, “Note on Jordan elimination, linear programming and Tchebycheff approximation”, Numerische Mathematik, 2:1 (1960), 1–17 | DOI | MR | Zbl

[10] S. I. Zukhovitsky, L. I. Avdeeva, Linear and Convex Programming, Nauka, M., 1967

[11] A. Charnes, “Optimality and degeneracy in linear programming”, Econometrica: Journal of the Econometric Society, 20:2 (1952), 160–170 | DOI | MR | Zbl

[12] R. G. Bland, “New finite pivoting rules for the simplex method”, Mathematics of Operations Research, 2:2 (1977), 103–107 | DOI | MR | Zbl

[13] H. W. Kuhn, Class Notes, Princeton University, 1976

[14] A. S. Barsov, What is Linear Programming, Fizmatgiz, M., 1959

[15] V. G. Karmanov, Mathematical Programming, Fizmatlit, M., 2004

[16] Y. G. Evtushenko, A. A. Tret'yakov, E. E. Tyrtyshnikov, “New approach to Farkas' theorem of the alternative”, Doklady Mathematics, 99 (2019), 208–210 | DOI | Zbl

[17] G. D. Stepanov, “A Simple Algorithm for Finding a Non-negative Basic Solution of a System of Linear Algebraic Equations”, Modeling and analysis of information systems, 28:3 (2021), 234–237 | DOI | MR