《最优化方法之对偶理论讲解》由会员分享，可在线阅读，更多相关《最优化方法之对偶理论讲解（59页珍藏版）》请在金锄头文库上搜索。
1、最优化方法 Optimization 第七讲第四章 对偶理论 窗含西岭千秋雪， 门泊东吴万里船。-(唐)杜甫 对偶是一种普遍现象主要内容 对偶问题的形式普遍存在 L P 对偶形式及定理 对偶问题经济解释 对偶单纯形法 原-对偶算法对偶及鞍点问题Lagrange 对偶问题(1)定义(1)的对偶问题:(2)集约束Lagrange函数例：考虑线性规划问题若取集合约束D=x|x0，则该 线性规划问题的Lagrange函数为线性规划的对偶问题为：求下列非线性规划问题的对偶问题:对偶问题为:对偶定理定理1(弱对偶定理)推论1:推论2:推论3:推论4:对偶间隙：问题：LP 对偶问题的表达 （1）对称LP问题
2、的定义（2）对称LP问题的对偶问题(P)(D)例：写出下列LP问题的对偶问题对偶例：写出对偶问题(D)的对偶变形(D)对偶变形结论：对偶问题(D)的对偶为原问题(P) 。 (DD) min变成max 价值系数与右端向量互换 系数矩阵转置 变 原问题中约束条件的个数=对偶问题中变量的个数 原问题中变量的个数=对偶问题中约束条件的个数写出对称形式的对偶规划的要点非对称形式的对偶对称形式对偶(P)(D)例 min 5x1+4x2+3x3s.t. x1+x2+x3=43x1+2x2+x3 =5x1 0, x2 0, x3 0 对偶问题为max 4w1+5w2s.t. w1+3w25w1+2w2 4w1
3、+w2 3一般情形LP问题的对偶问题标准形对偶变量约束约束变量练习题LP对偶问题的基本性质原问题(P)对偶问题(D)定理1(弱对偶定理)例：1）原问题(P1)一可行解 x=(1, 1)T(P1)目标值 =40 40是(D1)最优目标值的上界.2）对偶问题(D1)一可行解 w=（1 1 1 1）目标值 =1010是(P1)最优目标值的下界.推论1推论2极大化问题的任何一个可行解所对应的目标 函数值都是其对偶问题的目标函数值的下界。极小化问题的任何一个可行解所对应的目标 函数值都是其对偶问题的目标函数值的上界。推论3若问题(P)或(D)有无界解，则其对偶问题(D)或(P) 无可行解； 若问题(P)
4、或(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)化成标准形式时,松
5、弛变量xn+j 对应的列为-ej，它在目标函数中的价格系数， 所以，判别数为 (B-1)TcB(-ej)-0=-wj 则松弛变量对应的判别数均乘以(-1)，便得到单纯 形乘子w=(w1,wm).当原问题达最优时,单纯形乘子即为对偶问题的最优解.解：化为标准形例: 求下列问题之对偶问题的最优解x1 x2 x3 x4 x5 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1-2 -3 0 0 0x3 x4 x58 16 1201 0 1 0 -1/2 4 0 0 1 0 0 1 0 0 1/4-2 0 0 0 3/4x3 x4 x22 16 3941x1 x2 x3 x4 x5 1 0 1
6、 0 -1/20 0 -4 1 2 0 1 0 0 1/40 0 2 0 -1/4x1 x4 x22 8 31321 0 0 1/4 00 0 -2 1/2 1 0 1 1/2 -1/8 00 0 3/2 1/8 0x1 x5 x24 4 214此时达到最优解。x*=(4,2), MaxZ=14。(P)(D)小结原问题(min) 对应关系 对偶问题(max) 有最优解有最优解无界解不可行不可行无界解（无可行解）（无可行解）w1w2 l2l1x1x2 l1l2（无界解）（无可行解）l2x1x2l1zy1y2l1l2定理4（互补松驰定理）证明：（必要性）证明：（充分性） 定理4：互补松驰定理(非对
7、称形式 ）例: 考虑下面问题解:1、定义对偶问题的经济学解释：影子价格(自学)2、含义考虑在最优解处,右端项bi的微小变动对目标函数值的影响. 若把原问题的约束条件看成是广义的资源约束,则右 端项的值表示每种资源的可用量. 对偶解的经济含义:资源的单位改变量引起目标函数 值的增加量. 通常称对偶解为影子价格. 影子价格的大小客观地反映了资源在系统内的稀缺程 度.资源的影子价格越高,说明资源在系统内越稀缺, 而增加该资源的供应量对系统目标函数值贡献越大.木门 木窗 木工 4小时 3小时 120小时/日 油漆工 2小时 1小时 50小时/日 收入 56 30 解：设该车间每日安排 x1 x2 x3
8、 x4 生产木门x1扇，木窗x2 x3 4 3 1 0 120 max z=56 x1 +30 x2 x4 2 1 0 1 50s.t. 4 x1 +3 x2120 -56 -30 0 0 02 x1 + x2 50 x3 0 1 1 -2 20x1 x2 0 x1 1 1/2 0 1/2 250 -2 0 28 1400x2 0 1 1 -2 20x1 0 0 -1/2 -1/2 150 0 2 24 1440对偶问题的解为: w*=(2, 24)（2）告诉管理者花多大代价购买进资源或卖出资源是合适的 3、影子价格的作用（1）告诉管理者增加何种资源对企业更有利（3）为新产品定价提供依据对偶单
9、纯形法 定义：设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，所谓改进的对偶可行的基解，是指对于原问 题的这个基解，相应的对偶问
10、题的目标函数值 wb有改进（选择离基变量和进基变量，进行主 元消去）； 当得到的对偶可行的基解是原问题的可行解时 ，就达到最优解。与原单纯形法的区别： 原单纯形法保持原问题的可行性，对偶单纯 形法保持所有检验数wPj-cj 0，即保持对偶问 题的可行性。 特点：先选择出基变量，再选择进基变 量。3、换基迭代1、 化标准型,建立初始单纯形表4、回到第2步(若所有yrj0,则该LP无可行解）步骤：x1 x2 x3 x4 x5-3 -1 -1 1 0 1 -4 -1 0 1 -1 -1 -1 0 0x4 x5-1 -20-4-13/4 0 -3/4 1 -1/4 -1/4 1 1/4 0 -1/4 -5/4 0 -3/4 0 -1/4x4 x2-1/2 1/21/2-13/41 0 3/13 -4/13 1/13 0 1 4/13 -1/13 -3/13 0 0 -6/13 -5/13 -2/13x1 x22/13 7/139/13用对偶单纯形法求解下列LP问题解：原问题变形为x1 x2 x3 x4 x5 x6-1 1 -1 1 0 0 1 1 2 0 1 0 0 -1 1 0 0 1x4 x5 x6-1 -2 -3 0 0 0-4 8 -2 0 1 -1 1 -1 0 0 0 2 1 1 1 0 0 -1 1 0
