[科普中国]-退化问题

退化问题是指在线性规划中，单纯形表中的基本可行解中出现一个或多个基变量等于零时，或者按最小比值来确定换出基的变量时，存在两个以上相同最小比值的线性规划问题。出现的原因是模型中存在多余的约束，使多个基本可行解对应统一顶点。这时有可能出现单纯形法迭代的循环。

基本内容当线性规划原问题是退化问题时，由线性规划问题的几何解释可知，通过该可行域某个极点的超平面超过n个，所以该点为一个退化的极点。根据摄动法原理，可在退化问题约束方程的右边项做微小的扰动，使得超平面有一个微小的位移，原来相交于一点的若干个超平面略微错开一些，退化极点变成不退化极点。决策者可根据问题的实际情况，适当增加或减少某些资源的数量，使得其迭代变为非退化的，以得到问题的最优解。

在线性规划原问题是退化问题时，不能简单地认为某一求解过程中的影子价格为0，所对应的资源一定是富余资源。由上述问题得到的最优解，对约束方程进行计算，得到约束方程的三个方程全部取等式，即三种资源在最优解的情况下，松驰变量均为零。由资源的灵敏度分析可知，在此约束条件下，资源正恰好按最优方式全部用完，目标函数总收益达到最大。所以当线性规划原问题为退化问题时，资源的影子价格不数的数称为“下溢”。1

处理方法若在最终表中原问题的解为非退化最优解，而其对偶问题的最优解为退化解，则原问题一定有无穷多个最优解。此时，以检验数为零的非基变量为入基变量，用单纯形法继续迭代，即可求出原问题的其它最优解；

若在最终表中原问题的解为退化最优解，而其对偶问题的最优解为非退化解，则对偶问题一定有无穷多个最优解。此时，以原问题基变量中等于零的分量为出基变量，用对偶单纯形法继续迭代，即可求出对偶问题的其它最优解；

若在最终表中原问题与对偶问题的最优解均为退化最优解，则可采用单纯形法也可采用对偶单纯形法继续迭代，至于问题是否有无穷多个最优解，要根据具体情况再做判断。2

应用线性规划理论在工程设计、生产管理、交通运输、国防等领域以及自然科学的很多学科中都有着广泛的应用。线性规划问题虽然是一个古老的问题，但求解线性规划问题的方法在不断发展：从单纯形法、对偶单纯形法、椭圆方法到内点方法等等。虽然线性规划有这么多解法，但是单纯形方法在其中的统治地位始终没变。对于退化线性规划问题，用单纯形方法求解时有可能产生循环，因此，研究退化线性规划问题成为人们研究线性规划问题的一个重要方面。1952年A. Charnes和W. W. Cooper给出了求解退化线性规划问题的摄动法，1954年G. B. Dantzig, A. Orden和P. Wolfe提出了求解退化线性规划问题的字典序法，1976年G. G. Bland提出了求解退化线性规划问题的Bland法则，这些方法都能避免循环发生。1

本词条内容贡献者为:

孙和军 - 副教授 - 南京理工大学