从检验数可知此基本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最优解，从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解，不妨用向量Z1，Z2表示上述两个最优解即Z1 =（50，250，0，50，0）， Z2 =（100，200，0，0，50），则此线段上的任一点，即可表示为αZ1+（1- α ）Z2，其中0≤α≤1。如图5-1所示：
在一个已得到最优解的单纯形表中，如果存在一个非基变量的检验数为零，为什么我们把这个非基变量xs作为入基变量进行迭代时，得到的最优解仍为最优解呢？
不妨设出基变量为xk，则原最优单纯形表可表示如下：
xk?ckx1?xk?1xkxk?1?xmc1?ck?1?ck?cm??ck?1??0?010?00????xscsa1s??ak?1,sak,s?am,s0m?ak?1,s?j?cj?zj从此表可知?s?0,即有c1a1s?c2a2s???cmams?cs?0，也就是cs??ciais。i?1通过迭代，我们得到了新的单纯形表，其中xs为基变量了，而xk为非基变量了。我们可得到下表。
36
又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可证明其他的非基变量的检验数不变，仍然小于零，这样就证明了新得到的基本可行解仍然是最优解。
这样我们得到了判断线性规划有无穷多最优解的方法：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解。
37
四、退化问题
在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。 3目标函数maxz?2x?x3例4.用单纯形表，求解下列线性规划问题。 12解：加上松驰变量s1,s2,s3化为标准形式后，
约束条件x1?x2?2,填入单纯形表计算得：
2x1?x3?4,x1?x2?x3?3,x1,x2,x3?0.
在以上的计算中可以看出在0次迭代中，由于比值b1/a11=b2/a21=2为最小比值，导致在第1次迭代中出现了退化，基变量s2=0。又由于在第1次迭代出现了退化，基变量s2=0，又导致第2次迭代所取得的目标函数值并没有得到改善，仍然与第1次迭代的一样都等于4。像这样继续迭代而得不到目标函数的改善，当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。像本题继续计算如下：
38
得到了最优解x1=1，x2=0，x3=2，s1=1，s2=0，s3=0，其最优值为5。
但有时候当出现退化时，即使存在最优解，而迭代过程总是重复解的某一部分迭代过程，出现了计算过程的循环，目标函数值总是不变，永远达不到最优解。? 下面一个是由E.Beale给出的循环的例子。 例5
目标函数 ：?min f =－（3/4）x4+20x5－（1／2）x6+6x7.? 约束条件：x1+（1／4）x4－8x5－x6+9x7=0，?
x2+（1／2）x4－12x5－（1／2）x6+3x7=0，? x3+x6=1，?
x1，x2，x3，x4，x5，x6，x7≥0.
这个例题的确存在最优解，但用一般单纯形表法，经过6次迭代后得到的单纯形表与第0次单纯形表一样，而目标函数都是零，没有任何变化，这样迭代下去，永远达不到最优解。为了避免这种现象，我们介绍勃兰特法则。?
首先我们把松弛变量（剩余变量）、人工变量都用xj表示，一般松弛变量（剩余变量）的下标号列在决策变量之后，人工变量的下标号列在松弛变量（剩余变量）之后，在计算中，遵守以下两个规则：? （1）在所有检验数大于零的非基变量中，选一个下标最小的作为入基变量。 （2）在存在两个和两个以上最小比值时，选一个下标最小的基变量为出基变量。 这样就一定能避免出现循环。
39