单纯形法(第三章线性规划2)课件.ppt

1、一、求解一、求解LP问题的单纯形法问题的单纯形法 1.单纯形法的求解原理单纯形法的求解原理 单纯形法引例单纯形法引例max fxx712129436045200310300012121212xxxxxxx x,5,2,1,03001032005436049521421321jxxxxxxxxxxjmax fxx71212标准化标准化1xxxxxxxxx3124125123609420045300310fxxStep2.确定换入换出变量，进行第一次迭代确定换入换出变量，进行第一次迭代 Step1.确定初始基可行解。确定初始基可行解。初始基可行解为：初始基可行解为：X1=(0 0 360 200

2、300)Tf1=00103000520004360252423xxxxxxxxx2223604902005403001030*3030,40,90min2xxxxxxxxxx3154152152407804502505300301.512.14.3360 xxfTX)050,240,30,(0,2f2 =360 Step3.确定新的换入换出变量，进行第二次迭代确定新的换入换出变量，进行第二次迭代xxx1112407830775025203003100.*xxxxxxxxx3451452458431211620040224012016.5452.036.1428xxfTX)00842420(3目

3、标函数值目标函数值 f 3=428。即当即当A产品生产产品生产20kg，B产品生产产品生产24kg，工厂才能获得最大利工厂才能获得最大利润润428百元。百元。x3=84代表煤的剩余量为代表煤的剩余量为84t，x4=x5=0表示电力表示电力和劳动日完全利用，没有剩余。和劳动日完全利用，没有剩余。X3为最优解为最优解2.单纯形法的主要步骤单纯形法的主要步骤Step1.标准化，找初始基可行解，建立初始的单纯形表；标准化，找初始基可行解，建立初始的单纯形表；对于对于(max,max,)，松弛变量对应的列构成一个单位阵松弛变量对应的列构成一个单位阵Step2.检验当前基可行解是否为最优解检验当前基可行解

4、是否为最优解所有检验数所有检验数 j 0 0，则得到最优解则得到最优解（若存在若存在k 0，且，且pk 0,则该问题则该问题无最优解，停止计算）无最优解，停止计算）否则进行下一步。否则进行下一步。Step3.换基迭代（改进基可行解）换基迭代（改进基可行解）n从从 j 0 0 中找最大者中找最大者 k ，其对应变量，其对应变量xk称为称为换入变量换入变量（若最大判别数（若最大判别数有同样大的，选对应下标小的变量为换入变量有同样大的，选对应下标小的变量为换入变量)nxk所在所在列称为主元列列称为主元列n确定换入变量的最大值和换出变量确定换入变量的最大值和换出变量n最小比值原则最小比值原则 0iki

5、kiaab5n设第设第 l 行使行使 最小，则第最小，则第 l 行对应的基变量行对应的基变量x l称称为为换出变量换出变量，第，第 l 行称为主元行，行称为主元行，alk 称为主元。称为主元。Step4.迭代过程迭代过程n迭代过程以主元迭代过程以主元alk为中心进行，即要将主元为中心进行，即要将主元 alk变变为为1 1，主列主列上其它元素变为上其它元素变为0 0，得到一个新的单纯形，得到一个新的单纯形表，同时得到一个新的基可行解。表，同时得到一个新的基可行解。n转回转回Step2。63.单纯形表及其格式单纯形表及其格式 x1 x2 xn xn+1 xn+2 xn+m b xn+1 a11 a

6、12 a1n 1 0 0 b1 xn+2 a21 a22 a2n 0 1 0 b2 xn+m am1 am2 amn 0 0 1 bm j 1 2 n n+1 n+2 n+m 7 max f=40 x1+50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 0 0例例1 用单纯形法求解下列用单纯形法求解下列LP问题问题 x1+2x2+x3 =30 3x1+2x2 +x4 =60 2x2+x5=24 x1,x5 0 0 max f=40 x1+50 x2+0 x3+0 x4+0 x5标准化标准化建立初始单纯形表建立初始单纯形表 xj x1 x2 x3 x4 x5bx3 1

7、 2 1 0 030 x4 3 2 0 1 060 x5 0 2 0 0 124 40 50 0 0 0 0基变量基变量*30/2=1560/2=3024/2=1240 50 0 0 0000第一步迭代第一步迭代 xj x1 x2 x3 x4 x5bx3 1 0 1 0 -16x4 3 0 0 1 -136x2 0 1 0 0 0.512 40 0 0 0 -25 -600基变量基变量6/1=636/3=12_40 50 0 0 00050第二步迭代第二步迭代 xj x1 x2 x3 x4 x5bx1 1 0 1 0 -16x4 0 0 -3 1 218x2 0 1 0 0 0.512 0 0

8、 -40 0 15-840基变量基变量18/2=912/0.5=24_40 50 0 0 040050第三步迭代第三步迭代 xj x1 x2 x3 x4 x5bx1 1 0 -0.5 0.5 015x5 0 0 -1.5 0.5 19x2 0 1 0.75 -0.25 07.5 0 0 -17.5 -7.5 0-975基变量基变量该问题的最优解为：该问题的最优解为：X=(15,7.5,0,0,9)T40 50 0 0 040050例例2 用单纯形法求解下列用单纯形法求解下列LP问题问题0,33242max2121212121xxxxxxxxxxf0,33242max54321521421321

9、21xxxxxxxxxxxxxxxxf xj x1 x2 x3 x4 x5bx3 -2 1 1 0 04x4 1 -1 0 1 02x5 -3 1 0 0 13 1 1 0 0 0 0基变量基变量 1 1 0 0 00000-12893-2002-1-2x11该问题具有无界解该问题具有无界解例例2 用单纯形法求解下列用单纯形法求解下列LP问题问题nmax f=x1+x2+2x3-x4 x1 +x3-x4 =1 -x1+x2+2x4 =0 x1,x4 0 0 max f=x1+x2+2x3-x42-x4 xj x1 x2 x3 x4bx3x2 1 0 1 -1 -1 1 0 210 0 0 0

10、-1-2基变量基变量 xj x1 x2 x3 x4bx1x2 1 0 1 -1 0 1 1 111 0 0 0 -1-2此问题具有无穷多最优解此问题具有无穷多最优解 max f=2总结：解的判别1、最优解的判别：最优解的判别：若若X（x1x2.xn）T为对应于基为对应于基B的一个基可行解，且所有的一个基可行解，且所有j 0 0，则则X X为最优解。为最优解。2 2、无穷多最优解的判别：、无穷多最优解的判别：若若X（x1x2.xn）T为为一个基可行解，存在所有一个基可行解，存在所有j 0 0，又又存在存在某一非基变量某一非基变量x xk k对应的判别数对应的判别数k =0,0,则此则此LPLP问

11、题有无穷多解。问题有无穷多解。3 3、无界解的判别：、无界解的判别：若若X（x1x2.xn）T为一个基可行解，其中为一个基可行解，其中某个非基变量某个非基变量x xk k对应对应的判别数的判别数k 0 0，且且对应的系数矩阵对应的系数矩阵a aikik 0,则此则此LPLP问题具有无界问题具有无界解。（或称无最优解，最优解解。（或称无最优解，最优解 无穷）无穷）4.人工变量的引入及其解法人工变量的引入及其解法 当约束条件为当约束条件为“”型，引入剩余变量和人工变量型，引入剩余变量和人工变量n由于所添加的剩余变量的系数为由于所添加的剩余变量的系数为 1，不能构成初始基，不能构成初始基变量，为此引

12、入一个人为的变量（注意，此时约束条变量，为此引入一个人为的变量（注意，此时约束条件已为件已为“=”型），以便取得初始基变量，故称为人型），以便取得初始基变量，故称为人工变量工变量n由于人工变量在原问题的解中是不能存在的，应尽快由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的系数被迭代出去，因此人工变量在目标函数中对应的系数应具有惩罚性，称为罚系数。罚系数的取值视解法而应具有惩罚性，称为罚系数。罚系数的取值视解法而定定n两种方法两种方法n大大M法法n两阶段法两阶段法20（1）两阶段法：）两阶段法：njjjxcf1maxnjxmibxajinjjij,.,2

13、,10,.,2,11作辅助问题作辅助问题解题过程：解题过程：第一阶段：求解辅助问题第一阶段：求解辅助问题当进行到最优表时，若当进行到最优表时，若 =0,则得到原问题的一则得到原问题的一个基本可行解，转入第二阶段。个基本可行解，转入第二阶段。若若 0,则判定原问题无可行解。则判定原问题无可行解。),.,2,1;,.,2,1(,0,0),.,2,1(.min121njmiyxmibyxayyyijnjiijijmmax=-y1-y2-ym 从第一阶段得到的基本可行解开始，继续用从第一阶段得到的基本可行解开始，继续用单纯形法进行迭代，直到找出原问题的最优解或单纯形法进行迭代，直到找出原问题的最优解或

14、判断具有无界解。判断具有无界解。第二阶段第二阶段:例例3 用两阶段法求解下列用两阶段法求解下列LP问题问题max fxxx31230,1232411232131321321xxxxxxxxxxx0,12324112513153214321xxxxxxxxxxxx76maxxxw0,1232411271731653214321xxxxxxxxxxxxxx引入人工变量引入人工变量x6,x7构造下列辅助问题：构造下列辅助问题：xj x1 x2 x3 x4 x5 x6 x7B-1bx4x6x7 1 -2 1 1 0 0 0 -4 1 2 0 -1 1 0 -2 0 1 0 0 0 11131-6 1

15、3 0 -1 0 04-f 3 -1 -1 0 0 0 00 x300-2130-11000-311011xj x1 x2 x3 x4 x5 x6 x7B-1bx4x6x7 3 -2 0 1 0 0 -1 0 1 0 0 -1 1 -2 -2 0 1 0 0 0 11011-0 1 0 0 -1 0 -31-f 1 -1 0 0 0 0 11x300-2112-1x20-2-50000-11-12-12xj x1 x2 x3 x4 x5B-1bx4x2x3 3 0 0 1 -2 0 1 0 0 -1 -2 0 1 0 01211-f 1 0 0 0 -12x11/3-2/34102/3-4/3

16、0-1/3-1/3-29得到原问题的最优解为：得到原问题的最优解为：X*=（4 1 9 0 0）T f*=2（2）大大M法法:0,1232411271731653214321xxxxxxxxxxxxxx3213maxxxxfMx6 Mx7(M为任意大的正数为任意大的正数)xj x1 x2 x3 x4 x5 x6 x7B-1bx4x6x7 1 -2 1 1 0 0 0 -4 1 2 0 -1 1 0 -2 0 1 0 0 0 11131-f3 6M -1+M -1+3M 0 -M 0 04M3 -1 -1 0 0 -M -M0-M-Mxj x1 x2 x3 x4 x5 x6 x7B-1bx4x6

17、x3 3 -2 0 1 0 0 -1 0 1 0 0 -1 1 -2 -2 0 1 0 0 0 11011-f 1 -1+M 0 0 -M 0 -3M+1M+13 -1 -1 0 0 -M -M0-M-1xj x1 x2 x3 x4 x5 x6 x7B-1bx4x2x3 3 0 0 1 -2 2 -5 0 1 0 0 -1 1 -2 -2 0 1 0 0 0 11211-f 1 0 0 0 -1 -M+1 -M-123 -1 -1 0 0 -M -M0-1-1xj x1 x2 x3 x4 x5 B-1bx1x2x3 1 0 0 1/3 -2/3 0 1 0 0 -1 0 0 1 2/3 -4/

18、3 419-f 0 0 0 -1/3 -1/3 -23 -1 -1 0 0 3-1-1得到原问题的最优解为：得到原问题的最优解为：X*=（4 1 9 0 0）T f*=2练习：练习：0,46 2.7810)(min32132121321xxxxxxxxtsxxxxf标准化：标准化：6,.,2,1,0462.7810)(max532164216321jxxxxxxxxxtsMxxxxxfj34大大M法的一些说明法的一些说明 大大M法实质上与原单纯形法一样，法实质上与原单纯形法一样，M可看成一个很大的常数可看成一个很大的常数人工变量被迭代出去后就不会再成为基变量人工变量被迭代出去后就不会再成为基变

19、量当检验数都满足最优条件，但基变量中仍有人工变量，说当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解明原线性规划问题无可行解大大M法手算很不方便法手算很不方便因此提出了两阶段法因此提出了两阶段法计算机中常用大计算机中常用大M法法两阶段法手算可能容易两阶段法手算可能容易单纯型法的一些具体问题单纯型法的一些具体问题 a.关于无界解问题关于无界解问题n可行区域不闭合可行区域不闭合(缺约束条件缺约束条件)n单纯型表中入变量单纯型表中入变量 x j*对应的列中所有对应的列中所有0*ija0,501002.)(max21212121xxxxxxtsxxxff(x)=x1+x2x1

20、x2505050100 x1-x2=50-2x1+x2=10036 b.关于多重解问题关于多重解问题n多个基可行解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行n最优单纯形表中有非基变量的检验数为0n最优解的线性组合仍是最优解，即 X=k1X1+k2X2，k1+k2=10,12023310032.254540)(max321321321321xxxxxxxxxtsxxxxf37 c.关于无可行解问题关于无可行解问题n约束条件互相矛盾，无可行域约束条件互相矛盾，无可行域n单纯形表迭代到最优解时，人工变量仍在基变量中单纯形表迭代到最优解时，人工变量仍在基变量中 0,1212.2)

21、(max321321321321321xxxxxxxxxxxxtsxxxxf38 d.关于退化问题关于退化问题n退化问题的原因很复杂退化问题的原因很复杂n当单纯形表中同时有多个基变量可选作出变量时当单纯形表中同时有多个基变量可选作出变量时n退化的严重性在于可能导致死循环，克服死循环的方法有退化的严重性在于可能导致死循环，克服死循环的方法有“字典序字典序”法法 39 一、判断题1、线性规划问题的每一个基解对应可行域的一个顶点。、线性规划问题的每一个基解对应可行域的一个顶点。2、图解法与单纯形法，虽然求解的形式不同，但从几何上理、图解法与单纯形法，虽然求解的形式不同，但从几何上理解，两者是一致的。

22、解，两者是一致的。3、线性规划问题存在最优解，则最优解一定对应可行域边界、线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。上的一个点。4、若、若x1、x2分别是某一线性规划问题的最优解，则分别是某一线性规划问题的最优解，则x1 x1+2x2也是该线性规划问题的最优解，其中也是该线性规划问题的最优解，其中12为正的实数。为正的实数。5、对一个有、对一个有n个变量、个变量、m个约束的标准形的线性规划问题，其可行域个约束的标准形的线性规划问题，其可行域的顶点恰好为的顶点恰好为Cnm6、单纯形法迭代的过程就是从一个基可行解（顶点）到另一单纯形法迭代的过程就是从一个基可行解（顶点）到另一个

23、基可行解（顶点）的过程。个基可行解（顶点）的过程。7、用单纯形方法，正的判别数对应的变量都可以作为换入变、用单纯形方法，正的判别数对应的变量都可以作为换入变量。量。8、线性规划问题的数学模型增加约束条件，可行域范围一般、线性规划问题的数学模型增加约束条件，可行域范围一般缩小，减少约束条件，可行域范围一般扩大。缩小，减少约束条件，可行域范围一般扩大。2、计算题 下表是求极大化线性规划问题的单纯形表，下表是求极大化线性规划问题的单纯形表，表中无人工变量，表中无人工变量，a1，a2，a3，d，c1，c2为为待定常数，试说明这些常数满足什么条件，能待定常数，试说明这些常数满足什么条件，能使以下结论成立

24、：使以下结论成立：xj x1 x2 x3 x4 x5 x6B-1bx3x4x6 4 a1 1 0 a2 0 -1 -3 0 1 -1 0 a3 -5 0 0 -4 1 d23-f c1 c2 0 0 -3 0 (1)表中解为唯一最优解；表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题无最优解；）该线性规划问题无最优解；（4）现行解不可行（说出哪一个变量）；）现行解不可行（说出哪一个变量）；（5）现行解是退化的基可行解（哪个变量造成了退）现行解是退化的基可行解（哪个变量造成了退化）；化）；（6）表中解非最优，为改进解，选换入变量）表中解非最优，为改进解，选换入变量x1,换出换出变量变量x6.3、maxf=5x1+3x2，求abcdefg的值xj 5 3 0 0 x1 x2 x3 x4 B-1b0 x35 x1 c 0 1 1/5 d e 0 1 2a-f b 1 f g-10