scientific article; zbMATH DE number 4027164

From MaRDI portal
Publication:3768671





Our paper presents two new algorithms for solving linear programming problems. These algorithms are based on the convergent criss-cross method and on the idea of the ``Hungarian Method. Similarly to the primal dual algorithm of Dantzig, Ford and Fulkerson, our algorithms improve a feasible (may be not basic) solution step by step, but we use the second author's [Optimization 16, 683-690 (1985; Zbl 0581.90052)] convergent criss-cross method for solving the subproblems. Our algorithms solve linear programming problems in a finite number of steps (i.e. cycling cannot occur). We show that the primal and dual simplex methods are special cases of our algorithms. In these simplex methods we use \textit{R. G. Bland}'s [Math. Oper. Res. 2, 103-107 (1977; Zbl 0408.90050)] pivoting rule only if the basic transformations are degenerate. By this we show that one can derive the primal or dual simplex method from Terlaky's criss-cross method.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3768671)