Selecting Different Dropping Variables in the Simplex Algorithm

摘要

At any interaction (after the first) of the simplex algorithm, it may be possible to secure additional objective function decrease by making basic the variable which left the basis at the last iteration, we well as the one chosen by the usual criterion. In solving linear programs on a computer, this decrease can be obtained without the time-consuming searching of external memory required to perform a complete iteration. The report presents tests for determining when such a procedure will be beneficial, describes an algorithm incorporating these ideas, and summarizes computational results for some sample problems. (Author)