资源描述
,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2.3,对偶单纯形法,一、什么是对偶单纯形法？,对偶单纯形法,是应用,对偶原理,求解原始线性规划的一种方法,在原始问题的单纯形表格上进行,对偶处理,。,注意：,不是解对偶问题的单纯形法！,二、对偶单纯形法的基本思想,1,、对“单纯形法”求解过程认识的提升,从更高的层次理解单纯形法,初始可行基,（对应一个初始基本可行解）,迭代,另一个可行基,（对应另一个基本可行解），直至,所有检验数,0,为止,。,所有检验数,0,意味着,，,说明,原始问题的最优基也是对偶问题的可行基,。换言之，当原始问题的基,B,既是原始可行基又是对偶可行基时，,B,成为最优基。,定理,2-5,B,是线性规划的最优基,的,充要条件,是，,B,是可行基，同时也是对偶可行基。,LP,原问题,:,若,B,是,A,中的一个基,可行基,B,对应的解是基本可行解，则,B,是可行基,对偶可行基,若单纯形乘子,是对偶问题的可行解，则,B,是对偶可行基,是对偶问题的可行解,检验数,等价,证明：,单纯形法的求解过程就是：,在保持,原始可行,的前提下,(b,列保持,0),，,通过逐步迭代,实现对偶可行,(,检验数行,0),。,2,、,对偶单纯形法思想：,换个角度考虑,LP,求解过程,：,保持,对偶可行,的前提下（,检验数行保持,0,）,，通过逐步迭代,实现原始可行,（,b,列,0,，从非可行解变成可行解）。,对偶单纯形法的思想（图示）,原问题,初始基本可行解,保持为基本可行解,初始对偶可行解,保持对偶可行性,最优解,基本可行性,对偶可行性,始终满足解的可行性,始终满足对偶可行性,三、对偶单纯形法的实施,1,、使用条件：,检验数全部,0,；,解答列至少一个元素,0,；,2,、实施对偶单纯形法的基本原则：,在保持对偶可行的前提下进行基变换,每一次迭代过程中取出,基变量中的一个负分量,作为,换出变量,去,替换,某个,非基变量,(,作为,换入变量,),使原始问题的非可行解向可行解靠近。,3,、计算步骤,：,建立初始单纯形表，计算检验数行。,解答列,0,已得最优解；,至少一个元素,0,转下步,;,解答列,0,原始单纯形法；,至少一个元素,0,另外处理；,检验数全部,0,（非基变量检验数,0,基变换：,先确定换出变量,解答列中的负元素,（一般选最小的负元素）,对应的基变量,出基,；,即,相应的行,为主元行,。,然后,确定换入变量,原则,是：在,保持对偶可行的前提,下，,减少原始问题的不可行性,。,如果,(,最小比值原则,),则选,为换入变量,相应的列为,主元列,主元行和主元列交叉处的元素,为主元素,。,若,要计算最小比值吗？为什么？,按主元素进行换基迭代,（旋转运算、枢运算）,，,将主元素变成,1,，主元列变成单位向量,，得到新的单纯形表。,循环以上步骤，直至求出最优解。,3,、举例,用对偶单纯形法求解,LP,：,化为标准型,将两个等式约束两边分别乘以,-1,，得,以此形式进行列表求解，满足对偶单纯形法的基本条件，具体如下：,-2/-2 -4/-3 -,比,值,-2 -3 -4 0 0,0,-Z,-1 -2 -1 1 0,-2 1 -3 0 1,-3,-4,x,4,x,5,0,0,-2 -3 -4 0 0,x,1,x,2,x,3,x,4,x,5,c,j,x,j,b,X,B,C,B,-4/-5/2 -1/-1/2,比,值,0 -4 -1 0 -1,0,cj-zj,0 -5/2 1/2 1 -1/2,1 -1/2 3/2 0 -1/2,-1,2,x,4,x,1,0,-2,-2 -3 -4 0 0,x,1,x,2,x,3,x,4,x,5,c,j,x,j,b,X,B,C,B,0 0 -3/5 -8/5 -1/5,0,cj-zj,0 1 -1/5 -2/5 1/5,1 0 7/5 -1/5 -2/5,2/5,11/5,x,2,x,1,-3,-2,-2 -3 -4 0 0,x,1,x,2,x,3,x,4,x,5,c,j,x,j,b,X,B,C,B,最优解,:,X*=,（,11/5,，,2/5,0,0,0,）,T,，,最优值,:,minW,=-,maxZ,*=,-11/5(-2)+2/5(-3)=28/5,4,、举例,用对偶单纯形法求解,LP,：,化为,标准型,将三个等式约束两边分别乘以,-1,，然后,列表求解如下：,-3/-1 -9/-1 -,比,值,-3 -9 0 0 0,0,-Z,-1,-1,1 0 0,-1 -4 0 1 0,-1 -7 0 0 1,-2,-3,-3,y,3,y,4,y,5,0,0,0,-3 -9 0 0 0,y,1,y,2,y,3,y,4,y,5,c,j,y,j,b,X,B,C,B,-6/-3 -3/-1 -,比,值,0 -6 -3 0 0,6,-Z,1 1 -1 0 0,0 -3 -1 1 0,0 -6 -1 0 1,2,-1,-1,y,1,y,4,y,5,-3,0,0,-3 -9 0 0 0,y,1,y,2,y,3,y,4,y,5,c,j,y,j,b,X,B,C,B,0 0 -1 -2 0,8,-Z,1 0 -4/3 1/3 0,0 1 1/3 -1/3 0,0 0 1 -2 1,5/3,1/3,1,y,1,y,2,y,5,-3,-9,0,-3 -9 0 0 0,y,1,y,2,y,3,y,4,y,5,c,j,y,j,b,X,B,C,B,最优解是,Y*=,（,5/3,，,1/3,，,0,，,0,，,1,）,T,，,目标函数最优值为,W,min,=-,Z,max,=8,思考题：,能否不要化为标准型，直接按,极小化问题用单纯形表格迭代求解？,（结合课后小组讨论,4,一并思考研究）,
展开阅读全文