最优化方法之-对偶理论讲解-课件

最优化方法之 对偶理论讲解最优化方法最优化方法 Optimization Optimization第七讲第七讲第四章第四章 对偶理论对偶理论 窗含西岭千秋雪，门泊东吴万里船。-(唐)杜甫 对偶是一种普遍现象主要内容主要内容 对偶问题的形式对偶问题的形式普遍存在普遍存在 L P 对偶形式及定理对偶形式及定理 对偶问题经济解释对偶问题经济解释 对偶单纯形法对偶单纯形法 原原-对偶算法对偶算法对偶及鞍点问题对偶及鞍点问题Lagrange 对偶问题对偶问题(1)定义定义(1)的对偶问题的对偶问题:(2)集约束集约束Lagrange函数函数例：考虑线性规划问题例：考虑线性规划问题若取集合约束若取集合约束D=x|x0，则该，则该线性规划问题的线性规划问题的Lagrange函数为函数为线性规划的对偶问题为：线性规划的对偶问题为：求下列非线性规划问题的对偶问题求下列非线性规划问题的对偶问题:对偶问题为对偶问题为:对偶定理对偶定理定理定理1(弱对偶定理弱对偶定理)推论推论1:推论推论2:推论推论3:推论推论4:对偶间隙：对偶间隙：问题问题：LP 对偶问题的表达对偶问题的表达（1 1）对称）对称LPLP问题的定义问题的定义（2）对称对称LPLP问题的对偶问题问题的对偶问题(P)(D)例：写出下列例：写出下列LPLP问题的对偶问题问题的对偶问题对偶例：写出对偶问题例：写出对偶问题(D)的对偶的对偶变形(D)对偶变形结论结论：对偶问题：对偶问题(D)的对偶的对偶 为原问题为原问题(P)。(DD)minmin变成变成maxmax 价值系数与右端向量互换价值系数与右端向量互换系数矩阵转置系数矩阵转置 变变 原问题中约束条件的个数原问题中约束条件的个数=对偶问题中变量的个数对偶问题中变量的个数原问题中变量的个数原问题中变量的个数=对偶问题中约束条件的个数对偶问题中约束条件的个数写出对称形式的对偶规划的要点写出对称形式的对偶规划的要点非对称形式的对偶非对称形式的对偶对称形式对称形式对偶对偶(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一般情形一般情形LPLP问题的对偶问题问题的对偶问题标准形标准形对偶对偶变变量量约约束束约约束束变变量量练习题练习题LP对偶问题的基本性质对偶问题的基本性质原问题原问题(P)对偶问题对偶问题(D)定理定理1(1(弱对偶定理弱对偶定理)例：1）原问题）原问题(P1)一可行解一可行解 x=(1,1)T(P1)目标值目标值=4040是是(D1)最优目标值的上界最优目标值的上界.2）对偶问题）对偶问题(D1)一可行解一可行解 w=（1 1 1 1）目标值目标值=10 10是是(P1)最优目标值的下界最优目标值的下界.推论推论1推论推论2 2极大化问题的任何一个可行解所对应的目标极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的下界。函数值都是其对偶问题的目标函数值的下界。极小化问题的任何一个可行解所对应的目标极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的上界。函数值都是其对偶问题的目标函数值的上界。推论推论3 3若问题若问题(P)或或(D)有无界解，则其对偶问题有无界解，则其对偶问题(D)或或(P)无可行解；无可行解；若问题若问题(P)或或(D)无可行解，则其对偶问题无可行解，则其对偶问题(D)或或(P)或者无可行解或者无可行解,或者目标函数值趋于无穷。或者目标函数值趋于无穷。定理定理2(2(最优性准则最优性准则)证明：证明：例例定理定理3(3(强对偶强对偶定理定理)若若(P),(D)(P),(D)均有可行解均有可行解,则则(P),(D)(P),(D)均有最优解均有最优解,且且(P),(D)(P),(D)的的最优目标函数值相等最优目标函数值相等.证明：因为证明：因为(P),(D)(P),(D)均有可行解均有可行解,由推论由推论2,2,推论推论3 3知知,(P),(P)的目标的目标函数值在其可行域内有下界函数值在其可行域内有下界,(D),(D)的目标函数值在其可行域内的目标函数值在其可行域内有上界有上界,故则故则(P),(D)(P),(D)均有最优解均有最优解.引入剩余变量，把引入剩余变量，把(P)(P)化为标准形化为标准形:推论推论在用单纯形法求解在用单纯形法求解LPLP问题（问题（P P）的最优单纯）的最优单纯形表中松弛变量的检验数的相反数形表中松弛变量的检验数的相反数(单纯形单纯形乘子乘子w=(B-1)TcB)就是其对偶问题（就是其对偶问题（D D）的最优解）的最优解.由于由于(P)(P)化成标准形式时化成标准形式时,松弛变量松弛变量x xn n+j j 对应的列为对应的列为-e ej j，它在目标函数中的价格系数，它在目标函数中的价格系数，所以，判别数为所以，判别数为 (B (B-1-1)T Tc cB B(-(-e ej j)-0=-)-0=-w wj j则松弛变量对应的判别数均乘以则松弛变量对应的判别数均乘以(-1)(-1)，便得到单纯，便得到单纯形乘子形乘子w w=(=(w w1 1,w wm m).).当原问题达最优时当原问题达最优时,单纯形乘子即为对偶问题的最优解单纯形乘子即为对偶问题的最优解.解：化为标准形：化为标准形例例:求下列问题之对偶问题的最优解求下列问题之对偶问题的最优解x1 x2 x3 x4 x5 1 2 1 0 04 0 0 1 00 4 0 0 1-2 -3 0 0 0 x3x4x58161201 0 1 0 -1/24 0 0 1 00 1 0 0 1/4-2 0 0 0 3/4x3x4x22163941x1 x2 x3 x4 x5 1 0 1 0 -1/20 0 -4 1 20 1 0 0 1/40 0 2 0 -1/4x1x4x22831321 0 0 1/4 00 0 -2 1/2 10 1 1/2 -1/8 00 0 3/2 1/8 0 x1x5x244214此时达到最优解。此时达到最优解。x*=(4,2),MaxZ=14=(4,2),MaxZ=14。(P)(D)小结小结原问题原问题(min)对应关系对应关系 对偶问题对偶问题(max)有最优解有最优解无界解不可行不可行无界解（无可行解）（无可行解）（无可行解）（无可行解）w1w2l2l1x1x2l1l2 （无界解）（无界解）（无可行解）（无可行解）l2x1x2l1zy1y2l1l2定理定理4 4（互补松驰定理）（互补松驰定理）证明：（必要性）证明：（必要性）证明：（充分性）证明：（充分性）定理定理44：互补松驰定理：互补松驰定理(非对称形式）非对称形式）例例:考虑下面问题考虑下面问题解解:1 1、定义、定义对偶问题的经济学解释：影子价格对偶问题的经济学解释：影子价格(自学自学)2 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 2）告诉管理者花多大代价购买进资源或卖出资源是合适的）告诉管理者花多大代价购买进资源或卖出资源是合适的 3 3、影子价格的作用、影子价格的作用（1 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,则该则该LPLP无可行解）无可行解）步骤：步骤：x1 x2 x3 x4 x5-3 -1 -1 1 01 -4 -1 0 1-1 -1 -1 0 0 x4x5-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/4x4x2-1/21/21/2-13/41 0 3/13 -4/13 1/130 1 4/13 -1/13 -3/130 0 -6/13 -5/13 -2/13x1x22/137/139/13用对偶单纯形法求解下列用对偶单纯形法求解下列LPLP问题问题解：原问题变形为解：原问题变形为