关于线性规划问题退化解的教学思考

On the Teaching of Degenerate Solutions to Linear Programming Problems

摘要: 本文通过三个实例探讨了线性规划问题退化解的单纯形法求解。退化可能带来单纯形法求解效率下降，在高度退化情形下，进基变量或离基变量选择不当，可能陷入退化循环；退化可能导致最优解的误判或遗漏。当线性规划问题存在退化最优解时，多重最优解的判定准则失效，最优解具有唯一性，但最优基可能有多个。

Abstract: This paper illustrates how to solve degenerate solutions to linear programming problems using the simplex method with three examples. Degeneracy might have the simplex method become not very efficient. In the circumstance of highly degeneracy, wrong selection of entering basic variables or leaving basic variables could have the iterations go round in a perpetual loop. Degeneracy could cause misjudgment or omission of optimal solutions. When a linear programming problem has a degenerate optimal solution, the multiple optimality test rule becomes ineffective, there is exactly one optimal solution with multiple optimal bases.