第单纯形法学习教案

1、会计学1第第 单纯形法单纯形法第一页，共46页。2100100101200111),(54321pppppA第1页/共46页第二页，共46页。31010010113B第2页/共46页第三页，共46页。4第3页/共46页第四页，共46页。5010001100第4页/共46页第五页，共46页。61000100012B第5页/共46页第六页，共46页。7第6页/共46页第七页，共46页。8j0jjj Jzzxjjjj Jxjjj Jxjj第7页/共46页第八页，共46页。9增加得更大些，一般选其中的增加得更大些，一般选其中的jj最大者的非基变量为入基变量，最大者的非基变量为入基变量，在本例题在本例题

2、中中2=1002=100是检验数中最大的正数，故选是检验数中最大的正数，故选x2x2为入基变量。为入基变量。第8页/共46页第九页，共46页。10第9页/共46页第十页，共46页。1112112223300,2400,250.xxsxxsxs312122232300400250300,400,250.111bbbaaa第10页/共46页第十一页，共46页。12332ba30,0,1Te 第11页/共46页第十二页，共46页。13j112211,111,122,112,2,11,max.,0.1,2,nnmmnnmmnnmm mmm nnmjzc xc xc xxaxaxbxaxaxbxaxax

3、bxjn1,2,ix im1,2,jxjmmn第12页/共46页第十三页，共46页。14,11,22,1.1,2,iii mmi mmi nnniijjj mxbaxaxa xba xim1 122110011mnnniijjij mnnjjjjjj mj mzc xc xc xc xc xzcz xzx01,;miijjjizcbcz121 12212112,jmjjiijjjmmjmimjmjaazc ac ac ac ac ccac ccp第13页/共46页第十四页，共46页。151,2,jpjn1,jBBmjBjzccpcp第14页/共46页第十五页，共46页。16jjjcz迭代次数基

4、变量 cB x1 x2 s1 s2 s3 b比值Bi/ai2 50 100 0 0 00 s1 s2 s3 0 0 0 1 1 1 0 0 2 1 0 1 0 0 1 0 0 1300400250300/1400/1250/1 zj 0 0 0 0 0 50 100 0 0 0z=0jjjcz150050210第15页/共46页第十六页，共46页。1730,0,1Te jjjcz迭代次数基变量 cB x1 x2 s1 s2 s3 b 比值 bi/aij 50 100 0 0 01 s1 s2 x2 0 0 100 1 0 1 0 -1 2 0 0 1 -1 0 1 0 0 1 50 150 2

5、50 50/1 150/2 zj 0 100 0 0 100 50 0 0 0 -10025000第16页/共46页第十七页，共46页。181500jjjcz迭代次数基变量 cB x1 x2 s3 s4 s5 b 比值 bi/aij 50 100 0 0 02 x1 s2 x2 50 0 100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 1 50 50 250 zj 50 100 50 0 50 0 0 -50 0 -5027500第17页/共46页第十八页，共46页。19第18页/共46页第十九页，共46页。2012min23.fxx1211212350,125,2600,

6、0.xxxxxx x1211212312123350,125,2600,0.xxsxsxxsx x s s s第19页/共46页第二十页，共46页。21第20页/共46页第二十一页，共46页。22第21页/共46页第二十二页，共46页。23迭代迭代次数次数基变基变量量cB x1 x2 s1 s2 s3 a1 a2b比值比值 -2 -3 0 0 0 -M -M0a1a2s3-M-M0 1 1 -1 0 0 1 0 1 0 0 -1 0 0 1 2 1 0 0 1 0 0350125600350/1125/1600/2 zj-2M -M M M 0 -M -M-2+2M -3+M -M -M 0

7、0 0-475M1a1x1s3-M-20 0 1 -1 0 0 1 -1 1 0 0 -1 0 0 1 0 1 0 2 1 0 -2225125350225-350/2 zj -2 -M M -M+2 0 -M -M-2 0 -3+M -M M-2 0 0 2-2M-225M-2502a1x1s2-M-20 0 1/2 -1 0 -1/2 1 0 1 1/2 0 0 1/2 0 0 0 1/2 0 1 1/2 0 1/2300/1/2175/1/2 zj -2 -1/2M-1 M 0 1/2M-1 -M 0 0 1/2M-2 -M 0 - 1/2M+1 0 -M-50

8、M-600jjjczjjjczjjjcz第22页/共46页第二十三页，共46页。24jjjcz迭代迭代次数次数基变基变量量 cB x1 x2 s1 s2 s3 a1 a2 b 比值比值 -2 -3 0 0 0 -M -M3 x2 x1 s2 -3 -2 0 0 1 -2 0 -1 2 0 1 0 1 0 1 -1 0 0 0 1 1 1 -1 -1 100 250 125 zj -2 -3 4 0 1 -4 0 0 0 -4 0 -1 -M+4 -M -800第23页/共46页第二十四页，共46页。2512max;zaa 12111221231212312350,125,2600,0.xxsa

9、xsaxxsx x s s s a a第24页/共46页第二十五页，共46页。26第25页/共46页第二十六页，共46页。27迭代迭代次数次数基变基变量量cB x1 x2 s1 s2 s3 a1 a2b比值比值 0 0 0 0 0 -1 -10a1a2s3-1-10 1 1 -1 0 0 1 0 1 0 0 -1 0 0 1 2 1 0 0 1 0 0350125600350/1125/1600/2 zj-2 -1 1 1 0 -1 -1 2 1 -1 -1 0 0 0-4701a1x1s3-100 0 1 -1 1 0 1 -1 1 0 0 -1 0 0 1 0 1 0 2 1 0 -222

10、5125350 zj 0 -1 1 -1 0 -1 1 0 1 -1 1 0 0 -22252x2x1s3000 0 1 -1 1 0 1 0 1 0 0 -1 0 0 1 0 0 1 1 1 -1 -1225125125 zj 0 0 0 0 0 0 0 0 0 0 0 0 -1 -10第26页/共46页第二十七页，共46页。28迭代迭代次数次数基变基变量量cB x1 x2 s1 s2 s3b比值比值 -2 -3 0 0 0 0 x2x1s3-3-20 0 1 -1 1 0 1 0 0 -1 0 0 1 0 2 1225125125225/1125/2 zj-2 -3 3 -1 0 0 0

11、-3 1 0-9251x2x1s2-3-20 0 1 -2 0 -1 1 0 1 0 1 0 0 1 1 1100250125 zj -2 -3 4 0 1 0 0 -4 0 -1-800 从表中可知其基本(jbn)可行解x1=250,x2=100,s1=0,s2=125,s3=0是本例的最优解，其最优值为z=-(-800)=800。第27页/共46页第二十八页，共46页。29. 0,40,30,1501033020max212112121xxxxxxxxxz约束条件目标函数一、无可行解一、无可行解 例例1、用单纯形表求解、用单纯形表求解(qi ji)下列线性规划问题下列线性规划问题解：在上述

12、问题解：在上述问题(wnt)的约束条件中加入松驰变量、剩余变量、人工变的约束条件中加入松驰变量、剩余变量、人工变量得到：量得到： 121121121231121231max2030310150,30,40,0.zxxMaxxsxsxxsax x s s s a目标函数约束条件 填入单纯形表计算得：填入单纯形表计算得：第28页/共46页第二十九页，共46页。30迭代迭代次数次数基变基变量量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

13、-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/10 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/

14、10 -11-7M/10 -M 0780-4M第29页/共46页第三十页，共46页。31NoImage 从第二次迭代的检验数都小于零来看，可知第从第二次迭代的检验数都小于零来看，可知第2次迭代所得的基本可行解次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为已经是最优解了，其最大的目标函数值为780-4M。我们把最优解。我们把最优解x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个约束方程得代入第三个约束方程得x1+x2-0+4=40,即有：即有：x1+x2=3640. 并不满足原来的约束条件并不满足原来的约束条件3，可知原线性规划问题无可行解，或者说其可，可知原

15、线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。行解域为空集，当然更不可能有最优解了。 像这样只要求线性规划的最优解里有人工变量大于零，则此线性规划无可像这样只要求线性规划的最优解里有人工变量大于零，则此线性规划无可行解。行解。二、无界解二、无界解 在求目标函数最大值的问题中，所谓无在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以界解是指在约束条件下目标函数值可以(ky)取取任意的大。下面我们用单纯形表来求第二任意的大。下面我们用单纯形表来求第二章中的例子。章中的例子。例例2 2、用单纯形表求解、用单纯形表求解(qi ji)(qi ji)下面线性下面线

16、性规划问题。规划问题。 12121212max1,326,0.zxxxxxxx x目标函数约束条件第30页/共46页第三十一页，共46页。32迭代迭代次数次数基变量基变量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-zj1 -1 1 00 2 -1 01填入单纯形表计算填入单纯形表计算(j sun)得：得：解：在上述问题的约束条件中加入解：在上述问题的约束条件中加入(jir)松驰变量，得标准型如下：松驰变量，得标准型如下：12121

17、1221212max1,326,0.zxxxxsxxsx x s s目标函数约束条件第31页/共46页第三十二页，共46页。3312a 从单纯形表中，从第一次迭代的检验数等于从单纯形表中，从第一次迭代的检验数等于2，可知所得的基本可行解，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进行第不是最优解。同时我们也知道如果进行第2次迭代，那么就次迭代，那么就选选x2为入基变量，但是在选择出基变量时遇到为入基变量，但是在选择出基变量时遇到(y do)了问题：了问题： =-1, =-1,找找不到大于零的不到大于零的 来确定出基变量。事实上如果我们碰到这种情况就

18、可以断定这来确定出基变量。事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从值可以取得无限大。从1次迭代的单纯形表中，得到约束方程：次迭代的单纯形表中，得到约束方程：22a22a 移项移项(y xin)可得：可得：1212121,39.xxsxss121221211212121,39.,0,1,0,9.121.xxssxsxM sxMxMssMzxxMMM 不妨设可得一组解：显然这是线性规划的可行解，此时目标函数第32页/共46页第三十三页，共46页。

19、34ij 由于由于M可以是任意大的正数，可知此目标函数值无界。可以是任意大的正数，可知此目标函数值无界。 上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：在某次迭代的单纯形表中，如果存在着一个大于零的检验数在某次迭代的单纯形表中，如果存在着一个大于零的检验数 ，并且该列，并且该列的系数向量的系数向量(xingling)的每个元素的每个元素aij(i=1,2,m)都小于或等于零，则此都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错误所引线性规划问题是无界的，一般地说此类问题的出现是由于建模的

20、错误所引起的。起的。三、无穷多最优解三、无穷多最优解例例3、用单纯形法表求解下面的线性规划问题。、用单纯形法表求解下面的线性规划问题。121212212max5050300,2400,250,0.zxxxxxxxx x目标函数约束条件第33页/共46页第三十四页，共46页。35 解：此题我们用图解法已求了解解：此题我们用图解法已求了解(lioji)，现在用单纯形表来求解。，现在用单纯形表来求解。123121211222312123,max5050300,2400,250,0.s sszxxxxsxxsxsx xs ss加入松弛变量，我们得到标准形：目标函数约束条件填入单纯形表计算填入单纯形表计

21、算(j sun)得：得：第34页/共46页第三十五页，共46页。36迭代迭代次数次数基变基变量量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 01150/2zjcj-zj0 50 0 0 5050 0 0 0 0125002x1s2x2500501 0 1 0 -10 0 -2 1 10 1 0 0 1

22、505025050/1250/1zjcj-zj50 50 50 0 00 0 -50 0 015000第35页/共46页第三十六页，共46页。37124, 这样我们求得了最优解为这样我们求得了最优解为x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划此线性规划的最优值为的最优值为15000。这个最优解是否是惟一的呢？由于在第。这个最优解是否是惟一的呢？由于在第2次迭代的检验次迭代的检验数中除了基变量的检验数数中除了基变量的检验数 等于零外，非基变量等于零外，非基变量s3的检验数也的检验数也等于零，这样我们可以断定此线性规划问题有无穷多最优解。不妨等于零，这样我们可以断定此线性

23、规划问题有无穷多最优解。不妨(bfng)我们把检验数也为零的非基变量选为入基变量进行第我们把检验数也为零的非基变量选为入基变量进行第3次迭代。次迭代。可求得另一个基本可行解，如下表所示：可求得另一个基本可行解，如下表所示：迭代迭代次数次数基基变变量量CBx1 x2 s1 s2 s3b50 50 0 0 03x1s3x2500501 0 -1 1 00 0 -2 1 10 1 2 -1 010050200zjcj-zj50 50 50 0 00 0 -50 0 015000第36页/共46页第三十七页，共46页。38 从检验数可知此基本可行解从检验数可知此基本可行解x1=100,x2=200,s

24、1=0,s2=0,s3=50,也是最优解，从图也是最优解，从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解，不妨用向量解法可知连接这两点的线段上的任一点都是此线性规划的最优解，不妨用向量Z1，Z2表示上述两个表示上述两个(lin )最优解即最优解即Z1 =（50，250，0，50，0），）， Z2 =（100，200，0，0，50），则此线段上的任一点，即可表示为），则此线段上的任一点，即可表示为Z1+（1- ）Z2，其中，其中01。如。如图图5-1所示：所示：100100200200300300100100200200300300250250Z Z1Z Z2图图5-1第37页/共

25、46页第三十八页，共46页。39s 在一个已得到最优解的单纯形表中，如果在一个已得到最优解的单纯形表中，如果(rgu)存在一个非基变量的检验数存在一个非基变量的检验数 为为零，为什么我们把这个非基变量零，为什么我们把这个非基变量xs作为入基变量进行迭代时，得到的最优解仍为最优解呢？作为入基变量进行迭代时，得到的最优解仍为最优解呢？ 不妨设出基变量为不妨设出基变量为xk，则原最优单纯形表可表示如下：，则原最优单纯形表可表示如下：111111,111,1122100100000,0ksksskkkskkk skkksmmm sjjjmsssmmsssiisixxccxcaxcaxcaxcaxcac

26、zc ac ac accc a从此表可知即有，也就是。第38页/共46页第三十九页，共46页。40 通过迭代，我们得到了新的单纯形表，其中通过迭代，我们得到了新的单纯形表，其中(qzhng)xs为基变量了，为基变量了，而而xk为非基变量了。我们可得到下表。为非基变量了。我们可得到下表。111111111111101101111000ksksskskmkiisiissiikksksksmkkksiiskkssikskssskskskkksmsmmksjksjjjkxxccaxcazc ac acaaaxcac ac acaaxcacaxcaaxcazzcczcz 在此表中把111.0.msiis

27、ikskksskksksjkjkc azcc accaaczcz，代入上式得：即又可得到：第39页/共46页第四十页，共46页。41 又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可证明其他的非基变量的检验数不变，仍然小于零，这样就证明了新得到证明其他的非基变量的检验数不变，仍然小于零，这样就证明了新得到的基本可行解仍然是最优解。的基本可行解仍然是最优解。 这样我们得到了判断线性规划有无穷多最优解的方法：对于这样我们得到了判断线性规划有无穷多最优解的方法：对于(duy)某个最优的基本可行解，如果存在某个非基变量的检验数为零，则

28、此线某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解。性规划问题有无穷多最优解。四、退化问题四、退化问题 在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。称之为退化。例例4.用单纯形表，求解下列线性规划问题。用单纯形表，求解下列线性规划问题。解：加上松驰变量解：加上松驰变量s1,s2,s3化为标准形式后，化为标准形式后，填入单纯形表计算得：填入单纯形表计算

29、得：1312131231233max222,24,3,0.zxxxxxxxxxx x x目标函数约束条件第40页/共46页第四十一页，共46页。42迭迭代代次次数数基基变变量量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 0 2 1 -2 1 00 2 1 -1 0 12010/21/2zjcj-zj2 -2 0 0 0 00 2 3/2 -2 0

30、 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 04第41页/共46页第四十二页，共46页。43 在以上的计算中可以看出在在以上的计算中可以看出在0次迭代中，由于比值次迭代中，由于比值b1/a11=b2/a21=2为最小比为最小比值，导致在第值，导致在第1次迭代中出现了退化，基变量次迭代中出现了退化，基变量s2=0。又由于在第。又由于在第1次迭代出现了退化，次迭代出现了退化，基变量基变量s2=0，又导致第，又导致第2次迭代所取得的目标函数值并没有得到改善，仍然与第次迭代所取得的目标函数值并没有得到改善，仍然与第1次次迭代的一样都等于迭代的一样都等于4。像这样继续迭代而得