资源描述：
《最优化方法之 对偶理论讲解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、最优化方法Optimization第七讲第四章对偶理论窗含西岭千秋雪，门泊东吴万里船。-----(唐)杜甫对偶是一种普遍现象主要内容对偶问题的形式—普遍存在LP对偶形式及定理对偶问题经济解释对偶单纯形法原-对偶算法对偶及鞍点问题Lagrange对偶问题(1)定义(1)的对偶问题:(2)集约束Lagrange函数例：考虑线性规划问题若取集合约束D={x
2、x≥0}，则该线性规划问题的Lagrange函数为线性规划的对偶问题为：求下列非线性规划问题的对偶问题:对偶问题为:对偶定理定理1(弱对偶定理)推论1:推论2:推论3:推论4:对偶间隙：问题：LP对偶问题的表达（
3、1）对称LP问题的定义（2）对称LP问题的对偶问题(P)(D)例：写出下列LP问题的对偶问题对偶例：写出对偶问题(D)的对偶变形(D)对偶变形结论：对偶问题(D)的对偶为原问题(P)。(DD)min变成max价值系数与右端向量互换系数矩阵转置≥变≤原问题中约束条件的个数=对偶问题中变量的个数原问题中变量的个数=对偶问题中约束条件的个数写出对称形式的对偶规划的要点非对称形式的对偶对称形式对偶(P)(D)例min5x1+4x2+3x3s.t.x1+x2+x3=43x1+2x2+x3=5x1≥0,x2≥0,x3≥0对偶问题为max4w1+5w2s.t.w1+3w2≤
4、5w1+2w2≤4w1+w2≤3一般情形LP问题的对偶问题标准形对偶变量约束约束变量练习题LP对偶问题的基本性质原问题(P)对偶问题(D)定理1(弱对偶定理)例：1）原问题(P1)一可行解x=(1,1)T(P1)目标值=4040是(D1)最优目标值的上界.2）对偶问题(D1)一可行解w=（1111）目标值=1010是(P1)最优目标值的下界.推论1推论2极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的下界。极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的上界。推论3若问题(P)或(D)有无界解，则其对偶问题(D)
5、或(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)就是其对
6、偶问题（D）的最优解.由于(P)化成标准形式时,松弛变量xn+j对应的列为-ej，它在目标函数中的价格系数＝０，所以，判别数为(B-1)TcB(-ej)-0=-wj则松弛变量对应的判别数均乘以(-1)，便得到单纯形乘子w=(w1,…,wm).当原问题达最优时,单纯形乘子即为对偶问题的最优解.解：化为标准形例:求下列问题之对偶问题的最优解x1x2x3x4x5121004001004001-2-3000x3x4x58161201010-1/24001001001/4-20003/4x3x4x22163941x1x2x3x4x51010-1/200-41201001
7、/40020-1/4x1x4x22831321001/4000-21/21011/2-1/80003/21/80x1x5x244214此时达到最优解。x*=(4,2),MaxZ=14。(P)(D)小结原问题(min)对应关系对偶问题(max)有最优解有最优解无界解不可行不可行无界解（无可行解）（无可行解）w1w2l2l1x1x2l1l2（无界解）（无可行解）l2x1x2l1zy1y2l1l2定理4（互补松驰定理）证明：（必要性）证明：（充分性）定理4’：互补松驰定理(非对称形式）例:考虑下面问题解:1、定义对偶问题的经济学解释：影子价格(自学)2、含义考虑在最
8、优解处,右端项bi的微小变动对目标函数值的影响.若把原问题的约束条件看成是广义的资源约束,则右端项的值表示每种资源的可用量.对偶解的经济含义:资源的单位改变量引起目标函数值的增加量.通常称对偶解为影子价格.影子价格的大小客观地反映了资源在系统内的稀缺程度.资源的影子价格越高,说明资源在系统内越稀缺,而增加该资源的供应量对系统目标函数值贡献越大.木门木窗木工4小时3小时120小时/日油漆工2小时1小时50小时/日收入5630解：设该车间每日安排x1x2x3x4生产木门x1扇，木窗x2x34310120maxz=56x1+30x2x4210150s.t.4x1+3
9、x2≤120-56-300002x1+
