资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,ppt课件完整,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,ppt课件完整,*,单纯形法迭代原理,1,ppt课件完整,单纯形法迭代原理1ppt课件完整,三. 单纯形法的基本思想,1、顶点的逐步转移,即,从可行域的,一个顶点,（基本可行解）开始，,转移到另一个顶点,（另一个基本可行解）的迭代过程，,转移的条件,是,使,目标函数值得到改善,（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。,2,ppt课件完整,三. 单纯形法的基本思想1、顶点的逐步转移,根据,线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。,于是，,若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。,顶点转移的依据？,3,ppt课件完整,根据线性规划问题的可行域是凸多边形或凸多面体,转移条件？ 转移结果？,使,目标函数值得到改善,得到LP最优解，目标函数达到最优值,2需要解决的问题：,(1)为了使目标函数逐步变优，怎么转移？,(2)目标函数何时达到最优,判断标准是什么？,4,ppt课件完整,转移条件？,解LP问题单纯形法的基本思路：,初始可行基：设法在约束矩阵 中 构造出一个,m,阶,单位阵,初始基本可行解,检验数,进基,变量：检验数,离基,变量：最小比值准则,5,ppt课件完整,解LP问题单纯形法的基本思路： 初始可行基：设法在约束矩阵,1.确定初始基本可行解,LP:,？,希望在化,LP,的标准形式时，A中都含有一个,m,阶单位阵。,6,ppt课件完整,1.确定初始基本可行解 LP:？希望在化LP的标,观察法,观察系数矩阵中,是否含有,现成的单位阵？,LP限制条件中,全部是“”,类型的约束,将新增的,松弛变量,(,+,)作为初始基变量，对应的系数列向量构成单位阵；,LP,限制条件,有“”,类型的约束,左端新增,剩余变量,(,-,),后，再加上一个非负的新变量,人工变量,。,LP,限制条件,有“=”,类型的约束,直接在左端加上,人工变量,。,7,ppt课件完整,观察法7ppt课件完整,在引入人工变量后，与原先的约束方程,不完全等价,，为此，需要在,目标函数,上做些“,修正,”,大,M,法,或,两阶段法,非基变量取0，算出基变量，搭配在一起构成,初始基本可行解,：,8,ppt课件完整,在引入人工变量后，与原先的约束方程不完全等价，为此，需要在目,2.,建立判别准则,判断：,初始,基本可行解,或,经过若干次迭代后得到的,新,基本可行解,当前解,是否,为最优解？,一般（经过若干次迭代），对于基,B,，,用,非基变量,表出,基变量,的表达式,为：,典式,若,9,ppt课件完整,2.建立判别准则判断：初始基本可行解或经过若干次迭代后得到的,用,非基变量,表示,目标函数,的表达式：,典式,检验数,10,ppt课件完整,用非基变量表示目标函数的表达式： 典式检验数10ppt课件完,其中,（1）最优性判别定理,（2）有,无穷多个,“最优解”的判别定理,11,ppt课件完整,其中（1）最优性判别定理（2）有无穷多个“最优解”的判别定理,3、,进行基变换,（1）进基变量的确定,原则：,正检验数（或,最大,正检验数）所对应的变量进基,，,目的是使目标函数得到改善。,（2）离基变量的确定在,保持解的,可行性,的前提下，使目标函数,较快增大,。,12,ppt课件完整,3、进行基变换（1）进基变量的确定原则：正检验数（或最大,=, = 当 时，为,离基变量：,是可行解！,是否还是基本解？,是,14,ppt课件完整,离基变量：是可行解！是否还是基本解？是14ppt课件完整,从而，目标函数得到了改善。,15,ppt课件完整,从而，目标函数得到了改善。15ppt课件完整,第四节 单纯形表,16,ppt课件完整,第四节 单纯形表16ppt课件完整,（1）建立初始单纯形表，假定B=I，b0,设maxZ=c,1,x,1,+c,2,x,2,+c,n,x,n,将目标函数改写为：-Z+c,1,x,1,+c,2,x,2,+c,n,x,n,=0,写成增广矩阵的形式,17,ppt课件完整,（1）建立初始单纯形表，假定B=I，b0将目标函数改写为：,-Z,x,1,x,2,x,m,x,m+1,x,n,右端,检验数行,-Z,0,-Z,X,B,c,j,x,1,x,2,x,m,x,m+1,x,n,c,1,c,2,c,m,c,m+1,c,n,C,B,最后一行是检验数行，标出了对应决策变量,x,j,的检验数,第一行是价值系数行，标出了决策变量,x,j,的价值系数,c,j,第二行是标示行，标出了表中主体各行的含义。,第一列标出了基变量的价值系数。,第二列标出了当前基变量的名称。,第三列是右端项，前,m,个元素是当前基本可行解的基变量的取值,最,小,比,值,准,则,18,ppt课件完整,-Zx1x2xmxm+1xn右端检验数行-Z0-ZXBc,-Z,0,-Z,X,B,c,j,x,1,x,2,x,m,x,m+1,x,n,c,1,c,2,c,m,c,m+1,c,n,C,B,将初始数据填入上表，可得到初始单纯形表。,观察,检验数行,，若所有的 ，则停止计算。否则进行下一步。,1.检验当前基本可行解是否为最优解？,最优性判别定理,19,ppt课件完整,-Z0-ZXBcjx1x2xmxm+1xnc1c2cmc,2.检验是否为无界解？,则该,LP,无最优解。,3.选择进基变量,从而,x,m+t,是进基变量，,p,m+t,为进基向量，并称表中,p,m+t,所在的列为,主列,。,4.选择离基变量,最小比值准则,从而,x,l,是离基变量， 并称表中离基变量所在的行为,主行,。,5. 基变换,主行和主列的交叉元素,称为,主元素,a,l,m+t,20,ppt课件完整,2.检验是否为无界解？则该LP无最优解。3.选择进基变量从而,-Z,0,-Z,X,B,c,j,x,1,x,2,x,m,x,m+1,x,n,c,1,c,2,c,m,c,m+1,c,n,C,B,n,m,mn,m,m,n,m,n,m,a,a,a,a,a,a,s,s,.,0,.,0,0,.,1,.,0,0,.,.,.,.,.,.,.,.,0,.,1,0,.,0,.,0,1,1,1,2,1,2,1,1,1,+,+,+,+,m,m,m,b,x,c,b,x,c,b,x,c,:,:,:,2,2,2,1,1,1,c,l,x,l,b,l,0 0 . . . 0 a,l,m+1,. . . a,ln, ,主行同除以,a,l,m+t,即将主元素化为,1,将新的主行的,(,-a,i,m+t,)倍分别加到第i行，即将主列的其他元素化为0.,将新的主行的,倍分别加到最后一行，即将,x,m+t,的检验数化为0.,21,ppt课件完整,-Z0-ZXBcjx1x2xmxm+1xnc1c2cmc,-Z,0,-Z,X,B,c,j,x,1,x,2,x,m,x,m+1,x,n,c,1,c,2,c,m,c,m+1,c,n,C,B,n,m,mn,m,m,n,m,n,m,a,a,a,a,a,a,s,s,.,0,.,0,0,.,1,.,0,0,.,.,.,.,.,.,.,.,0,.,1,0,.,0,.,0,1,1,1,2,1,2,1,1,1,+,+,+,+,m,m,m,b,x,c,b,x,c,b,x,c,:,:,:,2,2,2,1,1,1,c,m+t,x,m+t,b,m+t,0 0 . . . 0 a,l,m+1,. a,ln,6. 回到1,对新解作最优性检验。,22,ppt课件完整,-Z0-ZXBcjx1x2xmxm+1xnc1c2cm,例：用单纯形法求解线性规划问题,解：,标准化：,以,对应的系数列向量,构成一单位矩阵，取初始基,为基变量，,为非基变量。,23,ppt课件完整,例：用单纯形法求解线性规划问题解： 标准化：以对应的系数列向,建立初始单纯行表, ,基变换, ,确定,为离基变量，而,为进基变量，以,为主元素。,24,ppt课件完整,建立初始单纯行表 基变换 确定为离基变量,基变换, , ,确定,为离基变量，而,为进基变量，以,为主元素。,25,ppt课件完整,基变换 确定为离基变量，而为进基变,基变换, ,确定,为离基变量，而,为进基变量，以,为主元素。,26,ppt课件完整,基变换 确定为离基变量，而为进基变量，以为主元素,上表中检验数满足最优性条件，得到最优解：,及最大值：,27,ppt课件完整,上表中检验数满足最优性条件，得到最优解：及最大值：27ppt,说 明,用单纯形法从当前解迭代到下一个基本可行解时，两者之间,只有一个基变量不同,（从而也有一个非基变量不同），称两者为,相邻的,基本可行解（即相邻的顶点）。,28,ppt课件完整,说 明28ppt课件完整,作 业,P44,1.4,分别用,图解法,和,单纯形法,求解下述线性规划问题。,29,ppt课件完整,感谢亲观看此幻灯片，此课件部分内容来源于网络，,如有侵权请及时联系我们删除，谢谢配合！,感谢亲观看此幻灯片，此课件部分内容来源于网络，,
展开阅读全文