第1章 单纯形法精选文档.ppt

《第1章 单纯形法精选文档.ppt》由会员分享，可在线阅读，更多相关《第1章 单纯形法精选文档.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本讲稿第一页，共八十三页线性规划单纯形法线性规划单纯形法 单纯形法(Simplex Method)是美国人丹捷格(G.Dantzig)1947年创建的这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。单纯形法的表现形式：代数法表格法矩阵法本讲稿第二页，共八十三页单纯形法形法线性规划问题的几何意义：凸集：没有凹入部分，内部没有空洞。实习圆、实心球体、实心立方体都是凸集；两个凸集的交集是凸集。若线性规划问题存在可行域，则可行域是凸集。线性规划问题的基可行解对应可行域的顶点。若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。本讲稿第三页，共八十三页单纯形法的一般原

2、理单纯形法的一般原理考虑线形规划问题：max ZCX AXb X0如果有可行域DXRn|AX=b,X0非空有界，则D上的最优目标函数值ZCX一定可以在D的顶点达到。本讲稿第四页，共八十三页单纯形法的基本思路形法的基本思路根据线性规划问题的标准型，从可行域中某个基可行解一个顶点）开始，转换到另一个基可行解（顶点），并且使目标函数达到最大值时，问题就得到最优解。因此得到5个步骤：初始解判优判无界换基迭代本讲稿第五页，共八十三页确定初始的基本可行解确定初始的基本可行解确定初始的基本可行解确定初始的可行基初始的可行基确定对应初始基本可行解确定本讲稿第六页，共八十三页最优解判别最优解判别不妨假设不妨假设

3、 A=（B,N）（B为一个基为一个基为一个基为一个基）相应地有相应地有 X Xt t=(X=(XB B,X,XN N)t t C=(CB B,CN)由式由式 max ZCX AXb X0 Z=Z=(C(CB,C,CN)(XB,X,XN)t=C=CB B X XB+CN N XN AX AX（B,N)(XB,N)(XB,XN)t=B=B XB+N+N XN=b=b本讲稿第七页，共八十三页因为因为因为因为B B为一个基为一个基为一个基为一个基,det(B)0,det(B)0有有有有 X XB=B=B-1b-Bb-B-1-1N XN N （2.1）Z=CZ=CB B B-1-1b+(C(CN N-C

4、B B B-1N)N)X XN （2.22.2）令令令令X XN N0，则基变量，则基变量XBB-1bX X=(X=(XB B,X,XN N)=)=（B B-1-1b,0）T为基础解，其目标函数值为为基础解，其目标函数值为 Z=C CB B B-1b b只要只要只要只要X XB=B-1b=0,Xb=0,Xt t=（B-1-1b,0b,0）=0=0X为基础可行解为基础可行解,B就是可行基。就是可行基。本讲稿第八页，共八十三页对公式对公式对公式对公式Z=CZ=CB B B-1b+b+(CN N-C-CB B B B-1N)N)XN N （2.2）若满足若满足 C CN-CB B B B-1-1N

5、=0N =0 则对任意的则对任意的 x=0 有有 Z=CX=0 则对应于基则对应于基B的基础可行解的基础可行解x就是基础最优解，就是基础最优解，此时的可行基就是最优基。此时的可行基就是最优基。CB B-1A-C为检验数。为检验数。由于基变量的检验数：由于基变量的检验数：CB B-1B-CB=0CB B-1A-C=（0，CB B-1N-CN）本讲稿第十页，共八十三页单纯形法的求解步形法的求解步骤1、确定初始基可行解 basic feasible solution 先找出初始可行基，确定初始基可行解，建立初始单纯形表 initial simplex tableau。若能从列向量中直接观察到存在个线

6、性无关的单位向量，经过重新安排次序便可得到一个可行基。对约束条件都是，则加入的松驰变量就构成初始基。对约束条件都是，且不存在单位矩阵的等式约束，就要采用人造基的方法：大M法、对偶单纯法。本讲稿第十一页，共八十三页单纯形法的求解步形法的求解步骤 2 2：判：判优2、检验数判别得到初始基可行解后，要检验其是否为最优解：若是，问题解决；否则继续下一步。最优性判别定理：若所有检验数都j0，则找到最优解。本讲稿第十二页，共八十三页单纯形法的求解步形法的求解步骤 3 3：判无界：判无界3、判断是否无界在j 0,j=m+1,n 中，若有某个k 对应 xk 的系数列向量 Pk0，则此问题无界，停止计算；否则转

7、入下一步。即在单纯形表中的某 xk 检验数k 0，而该列系数全小于0，则无界。本讲稿第十三页，共八十三页单纯形法的求解步形法的求解步骤 4 4：换基基4、确定换入变量和换出变量换入变量=进基变量=Entering Variable根据 max(j 0)=k，确定 xk 为换入变量换出变量=出基变量=Leaving Variable按 规则计算，可确定 xl 为换出变量。本讲稿第十四页，共八十三页单纯形法的求解步形法的求解步骤 5 5：迭代：迭代 5、迭代以 alk 为主元素（pivot number）进行迭代，得到新的单纯形表。迭代又称旋转运算，或高斯消去法。本讲稿第十五页，共八十三页单纯形法

8、的求解步形法的求解步骤重复步骤25，直到终止。判优换基迭代判优换基迭代判优换基迭代判优 最优解本讲稿第十六页，共八十三页换入变量的确定最大增加原则假设检验向量 N N(C(CN N-C-CB B B B-1-1N)=(N)=(m+1m+1,m+2m+2,n n),),若其中有两个以上的检验数为正，选取最大正检验数所对应的若其中有两个以上的检验数为正，选取最大正检验数所对应的非基变量为换入变量。非基变量为换入变量。若：若：maxmax j j|j j0,m+1jn=0,m+1jn=m+Km+K 则选取对应的则选取对应的x xm+km+k为换入变量。为换入变量。基本可行解的改进基本可行解的改进本讲

9、稿第十七页，共八十三页换出变量的确定最小比值原则基本可行解的改进基本可行解的改进本讲稿第十八页，共八十三页例：maxZ=5x1+2x2+3x3-x4+x5 x1+2x2+2x3+x4 =8 3x1+4x2+x3 +x5=7 x1,x2,x3,x4,x50 其中用初等变换求改进了的基本可行解用初等变换求改进了的基本可行解在系数矩阵A中存在一个单位矩阵B（p4,p5）本讲稿第十九页，共八十三页取x4,x5为基变量，x1,x2,x3为非基变量，在这一情况下：（1 1）确定初始基本可行解）确定初始基本可行解本讲稿第二十页，共八十三页令XN=0,XB=B-1b=b=基本可行解X=(0,0,0,8,7)T

10、目标函数值：本讲稿第二十一页，共八十三页（2）检验X=(0,0,0,8,7)T是否最优：由最优解判别定理，非基变量检验数130，340,所以X=(0,0,0,8,7)T不是最优解本讲稿第二十二页，共八十三页 选取换入变量：因为max3,4=4,按最大增加原则，取x3为换入变量 选取换出变量 因为：所以取min(8/2,7/1)=4,由最小取值原则选取x4为换出变量 （3）基本可行解X=(0,0,0,8,7)T的改进本讲稿第二十三页，共八十三页（4）求改进的基本可行解X：本讲稿第二十四页，共八十三页再转向步骤（2）本讲稿第二十五页，共八十三页（2）检验X=(0,0,4,0,3)T是否最优：由最优

11、解判别定理，非基变量检验数110，所以X=(0,0,4,0,3)T不是最优解本讲稿第二十六页，共八十三页 选取换入变量：因为110,按最大增加原则，取x1为换入变量 选取换出变量 因为：所以取min(4/(1/2),3/(5/2)=6/5,由最小取值原则选取x5为换出变量 （3）基本可行解X=(0,0,4,0,3)T的改进本讲稿第二十七页，共八十三页（4）求改进的基本可行解X：本讲稿第二十八页，共八十三页再转向步骤（2）本讲稿第二十九页，共八十三页（2）检验X=(6/5,0,17/5,0,0)T是否最优：由最优解判别定理，非基变量检验数2,4,5 都小于0，所以X=(6/5,0,17/5,0,

12、0)T是最优解本讲稿第三十页，共八十三页表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。一、单纯形法表一、单纯形法表CjC1C2CjCn比值CBXBbx1x2xjxnCB1xB1b1a11a12a1ja1n1CB2xB2b2a21a22a2ja2n2CBnxBnbmam1am2amjamnm检验数j-Z12jn表格单纯形法表格单纯形法本讲稿第三十一页，共八十三页将线性规划问题化成标准型。找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。计算各非基变量xj的检验数j=Cj-CBPj，若所有j0，则问题已得到最优解，停止计算，否则转入下步。在大于0的检验数中，若某个

13、k所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下步。根据maxjj0=k原则，确定xk为换入变量(进基变量)，再按规则计算：=minbi/aik|aik0=bl/aik 确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为0，转第 步。二、单纯形法的计算步骤二、单纯形法的计算步骤 本讲稿第三十二页，共八十三页例例、某航空食品公司利用甲、乙、丙三种原料生产、某航空食品公司利用甲、乙、丙三种原料生产A1A1、A2A2、A3A3和和A4A4四种食品，每月可供应该公司

14、的原料及每种食品可四种食品，每月可供应该公司的原料及每种食品可获利情况如下表所示，试求该食品公司每月应如何安排生获利情况如下表所示，试求该食品公司每月应如何安排生产计划，才能使总利润最大。产计划，才能使总利润最大。15001500300030002500250020002000利润（元利润（元/吨）吨）2002000 01 12 21 1丙丙3003003 31 11 10 0乙乙5005002 22 21 11 1甲甲每月原料供每月原料供应量（吨）应量（吨）A4A3A2A1 消耗消耗 食品食品原料原料本讲稿第三十三页，共八十三页解：此问题的线性规划模型为Max Z=2000 x1+2500

15、x2+3000 x3+1500 x4 (1)x1+x2+2x3+2 x4 500 (2)x2+x3+3 x4 300 (3)x1+2 x2+x3 200 (4)xi0 (i=1,2,3,4)(5)x1+x2+2x3+2 x4+x5 =500 (2)x2+x3+3 x4 +x6 =300 (3)x1+2 x2+x3 +x7=200 (4)xi0 (i=1,2,7)(5)化为标准型：Max Z=2000 x1+2500 x2+3000 x3+1500 x4 (1)s.t.s.t.本讲稿第三十四页，共八十三页cBxBbx1x2x3x4x5x6x72000250030001500000 x5x6x70

16、0050030020010111221123010001000102000250030001500000-z 30002503002002001初始单纯形表0-1-1-11000-3-1-2x330001100重新计算检验数，结果如下页检验数判别换基迭代非基变量检验数为计算本讲稿第三十五页，共八十三页cBxBbx1x2x3x4x5x6x72000250030001500000 x5x600200121230100010-1-1000-3500150000-3000-z 05033.3-1第2单纯形表0-1-11000-3-1-2x3300011001x415001/3-1/3-1/333.30

17、-2/3033.3-1/3-1/3-7/3-4/30-500-2500-500-3000-650000检验数全非正,已经取得最优解,最优解为:X*=(0,0,200,33.3)T Z*=650000计算非基变量检验数为检验数判别最终单纯形表Final Simplex tableau0本讲稿第三十六页，共八十三页 maxZ=3x1+5 x2+0 x3+0 x4+0 x5=0 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 三、单纯形法计算举例三、单纯形法计算举例Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010012020103634001

18、x3x4x5000035000-12/2=636/4=9本讲稿第三十七页，共八十三页检验数检验数 j81010060101/2012300-21x3x2x5050-30300-5/208-4Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9本讲稿第三十八页，共八十三页Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数检验数 j40012/3-1/360101/20410

19、0-2/31/3x3x2x1053-42000-1/2-1最优解最优解:X*=(4,6,4,0,0)T，Z*=42本讲稿第三十九页，共八十三页最优基 Cj35000比值CBXBbx1x2x3x4x50 x340012/3-1/35x260101/203x14100-2/31/3检验数j-42000-1/2-1x3x2x1最优基的逆最优基的逆 最优基和最优基的逆最优基和最优基的逆本讲稿第四十页，共八十三页例如例如maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1,x2 0S.t.标准化标准化 maxZ=3x1+2 x2-2x1+x2+x3 =2 x1-3 x2 +x4=3

20、x1,x2,x3,x4 0Cj比值CBXBb检验数jx1x2x3x432002-211031-301x3x40003200-3检验数j80-512x3x103-31-301-90110-3此时，检验数2=11 0，还没有得到最优解。确定x2进基，但x2所在列的系数向量元素非正，无界值不存在，有进基变量但无离基变量。本讲稿第四十一页，共八十三页人工变量问题人工变量问题 用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“”时，加入松弛变量就形成了初始基。但实际存在“”或“”型的约束，没有现成的单位矩阵。一、人工变量一、人工变量 采用人造基的办法：采用人造基的办法：人工构造单位矩阵人工构

21、造单位矩阵人工构造单位矩阵人工构造单位矩阵在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。随问题，从而得到一个初始基。人工变量是在等式中人为加进的，只有它等于人工变量是在等式中人为加进的，只有它等于0 0时，约束条件才是它本来时，约束条件才是它本来的意义。的意义。处理方法有两种：处理方法有两种：大大M M 法法两阶段法两阶段法本讲稿第四十二页，共八十三页大大M M法法人工变量开始作为基变量，最后要换出来，全部成为非基变量，问题才有解。假设人工变量在目标函数中的价值系数为-M，M为很大的正

22、数；只要基变量中还存在人工变量，目标函数就不能实现极大化。本讲稿第四十三页，共八十三页大大M法：法：引入人工变量 xn+i 0（i=1,m）及充分大正数 M。得到：Maxz=c1x1+c2x2+cnxn-Mxn+1-Mxn+m s.t.a11 x1+a12 x2+a1n xn+xn+1=b1 a21 x1+a22 x2+a2n xn+xn+2 =b2 .am1 x1+am2 x2+amn xn+xn+m =bm x1，x2，xn ，xn+1，xn+m 0本讲稿第四十四页，共八十三页显然，xj=0 j=1,n;xn+i=bi i=1,m 是基本可行解。对应的基是单位矩阵。结论：若得到的最优解满足

23、 xn+i=0 i=1,m 则是原问题的最优解；否则，原问题无可行解。本讲稿第四十五页，共八十三页例 现有线性规划问题Min Z=-3x1+x2+x3 (1)x1-2x2+x3 11 (2)-4x1+x2+2 x3 3 (3)-2x1 +x3=1 (4)xi0 (i=1,2,3)(5)x1-2 x2+x3+x4 =11 (2)-4 x1+x2+2 x3 -x5+x6 =3 (3)-2x1 +x3 +x7=1 (4)xi0 (i=1,2,7)(5)解：化为标准型Max Z=3x1-x2-x3+0 x4+0 x5-M x6-M x7 (1)s.t.s.t.本讲稿第四十六页，共八十三页大大M法求解法

24、求解cBxBbx1x2x3x4x5x6x73-1-100-M-Mx4x6x70-M-M11311-4-2-2101211000-1001000103-6MM-1 3M-10-M00-z 3M-1113/2111初始单纯形表010-210-23-1x3-1110重新计算检验数，结果如下页检验数判别换基迭代非基变量检验数为计算本讲稿第四十七页，共八十三页cBxBbx1x2x3x4x5x6x73-1-100-M-Mx4x60-M1-20100-10010-21-M00-1-1第2单纯形表010103-1x3-11100 x2-111-20-2112-50201-3MM-1计算检验数判别0-11-M-

25、M-11第3单纯形表大大M法求解法求解10本讲稿第四十八页，共八十三页检验数全非正,已经取得最优解,最优解为:X*=(4,1,9)T Z*=-2（z取极小值-2）cBxBbx1x2x3x4x5x6x73-1-100-M-Mx401-2010-101-2-104-1010103x3-110 x2-1110-2112-5020计算检验数判别011-M-M-11第3单纯形表41/3x13-2/32/3-5/30902/3-4/34/3-7/30-1/3-1/3 1/3-M2/3-M检验数判别-z-2最终单纯形表非基变量检验数为 大大M法求解法求解0本讲稿第四十九页，共八十三页没有单位矩阵，不符合构造

26、初始基的条件，需加入人工变量。人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为-M。M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。大大M法法 练习练习 maxZ=3x1-x2-2 x3 3x1+2 x2-3 x3=6 x1 -2 x2+x3=4 x1,x2,x3 0S.t.本讲稿第五十页，共八十三页按大按大M法构造人造基，引入人工变量法构造人造基，引入人工变量x4,x5 的辅助问题如下：的辅助问题如

27、下：maxZ=3x1 -x2 -2 x3-M x4-M x5 3x1+2 x2-3 x3 +x4 =6 x1 -2 x2+x3 +x5=4 x1,x2,x3,x4,x5 0C Cj j比比值值C CB BX XB Bb b检验数检验数 j jx x1 1x x2 2x x3 3x x4 4x x5 53 3-1-1-2-2-M-M-M-M6 63 32 2-3-31 10 04 41 1-2-21 10 01 1-10M-10M3+4M3+4M-1-1-2-2M-2-2M0 00 0 x x4 4x x5 5-M-M-M-M2 24 4本讲稿第五十一页，共八十三页C Cj j比比值值C CB

28、BX XB Bb b检验数检验数 j jx x1 1x x2 2x x3 3x x4 4x x5 53 3-1-1-2-2-M-M-M-M6 63 32 2-3-31 10 04 41 1-2-21 10 01 13+4M3+4M-1-1-2-2M-2-2M0 00 0 x x4 4x x5 5-M-M-M-M2 24 4检验数检验数 j j2 21 12/32/3-1-11/31/30 02 20 0-8/3-8/32 2-1/3-1/31 10 0-3-8M/3-3-8M/31+2M1+2M-1-4M/3-1-4M/30 0 x x1 1x x5 53 3-M-M-1 1检验数检验数 j

29、j3 31 1-2/3-2/30 01/61/61/21/21 10 0-4/3-4/31 1-1/6-1/61/21/20 0-5/3-5/30 0-M-5/6-M-5/6-M-1/2-M-1/2x x1 1x x3 33 3-2-2本讲稿第五十二页，共八十三页 两阶段法：引入人工变量 xn+i 0，i=1,m；构造:Max z=-xn+1-xn+2-xn+m s.t.a11x1+a12x2+a1nxn+xn+1=b1 a21x1+a22x2+a2nxn+xn+2=b2 .am1x1+am2x2+amnxn+xn+m=bm x1,x2.xn,xn+1,xn+m 0本讲稿第五十三页，共八十三页

30、 第一阶段求解上述问题：第一阶段求解上述问题：显然，显然，x xj j=0 =0 j j=1,=1,n n;x xn+in+i=b bi i i i=1,=1,m m 是基本可行解是基本可行解,它对应的基它对应的基 是单位矩阵。是单位矩阵。结论：结论：若得到的最优解满足若得到的最优解满足 x xn+in+i=0=0 i i=1,=1,m m 则是原问题的基本可行解则是原问题的基本可行解;否则，原问题无否则，原问题无可行解。可行解。得到原问题的基本可行解后，第二阶段求解原问题。得到原问题的基本可行解后，第二阶段求解原问题。本讲稿第五十四页，共八十三页例（LP）Max z=5x1+2x2+3x3-

31、x4 s.t.x1+2x2+3x3=15 2x1+x2+5x3=20 x1+2x2+4x3 +x4 =26 x1,x2,x3,x4 0本讲稿第五十五页，共八十三页 第一阶段问题（LP-1）Max z=-x5-x6 s.t.x1+2x2+3x3+x5 =15 2x1+x2+5x3+x6=20 x1+2x2+4x3 +x4 =26 x1,x2,x3,x4,x5,x6 0本讲稿第五十六页，共八十三页第一阶段第一阶段 (LP-1）得到原问题的基本可行解:(0，15/7，25/7，52/7)T 本讲稿第五十七页，共八十三页第二阶段第二阶段 把基本可行解填入表中 得到原问题的最优解:(25/3，10/3，

32、0，11)T 最优目标值：112/3本讲稿第五十八页，共八十三页例 求解下列线形规划问题：单纯形表与线形规划解的讨论单纯形表与线形规划解的讨论无可行解本讲稿第五十九页，共八十三页引入人工变量x7,x8,并利用大M法求解：maxZmaxZ=-3x=-3x1 1-2x-2x2 2-x-x3 3-Mx-Mx7 7-Mx-Mx8 8 x x1 1+x+x2 2+x+x3 3+x+x4 4 =6 =6 x x1 1 -x -x3 3 -x -x5 5 +x +x7 7 =4 =4 x x2 2-x-x3 3 -x -x6 6 +x +x8 8=3=3 x xj j0,j=1,2,3,4,5,60,j=1

33、,2,3,4,5,6本讲稿第六十页，共八十三页在第三张单纯形表中，所有的非基检验数都小于0，所有为最优单纯形表，但人工变量X71为基变量。本讲稿第六十一页，共八十三页例 求解下列线形规划问题：单纯形表与线形规划解的讨论单纯形表与线形规划解的讨论无界解本讲稿第六十二页，共八十三页Cj比比值值CBXBbZx x1 1x x2 2x x3 3x x4 42 22 20 00 01 11 11 11 10 02 21/21/21 10 01 10 02 22 20 00 0 x x3 3X X4 40 00 0表中表中1 120,20,但非基变量但非基变量x1x1对应的系数列向量对应的系数列向量P10

34、P10，所有原，所有原线形规划问题无界解。线形规划问题无界解。本讲稿第六十三页，共八十三页退化解p29 当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解；产生原因：有时存在两个或两个以上相同的最小比值，导致下次迭代出现一个或多个基变量取值为零本讲稿第六十四页，共八十三页例 求解下列线形规划问题：退化解本讲稿第六十五页，共八十三页解：引入松弛变量x5、x6、x7，化标准型本讲稿第六十六页，共八十三页Cj3-802-24000比值CBXBbx1x2x3x4x5x6x70X501-32-43610000X601-24-1601000 x7100100011Z03-802

35、-240000X500-8-3301-10/3X101-24-16010/0 x7100100111Z00-85-420-300X530-80301-133X111-24060112x310010011Z50-80-420-3-5本讲稿第六十七页，共八十三页无穷多最优解(p33-34)例：某一非基变量检验数n0，存在Pn列向量中至少一个元素ain0,且能够找出另一最优解本讲稿第六十八页，共八十三页对maxZ=CX AX bX0A=(P1 P2 Pn)(1)、已有初始可行基B，求B-1，XB=B-1 b(2)、计算j=Cj-CB B-1Pj 若全部 j 0，则计算Z0=CB B-1 b,停；否则

36、，取m+k=maxj，Xm+k换入。j0改进单纯形法本讲稿第六十九页，共八十三页(3)、计算Pm+k=B-1Pm+k，若Pm+k 0，则无有限最优解,停；否则(5)、新基B。转(1)。=minbiAim+karm+k 0=brarm+kXr 换出(4)、最小比值法：本讲稿第七十页，共八十三页(5)、1)求初等变换矩阵Er(r 换出变量在基中的位置)B=(P1 Pr-1 Pr Pr+1 Pm)B=(P1 Pr-1 Pm+k Pr+1 Pm)BB=(B-1P1,B-1Pr-1,B-1Pr,B-1Pr+1,B-1Pm)=EB-1B=(B-1P1,B-1Pr-1,B-1Pm+k,B-1Pr+1,B-1

37、Pm)本讲稿第七十一页，共八十三页B-1B=1 a1m+k 1 ar-1m+k arm+k ar+1m+k 1 amm+k 1 rr本讲稿第七十二页，共八十三页E Er r=(B=(B-1-1B)B)-1-1=a a1m+k1m+ka arm+krm+k-a ar-1 m+kr-1 m+ka arm+krm+k-1 1a arm+krm+ka ar+1 m+kr+1 m+ka arm+krm+k-a am m+km m+ka arm+krm+k-1 11 11 11 1本讲稿第七十三页，共八十三页改进单纯形法的步骤：本讲稿第七十四页，共八十三页例 用改进单纯形法求解：本讲稿第七十五页，共八十三页本讲稿第七十六页，共八十三页本讲稿第七十七页，共八十三页重复以上步骤，进入第二循环：本讲稿第七十八页，共八十三页本讲稿第七十九页，共八十三页本讲稿第八十页，共八十三页进入第三循环：本讲稿第八十一页，共八十三页即x*=(20,20,0,0)T为最优解，目标函数最优值maxZ100本讲稿第八十二页，共八十三页单纯法总结单纯法总结添加松驰变量、人工变量、列出初始单纯形表计算非基变量各列的检验数 j基变量中有否非零的人工变量所有 j0？有否非基变量检验数为零对任一 j0有否 aik0迭代换基是无界解是否唯一最优解否无可行解是否12345无穷多最优解是最优解是本讲稿第八十三页，共八十三页