A method for selecting entering and leaving variables In the simplex algorithm

In this article, a novel method for selecting input and output variables in the simplex algorithm is introduced for solving linear programming (LP) problems. One of the critical stages of the simplex algorithm is the application of a proper pivot rule to determine the entering and exiting variables. Unfortunately, this classical pivot rule may not only fail to minimize the associated computational cost but also lead to cycling issues (addressed by the Bland’s Rule) or fail to effectively enhance the objective function. The proposed method focuses on improving the Dantzig’s pivot rule, aiming to address issues such as cycling and suboptimality. By reducing the number of iterations, the new rule enhances the overall algorithmic efficiency. Computational results demonstrate that the proposed rule not only ensures optimality in each step but also reduces the time needed to solve linear problems compared to existing pivot rules. The proposed new pivot rule solves the cycling problem in the original Dantzig’s simplex pivot rule and leads to an optimal improvement of the objective function at each iteration. In addition, can lead to the optimal solution of LP with a lower number of iterations.

کلیدواژه ها:

Linear Programming ، Simplex Algorithm ، Pivot Rule ، Iteration Reduction ، Optimization