Chapter02线性规划的对偶理论ppt课件

1、第2章 线性规划的对偶实际 2019年3月1 对偶问题的提出n设备租赁问题假定有四海机器厂想扩展消费规模想租赁常山机器厂的三种设备，常山方面应如何决议出租价钱呢？n设常山机器厂对三种设备的出租定价分别为y1,y2,y3元/小时。n常山机器厂的思索：不能比本人组织消费获利少(约束条件)；n四海机器厂的思索：租金尽能够少(目的函数)加工设备ABC单件利润产品 I2402元产品 II2053元设备时限12h16h15h0,155 16 41222. .32max21212121xxxxxxtsxxz两种产品的件数。在计划期内应该生产为常山机器厂和21xx租赁问题构成的新规划模型0,155 16 41

2、222. . 32 max )(21212121xxxxxxtsxxz原问题0,35 22 42. . 151612 min )(3213121321yyyyyyytsyyyw对偶问题n写出原问题和新问题的约束矩阵，右端项和目的函数系数)3 ,2( 151612,500422 )(cbA原问题)15,16,12( 32,502042 )(cbA对偶问题问题：原问题的约束矩阵等和对偶问题的之间有什么关系？原问题和对偶问题之间的关系0,155 16 41222. . 32 max )(21212121xxxxxxtsxxz原问题0,35 22 42. . 151612 min )(32131213

3、21yyyyyyytsyyyw对偶问题n原问题和对偶问题A, b 和 c 的对应关系： A AT, bT c , cT b ;n原问题是极大化问题，对偶问题是极小化问题；n原问题 vs. 对偶问题：约束条件个数 = 决策变量个数，反之依然；n原问题的约束为“号，对偶问题的约束为“号。对称方式的对偶规划n定义2.1 原问题 (LP) 的对偶问题为DP其中 y = (y1,y2,ym)T 为对偶问题的决策变量，称(LP)为规范方式原问题。注：在对偶实际中，普通不再要求x和 b 非负。n例2.1 求下述问题的对偶问题。0s.t. max xbAxcxzTT0s.t. min ycyAybTw0, 0

4、121 s.t.5 max21212121xxxxxxxxz规范原问题0, 0121 s.t.5 max21212121xxxxxxxxz问题：请某位同窗上黑板写下对偶问题 (4)？对偶规划的对偶规划为原问题n定理2.1 对偶问题 (DP) 的对偶问题为LPn证明思绪：将对偶问题转化为规范方式原问题，即 “max + 约束 方式，再用定义求解。0s.t. max xbAxcxzTT0s.t. min ycyAybTw两个推论 非规范原问题的对偶问题).12(.s.t. s.t. 1 . 2min max TTT，也可用定义证明可以利用定理的对偶问题为原问题推论0ycyA0 xbAxybcxwz

5、难点记住：对偶问题约束的符号取决于原问题的变量符号； 对偶问题的变量符号取决于原问题的约束符号。)(.s.t. s.t. 2 . 2max min TTT当做课堂练习的对偶问题为原问题推论0ycyA0 xbAxybcxwz约束为“的原问题的对偶问题)(.s.t. s.t. 2 . 2min max TTT证明过程：见黑板的取值无限制的对偶问题为原问题定理ycyA0 xbAxybcxwz混合方式原问题的对偶问题(书中P56例2)n设对偶问题的决策变量为 y = (y1,y2,y3)T， 对偶问标题的函数，约束矩阵，右端项容易写出；关键是约束符号和变量符号问题。n第1约束：min + x1 0, 假设x10, 对偶问题约束该取“，此处相反取 “；n第2约束取“=；第3约束为 min + x3 0，约束取“；n对偶问题第1变量y1: 由 min+第1约束“ 决议，y1 0 ;变量y2: 由 min+第2约束“ 决议，y2 0 ; 原问题第3个等式决议了变量y3取值无限制。0, 0303 5 5146324624 s.t.347min 32