第2章 单纯形法的几种特殊情况.ppt

1、1,4 几种特殊情况,一、无可行解例1、用单纯形表求解下列线性规划问题,解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：,填入单纯形表计算得：,2,4 几种特殊情况,3,4 几种特殊情况,从第二次迭代的检验数都小于零来看，可知第2次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为780-4M。我们把最优解x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个约束方程得x1+x2-0+4=40,即有：x1+x2=3640.并不满足原来的约束条件3，可知原线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。像这样只要求线性规划的最优解里有

2、人工变量大于零，则此线性规划无可行解。 二、无界解在求目标函数最大值的问题中，所谓无 界解是指在约束条件下目标函数值可以取 任意的大。下面我们用单纯形表来求第二 章中的例子。,例2、用单纯形表求解下面线性 规划问题。,4,4 几种特殊情况,填入单纯形表计算得：,解：在上述问题的约束条件中加入松驰变量，得标准型如下：,5,4 几种特殊情况,从单纯形表中，从第一次迭代x2的检验数等于2，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进行第2次迭代，那么就选x2为入基变量，但是在选择出基变量时遇到了问题： =-1, =-1,找不到大于零的比值来确定出基变量。

3、事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从1次迭代的单纯形表中，得到约束方程：,移项可得：,6,4 几种特殊情况,由于M可以是任意大的正数，可知此目标函数值无界。上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：在某次迭代的单纯形表中，如果存在着一个大于零的检验数 ，并且该列的系数向量的每个元素aij(i=1,2,m)都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错误所引起的。 三、无穷多最优解 例3、用单纯形法表求解下面的线性规划问题。,7,4 几种特殊情况,解：此题

4、我们用图解法已求了解，现在用单纯形表来求解。,填入单纯形表计算得：,8,4 几种特殊情况,9,4 几种特殊情况,这样我们求得了最优解为x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的最优值为15000。这个最优解是否是惟一的呢？由于在第2次迭代的检验数中除了基变量的检验数 等于零外，非基变量s3的检验数也等于零，这样我们可以断定此线性规划问题有无穷多最优解。不妨我们把检验数也为零的非基变量选为入基变量进行第3次迭代。可求得另一个基本可行解，如下表所示：,从检验数可知此基本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最优解,10,4 几种特殊情况,

5、四、退化问题在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。 例4.用单纯形表，求解下列线性规划问题。解：加上松驰变量s1,s2,s3化为标准形式后， 填入单纯形表计算得：,11,4 几种特殊情况,12,4 几种特殊情况,在以上的计算中可以看出在0次迭代中，由于比值b1/a11=b2/a21=2为最小比值，导致在第1次迭代中出现了退化，基变量s2=0。又由于在第1次迭代出现了退化，基变量s2=0，又导致第2次迭代所取得的目标函数值并没有得到改善，仍然与第1次迭代的一样都等于4。像这样继续迭代而得不到目标函数的改

6、善，当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。像本题继续计算如下：,13,4 几种特殊情况,14,4 几种特殊情况,得到了最优解x1=1，x2=0，x3=2，s1=1，s2=0，s3=0，其最优值为5。但有时候当出现退化时，即使存在最优解，而迭代过程总是重复解的 某一部分迭代过程，出现了计算过程的循环，目标函数值总是不变，永远 达不到最优解。下面一个是由E.Beale给出的循环的例子。 例5目标函数 ：min f =（3/4）x4+20x5（12）x6+6x7.约束条件：x1+（14）x48x5x6+9x7=0，x2+（12）x412x5（12）x6+3x7=0，x3+x6=

7、1， x1，x2，x3，x4，x5，x6，x70.,15,4 几种特殊情况,这个例题的确存在最优解，但用一般单纯形表法，经过6次迭代后得到的单纯形表与第0次单纯形表一样，而目标函数都是零，没有任何变化，这样迭代下去，永远达不到最优解。为了避免这种现象，我们介绍勃兰特法则。首先我们把松弛变量（剩余变量）、人工变量都用xj表示，一般松弛变量（剩余变量）的下标号列在决策变量之后，人工变量的下标号列在松弛变量（剩余变量）之后，在计算中，遵守以下两个规则： （1）在所有检验数大于零的非基变量中，选一个下标最小的作为入基变量。 （2）在存在两个和两个以上最小比值时，选一个下标最小的基变量为出基变量。这样就一定能避免出现循环。,16,单纯性法小结,化标准性:,17,单纯性法小结,解的判别： 1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线 规划具有唯一最优解。 2）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。 3）无界解判别：某个k0且aik（i=1，2,m）则线性规划具有无界解。 4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri0时，则表明原线性规划无可行解。 5）退化解的判别：存在某个基变量为零的基本可行解。,