单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,ppt课件完整,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,ppt课件完整,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,ppt课件完整,*,单纯形法求解,动态演示,在求解,LP,问题时,有人给出了图解法,但对多维变量时,却无能为力,于是,美国数学家,GBDantgig(,丹捷格,),发明了一种“单纯形法”的代数算法，尤其是方便于计算机运算。这是运筹学史上最辉煌的阶段。,1,ppt课件完整,单纯形法求解动态演示在求解LP问题时,有人给出了图解法,但,线性规划问题标准型的矩阵形式：,Max Z=CX,（,a,）,s.t.AX=b,（,b,）,X,0,（,c,）,a,11,a,12,.a,1n,b,1,A=,a,21,a,22,.a,2n,b,=,b,2,a,m1,a,m2,.a,mn,b,m,一、关于标准型解的若干基本概念,2,ppt课件完整,线性规划问题标准型的矩阵形式：a11,基矩阵,示例,:,0,0,0,0,3,2,0,2,0,0,0,1,0,1,0,x1,x2,x4,x3,0,0,1,3,0,0,3,2,1,=,目标函数,约束条件,行列式,0,基矩阵,X1,x2,x3,为基变量,x4,为非基变量,3,ppt课件完整,基矩阵 示例:000032020001010 x1,因为,B,为基,故有,X,B,+B,-1,N X,N,=B,-1,b,，,解得可行解,X,B,=B,-1,b-B,-1,NX,N,，,代入目标函数,Z,，,Z =,C,B,B,-1,b+,(C,N,-,C,B,B,-1,N),X,N,令非基变量,X,N,=0,，则有,X,T,=(X,B,X,N,),T,=,（,B,-1,b,0),T,Z=,C,B,B,-1,b,AX=b,Z=CX,设,A=,（,B,N,）（,B,为一个基，即线性无关向量组,R(A)=R(B),）,X,T,=(X,B,X,N,),T,（,X,B,为基变量，,X,N,为非基变量）,C=(C,B,C,N,),（,C,B,为基变量系数，,C,N,为非基变量系数）,则有：,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,1,、单纯形法原理：,4,ppt课件完整,因为B为基,故有 XB+B-1N XN=B-1b，,Z =,C,B,B,-1,b+,(C,N,-,C,B,B,-1,N),X,N,如果,C,N,-,C,B,B,-1,N,小于,0,，无论,X,N,取任何,大于,0,值，只会让,Z,变小，因此我们可以通过,C,N,-,C,B,B,-1,N,来判断,Z,取得是不是最大值。,如果存在一个,C,N,-,C,B,B,-1,N,大于,0,，则说明,Z,的值会随着,X,N,增大而增大，说明,Z,有调整的余地。,定理一：若某个基本可行解所对应的检验向量,C,N,-,C,B,B,-1,N=0,19,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,X2,s1,s2,S3,b,比值,50,100,0,0,0,2,S1,0,1,1,1,0,0,300,S2,0,2,1,0,1,0,400,x2,0,1,0,0,1,250,Z,j=,C,B,N,j,Z=C,B,B,-1,b,可行解,X,B,=B,-1,b-B,-1,NX,N,=0,20,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,X2,s1,s2,S3,b,比值,50,100,0,0,0,2,S1,0,1,1,1,0,0,300,S2,0,2,1,0,1,0,400,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,Z=C,B,B,-1,b,21,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,X2,s1,s2,S3,b,比值,50,100,0,0,0,2,S1,0,1,1,1,0,0,300,S2,0,2,1,0,1,0,400,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,Z=C,B,B,-1,b,22,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,X2,s1,s2,S3,b,比值,50,100,0,0,0,2,S1,0,1,1,1,0,0,300,S2,0,2,1,0,1,0,400,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,Z=C,B,B,-1,b,23,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,X2,s1,s2,S3,b,比值,50,100,0,0,0,2,S1,0,1,0,1,0,-1,50,S2,0,2,0,0,1,-1,150,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,Z=25000,24,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,X2,s1,s2,S3,b,比值,50,100,0,0,0,2,S1,0,1,0,1,0,-1,50,S2,0,2,0,0,1,-1,150,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,0,100,0,0,100,Z=25000,25,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,X2,s1,s2,S3,b,比值,50,100,0,0,0,2,S1,0,1,0,1,0,-1,50,S2,0,2,0,0,1,-1,150,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,0,100,0,0,100,Z=25000,50,0,0,0,-100,26,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,X2,s1,s2,S3,b,比值,50,100,0,0,0,2,S1,0,1,0,1,0,-1,50,S2,0,2,0,0,1,-1,150,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,0,100,0,0,100,Z=25000,50,0,0,0,-100,27,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,X2,s1,s2,S3,b,比值,50,100,0,0,0,2,S1,0,1,0,1,0,-1,50,S2,0,2,0,0,1,-1,150,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,0,100,0,0,100,Z=,25000,50,0,0,0,-100,28,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,X2,s1,s2,S3,b,比值,50,100,0,0,0,3,S1,0,1,0,1,0,-1,50,S2,0,2,0,0,1,-1,150,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,x1,50,x1,50,29,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,x2,s1,s2,S3,b,比值,50,100,0,0,0,3,x1,50,1,0,1,0,-1,50,S2,0,2,0,0,1,-1,150,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,30,ppt课件完整,初始单纯形表迭代次数基变量CBx1x2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,x2,s1,s2,S3,b,比值,50,100,0,0,0,3,x1,50,1,0,1,0,-1,50,S2,0,2,0,0,1,-1,150,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,31,ppt课件完整,初始单纯形表迭代次数基变量CBx1x2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,X2,s1,s2,S3,b,比值,50,100,0,0,0,3,x1,50,1,0,1,0,-1,50,S2,0,0,0,-2,1,1,50,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,Z=,27500,32,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,X2,s1,s2,S3,b,比值,50,100,0,0,0,3,x1,50,1,0,1,0,-1,50,S2,0,0,0,-2,1,1,50,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,50,100,50,0,50,Z=,27500,33,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,初始单纯形表,迭代次数,基变量,C,B,x1,X2,s1,s2,S3,b,比值,50,100,0,0,0,3,x1,50,1,0,1,0,-1,50,S2,0,0,0,-2,1,1,50,x2,100,0,1,0,0,1,250,Z,j=,C,B,N,j,50,100,50,0,50,Z=,27500,0,0,-50,0,-50,34,ppt课件完整,初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50,表格中，检验系数,j,全部小于或等于,0,，根据判断规则，,Z,值为最优值（,Z=27500,），其解：,X1=50,S1=50,X2=250,s2=s3=0,为模型的最优解。,35,ppt课件完整,表格中，检验系数j全部小于或等于0，根据判断规则，Z值为最,感谢亲观看此幻灯片，此课件部分内容来源于网络，,如有侵权请及时联系我们删除，谢谢配合！,36,感谢亲观看此幻灯片，此课件部分内容来源于网络，36,感谢亲观看此幻灯片，此课件部分内容来源于网络，,如有侵权请及时联系我们删除，谢谢配合！,感谢亲观看此幻灯片，此课件部分内容来源于网络，,