《对偶理论》PPT课件.ppt
第四章对偶原理,窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象,2,x1x2x3,y1y2y3y4,假设工厂考虑不进行生产而把全部可利用的资源都让给其他企业，工厂希望给这些资源定出一个合理的价格，即使别的单位愿意购买，又使本工厂能得到生产这些产品所能获得的最大收益。,3,二、对偶问题的表达,（1）对称LP问题的定义,（2）对称LP问题的对偶问题,第一类对称形式,第二类对称形式,(L),(D),4,例1：写出下列LP问题的对偶问题,对偶,5,（3）对偶问题的对偶,推导过程,变形,(D),6,对偶,变形,结论：对偶问题的对偶为原问题。,(DD),7,写出下列LP问题的对偶问题：,例2：,8,写出对称形式的对偶规划的要点：(1)min变成max(2)价值系数与右端向量互换(3)系数矩阵转置(4)变 原问题中约束条件的个数=对偶问题中变量的个数原问题中变量的个数=对偶问题中约束条件的个数,9,非对称形式的对偶,写成对称形式,对偶问题为：,10,例 min 5x1+4x2+3x3 s.t.x1+x2+x3=4 3x1+2x2+x3=5 x1 0,x2 0,x3 0 对偶问题为 max 4w1+5w2 s.t.w1+3w25 w1+2w2 4 w1+w2 3,11,一般情形LP问题的对偶问题,min cxs.t.A1x b1 A1 为m1n,b1为m11 A2x=b2 A2 为m2n,b2为m21 A3x b3 A3 为m3n,b3为m31 x 0引入松弛变量 min cx s.t.A1x xs=b1 xs为m11 A2x=b2 A3x+xt=b3 xt为m31 x,xs,xt 0,12,min cxs.t.A1x xs=b1 xs为m11 A2x=b2 A3x+xt=b3 xt为m31 x,xs,xt 0对偶问题为max w1b1+w2b2+w3b3s.t.w1A1+w2A2+w3A3 c w1Is 0 w3It 0 max w1b1+w2b2+w3b3 s.t.w1A1+w2A2+w3A3 c w1 0,w3 0,13,min max变 0 约量 0 束 无限制=方 程约 0 束 0 变方=无限制 量程,14,15,直接写出LP问题的对偶问题,例3,16,17,第二节 对偶问题的基本性质,原问题(L)对偶问题(D)min cx max wb s.t.Ax b s.t.wA c x 0 w 0,18,定理1：弱对偶定理,19,例：,1）原问题任一可行解 x=(1,1)T,（LP）,目标值=40,40是DLP问题最优目标值的上界.,2）对偶问题任一可行解 w=（1 1 1 1）目标值=10 10是LP问题最优目标值的下界.,20,推论1：,若LP(或DLP)问题有无界解，则其对偶问题(或原问题)无可行解；若LP(或DLP)问题无可行解，则对偶问题(或原问题)或者无可行解,或者目标函数值趋于无穷。,推论2：,极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的下界。,极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的上界。,推论3：,21,定理2：最优性准则,证明：,22,例5,23,定理3：强对偶定理,若(L),(D)均有可行解,则(L),(D)均有最优解,且(L),(D)的最优目标函数值相等.,证明：,24,(L),引入剩余变量，把(L)化为标准形,25,26,推论：,在用单纯形法求解LP问题（L）的最优单纯形表中松弛变量的检验数的相反数(单纯形乘子w=cBB-1)就是其对偶问题（D）的最优解,27,方法,由于(L)化成标准形式时,松弛变量xn+j对应的列为-ej，它在目标函数中的价格系数，所以，判别数cBB-1(-ej)-0=-wj则松弛变量对应的判别数均乘以(-1)，得到单纯形乘子w=(w1,wm).当原问题达最优时,单纯形乘子即为对偶问题的最优解.,28,解：化为标准型,例5 求下列问题对偶问题的最优解,29,4,1,30,2,此时达到最优解。x*=(4,2),MaxZ=14。,31,(L),(DL),32,小结,原问题(min)对应关系 对偶问题(max),有最优解,有最优解,无界解,不可行,不可行,无界解,33,（无可行解）,（无可行解）,34,（无界解）,（无可行解）,35,定理4：互补松驰定理,36,证明：（必要性）,37,证明：（充分性）,38,定理4：互补松驰定理(非对称形式）,39,例6 考虑下面问题,40,解:,则，,41,1、定义,对偶问题的经济学解释：影子价格,2、含义,考虑在最优解处,右端项bi的微小变动对目标函数值的影响.,42,若把原问题的约束条件看成是广义的资源约束,则右端项的值表示每种资源的可用量.对偶解的经济含义:资源的单位改变量引起目标函数值的增加量.通常称对偶解为影子价格.影子价格的大小客观地反映了资源在系统内的稀缺程度.资源的影子价格越高,说明资源在系统内越稀缺,而增加该资源的供应量对系统目标函数值贡献越大.,43,木门 木窗木工 4小时 3小时 120小时/日油漆工 2小时 1小时 50小时/日收入 56 30解：设该车间每日安排 x1 x2 x3 x4生产木门x1扇，木窗x2。x3 4 3 1 0 120max z=56 x1+30 x2 x4 2 1 0 1 50 s.t.4 x1+3 x2120-56-30 0 0 0 2 x1+x2 50 x3 0 1 1-2 20 x1 x2 0 x1 1 1/2 0 1/2 25 0-2 0 28 1400 x2 0 1 1-2 20 x1 0 0-1/2-1/2 15 0 0 2 24 1440,对偶问题的解为:w*=(2,24),44,（2）告诉管理者花多大代价购买进资源或卖出资源是合适的,3、影子价格的作用,（1）告诉管理者增加何种资源对企业更有利,（3）为新产品定价提供依据,45,对偶单纯形法,定义：设x(0)是(L)的一个基本解（不一定是可行解），它对应的矩阵为B，记w=cBB-1，若w是(L)的对偶问题的可行解，即对任意的j,wPj-cj 0，则称x(0)为原问题的对偶可行的基本解。结论：当对偶可行的基本解是原问题的可行解时，由于判别数0，因此，它就是原问题的最优解。,46,所以，x(0)为对偶可行的基本解。,47,基本思想：从原问题的一个对偶可行的基本解出发；求改进的对偶可行的基本解：每个对偶可行的基本解x=(xBT,0)T对应一个对偶问题的可行解w=cBB-1，相应的对偶问题的目标函数值为wb=cBB-1b，所谓改进的对偶可行的基本解，是指对于原问题的这个基本解，相应的对偶问题的目标函数值wb有改进（选择离基变量和进基变量，进行主元消去）；当得到的对偶可行的基本解是原问题的可行解时，就达到最优解。,48,与原单纯形法的区别：原单纯形法保持原问题的可行性，对偶单纯形法保持所有检验数wPj-cj 0，即保持对偶问题的可行性。特点：先选择出基变量，再选择进基变 量。,49,3、换基迭代,1.化标准型,建立初始单纯形表,4、回到第2步,(若所有yrj0,则该LP无可行解）,步骤：,50,51,52,-4,-13/4,53,用对偶单纯形法求解下列LP问题,解：原问题变形为,54,-1,-1,55,关于初始对偶可行的基本解,min cxs.t.Ax=b x 0若初始对偶可行的基本解不易直接得到，则解一个扩充问题，通过这个问题的求解，给出原问题的解答。,56,方法,附加人工约束,57,58,59,60,显然，（2，3，-2，0，0）不是对偶可行解，所以加一个约束,61,62,方法一,x1 x2 x3 x4 x5 x6,1,-1,最优解为(0,9,0,2,0)最优值=-4,63,x1 x2 x3 x4 x5 x6,x1x2x3x6,1 0 0 1-2 0,0 1 0-3 1 0,0 0 1-1-1 0,0 0 0 1 1 1,0 0 0 2-4 0,1 0 0 0-3-1,0 1 0 0 4 3,0 0 1 0 0 1,0 0 0 1 1 1,0 0 0 0-6-2,-1/3 0 0 0 1 1/3,-4/3 1 0 0 0 5/3,0 0 1 0 0 1,1/3 0 0 1 6 2/3,-2 0 0 0 0 0,x1x2x3x4,x5x2x3x4,23-2M,2-M3+3MM-2M,(M-2)/317/3+5M/3M-22/3+2M/3,0,-2M,-4,1,-3,方法二,64,扩充问题有最优解,最优值=-4,原问题最优值=-4,原问题最优解为,最优值=-4,65,用对偶单纯形法解下列问题,66,最优表为:,扩充问题的最优解是:,所以原问题无界。,67,原始-对偶算法,基本思想：从对偶问题的一个可行解开始，同时计算原问题和对偶问题，试图求出原问题的满足互补松弛条件的可行解。,68,原问题：,对偶问题：,69,限定原始问题Restricted primal problem,人工变量,70,限定原始问题的对偶问题,71,72,73,由于对偶问题无上界，所以原问题无可行解。,74,计算步骤,75,76,限定原始问题目标函数值,对偶问题可行解为w时所有的wpj-cj,对偶问题函数值f=wb,限定原始问题的判别数,77,用原始-对偶算法解下列问题,解：对偶问题为,78,限定原始问题为：,79,80,1,81,82,83,解：它的对偶规划是,84,限定原始问题为,85,86,87,88,89,
