对偶问题和对偶单纯形法.ppt

第七章 对偶问题和对偶单纯形法,一、问题的提出二、对偶问题和原问题的转换三、对偶规划的性质四、对偶单纯形法五、交替单纯形法,一、问题的提出,原问题：a和b产量各为多少可以使利润最大？,一、问题的提出,原LP 模型：Max z=50 x1+100 x2 s.t：1x1+1x2300 2x1+1 x2400 0 x1+1 x2250 x1 0，x2 0,一、问题的提出,若考虑将三种设备出租，如何合理确定各设备的租金y1、y2、y3（元/台时）？目标函数：min z=300y1+400 y2+250 y3约束条件：y1+2y2 50 y1+y2+y3 100 y1、y2、y3 0,一、问题的提出,这样两个线性规划问题就是一对对偶问题。称其中一个为原问题（LP问题），另一个为对偶问题（DLP问题）。由于它们内在的联系，可以根据其中一个模型，写出其对偶问题的模型。,二、对偶问题和原问题的转换,LP问题和DLP问题的关系：,规范形(LP)Max z=cT x s.t.Ax b x 0,(DLP)Min f=bT ys.t.AT y c y 0,二、对偶问题和原问题的转换,1、对于规范型，直接按对应关系转换例：Max z=20 x1+8 x2+6 x3 s.t：8x1+3x2+2x3 250 2x1+x2 50 4x1+3x3 150 x1，x2，x3 0写出该线性规划问题的对偶问题。,二、对偶问题和原问题的转换,则对偶问题为：Min f=250 y1+50 y2+150 y3 s.t：8y1+2y2+4y3 20 3y1+y2 8 2 y1+3y3 6 y1，y2，y3 0,二、对偶问题和原问题的转换,2、对于非规范形式，先化为规范形式例：写出线性规划模型的对偶问题Min z=3x1+4 x2+6 x3 s.t：x1+3x2-2x3+x4 25 2x1+7x3+2x4 60 2x1+2x2-4x3 30 x1，x2，x4 0，x3 无非负约束,二、对偶问题和原问题的转换,首先转换为规范形Min z=3x1+4 x2+6 x3变为Max(-z)=-3x1-4 x2-6 x3 约束条件x1+3x2-2x3+x4 25等同于x1+3x2-2x3+x4 25和 x1+3x2-2x3+x4 25联立,二、对偶问题和原问题的转换,2x1+7x3+2x4 60可转化为-2x1-7x3-2x4-60 x3 无非负约束，则令x3 x3-x3x3-x3 0则原LP模型可以化为规范形：,二、对偶问题和原问题的转换,Max(-z)=-3x1-4 x2-6 x3+6 x3 s.t：x1+3x2-2 x3+2 x3+x4 25-x1-3x2+2 x3-2 x3-x4-25-2x1-7 x3+7x3-2x4-60 2x1+2x2-4 x3+4 x3 30 x1,x2,x3,x3,x4 0,二、对偶问题和原问题的转换,故DLP可写出：Min f25 y1-25 y2-60 y3+30 y4 s.t：y1-y2-2 y3+2y4-3 3y1-3y2+2y4-4-2y1+2y2-7y3-4 y4-6 2y1-2y2+7y3+4y4 6 y1-y2-2y3 0 y1，y2，y3，y4，y5 0,二、对偶问题和原问题的转换,将DLP模型整理可得：Min f25 y5+60 y3+30 y4 s.t：y5+2 y3+2y4-3 3y5+2y4-4-2y5+7y3-4y4-6 y5+2y3 0 y5 无非负约束，y3 0，y4 0,LP与DLP的一般对应关系,练习,写出下面LP问题的DLP模型Min z=x1+2 x2+5 x3 s.t：2x1+3x2+x3 10 3x1+x2+x3 50 x1+x3 20 x1 0，x2 0，x3 无非负约束,三、对偶规划的性质,1、对称性：对偶问题的对偶是原问题。2、弱对偶性：若X是原问题（max）的可行解，Y是对偶问题（min）的可行解，则存在CXbTY,三、对偶规划的性质,推论 a：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。推论b：若原问题解无界，则其对偶问题无可行解；若对偶问题解无界，则原问题无可行解。（逆命题不成立）推论c：若原问题有可行解而对偶问题无可行解，则原问题无界；反之，对偶问题有可行解而原问题无可行解，则对偶问题解无界。,三、对偶规划的性质,3、最优性：若x,y分别是原问题和对偶问题的可行解,且cx=bTy，那么x,y分别为原问题和对偶问题的最优解。,三、对偶规划的性质,4、强对偶性：若原问题和对偶问题都有可行解，则两者都有最优解，且最优目标函数值相等。,三、对偶规划的性质,5、互补松弛定理：在原问题的最优解中，如果对应某一约束条件的对偶变量值不为0，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为0，即若Yi*0，则有aijxj*bi若aijxj*bi，则有Yi*0,对偶问题解的意义,若x*,y*分别为（LP）和（DLP）的最优解，那么，cx*=bT y*。根据 f=bTy*=b1y1*+b2y2*+bmym*可知 f/bi=yi*yi*表示 bi 变化1个单位对目标 f 产生的影响。,对偶问题解的意义,因此：对偶问题的最优解就是原问题中相应资源常数项的影子价格。若B是初始基在最优表中的形式，影子价格向量 Y*=BCB确定影子价格在原问题和对偶问题中的对应关系后，可以由原问题最优单纯形表求对偶问题最优解。,对偶问题解的意义,如范例最优表：,对偶问题解的意义,原问题的最优解为：x1=50 x2=250 x4=50对偶问题的最优解为：y1=50 y2=0 y3=50（影子价格）,四、对偶单纯形法,最优表特征：,基向量为单位向量,右端项非负,检验数非正,四、对偶单纯形法,单纯形法的迭代：,保证基向量为单位向量,保证右端项非负,检验数由正变为非正,右端项由负变为非负,保证基向量为单位向量,四、对偶单纯形法,对偶单纯形法的迭代：,保证检验数非正,四、对偶单纯形法,在满足对偶单纯形迭代前提条件的表上确定主行和出基变量：,1、按最小b值原则确定主行和出基变量,四、对偶单纯形法,确定主列和进基变量,0,-50,0,-50,0,0,j,2.5,50,-20,1,1,-1,0,x5,250,0,0,0,1,0,100,x2,0,1,0,0,0,x6,5,j/alj,27500,0,50,100,50,zj,-3000,0,-10,0,0,0,x6,50,1,-2,0,0,0,x4,50,0,1,0,1,50,x1,0,0,100,50,b,x4,x3,x2,x1,CB,基变量XB,1、按最小比值原则确定主列和进基变量,主元,四、对偶单纯形法,迭代：与原始单纯形法一样，通过行变换将主列变为主元为1的单位列。,四、对偶单纯形法,所有b值都大于0，该表中的解为可行解，故最优解为（140，120，40，0，130，0）。,四、对偶单纯形法,对偶单纯形法过程：1、建立初始对偶单纯形表,对应一个基本解,所有检验数均非正；2、若b0,则得到最优解,停止；若有b 0 则选其中最小的bl所在的第l行的基变量为出基变量；,四、对偶单纯形法,3、若所有alj0(j=1,2,n)，则原问题无可行解,停止；若有alj0 则选=minj/aljalj0=k/alk那么xk为进基变量；4、以alk为主元,作矩阵行变换使其变为1,该列其他元变为0。所有b值非负时达到最优。,四、对偶单纯形法,练习：用对偶单纯形法求解Min f=2x1+3x2+4x3 S.t.x1+2x2+x3 3 2x1-x2+x3 4 x1,x2,x3 0,四、对偶单纯形法,首先变形，使其具备对偶单纯形迭代的前提条件：Max z=-2x1-3x2-4x3 s.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4 x1,x2,x3,x4,x5 0,-2,-3,-2,0,-1/5,-8/5,-9/5,0,0,jcjzj,-28/5,1/5,8/5,-11/5,-3,-2,zj,11/5,-2/5,-1/5,7/5,0,1,x1,2/5,1/5,-2/5,-1/5,1,0,x2,2,8/5,j/alj,-1,0,-1,-4,0,jcjzj,-4,1,0,-3,1,-2,zj,2,-1/2,0,3/2,-1/2,1,x1,-1,-1/2,1,1/2,-5/2,0,x4,4/3,1,j/alj,0,0,-4,-3,-2,jcjzj,0,0,0,0,0,0,zj,-4,1,0,-3,1,-2,0,x5,-3,0,1,-1,-2,-1,0,x4,0,0,-4,-3,-2,b,x5,x4,x3,x2,x1,CB,基变量XB,对偶单纯形法与单纯形法的比较,五、交替单纯形法,不管是原始单纯形法，还是对偶单纯形法，初始表都有前提条件。如果两种方法的初始条件都不能满足，怎么办？,五、交替单纯形法,例如：Max z=-3x1+2x2-x3 s.t：-x1-x2+x3-4 2x1+3x2+x320 3x1+x2+x3 28 x1，x2，x3 0,五、交替单纯形法,检验数不满足非正，不能用对偶单纯形法,右端项不满足非负，不能用原始单纯形法,五、交替单纯形法,解决办法：先变为原始可行或对偶可行对上例的处理是：先用对偶单纯形法，将其变为原始可行，再用原始单纯形法迭代求解。,五、交替单纯形法,五、交替单纯形法,8,24,8,4,b,0,0,2,1,0,-5,j,0,0,1,0,0,x5,24,1,1,2,0,2,0,x6,0,0,0,0,x6,-2,-2,2,2,zj,8/3,3,4,0,-1,0,x5,-1,-1,1,1,2,x2,0,-1,2,-3,比值,x4,x3,x2,x1,CB,基变量XB,右端项已满足非负，应用原始单纯形法,五、交替单纯形法,满足最优性条件，已达最优。,作业,教材125页：8（1）、9题。,