优化方法之对偶理论讲解.ppt
最优化方法 Optimization第七讲,第四章 对偶理论,窗含西岭千秋雪，门泊东吴万里船。-(唐)杜甫,对偶是一种普遍现象,主要内容,对偶问题的形式普遍存在 L P 对偶形式及定理 对偶问题经济解释 对偶单纯形法 原-对偶算法,对偶及鞍点问题,Lagrange 对偶问题,(1),定义(1)的对偶问题:,(2),集约束,Lagrange函数,例：考虑线性规划问题,若取集合约束D=x|x0，则该线性规划问题的Lagrange函数为,线性规划的对偶问题为：,求下列非线性规划问题的对偶问题:,对偶问题为:,对偶定理,定理1(弱对偶定理),推论1:,推论2:,推论3:,推论4:,对偶间隙：,问题：,LP 对偶问题的表达,（1）对称LP问题的定义,（2）对称LP问题的对偶问题,(P),(D),例：写出下列LP问题的对偶问题,对偶,例：写出对偶问题(D)的对偶,变形,(D),对偶,变形,结论：对偶问题(D)的对偶 为原问题(P)。,(DD),min变成max 价值系数与右端向量互换系数矩阵转置 变 原问题中约束条件的个数=对偶问题中变量的个数原问题中变量的个数=对偶问题中约束条件的个数,写出对称形式的对偶规划的要点,非对称形式的对偶,对称形式,对偶,(P),(D),例 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,一般情形LP问题的对偶问题,标准形,对偶,变量,约束,约束,变量,练习题,LP对偶问题的基本性质,原问题(P),对偶问题(D),定理1(弱对偶定理),例：,1）原问题(P1)一可行解 x=(1,1)T,(P1),目标值=40,40是(D1)最优目标值的上界.,2）对偶问题(D1)一可行解 w=（1 1 1 1）目标值=10 10是(P1)最优目标值的下界.,推论1,推论2,极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的下界。,极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的上界。,推论3,若问题(P)或(D)有无界解，则其对偶问题(D)或(P)无可行解；若问题(P)或(D)无可行解，则其对偶问题(D)或(P)或者无可行解,或者目标函数值趋于无穷。,定理2(最优性准则),证明：,例,定理3(强对偶定理),若(P),(D)均有可行解,则(P),(D)均有最优解,且(P),(D)的最优目标函数值相等.,证明：因为(P),(D)均有可行解,由推论2,推论3知,(P)的目标函数值在其可行域内有下界,(D)的目标函数值在其可行域内有上界,故则(P),(D)均有最优解.,引入剩余变量，把(P)化为标准形:,推论,在用单纯形法求解LP问题（P）的最优单纯形表中松弛变量的检验数的相反数(单纯形乘子w=(B-1)TcB)就是其对偶问题（D）的最优解.,由于(P)化成标准形式时,松弛变量xn+j 对应的列为-ej，它在目标函数中的价格系数，所以，判别数为(B-1)TcB(-ej)-0=-wj则松弛变量对应的判别数均乘以(-1)，便得到单纯形乘子w=(w1,wm).当原问题达最优时,单纯形乘子即为对偶问题的最优解.,解：化为标准形,例:求下列问题之对偶问题的最优解,4,1,2,此时达到最优解。x*=(4,2),MaxZ=14。,(P),(D),小结,原问题(min)对应关系 对偶问题(max),有最优解,有最优解,无界解,不可行,不可行,无界解,（无可行解）,（无可行解）,（无界解）,（无可行解）,定理4（互补松驰定理）,证明：（必要性）,证明：（充分性）,定理4：互补松驰定理(非对称形式）,例:考虑下面问题,解:,1、定义,对偶问题的经济学解释：影子价格(自学),2、含义,考虑在最优解处,右端项bi的微小变动对目标函数值的影响.,若把原问题的约束条件看成是广义的资源约束,则右端项的值表示每种资源的可用量.对偶解的经济含义:资源的单位改变量引起目标函数值的增加量.通常称对偶解为影子价格.影子价格的大小客观地反映了资源在系统内的稀缺程度.资源的影子价格越高,说明资源在系统内越稀缺,而增加该资源的供应量对系统目标函数值贡献越大.,木门 木窗木工 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),（2）告诉管理者花多大代价购买进资源或卖出资源是合适的,3、影子价格的作用,（1）告诉管理者增加何种资源对企业更有利,（3）为新产品定价提供依据,对偶单纯形法,定义：设x(0)是(P)的一个基本解（不一定是可行解），它对应的矩阵为B，记w=cBB-1，若w是(P)的对偶问题的可行解，即对任意的j,wPj-cj 0，则称x(0)为原问题的对偶可行的基解。结论：当对偶可行的基解是原问题的可行解时，由于判别数0，因此，它就是原问题的最优解。,所以，x(0)为对偶可行的基解。,基本思想：从原问题的一个对偶可行的基解出发；求改进的对偶可行的基解：每个对偶可行的基解x=(xBT,0)T对应一个对偶问题的可行解w=cBB-1，相应的对偶问题的目标函数值为wb=cBB-1b，所谓改进的对偶可行的基解，是指对于原问题的这个基解，相应的对偶问题的目标函数值wb有改进（选择离基变量和进基变量，进行主元消去）；当得到的对偶可行的基解是原问题的可行解时，就达到最优解。,与原单纯形法的区别：原单纯形法保持原问题的可行性，对偶单纯形法保持所有检验数wPj-cj 0，即保持对偶问题的可行性。特点：先选择出基变量，再选择进基变 量。,3、换基迭代,1、化标准型,建立初始单纯形表,4、回到第2步,(若所有yrj0,则该LP无可行解）,步骤：,-4,-13/4,用对偶单纯形法求解下列LP问题,解：原问题变形为,-1,-1,
