第2章 单纯形法的几种特殊情况（清风课堂）

1、管管 理理 运运 筹筹 学学4几种特殊情况 . 0,40,30,1501033020max212112121xxxxxxxxxz约束条件目标函数一、无可行解一、无可行解 例例1、用单纯形表求解下列线性规划问题、用单纯形表求解下列线性规划问题解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到： 121121121231121231max2030310150,30,40,0.zxxMaxxsxsxxsax x s s s a目标函数约束条件 填入单纯形表计算得：填入单纯形表计算得：1青苗学班B管管 理理 运运 筹筹 学学4

2、几种特殊情况迭迭代代次次数数基变基变量量CBx1 x2 s1 s2 s3 a1b比值比值20 30 0 0 0 -M0s1s2a100-M3 10 1 0 0 01 0 0 1 0 01 1 0 0 -1 11503040150/1040/1zjcj-zj-M -M 0 0 M -M20+M 30+M 0 0 -M 0-40M1x2s2a1300-M3/10 1 1/10 0 0 0 1 0 0 1 0 07/10 0 -1/10 0 -1 115302515/(3/10)30/125/(7/10)zjcj-zj9-7/10M 30 3+M/10 0 M -M11+7/10M 0 -3-M/1

3、0 0 -M 0 450-25M2x2x1a13020-M0 1 1/10 -3/10 0 01 0 0 1 0 00 0 -1/10 -7/10 -1 1 6304zjcj-zj20 30 3+M/10 11+7M/10 M -M0 0 -3-M/10 -11-7M/10 -M 0780-4M2青苗学班B管管 理理 运运 筹筹 学学4几种特殊情况 从第二次迭代的检验数都小于零来看，可知第从第二次迭代的检验数都小于零来看，可知第2次迭代所得的基本可次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为行解已经是最优解了，其最大的目标函数值为780-4M。我们把最优解。我们把最优解x1=30

4、,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个约束方程得代入第三个约束方程得x1+x2-0+4=40,即有：即有：x1+x2=3640. 并不满足原来的约束条件并不满足原来的约束条件3，可知原线性规划问题无可行解，或者说，可知原线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。其可行解域为空集，当然更不可能有最优解了。 像这样只要求线性规划的像这样只要求线性规划的最优解里有人工变量大于零最优解里有人工变量大于零，则此线性规划，则此线性规划无可行解无可行解。二、无界解二、无界解 在求目标函数最大值的问题中，所谓无在求目标函数最大值的问题中，所谓无界解是指在约束

5、条件下目标函数值可以取界解是指在约束条件下目标函数值可以取任意的大。下面我们用单纯形表来求第二任意的大。下面我们用单纯形表来求第二章中的例子。章中的例子。例例2 2、用单纯形表求解下面线性、用单纯形表求解下面线性规划问题。规划问题。 12121212max1,326,0.zxxxxxxx x目标函数约束条件3青苗学班B管管 理理 运运 筹筹 学学4几种特殊情况 迭迭代代次次数数基基变变量量CBx1 x2 s1 s2b比比值值1 1 0 00s1s2001 -1 1 0-3 2 0 1161zjcj-zj0 0 0 0 1 1 0 001x1s2101 -1 1 0 0 -1 3 119zjcj

6、-zj1 -1 1 00 2 -1 01填入单纯形表计算得：填入单纯形表计算得：解：在上述问题的约束条件中加入松驰变量，得标准型如下：解：在上述问题的约束条件中加入松驰变量，得标准型如下：121211221212max1,326,0.zxxxxsxxsx x s s目标函数约束条件4青苗学班B管管 理理 运运 筹筹 学学4几种特殊情况 12a 从单纯形表中，从第一次迭代从单纯形表中，从第一次迭代x2的检验数等于的检验数等于2，可知所得的基本可行，可知所得的基本可行解解x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进行第不是最优解。同时我们也知道如果进行第2次迭代，那次迭代

7、，那么就选么就选x2为入基变量，但是在选择出基变量时遇到了问题：为入基变量，但是在选择出基变量时遇到了问题： =-1, =-1,找找不到大于零的比值来确定出基变量不到大于零的比值来确定出基变量。事实上如果我们碰到这种情况就可以。事实上如果我们碰到这种情况就可以断定断定这个线性规划问题是无界这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从此目标函数值可以取得无限大。从1次迭代的单纯形表中，得到约束方程：次迭代的单纯形表中，得到约束方程：22a 移项可得：移项可得：1212121,39.xxsxss1212212112

8、12121,39.,0,1,0,9.121.xxssxsxM sxMxMssMzxxMMM 不妨设可得一组解：显然这是线性规划的可行解，此时目标函数5青苗学班B管管 理理 运运 筹筹 学学4几种特殊情况 ij 由于由于M可以是任意大的正数，可知此目标函数值无界。可以是任意大的正数，可知此目标函数值无界。 上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：在某次迭代的单纯形表中，如果在某次迭代的单纯形表中，如果存在着一个大于零的检验数存在着一个大于零的检验数 ，并且，并且该列该列的系数向量的每个元素的系数向量的每个元素ai

9、j(i=1,2,m)都小于或等于零都小于或等于零，则此线性规划问题，则此线性规划问题是无界是无界的，一般地说此类问题的出现是由于建模的错误所引起的。的，一般地说此类问题的出现是由于建模的错误所引起的。三、无穷多最优解三、无穷多最优解例例3、用单纯形法表求解下面的线性规划问题。、用单纯形法表求解下面的线性规划问题。121212212max5050300,2400,250,0.zxxxxxxxx x目标函数约束条件6青苗学班B管管 理理 运运 筹筹 学学4几种特殊情况 解：此题我们用图解法已求了解，现在用单纯形表来求解。解：此题我们用图解法已求了解，现在用单纯形表来求解。1231212112223

10、12123,max5050300,2400,250,0.s sszxxxxsxxsxsx xs ss加入松弛变量，我们得到标准形：目标函数约束条件填入单纯形表计算得：填入单纯形表计算得：7青苗学班B管管 理理 运运 筹筹 学学4几种特殊情况迭迭代代次次数数基变基变量量CBx1 x2 s1 s2 s3b比值比值50 50 0 0 00s1s2s30001 1 1 0 02 1 0 1 00 1 0 0 1300400250300/1400/1250/1zjcj-zj0 0 0 0 050 50 0 0 001s1s2x200501 0 1 0 -12 0 0 1 -10 1 0 0 150150

11、25050/1150/2zjcj-zj0 50 0 0 5050 0 0 0 0125002x1s2x2500501 0 1 0 -10 0 -2 1 10 1 0 0 1505025050/1250/1zjcj-zj50 50 50 0 00 0 -50 0 0150008青苗学班B管管 理理 运运 筹筹 学学4几种特殊情况 124, 这样我们求得了最优解为这样我们求得了最优解为x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的此线性规划的最优值为最优值为15000。这个最优解是否是惟一的呢？由于在第。这个最优解是否是惟一的呢？由于在第2次迭代的检验数次迭代的检验数中除了

12、基变量的检验数中除了基变量的检验数 等于零外，等于零外，非基变量非基变量s3的检验数也等的检验数也等于零于零，这样我们可以断定此线性规划问题有无穷多最优解。不妨我们把检，这样我们可以断定此线性规划问题有无穷多最优解。不妨我们把检验数也为零的非基变量选为入基变量进行第验数也为零的非基变量选为入基变量进行第3次迭代。可求得另一个基本次迭代。可求得另一个基本可行解，如下表所示：可行解，如下表所示：迭代迭代次数次数基基变变量量CBx1 x2 s1 s2 s3b50 50 0 0 03x1s3x2500501 0 -1 1 00 0 -2 1 10 1 2 -1 010050200zjcj-zj50 5

13、0 50 0 00 0 -50 0 015000 从检验数可知此基本可行解从检验数可知此基本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最优解也是最优解9青苗学班B管管 理理 运运 筹筹 学学4几种特殊情况 四、退化问题四、退化问题 在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。为退化。例例4.用单纯形表，求解下列线性规划问题。用单纯形表，求解下列线性规划问题。

14、解：加上松驰变量解：加上松驰变量s1,s2,s3化为标准形式后，化为标准形式后，填入单纯形表计算得：填入单纯形表计算得：1312131231233max222,24,3,0.zxxxxxxxxxx x x目标函数约束条件10青苗学班B管管 理理 运运 筹筹 学学4几种特殊情况迭迭代代次次数数基基变变量量CBx1 x2 x3 s1 s2 s3b比值比值2 0 3/2 0 0 00s1s2s30001 -1 0 1 0 02 0 1 0 1 01 1 1 0 0 12432/14/23/1zjcj-zj0 0 0 0 0 02 0 3/2 0 0 001x1s2s32001 -1 0 1 0 0

15、0 2 1 -2 1 00 2 1 -1 0 12010/21/2zjcj-zj2 -2 0 0 0 00 2 3/2 -2 0 042x1x2s32001 0 1/2 0 1/2 00 1 1/2 - 1 1/2 00 0 0 1 -1 1 2012/(1/2)0/(1/2)zjcj-zj2 0 1 0 1 00 0 1/2 0 -1 0411青苗学班B管管 理理 运运 筹筹 学学4几种特殊情况 在以上的计算中可以看出在在以上的计算中可以看出在0次迭代中，由于比次迭代中，由于比值值b1/a11=b2/a21=2为最小比值，导致在第为最小比值，导致在第1次迭代中出次迭代中出现了退化，基变量现了

16、退化，基变量s2=0。又由于在第。又由于在第1次迭代出现了次迭代出现了退化，基变量退化，基变量s2=0，又导致第，又导致第2次迭代所取得的目标次迭代所取得的目标函数值并没有得到改善，仍然与第函数值并没有得到改善，仍然与第1次迭代的一样都次迭代的一样都等于等于4。像这样继续迭代而得不到目标函数的改善，。像这样继续迭代而得不到目标函数的改善，当然减低了单纯形算法的效率，但一般来说还是可当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。像本题继续计算如下：以得到最优解的。像本题继续计算如下：12青苗学班B管管 理理 运运 筹筹 学学4几种特殊情况迭迭代代次次数数基基变变量量CBx1 x2

17、x3 s1 s2 s3b比值比值2 0 3/2 0 0 03x1x3s323/201 -1 0 1 0 00 2 1 - 2 1 00 0 0 1 -1 1 2012/11/1zjcj-zj2 1 3/2 -1 3/2 00 -1 0 1 -3/2 044x1x3s123/201 -1 0 0 1 -10 2 1 0 -1 20 0 0 1 -1 1 221zjcj-zj2 1 3/2 0 1/2 10 -1 0 0 -1/2 -1513青苗学班B管管 理理 运运 筹筹 学学4几种特殊情况 得到了最优解得到了最优解x x1 1=1=1，x x2 2=0=0，x x3 3=2=2，s s1 1=

18、1=1，s s2 2=0=0，s s3 3=0=0，其最优值为，其最优值为5 5。 但有时候当出现退化时，即使存在最优解，而迭代过程总是重复解的但有时候当出现退化时，即使存在最优解，而迭代过程总是重复解的某一部分迭代过程，出现了计算过程的循环，目标函数值总是不变，永远某一部分迭代过程，出现了计算过程的循环，目标函数值总是不变，永远达不到最优解。达不到最优解。 下面一个是由下面一个是由E.Beale给出的循环的例子。给出的循环的例子。例例5 5 目标函数目标函数 ：min f =min f =（3/43/4）x x4 4+20 x+20 x5 5（1 12 2）x x6 6+6x+6x7 7.

19、. 约束条件：约束条件：x x1 1+ +（1 14 4）x x4 48x8x5 5x x6 6+9x+9x7 7=0=0， x x2 2+ +（1 12 2）x x4 412x12x5 5（1 12 2）x x6 6+3x+3x7 7=0=0， x x3 3+x+x6 6=1=1， x x1 1，x x2 2，x x3 3，x x4 4，x x5 5，x x6 6，x x7 70.0.14青苗学班B管管 理理 运运 筹筹 学学4几种特殊情况 这个例题的确存在最优解，但用一般单纯形表法，经过这个例题的确存在最优解，但用一般单纯形表法，经过6 6次迭代后得到的单纯形表与第次迭代后得到的单纯形表与第0 0次单纯形表一样，而目标函数次单纯形表一样，而目标函数都