- 中文名
- 退化问题
- 外文名
- Degradation problem
- 拼 音
- Tuì huà wèn tí
- 隶 属
- 数理科学
- 学 科
- 运筹学
- 解决方法
- 摄动法、字典序法等
当线性规划原问题是退化问题时，由线性规划问题的几何解释可知，通过该可行域某个极点的超平面超过n个，所以该点为一个退化的极点。根据摄动法原理，可在退化问题约束方程的右边项做微小的扰动，使得超平面有一个微小的位移，原来相交于一点的若干个超平面略微错开一些，退化极点变成不退化极点。决策者可根据问题的实际情况，适当增加或减少某些资源的数量，使得其迭代变为非退化的，以得到问题的最优解。
在线性规划原问题是退化问题时，不能简单地认为某一求解过程中的影子价格为0，所对应的资源一定是富余资源。由上述问题得到的最优解，对约束方程进行计算，得到约束方程的三个方程全部取等式，即三种资源在最优解的情况下，松驰变量均为零。由资源的灵敏度分析可知，在此约束条件下，资源正恰好按最优方式全部用完，目标函数总收益达到最大。所以当线性规划原问题为退化问题时，资源的影子价格不数的数称为“下溢”。 [1]
- 1.
- 2.
- 3.
线性规划理论在工程设计、生产管理、交通运输、国防等领域以及自然科学的很多学科中都有着广泛的应用。线性规划问题虽然是一个古老的问题，但求解线性规划问题的方法在不断发展：从单纯形法、对偶单纯形法、椭圆方法到内点方法等等。虽然线性规划有这么多解法，但是单纯形方法在其中的统治地位始终没变。对于退化线性规划问题，用单纯形方法求解时有可能产生循环，因此，研究退化线性规划问题成为人们研究线性规划问题的一个重要方面。1952年A. Charnes和W. W. Cooper给出了求解退化线性规划问题的摄动法，1954年G. B. Dantzig, A. Orden和P. Wolfe提出了求解退化线性规划问题的字典序法，1976年G. G. Bland提出了求解退化线性规划问题的Bland法则，这些方法都能避免循环发生。 [1]
