A procedure for choosing incoming and exiting variables in the simplex algorithm

Abstract

A new selection of input-output variables for a simplex algorithm in linear programming (LP) problems is introduced in this paper. An appropriate pivot rule to find the entering and leaving variable is one of fundamental steps for simplex method. Unfortunately, such a classical pivot does not only fail to bring about any savings in a associated computational cost, it may also lead to cycling problems (which are typically solved by Bland's scheme) or simply it fails to improve the objective function. Combining the perturbation scheme of suboptimality and cycling, with Dantzig's pivot rule we propose a procedure that addresses these issues. The new rule has an improved algorithm effectiveness in the sense of the reduction for the number of iterations. When compared to those of existing pivot rules, calculational results demonstrate that the suggested rule is not only optimal during each iteration but also facilitates improvements in computation time for linear programming problems. The cycle problem of the Dantzig's simplex pivot rule is settled by a new pivot rule proposed, which similarly as much improves the objective function How possible with every iteration. Moreover, it can have the optimal LP value in less iterations.