第1章 单纯形法PPT讲稿.ppt
第1页，共83页，编辑于2022年，星期日线性规划单纯形法线性规划单纯形法 单纯形法(Simplex Method)是美国人丹捷格(G.Dantzig)1947年创建的这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。单纯形法的表现形式：代数法表格法矩阵法第2页，共83页，编辑于2022年，星期日单纯形法形法线性规划问题的几何意义：凸集：没有凹入部分，内部没有空洞。实习圆、实心球体、实心立方体都是凸集；两个凸集的交集是凸集。若线性规划问题存在可行域，则可行域是凸集。线性规划问题的基可行解对应可行域的顶点。若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。第3页，共83页，编辑于2022年，星期日单纯形法的一般原理单纯形法的一般原理考虑线形规划问题：max ZCX AXb X0如果有可行域DXRn|AX=b,X0非空有界，则D上的最优目标函数值ZCX一定可以在D的顶点达到。第4页，共83页，编辑于2022年，星期日单纯形法的基本思路形法的基本思路根据线性规划问题的标准型，从可行域中某个基可行解一个顶点）开始，转换到另一个基可行解（顶点），并且使目标函数达到最大值时，问题就得到最优解。因此得到5个步骤：初始解判优判无界换基迭代第5页，共83页，编辑于2022年，星期日确定初始的基本可行解确定初始的基本可行解确定初始的基本可行解确定初始的可行基初始的可行基确定对应初始基本可行解确定第6页，共83页，编辑于2022年，星期日最优解判别最优解判别不妨假设不妨假设不妨假设不妨假设 A=（B,N）（B为一个基为一个基为一个基为一个基）相应地有相应地有 Xt=(XB B,X,XN)t C=(CB B,C,CN N)由式由式 max ZCX AXb X0 Z=Z=(CB,CN)(XB B,X,XN N)t t=C=CB B X XB B+C CN N XN N AX AX（B,N)(XB,N)(XB,X,XN N)t t=B=B X XB B+N+N XN=b第7页，共83页，编辑于2022年，星期日因为因为因为因为B B为一个基为一个基为一个基为一个基,det(B)0,det(B)0有有有有 X XB B=B=B-1b-Bb-B-1-1N XN XN N （2.12.1）Z=CZ=CB B B-1-1b+(CN N-C CB B B-1-1N)N)XN N （2.22.2）令令XN N0 0，则基变量，则基变量，则基变量，则基变量X XB BB B-1-1b bX =(X=(XB B,XN N)=（B-1b,0b,0）T T为基础解，其目标函数值为为基础解，其目标函数值为为基础解，其目标函数值为为基础解，其目标函数值为 Z=Z=C CB B B B-1-1b只要只要XB B=B=B-1-1b=0,Xb=0,Xt t=（B B-1b,0b,0）=0=0X X为基础可行解为基础可行解为基础可行解为基础可行解,B,B就是可行基。就是可行基。就是可行基。就是可行基。第8页，共83页，编辑于2022年，星期日对公式对公式对公式对公式Z=CZ=CB B B B-1-1b+(C(CN N-CB B B-1-1N)N)X XN N （2.2）若满足若满足 C CN-C CB B B B-1-1N =0N =0=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）第10页，共83页，编辑于2022年，星期日单纯形法的求解步形法的求解步骤1、确定初始基可行解 basic feasible solution 先找出初始可行基，确定初始基可行解，建立初始单纯形表 initial simplex tableau。若能从列向量中直接观察到存在个线性无关的单位向量，经过重新安排次序便可得到一个可行基。对约束条件都是，则加入的松驰变量就构成初始基。对约束条件都是，且不存在单位矩阵的等式约束，就要采用人造基的方法：大M法、对偶单纯法。第11页，共83页，编辑于2022年，星期日单纯形法的求解步形法的求解步骤 2 2：判：判优2、检验数判别得到初始基可行解后，要检验其是否为最优解：若是，问题解决；否则继续下一步。最优性判别定理：若所有检验数都j0，则找到最优解。第12页，共83页，编辑于2022年，星期日单纯形法的求解步形法的求解步骤 3 3：判无界：判无界3、判断是否无界在j 0,j=m+1,n 中，若有某个k 对应 xk 的系数列向量 Pk0，则此问题无界，停止计算；否则转入下一步。即在单纯形表中的某 xk 检验数k 0，而该列系数全小于0，则无界。第13页，共83页，编辑于2022年，星期日单纯形法的求解步形法的求解步骤 4 4：换基基4、确定换入变量和换出变量换入变量=进基变量=Entering Variable根据 max(j 0)=k，确定 xk 为换入变量换出变量=出基变量=Leaving Variable按 规则计算，可确定 xl 为换出变量。第14页，共83页，编辑于2022年，星期日单纯形法的求解步形法的求解步骤 5 5：迭代：迭代 5、迭代以 alk 为主元素（pivot number）进行迭代，得到新的单纯形表。迭代又称旋转运算，或高斯消去法。第15页，共83页，编辑于2022年，星期日单纯形法的求解步形法的求解步骤重复步骤25，直到终止。判优换基迭代判优换基迭代判优换基迭代判优 最优解第16页，共83页，编辑于2022年，星期日换入变量的确定最大增加原则假设检验向量 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为换入变量。为换入变量。基本可行解的改进基本可行解的改进第17页，共83页，编辑于2022年，星期日换出变量的确定最小比值原则基本可行解的改进基本可行解的改进第18页，共83页，编辑于2022年，星期日例：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）第19页，共83页，编辑于2022年，星期日取x4,x5为基变量，x1,x2,x3为非基变量，在这一情况下：（1 1）确定初始基本可行解）确定初始基本可行解第20页，共83页，编辑于2022年，星期日令XN=0,XB=B-1b=b=基本可行解X=(0,0,0,8,7)T目标函数值：第21页，共83页，编辑于2022年，星期日（2）检验X=(0,0,0,8,7)T是否最优：由最优解判别定理，非基变量检验数130，340,所以X=(0,0,0,8,7)T不是最优解第22页，共83页，编辑于2022年，星期日 选取换入变量：因为max3,4=4,按最大增加原则，取x3为换入变量 选取换出变量 因为：所以取min(8/2,7/1)=4,由最小取值原则选取x4为换出变量 （3）基本可行解X=(0,0,0,8,7)T的改进第23页，共83页，编辑于2022年，星期日（4）求改进的基本可行解X：第24页，共83页，编辑于2022年，星期日再转向步骤（2）第25页，共83页，编辑于2022年，星期日（2）检验X=(0,0,4,0,3)T是否最优：由最优解判别定理，非基变量检验数110，所以X=(0,0,4,0,3)T不是最优解第26页，共83页，编辑于2022年，星期日 选取换入变量：因为110,按最大增加原则，取x1为换入变量 选取换出变量 因为：所以取min(4/(1/2),3/(5/2)=6/5,由最小取值原则选取x5为换出变量 （3）基本可行解X=(0,0,4,0,3)T的改进第27页，共83页，编辑于2022年，星期日（4）求改进的基本可行解X：第28页，共83页，编辑于2022年，星期日再转向步骤（2）第29页，共83页，编辑于2022年，星期日（2）检验X=(6/5,0,17/5,0,0)T是否最优：由最优解判别定理，非基变量检验数2,4,5 都小于0，所以X=(6/5,0,17/5,0,0)T是最优解第30页，共83页，编辑于2022年，星期日表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。一、单纯形法表一、单纯形法表CjC1C2CjCn比值CBXBbx1x2xjxnCB1xB1b1a11a12a1ja1n1CB2xB2b2a21a22a2ja2n2CBnxBnbmam1am2amjamnm检验数j-Z12jn表格单纯形法表格单纯形法第31页，共83页，编辑于2022年，星期日将线性规划问题化成标准型。找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。计算各非基变量xj的检验数j=Cj-CBPj，若所有j0，则问题已得到最优解，停止计算，否则转入下步。在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下步。根据maxjj0=k原则，确定xk为换入变量(进基变量)，再按规则计算：=minbi/aik|aik0=bl/aik 确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为0，转第 步。二、单纯形法的计算步骤二、单纯形法的计算步骤 第32页，共83页，编辑于2022年，星期日例例、某航空食品公司利用甲、乙、丙三种原料生产、某航空食品公司利用甲、乙、丙三种原料生产A1A1、A2A2、A3A3和和A4A4四种食品，每月可供应该公司的原料及每种食品可四种食品，每月可供应该公司的原料及每种食品可获利情况如下表所示，试求该食品公司每月应如何安排生获利情况如下表所示，试求该食品公司每月应如何安排生产计划，才能使总利润最大。产计划，才能使总利润最大。15001500300030002500250020002000利润（元利润（元/吨）吨）2002000 01 12 21 1丙丙3003003 31 11 10 0乙乙5005002 22 21 11 1甲甲每月原料供每月原料供应量（吨）应量（吨）A4A3A2A1 消耗消耗 食品食品原料原料第33页，共83页，编辑于2022年，星期日解：此问题的线性规划模型为Max Z=2000 x1+2500 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.第34页，共83页，编辑于2022年，星期日cBxBbx1x2x3x4x5x6x72000250030001500000 x5x6x700050030020010111221123010001000102000250030001500000-z 30002503002002001初始单纯形表0-1-1-11000-3-1-2x330001100重新计算检验数，结果如下页检验数判别换基迭代非基变量检验数为计算第35页，共83页，编辑于2022年，星期日cBxBbx1x2x3x4x5x6x72000250030001500000 x5x600200121230100010-1-1000-3500150000-3000-z 05033.3-1第2单纯形表0-1-11000-3-1-2x3300011001x415001/3-1/3-1/333.30-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第36页，共83页，编辑于2022年，星期日 maxZ=3x1+5 x2+0 x3+0 x4+0 x5=0 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 三、单纯形法计算举例三、单纯形法计算举例Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9第37页，共83页，编辑于2022年，星期日检验数检验数 j81010060101/2012300-21x3x2x5050-30300-5/208-4Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9第38页，共83页，编辑于2022年，星期日Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数检验数 j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最优解最优解:X*=(4,6,4,0,0)T，Z*=42第39页，共83页，编辑于2022年，星期日最优基 Cj35000比值CBXBbx1x2x3x4x50 x340012/3-1/35x260101/203x14100-2/31/3检验数j-42000-1/2-1x3x2x1最优基的逆最优基的逆 最优基和最优基的逆最优基和最优基的逆第40页，共83页，编辑于2022年，星期日例如例如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 x1,x2,x3,x4 0Cj比值CBXBb检验数jx1x2x3x432002-211031-301x3x40003200-3检验数j80-512x3x103-31-301-90110-3此时，检验数2=11 0，还没有得到最优解。确定x2进基，但x2所在列的系数向量元素非正，无界值不存在，有进基变量但无离基变量。第41页，共83页，编辑于2022年，星期日人工变量问题人工变量问题 用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“”时，加入松弛变量就形成了初始基。但实际存在“”或“”型的约束，没有现成的单位矩阵。一、人工变量一、人工变量 采用人造基的办法：采用人造基的办法：人工构造单位矩阵人工构造单位矩阵人工构造单位矩阵人工构造单位矩阵在没有单位列向量的等式约束中加入人工变量，构成原线性规划问在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。题的伴随问题，从而得到一个初始基。人工变量是在等式中人为加进的，只有它等于人工变量是在等式中人为加进的，只有它等于0 0时，约束条件才是它本时，约束条件才是它本来的意义。来的意义。处理方法有两种：处理方法有两种：大大M M 法法两阶段法两阶段法第42页，共83页，编辑于2022年，星期日大大M M法法人工变量开始作为基变量，最后要换出来，全部成为非基变量，问题才有解。假设人工变量在目标函数中的价值系数为-M，M为很大的正数；只要基变量中还存在人工变量，目标函数就不能实现极大化。第43页，共83页，编辑于2022年，星期日大大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第44页，共83页，编辑于2022年，星期日显然，xj=0 j=1,n;xn+i=bi i=1,m 是基本可行解。对应的基是单位矩阵。结论：若得到的最优解满足 xn+i=0 i=1,m 则是原问题的最优解；否则，原问题无可行解。第45页，共83页，编辑于2022年，星期日例 现有线性规划问题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.第46页，共83页，编辑于2022年，星期日大大M法求解法求解cBxBbx1x2x3x4x5x6x73-1-100-M-Mx4x6x70-M-M11311-4-2-2101211000-1001000103-6MM-13M-10-M00-z 3M-1113/2111初始单纯形表010-210-23-1x3-1110重新计算检验数，结果如下页检验数判别换基迭代非基变量检验数为计算第47页，共83页，编辑于2022年，星期日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-M-11第3单纯形表大大M法求解法求解10第48页，共83页，编辑于2022年，星期日检验数全非正,已经取得最优解,最优解为: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/31/3-M2/3-M检验数判别-z-2最终单纯形表非基变量检验数为 大大M法求解法求解0第49页，共83页，编辑于2022年，星期日没有单位矩阵，不符合构造初始基的条件，需加入人工变量。人工变量最终必须等于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.第50页，共83页，编辑于2022年，星期日按大按大M法构造人造基，引入人工变量法构造人造基，引入人工变量x4,x5 的辅助问题如下：的辅助问题如下：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第51页，共83页，编辑于2022年，星期日C 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 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 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第52页，共83页，编辑于2022年，星期日 两阶段法：引入人工变量 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第53页，共83页，编辑于2022年，星期日 第一阶段求解上述问题：第一阶段求解上述问题：显然，显然，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 则是原问题的基本可行解则是原问题的基本可行解;否则，原问题无可否则，原问题无可行解。行解。得到原问题的基本可行解后，第二阶段求解原问题。得到原问题的基本可行解后，第二阶段求解原问题。第54页，共83页，编辑于2022年，星期日例（LP）Max z=5x1+2x2+3x3-x4 s.t.x1+2x2+3x3=15 2x1+x2+5x3=20 x1+2x2+4x3 +x4 =26 x1,x2,x3,x4 0第55页，共83页，编辑于2022年，星期日 第一阶段问题（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第56页，共83页，编辑于2022年，星期日第一阶段第一阶段 (LP-1）得到原问题的基本可行解:(0，15/7，25/7，52/7)T 第57页，共83页，编辑于2022年，星期日第二阶段第二阶段 把基本可行解填入表中 得到原问题的最优解:(25/3，10/3，0，11)T 最优目标值：112/3第58页，共83页，编辑于2022年，星期日例 求解下列线形规划问题：单纯形表与线形规划解的讨论单纯形表与线形规划解的讨论无可行解第59页，共83页，编辑于2022年，星期日引入人工变量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,2,3,4,5,6第60页，共83页，编辑于2022年，星期日在第三张单纯形表中，所有的非基检验数都小于0，所有为最优单纯形表，但人工变量X71为基变量。第61页，共83页，编辑于2022年，星期日例 求解下列线形规划问题：单纯形表与线形规划解的讨论单纯形表与线形规划解的讨论无界解第62页，共83页，编辑于2022年，星期日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对应的系数列向量对应的系数列向量P10P10，所有原线，所有原线形规划问题无界解。形规划问题无界解。第63页，共83页，编辑于2022年，星期日退化解p29 当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解；产生原因：有时存在两个或两个以上相同的最小比值，导致下次迭代出现一个或多个基变量取值为零第64页，共83页，编辑于2022年，星期日例 求解下列线形规划问题：退化解第65页，共83页，编辑于2022年，星期日解：引入松弛变量x5、x6、x7，化标准型第66页，共83页，编辑于2022年，星期日Cj3-802-24000比值CBXBbx1x2x3x4x5x6x70X501-32-43610000X601-24-1601000 x7100100011Z03-802-240000X500-8-3301-10/3X101-24-16010/0 x7100100111Z00-85-420-300X530-80301-133X111-24060112x310010011Z50-80-420-3-5第67页，共83页，编辑于2022年，星期日无穷多最优解(p33-34)例：某一非基变量检验数n0，存在Pn列向量中至少一个元素ain0,且能够找出另一最优解第68页，共83页，编辑于2022年，星期日对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,停；否则，取m+k=maxj，Xm+k换入。j0改进单纯形法第69页，共83页，编辑于2022年，星期日(3)、计算Pm+k=B-1Pm+k，若Pm+k 0，则无有限最优解,停；否则(5)、新基B。转(1)。=minbiAim+karm+k 0=brarm+kXr 换出(4)、最小比值法：第70页，共83页，编辑于2022年，星期日(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-1Pm)第71页，共83页，编辑于2022年，星期日B-1B=1 a1m+k 1 ar-1m+k arm+k ar+1m+k 1 amm+k 1 rr第72页，共83页，编辑于2022年，星期日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第73页，共83页，编辑于2022年，星期日改进单纯形法的步骤：第74页，共83页，编辑于2022年，星期日例 用改进单纯形法求解：第75页，共83页，编辑于2022年，星期日第76页，共83页，编辑于2022年，星期日第77页，共83页，编辑于2022年，星期日重复以上步骤，进入第二循环：第78页，共83页，编辑于2022年，星期日第79页，共83页，编辑于2022年，星期日第80页，共83页，编辑于2022年，星期日进入第三循环：第81页，共83页，编辑于2022年，星期日即x*=(20,20,0,0)T为最优解，目标函数最优值maxZ100第82页，共83页，编辑于2022年，星期日单纯法总结单纯法总结添加松驰变量、人工变量、列出初始单纯形表计算非基变量各列的检验数 j基变量中有否非零的人工变量所有 j0？有否非基变量检验数为零对任一 j0有否 aik0迭代换基是无界解是否唯一最优解否无可行解是否12345无穷多最优解是最优解是第83页，共83页，编辑于2022年，星期日
