苏大张芳华运筹学课件第二章对偶理论.ppt

第二章 对偶线性规划,对偶的定义对偶问题的性质对偶单纯形法对偶的经济解释灵敏度分析,原始问题min z=CTXs.t.AXbX 0,对偶问题Max w=bT ys.t.AT y C y 0,min,b,A,CT,C,AT,bT,max,m,n,m,n,一、对偶的定义,对偶的定义,当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。,原始问题（prime)与对偶问题之间的关系,极小化问题（min)极大化问题（max)变量 Xj 0 约束 aijwj bi Xj:unr aijwj=bi Xj 0 aijwj bi约束 aijxj bi 变量 wj 0 aijxj=bi wj:unr aijxj bi wj 0,对偶问题的形成,min z=2x1+4x2-x3s.t.3x1-x2+2x3 6-x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max w=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y4 2-y1+2y2+y3+3y4 4 2y1-3y2+2y3-y4-1 y1 0,y2,y3 0,y4 0,=,unr,=,x10,x20,x3:unr,对偶问题的解p84,当原始问题有最优解时，对偶问题也有最优解，而且两者相等；原问题的最优解和对偶问题的最优解构成互补松弛关系；原问题最优表中松弛变量的检验数的反号就是对偶问题的最优解；对偶问题最优表中松弛变量的检验数的反号就是原问题的最优解。,1、对偶的对偶就是原始问题,二、对偶问题的性质,2、可行解的目标函数值之间的关系 设XF、y F分别是原始问题和对偶问题的可行解z=CTXF y TAXF y Tb=w3、最优解的目标函数值之间的关系 设Xo、yo分别是原始问题和对偶问题的最优解 z=CTXo=y oTAXo=y oTb=w,4、原始问题和对偶问题最优解之间的互补松弛关系,min z=CTXs.t.AX-u=b X,u0,max w=bTys.t.ATy+v=C y,v0,min z=CTXs.t.AXb X 0,max w=bTys.t.ATyC y0,互补松弛关系,min z=CTXs.t.AX-u=bX,u 0,max w=bTys.t.ATy+v=Cy,v 0,XTv=0yTu=0,m,n,=,y,v,AT,I,C,n,=,A,u,-I,b,n,m,m,X,原始问题和对偶问题变量、松弛变量的维数,y1 yi ym vm+1 vm+j vn+m,x1 xj xn un+1 un+i un+m,对偶问题的变量 对偶问题的松弛变量,原始问题的变量 原始问题的松弛变量,xjvm+j=0yiun+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0,1、单纯形表最优基必须同时满足两个条件,右端列中的所有i0,可行性条件,全部检验数j0,最优性条件,（1）,（2）,三、对偶单纯形法,单纯形法的迭代过程,i 0 j0,i0 j 0,i0 j0,对偶单纯形法的迭代过程,i0 j0,2、对偶单纯形法 例题1,min=15y1+5y2+11y3s.t.3y1+2y2+2y355y1+y2+2y34y1，y2，y30,解:将每个不等式两边乘以-1,再引入松驰变量S1和S2,则上述问题化为:,直接写成标准式时有-S1和-S2,则无法有初始基,因此乘个-1,min=15y1+5y2+11y3 s.t.-3y1-2y2-2y3+S1=-5-5y1-y2-2y3+S2=-4 y1，y2，y3,S1,S2,0,对偶单纯形法2,建立该问题的初始单纯形表,由表知1的两个基变量均取负值,故它不是可行基,从而不能从1出发应用单纯形法。但由于表(I)中所有j0,我们目的是要保证全部检验数始终为非正的前提下,逐步使全部基变量取的值0,为此要按以下方法换基.,(I),对偶单纯形法3,出基变量确定：可选任何一个取负值的基变量（通常选 取值最小的一个）为出基变量入基变量的确定：考虑出基变量行中那些取负值的ij,对每个这样的ij,作比式j/aij令：=minj/aijaij0=s/ais则取xs为入基变量。,(I),然后进行单纯形迭代,得表（II）,(III),(II),得最优解：y1=3/7,y2=13/7,y3=s1=s2=0,对偶单纯形法对偶单纯形法用来求解最优性条件满足，可行性条件不满足的问题。对偶单纯形法的步骤Step 0：从一个最优性条件满足，可行性条件不满足的解出发，确定基变量、非基变量，列出单纯形表，转Step 1。Step 1：如果右边常数全为非负，得到最优解，算法终止。否则，选择右边常数为负数，绝对值最大的基变量离基，转Step 2。Step 2：在离基变量行中，选择系数为负数并且和目标函数行的比值最小的元素作为主元，确定进基变量。Step 3：对单纯形表进行行变换，使主元为1，主元所在列的其他元素为0，转Step 1。,1、原始问题是利润最大化的生产计划问题,单位产品的利润（元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（吨/件）,剩余的资源（吨）,消耗的资源（吨）,四、对偶的经济解释,2、对偶问题,资源限量（吨）,资源价格（元/吨）,总租金（元）,对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 max z=min w,3、资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,4、互补松弛关系的经济解释,wixn+i=0,如果wi0，则xn+i=0,如果xn+i0，则wi=0,边际利润大于0的资源，在最优生产计划条件下没有剩余,wm+jxj=0,如果wm+j0，则xj=0,如果xj0，则wm+j=0,最优生产计划条件下有剩余的资源，其边际利润等于0,差额成本大于0（机会成本大于利润）的产品，不安排生产,安排生产的产品，差额成本等于0（机会成本等于利润）,max z=4x1+3x2+5x3s.t.2x1+x2+3x3200 x1+2x2+2x3350 3x1+4x2+x3220 2x1+3x2+2x3400 x1，x2，x30,引进松弛变量x4,x5,x6，x70,得到：max z=4x1+3x2+5x3s.t.2x1+x2+3x3+x4=200 x1+2x2+2x3+x5=350 3x1+4x2+x3+x6=220 2x1+3x2+2x3+x7=400 xi0,得到最优解：X1=0,x2=460/11=41.82,x3=580/11(件），最大利润z=389.09(万元），可以得到资源的剩余量：X4=200-(2x1+x2+3x3)=0(t)X5=350-(x1+2x2+2x3)=1770/11=160.9(t)X6=220-(3x1+4x2+x3)=0X7=400-(2x1+3x2+2x3)=1860/11=169.9,这个问题的对偶问题是：Min y=200w1+350w2+220w3+400w4S.t 2w1+w2+3w3+2w4-w5=4 w1+2w2+4w3+3w4 w6=3 3w1+2w2+w3+2w4-w7=5 wi0,利用互补松弛关系，得到：W1=17/11,w2=0,w3=4/11,w4=0,w5=2/11即四种资源的影子价格为：W1=17/11,w2=0,w3=4/11,w4=0由此可以计算出三种产品的机会成本：产品1：2w1+w2+3w3+2w4=4.18（万元/件）产品2：w1+2w2+4w3+3w4=3.0（万元/件）产品3：3w1+2w2+w3+2w4=5.0（万元/件）,