最优化方法之对偶理论讲解.ppt
《最优化方法之对偶理论讲解.ppt》由会员分享,可在线阅读,更多相关《最优化方法之对偶理论讲解.ppt(59页珍藏版)》请在三一办公上搜索。
1、最优化方法 Optimization第七讲,第四章 对偶理论,窗含西岭千秋雪,门泊东吴万里船。-(唐)杜甫,对偶是一种普遍现象,主要内容,对偶问题的形式普遍存在 L P 对偶形式及定理 对偶问题经济解释 对偶单纯形法 原-对偶算法,对偶及鞍点问题,Lagrange 对偶问题,(1),定义(1)的对偶问题:,(2),集约束,Lagrange函数,例:考虑线性规划问题,若取集合约束D=x|x0,则该线性规划问题的Lagrange函数为,线性规划的对偶问题为:,求下列非线性规划问题的对偶问题:,对偶问题为:,对偶定理,定理1(弱对偶定理),推论1:,推论2:,推论3:,推论4:,对偶间隙:,问题:,
2、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 对偶问
3、题为 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,极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的下界。,极小化问题的任何一个可行解所对应的目标函数值都是其对偶问
4、题的目标函数值的上界。,推论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)的最优单纯形表中松
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 方法 对偶 理论 讲解
链接地址:https://www.31ppt.com/p-5749077.html