A computationally stable solution algorithm for linear programs

摘要

An active area of research for linear programming is to construct initial Simplex tableau that is close to the optimal solution, and to improve its pivoting selection strategies efficiently. In this paper, we present a new approach to the problem of initialization and pivoting rules: the algorithm is free from any artificial variables and artificial constraints, known as the big-M methods. By supplying the Simplex method without using any large numbers, therefore the result is computationally stable and provides a better initial basis that reduces the number of pivoting iterations efficiency. A three-phase simplex type solution algorithm is developed for solving general linear programs. In phase 1, greater-than constraints are relaxed and the problem is solved starting at the origin. If it is unbounded; then the objective function is modified in order to have a bound feasible solution. Then, in phase 2 the greater-than constraints are introduced in a dual simplex framework. Following this, in the case the original objective function was modified, phase 3 restores optimality for the original objective function. The algorithm is numerically stable and works with the original decision variables. Our initial experimental study indicates that the proposed algorithm is more efficient than both the primal and the dual simplex in terms of the number of iterations.