在系数矩阵 中，我们把 表示成 ，其中， 是初始基的单位矩阵， 是非基变量的系数矩阵。同时，将向量 也分成对应的两部分： ， 。其中， 分别为 中与基变量对应的 个分量组成的 维向量， 分别为 中与非基变量对应的 个分量对应的 维分量。

在线性规划的方程组 中，此方程组可写成

也就是： ，在此等式两边同时左乘 ,得到的结果是 ，移项后就得到 。此时，取非基变量 ，就得到基变量 。

在线性规划中，当线性规划问题标准化以后，得到系数矩阵的秩为 ，变量的个数为 个，从基解和基可行解的概念出发，如果 个非基变量都为零，而 个基变量是从线性方程组唯一解出，一般为正值。如果说，存在一个或一个以上的基变量为零，那么这样的情况称为退化情况，求得的解就称为退化解[1]。

3。 退化的基可行解的产生原因分析

退化的基可行解的产生有两种情形，第一种是在线性规划的约束条件中的右端常数项中含有零分量，在一开始就产生退化基可行解；第二种是一开始未产生退化基可行解，但在迭代过程中，由于出现相同的 值而产生退化基可行解。

3。1 右端常数项含有零分量

由于线性规划标准化之后，右端常数项中存在一个或一个以上的零，那么就称在一开始便出现退化解，即约束条件中存在 的情形。

例1 用单纯形法求解下述线性规划问题。

对以上问题用单纯形法进行迭代，迭代的最终单纯形表如表1所示(见下表1)。

那么，从表1中可以得到可行解为 ，然而，由于在此例题的约束条件中，右端常数项为 ，即满足线性规划在一开始就出现退化解的条件，因此，此可行解为退化可行解。

3。2 迭代过程出现相同 值

线性规划中产生退化基本可行解的情况为，在一开始不出现退化解，也就是 ，但是随着迭代的过程，中间或者最后会出现退化解。这种退化解产生的原因是在迭代过程中出现两个或多于两个的相同的 值。这时，任选一个对应的基变量作为换出变量时，在下一步单纯形表中，其他对应的基变量将取零值[2]。因此，在这样的情形下，我们称它产生了退化解。下面用例题来具体阐释这种情形。

例2 用单纯形法求解下述线性规划问题。

根据以上线性规划问题,将其化为标准形式以后列出初始单纯形表如表2所示。

在表2中可以看出，在第一步的迭代中就出现了两个相同的 值，因此，就产生了退化情况。在经过迭代以后，得到的最终表里显示出的可行解为 ，此可行解即为退化可行解。

4 退化解的情形分类

退化解的情形分类有两种，一种是唯一最优解是是唯一的并且是退化的，另一种是无穷多最优解，并且有退化的解。

4。1 唯一最优解的情形

产生唯一最优解的情形我们可以用下面的公式做一个归纳，即为： ， ，在这样的情形下，原问题拥有唯一最优解。最优解的唯一性的证明过程在此不作细致讨论，可参考孔祥庆的《退化线性规划最优解的唯一性》。

本退化情形我们将用运输问题的模型来作出阐述。运输问题在生活中存在普遍性，无论是商品销售、生产经营、物资管理还是经济建设，都会从中遇到各种各样的调运问题，也就是说，在解决这些问题的时候，我们需要考虑的是如何将各生产地的生产资料和生活资料运到销售地，也可以说是从供给地运到需求地，因为资源的有限性以及运输过程的限制性，我们需要使用最合理科学的方案将资源运送到目的地，这样才能够提高运输的经济效益。归结来说，运输问题就是在数量和单位运价给定的情况下，将某种资源从供给地运输到目的地，同时需要保持供需平衡，然后制定出最优的流量和流向，以降低总运输成本[3]。 关于线性规划解的退化问题的讨论(2):http://www.youerw.com/kuaiji/lunwen_202679.html