Chapter02.线性规划的对偶理论.ppt
《Chapter02.线性规划的对偶理论.ppt》由会员分享,可在线阅读,更多相关《Chapter02.线性规划的对偶理论.ppt(10页珍藏版)》请在三一文库上搜索。
1、黑龙江大学数学科学学院 信息与计算数学系 All rights reserved,第2章 线性规划的对偶理论,2011年3月,2,2019/2/14,1 对偶问题的提出,设备租赁问题 假定有四海机器厂想扩大生产规模想租赁常山机器厂的三种设备,常山方面应如何决定出租价格呢? 设常山机器厂对三种设备的出租定价分别为y1,y2,y3元/小时。 常山机器厂的考虑: 不能比自己组织生产获利少(约束条件); 四海机器厂的考虑: 租金尽可能少(目标函数),3,2019/2/14,租赁问题形成的新规划模型,写出原问题和新问题的约束矩阵,右端项和目标函数系数,问题:原问题的约束矩阵等和对偶问题的之间有什么关系?
2、,4,2019/2/14,原问题和对偶问题之间的关系,原问题和对偶问题A, b 和 c 的对应关系: A AT, bT c , cT b ; 原问题是极大化问题,对偶问题是极小化问题; 原问题 vs. 对偶问题:约束条件个数 = 决策变量个数,反之依然; 原问题的约束为“”号,对偶问题的约束为“”号。,5,2019/2/14,对称形式的对偶规划,定义2.1 原问题 (LP) 的对偶问题为(DP) 其中 y = (y1,y2,ym)T 为对偶问题的决策变量,称(LP)为标准形式原问题。 注:在对偶理论中,一般不再要求x和 b 非负。,例2.1 求下述问题的对偶问题。,标准原问题,问题:请某位同学
3、上黑板写下对偶问题 (4)?,6,2019/2/14,对偶规划的对偶规划为原问题,定理2.1 对偶问题 (DP) 的对偶问题为(LP),证明思路:将对偶问题转化为标准形式原问题,即 “max + 约束” 形式,再用定义求解。,7,2019/2/14,两个推论 非标准原问题的对偶问题,难点记住:对偶问题约束的符号取决于原问题的变量符号; 对偶问题的变量符号取决于原问题的约束符号。,8,2019/2/14,约束为“”的原问题的对偶问题,9,2019/2/14,混合形式原问题的对偶问题(书中P56例2),设对偶问题的决策变量为 y = (y1,y2,y3)T, 对偶问题目标函数,约束矩阵,右端项容易写出;关键是约束符号和变量符号问题。 第1约束:min + x1 0, 如果x10, 对偶问题约束该取“”,此处相反取 “”; 第2约束取“=”;第3约束为 min + x3 0,约束取“”; 对偶问题第1变量y1: 由 min+第1约束“” 决定,y1 0 ;变量y2: 由 min+第2约束“” 决定,y2 0 ; 原问题第3个等式决定了变量y3取值无限制。,10,2019/2/14,作业,书P78, 2.1(b)(下周三交),
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Chapter02 线性规划 对偶 理论
链接地址:https://www.31doc.com/p-2102146.html