毕业答辩ppt模板-中国地质大学.ppt

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,运筹学,*,华东交通大学工业工程与物流管理系,第一章 单纯形法,线性规划单纯形法,单纯形法,(Simplex Method),是美国人丹捷格,(G.Dantzig)1947,年创建的,这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。,单纯形法的表现形式：,代数法,表格法,矩阵法,单纯形法,线性规划问题的几何意义：,凸集：没有凹入部分，内部没有空洞。实习圆、实心球体、实心立方体都是凸集；两个凸集的交集是凸集。,若线性规划问题存在可行域，则可行域是凸集。,线性规划问题的基可行解对应可行域的顶点。,若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。,单纯形法的一般原理,考虑线形规划问题：,max Z,CX,AX,b,X0,如果有可行域,D,XRn|AX=b,X0,非空有界，则,D,上的最优目标函数值,Z,CX,一定可以在,D,的顶点达到。,单纯形法的基本思路,根据线性规划问题的标准型，从可行域中某个基可行解一个顶点）开始，转换到另一个基可行解（顶点），并且使目标函数达到最大值时，问题就得到最优解。,因此得到,5,个步骤：,初始解,判优,判无界,换基,迭代,确定初始的基本可行解,确定初始的基本可行解确定初始的可行基,初始的可行基确定,对应初始基本可行解确定,最优解判别,不妨假设,A=,（,B,N,）（,B,为一个基,）,相应地有,X,t,=(X,B,X,N,),t,C=(C,B,C,N,),由式,max Z,CX,AX,b,X0,Z=,(C,B,C,N,)(X,B,X,N,),t,=C,B,X,B,+,C,N,X,N,AX,（,B,N)(X,B,X,N,),t,=B,X,B,+N,X,N,=b,因为,B,为一个基,det(B)0,有,X,B,=B,-1,b-B,-1,N X,N,（,2.1,）,Z=C,B,B,-1,b+,(C,N,-,C,B,B,-1,N),X,N,（,2.2,）,令,X,N,0,，则基变量,X,B,B,-1,b,X,=(X,B,X,N,)=,（,B,-1,b,0,）,T,为基础解，其目标函数值为,Z=,C,B,B,-1,b,只要,X,B,=B,-1,b=0,X,t,=,（,B,-1,b,0,）,=0,X,为基础可行解,B,就是可行基。,对公式,Z=C,B,B,-1,b+,(C,N,-C,B,B,-1,N),X,N,（,2.2,）,若满足,C,N,-,C,B,B,-1,N =0,则对任意的,x=0,有,Z=CX=0,则对应于基,B,的基础可行解,x,就是,基础最优解，此时的可行基就是最优基。,C,B,B,-1,A-C,为检验数。,由于基变量的检验数：,C,B,B,-1,B-C,B,=0,C,B,B,-1,A-C=,（,0,，,C,B,B,-1,N-C,N,）,单纯形法的求解步骤,1,、,确定初始基可行解,basic feasible solution,先找出初始可行基，确定初始基可行解，建立初始单纯形表,initial simplex tableau,。,若能从列向量中直接观察到存在个线性无关的单位向量，经过重新安排次序便可得到一个可行基。,对约束条件都是,，则加入的松驰变量就构成初始基。,对约束条件都是,，且不存在单位矩阵的等式约束，就要采用人造基的方法：大,M,法、对偶单纯法。,单纯形法的求解步骤,2,：判优,2,、检验数,判别,得到初始基可行解后，要检验其是否为最优解：,若是，问题解决；否则继续下一步。,最优性判别定理：若所有检验数都,j,0,，则找到最优解。,单纯形法的求解步骤,3,：判无界,3,、,判断是否无界,在,j,0,j,=,m,+1,n,中，若有某个,k,对应,x,k,的系数列向量,P,k,0,，则此问题无界，停止计算；否则转入下一步。,即在单纯形表中的某,x,k,检验数,k,0,，而该列系数全小于,0,，则无界。,单纯形法的求解步骤,4,：换基,4,、,确定换入变量和换出变量,换入变量,=,进基变量,=,Entering Variable,根据,max,(,j,0)=,k,，确定,x,k,为换入变量,换出变量,=,出基变量,=,Leaving Variable,按,规则计算，可确定,x,l,为换出变量,。,单纯形法的求解步骤,5,：迭代,5,、,迭代,以,a,lk,为主元素（,pivot number,）,进行迭代，得到新的单纯形表。,迭代又称旋转运算，,或高斯消去法。,单纯形法的求解步骤,重复步骤,25,，直到终止。,判优,换基,迭代,判优,换基,迭代,判优,换基,迭代,判优,最优解,换入变量的确定,最大增加原则,假设检验向量,N,(C,N,-C,B,B,-1,N)=(,m+1,m+2,n,),若其中有两个以上的检验数为正，选取最大正检验数所对应的,非基变量为换入变量。,若：,max,j,|,j,0,m+1jn=,m+K,则选取对应的,x,m+k,为换入变量。,基本可行解的改进,换出变量的确定,最小比值原则,基本可行解的改进,例：,maxZ=5x,1,+2x,2,+3x,3,-x,4,+x,5,x,1,+2x,2,+2x,3,+x,4,=8,3x,1,+4x,2,+x,3,+x,5,=7,x,1,x,2,x,3,x,4,x,5,0,其中,用初等变换求改进了的基本可行解,在系数矩阵,A,中存在一个单位矩阵,B,（,p,4,p,5,）,取,x,4,x,5,为基变量，,x,1,x,2,x,3,为非基变量，在这一情况下：,（,1,）确定初始基本可行解,令,X,N,=0,X,B,=B,-1,b=b=,基本可行解,X=(0,0,0,8,7),T,目标函数值：,（,2,）检验,X=(0,0,0,8,7),T,是否最优：,由最优解判别定理，非基变量检验数,1,30,，,3,40,所以,X=(0,0,0,8,7)T,不是最优解,选取换入变量：,因为,max3,4=4,按最大增加原则，取,x,3,为换入变量,选取换出变量,因为：,所以取,min(8/2,7/1)=4,由最小取值原则选取,x,4,为换出变量,（,3,）基本可行解,X=(0,0,0,8,7),T,的改进,（,4,）求改进的基本可行解,X,：,再转向步骤（,2,）,（,2,）检验,X,=(0,0,4,0,3),T,是否最优：,由最优解判别定理，非基变量检验数,1,10,，,所以,X,=(0,0,4,0,3)T,不是最优解,选取换入变量：,因为,1,10,按最大增加原则，取,x,1,为换入变量,选取换出变量,因为：,所以取,min(4/(1/2),3/(5/2)=6/5,由最小取值原则选取,x,5,为换出变量,（,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,0,),T,是最优解,表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。,一、单纯形法表,C,j,C,1,C,2,C,j,C,n,比,值,C,B,X,B,b,x,1,x,2,x,j,x,n,C,B1,x,B1,b,1,a,11,a,12,a,1j,a,1n,1,C,B2,x,B2,b,2,a,21,a,22,a,2j,a,2n,2,C,Bn,x,Bn,b,m,a,m1,a,m2,a,mj,a,mn,m,检验数,j,-Z,1,2,j,n,表格单纯形法,将线性规划问题化成标准型。,找出或构造一个,m,阶单位矩阵作为初始可行基，建立初始单纯形表。,计算各非基变量,x,j,的检验数,j,=,C,j,-C,B,P,j,，若所有,j,0,，则问题已得到最优解，停止计算，否则转入下步。,在大于,0,的检验数中，若某个,k,所对应的系数列向量,P,k,0,，则此问题是无界解，停止计算，否则转入下步。,根据,max,j,j,0=,k,原则，确定,x,k,为换入变量,(,进基变量,),，再按,规则计算：,=,min,b,i,/a,ik,|,a,ik,0=,b,l,/,a,ik,确定,x,B,l,为换出变量。建立新的单纯形表，此时基变量中,x,k,取代了,x,B,l,的位置。,以,a,ik,为主元素进行迭代，把,x,k,所对应的列向量变为单位列向量，即,a,ik,变为,1,，同列中其它元素为,0,，转第 步。,二、单纯形法的计算步骤,例,、某航空食品公司利用甲、乙、丙三种原料生产,A1,、,A2,、,A3,和,A4,四种食品，每月可供应该公司的原料及每种食品可获利情况如下表所示，试求该食品公司每月应如何安排生产计划，才能使总利润最大。,1500,3000,2500,2000,利润（元,/,吨）,200,0,1,2,1,丙,300,3,1,1,0,乙,500,2,2,1,1,甲,每月原料供应量（吨）,A4,A3,A2,A1,消耗 食品,原料,解：此问题的线性规划模型为,Max Z,=2000,x,1,+2500,x,2,+3000,x,3,+1500,x,4,(1),x,1,+,x,2,+2,x,3,+2,x,4,500,(2),x,2,+,x,3,+3,x,4,300,(3),x,1,+2,x,2,+,x,3,200,(4),x,i,0,(,i,=1,2,3,4)(5),x,1,+,x,2,+2,x,3,+2,x,4,+,x,5,=,500,(2),x,2,+,x,3,+3,x,4,+,x,6,=,300,(3),x,1,+2,x,2,+,x,3,+,x,7,=,200,(4),x,i,0,(,i,=1,2,7)(5),化为标准型：,Max Z,=2000,x,1,+2500,x,2,+3000,x,3,+1500,x,4,(1),s.t.,s.t.,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,2000,2500,3000,1500,0,0,0,x,5,x,6,x,7,0,0,0,500,300,200,1,0,1,1,1,2,2,1,1,2,3,0,1,0,0,0,1,0,0,0,1,0,2000,2500,3000,1500,0,0,0,-z,3000,250,300,200,200,1,初始单纯形表,0,-1,-1,-1,100,0,-3,-1,-2,x,3,3000,1,100,重新计算检验数，结果如下页,检验数判别,换基,迭代,非基变量检验数为,计算,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,2000,2500,3000,1500,0,0,0,x,5,x,6,0,0,200,1,2,1,2,3,0,1,0,0,0,1,0,-1,-,1000,-,3500,1500,0,0,-,3000,-z,0,50,33.3,-,1,第,2,单纯形表,0,-1,-1,100,0,-3,-1,-2,x,3,3000,1,100,1,x,4,1500,1/3,-1/3,-1/3,33.3,0,-2/3,0,33.3,-1/3,-1/3,-7/3,-4/3,0,-500,-,2500,-,500,-,3000,-650000,检验数全非正,已经取得最优解,最优解为,:,X,*=(0,0,200,33.3),T,Z,*=650000,计算,非基变量检验数为,检验数判别,最终单纯形表,Final Simplex tableau,0,maxZ=3x,1,+5,x,2,+0,x,3,+0,x,4,+0,x,5,=0,x,1,+,x,3,=8,2,x,2,+,x,4,=12,3x,1,+4,x,2,+,x,5,=36,三、单纯形法计算举例,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,3,5,0,0,0,8,1,0,1,0,0,12,0,2,0,1,0,36,3,4,0,0,1,x,3,x,4,x,5,0,0,0,0,3,5,0,0,0,-,12/2=6,36/4=9,检验数,j,8,1,0,1,0,0,6,0,1,0,1/2,0,12,3,0,0,-2,1,x,3,x,2,x,5,0,5,0,-30,3,0,0,-5/2,0,8,-,4,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,3,5,0,0,0,8,1,0,1,0,0,12,0,2,0,1,0,36,3,4,0,0,1,x,3,x,4,x,5,0,0,0,0,3,5,0,0,0,-,12/2=6,36/4=9,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,3,5,0,0,0,8,1,0,1,0,0,6,0,1,0,1/2,0,12,3,0,0,-2,1,x,3,x,2,x,5,0,5,0,-30,3,0,0,-5/2,0,8,-,4,检验数,j,4,0,0,1,2/3,-1/3,6,0,1,0,1/2,0,4,1,0,0,-2/3,1/3,x,3,x,2,x,1,0,5,3,-42,0,0,0,-1/2,-1,最优解,:,X,*,=(4,6,4,0,0),T,，,Z,*,=42,最优基,C,j,3,5,0,0,0,比,值,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,4,0,0,1,2/3,-1/3,5,x,2,6,0,1,0,1/2,0,3,x,1,4,1,0,0,-2/3,1/3,检验数,j,-42,0,0,0,-1/2,-1,x,3,x,2,x,1,最优基的逆,最优基和最优基的逆,例如,maxZ=,3x,1,+2,x,2,-2x,1,+,x,2,2,x,1,-3,x,2,3,x,1,x,2,0,S.t.,标准化,maxZ=,3x,1,+2,x,2,-2x,1,+,x,2,+,x,3,=2,x,1,-3,x,2,+,x,4,=3,x,1,x,2,x,3,x,4,0,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,3,2,0,0,2,-2,1,1,0,3,1,-3,0,1,x,3,x,4,0,0,0,3,2,0,0,-,3,检验数,j,8,0,-5,1,2,x,3,x,1,0,3,-,-,3,1,-3,0,1,-9,0,11,0,-3,此时，,检验数,2,=11,0,，还没有得到最优解。,确定,x,2,进基，但,x,2,所在列的系数向量元素非正，无界,值不存在，有进基变量但无离基变量。,人工变量问题,用单纯形法解题时，需要有一个单位阵作为初始基。,当约束条件都是,“,”,时，加入松弛变量就形成了初始基。,但实际存在,“,”,或,“,”,型的约束，没有现成的单位矩阵。,一、人工变量,采用人造基的办法：,人工构造单位矩阵,在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。,人工变量是在等式中人为加进的，只有它等于,0,时，约束条件才是它本来的意义。,处理方法有两种：,大,M,法,两阶段法,大,M,法,人工变量开始作为基变量，最后要换出来，全部成为非基变量，问题才有解。,假设人工变量在目标函数中的价值系数为,-,M,，,M,为很大的正数；,只要基变量中还存在人工变量，目标函数就不能实现极大化。,大,M,法：,引入人工变量,x,n+i,0,（,i,=1,m,）及充分大正数,M,。,得到：,Max,z,=,c,1,x,1,+,c,2,x,2,+,+,c,n,x,n,-,Mx,n+1,-,-,Mx,n+m,s.t.,a,11,x,1,+,a,12,x,2,+,+,a,1n,x,n,+,x,n+1,=,b,1,a,21,x,1,+,a,22,x,2,+,+,a,2n,x,n,+,x,n+2,=,b,2,.,.,.,a,m1,x,1,+,a,m2,x,2,+,+,a,mn,x,n,+,x,n+m,=,b,m,x,1,，,x,2,，,，,x,n,，,x,n+1,，,，,x,n+m,0,显然,，,x,j,=0,j,=1,n,;,x,n+i,=,b,i,i,=1,m,是基本可行解。,对应的基是单位矩阵。,结论：,若得到的最优解满足,x,n+i,=0,i,=1,m,则是原问题的最优解；否则，原问题无可行解。,例 现有线性规划问题,Min Z,=,-,3,x,1,+,x,2,+,x,3,(1),x,1,-,2,x,2,+,x,3,11,(2),-,4,x,1,+x,2,+2,x,3,3,(3),-,2,x,1,+,x,3,=1 (4),x,i,0,(,i,=1,2,3)(5),x,1,-,2,x,2,+,x,3,+,x,4,=,11,(2),-,4,x,1,+,x,2,+2,x,3,-,x,5,+,x,6,=,3,(3),-,2,x,1,+,x,3,+,x,7,=,1,(4),x,i,0,(,i,=1,2,7)(5),解：化为标准型,Max Z,=3,x,1,-,x,2,-,x,3,+0,x,4,+0,x,5,-,M,x,6,-,M,x,7,(1),s.t.,s.t.,大,M,法求解,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,3,-1,-1,0,0,-M,-M,x,4,x,6,x,7,0,-M,-M,11,3,1,1,-4,-2,-2,1,0,1,2,1,1,0,0,0,-1,0,0,1,0,0,0,1,0,3,-6M,M-1,3,M-1,0,-M,0,0,-z,3,M-1,11,3/2,1,1,1,初始单纯形表,0,1,0,-2,1,0,-2,3,-1,x,3,-1,1,10,重新计算检验数，结果如下页,检验数判别,换基,迭代,非基变量检验数为,计算,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,3,-1,-1,0,0,-M,-M,x,4,x,6,0,-M,1,-2,0,1,0,0,-1,0,0,1,0,-2,1,-M,0,0,-,1,-,1,第,2,单纯形表,0,1,0,1,0,3,-1,x,3,-1,1,10,0,x,2,-1,1,1,-2,0,-2,1,12,-5,0,2,0,1-,3M,M-1,计算,检验数判别,0,-1,1-M,-M-1,1,第,3,单纯形表,大,M,法求解,1,0,检验数全非正,已经取得最优解,最优解为,:,X,*=(4,1,9),T,Z,*=-2,（,z,取极小值,-2,）,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,3,-1,-1,0,0,-M,-M,x,4,0,1,-2,0,1,0,-1,0,1,-2,-1,0,4,-,-,1,0,1,0,1,0,3,x,3,-1,1,0,x,2,-1,1,1,0,-2,1,12,-5,0,2,0,计算,检验数判别,0,1,1-M,-M-1,1,第,3,单纯形表,4,1/3,x,1,3,-,2,/3,2/3,-,5,/3,0,9,0,2/3,-,4,/3,4/3,-,7,/3,0,-,1,/3,-,1,/3,1/,3,-,M,2/,3,-,M,检验数判别,-z,-2,最终单纯形表,非基变量检验数为,大,M,法求解,0,没有单位矩阵，不符合构造初始基的条件，需加入人工变量。,人工变量最终必须等于,0,才能保持原问题性质不变。,为保证人工变量为,0,，在目标函数中令其系数为,-M,。,M,为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。,如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。,大,M,法,练习,maxZ=,3x,1,-,x,2,-2,x,3,3x,1,+2,x,2,-3,x,3,=6,x,1,-2,x,2,+,x,3,=4,x,1,x,2,x,3,0,S.t.,按大,M,法构造人造基，引入人工变量,x,4,x,5,的辅助问题如下：,maxZ=,3x,1,-,x,2,-2,x,3,-M,x,4,-M,x,5,3x,1,+2,x,2,-3,x,3,+,x,4,=6,x,1,-2,x,2,+,x,3,+,x,5,=4,x,1,x,2,x,3,x,4,x,5,0,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,3,-1,-2,-M,-M,6,3,2,-3,1,0,4,1,-2,1,0,1,-10M,3+4M,-1,-2-2M,0,0,x,4,x,5,-M,-M,2,4,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,3,-1,-2,-M,-M,6,3,2,-3,1,0,4,1,-2,1,0,1,3+4M,-1,-2-2M,0,0,x,4,x,5,-M,-M,2,4,检验数,j,2,1,2/3,-1,1/3,0,2,0,-8/3,2,-1/3,1,0,-3-8M/3,1+2M,-1-4M/3,0,x,1,x,5,3,-M,-,1,检验数,j,3,1,-2/3,0,1/6,1/2,1,0,-4/3,1,-1/6,1/2,0,-5/3,0,-M-5/6,-M-1/2,x,1,x,3,3,-2,两阶段法：,引入人工变量,x,n+i,0,，,i,=1,m,；,构造,:,Max,z,=-,x,n+1,-,x,n+2,-,x,n+m,s.t.,a,11,x,1,+,a,12,x,2,+,+,a,1n,x,n,+,x,n+1,=,b,1,a,21,x,1,+,a,22,x,2,+,+,a,2n,x,n,+,x,n+2,=,b,2,.,.,.,a,m1,x,1,+,a,m2,x,2,+,+,a,mn,x,n,+,x,n+m,=,b,m,x,1,x,2,.,x,n,x,n+1,x,n+m,0,第一阶段求解上述问题：,显然，,x,j,=0,j,=1,n,;,x,n+i,=,b,i,i,=1,m,是基本可行解,它对应的基,是单位矩阵。,结论：,若得到的最优解满足,x,n+i,=0,i,=1,m,则是原问题的基本可行解,;,否则，原问题无可行解。,得到原问题的基本可行解后，第二阶段求解原问题。,例（,LP,）,Max,z,=5,x,1,+2,x,2,+3,x,3,-,x,4,s.t.,x,1,+,2,x,2,+,3,x,3,=15,2,x,1,+,x,2,+5,x,3,=20,x,1,+2,x,2,+4,x,3,+,x,4,=26,x,1,x,2,x,3,x,4,0,第一阶段问题（,LP-1,）,Max,z,=-,x,5,-,x,6,s.t.,x,1,+2,x,2,+3,x,3,+,x,5,=15,2,x,1,+,x,2,+5,x,3,+,x,6,=20,x,1,+2,x,2,+4,x,3,+,x,4,=26,x,1,x,2,x,3,x,4,x,5,x,6,0,两阶段法：,第一阶段,(LP-1,）,得到原问题的基本可行解,:(0,，,15/7,，,25/7,，,52/7),T,第二阶段,把基本可行解填入表中,得到原问题的最优解,:(25/3,，,10/3,，,0,，,11),T,最优目标值：,112/3,例 求解下列线形规划问题：,单纯形表与线形规划解的讨论,无可行解,引入人工变量,x7,x8,并利用大,M,法求解：,maxZ,=-3x,1,-2x,2,-x,3,-Mx,7,-Mx,8,x,1,+x,2,+x,3,+x,4,=6,x,1,-x,3,-x,5,+x,7,=4,x,2,-x,3,-x,6,+x,8,=3,x,j,0,j=1,2,3,4,5,6,在第三张单纯形表中，所有的非基检验数都小于,0,，所有为最优单纯形表，但人工变量,X,7,1,为基变量。,例 求解下列线形规划问题：,单纯形表与线形规划解的讨论,无界解,C,j,比,值,C,B,X,B,b,Z,x,1,x,2,x,3,x,4,2,2,0,0,1,1,1,1,0,2,1/2,1,0,1,0,2,2,0,0,x,3,X,4,0,0,表中,1,20,但非基变量,x1,对应的系数列向量,P10,，所有原线形规划问题无界解。,退化解,p29,当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解；,产生原因：有时存在两个或两个以上相同的最小比值,，导致下次迭代出现一个或多个基变量取值为零,例 求解下列线形规划问题：,退化解,解：引入松弛变量,x,5,、,x,6,、,x,7,，,化标准型,Cj,3,-80,2,-24,0,0,0,比,值,CB,XB,b,x1,x2,x3,x4,x5,x6,x7,0,X5,0,1,-32,-4,36,1,0,0,0,0,X6,0,1,-24,-1,6,0,1,0,0,0,x7,1,0,0,1,0,0,0,1,1,Z,0,3,-80,2,-24,0,0,0,0,X5,0,0,-8,-3,30,1,-1,0,/,3,X1,0,1,-24,-1,6,0,1,0,/,0,x7,1,0,0,1,0,0,1,1,1,Z,0,0,-8,5,-42,0,-3,0,0,X5,3,0,-8,0,30,1,-1,3,3,X1,1,1,-24,0,6,0,1,1,2,x3,1,0,0,1,0,0,1,1,Z,5,0,-8,0,-42,0,-3,-5,无穷多最优解,(p33-34),例：,某一非基变量检验数,n,0,，存在,P,n,列向量中至少一个元素,a,in,0,且能够找出另一最优解,对,maxZ=CX,AX,b,X,0,A=(P,1,P,2,P,n,),(1),、已有初始可行基,B,，求,B,-1,，,X,B,=,B,-1,b,(2),、计算,j,=C,j,-C,B,B,-1,P,j,若全部,j,0,，,则计算,Z,0,=C,B,B,-1,b,停；否则，取,m+k,=max,j,，,X,m+k,换入。,j,0,改进单纯形法,(3),、计算,P,m+k,=,B,-1,P,m+k,，若,P,m+k,0,，,则无有限最优解,停；否则,(5),、新基,B,。转,(1),。,=min,b,i,A,im+k,a,rm+k,0,=,b,r,a,rm+k,X,r,换出,(4),、最小,比值法,：,(5),、,1),求初等变换矩阵,E,r,(r,换出变量在基中的位置,),B=(,P,1,P,r-1,P,r,P,r+1,P,m,),B=(,P,1,P,r-1,P,m+k,P,r+1,P,m,),BB=(B,-1,P,1,B,-1,P,r-1,B,-1,P,r,B,-1,P,r+1,B,-1,P,m,),=E,B,-1,B=(B,-1,P,1,B,-1,P,r-1,B,-1,P,m+k,B,-1,P,r+1,B,-1,P,m,),B,-1,B=,1,a,1m+k,1,a,r-1m+k,a,rm+k,a,r+1m+k,1,a,mm+k,1,r,r,E,r,=(B,-1,B),-1,=,a,1m+k,a,rm+k,-,a,r-1 m+k,a,rm+k,-,1,a,rm+k,a,r+1 m+k,a,rm+k,-,a,m m+k,a,rm+k,-,1,1,1,1,改进单纯形法的步骤：,例 用改进单纯形法求解：,重复以上步骤，进入第二循环：,进入第三循环：,即,x*=(20,20,0,0),T,为最优解，目标函数最优值,maxZ,100,单纯法总结,添加松驰变量、人工变量、列出初始单纯形表,计算非基变量各列的检验数,j,基变量中,有否非零的,人工变量,所有,j,0,？,有否非基,变量检验数,为零,对任一,j,0,有否,a,ik,0,迭代,换基,是,无界解,是,否,唯一,最优解,否,无可行解,是,否,1,2,3,4,5,无穷多最优解,是,最优解,是,