
This article presents a strongly polynomial-time algorithm for the general linear programming problem. This algorithm is an implicit reduction procedure that works as follows. Primal and dual problems are combined into a special system of linear equations constrained by complementarity relations and non-negative variables. Each iteration of the algorithm consists of applying a pair of complementary Gauss-Jordan pivoting operations, guided by a necessary-condition lemma. The algorithm requires no more than k+n iterations, as there are only k+n complementary pairs of columns to compare one-pair-at-a-time, where k is the number of constraints and n is the number of variables of given general linear programming problem. Numerical illustration is given that includes an instance of a classical problem of Klee and Minty and a problem of Beale.
29 pages; Based on latest reviewers' and readers' suggestions, new annotations and remarks have been added to aid efficient reading and volunteered reviews. The results are the same as before
Optimization and Control (math.OC), Optimization and Control, FOS: Mathematics, Math OC
Optimization and Control (math.OC), Optimization and Control, FOS: Mathematics, Math OC
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
