zbMATH — the first resource for mathematics

Search for normal solutions in linear programming problems. (English. Russian original) Zbl 1030.90052
Comput. Math. Math. Phys. 40, No. 12, 1694-1714 (2000); translation from Zh. Vychisl. Mat. Mat. Fiz. 40, No. 12, 1766-1786 (2000).
Summary: For the general problem of Linear Programming (LP) given in the canonical form, form versions of necessary and sufficient optimality conditions differing in the number of variables and constraints of the types of equalities and inequalities, are considered. With the help of one of these conditions, a normal solution to the primal LP problem and a normal vector of optimal residuals of the dual LP problem are found as a result of a single act of unconstrained maximization of a concave smooth piecewise quadratic function. The number of variables in this problem exceeds the number of variables in the primal LP problem by one. The relationship of the unconstrained maximization problem with the methods of regularization and quadratic penalization for the LP problem is revealed. Some estimates for the regularization parameter and penalty coefficient are given, beginning with which the solutions obtained by these methods allow one to find the normal solution to the LP problem.

90C05 Linear programming
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)