null第2章 线性
规划
污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文
的对偶理论第2章 线性规划的对偶理论 2011年3月§1 对偶问题的提出§1 对偶问题的提出设备租赁问题 假定有四海机器厂想扩大生产规模想租赁常山机器厂的三种设备，常山方面应如何决定出租价格呢？
设常山机器厂对三种设备的出租定价分别为y1,y2,y3元/小时。
常山机器厂的考虑： 不能比自己组织生产获利少(约束条件)；
四海机器厂的考虑： 租金尽可能少(目标函数)租赁问题形成的新规划模型租赁问题形成的新规划模型写出原问题和新问题的约束矩阵，右端项和目标函数系数问题：原问题的约束矩阵等和对偶问题的之间有什么关系？原问题和对偶问题之间的关系原问题和对偶问题之间的关系原问题和对偶问题A, b 和 c 的对应关系： A ~ AT, bT ~ c , cT ~ b ;
原问题是极大化问题，对偶问题是极小化问题；
原问题 vs. 对偶问题：约束条件个数 = 决策变量个数，反之依然；
原问题的约束为“”号，对偶问题的约束为“”号。对称形式的对偶规划对称形式的对偶规划
定义2.1 原问题 (LP) 的对偶问题为（DP） 其中 y = (y1,y2,…,ym)T 为对偶问题的决策变量，称(LP)为标准形式原问题。 注：在对偶理论中，一般不再要求x和 b 非负。例2.1 求下述问题的对偶问题。标准原问题问题：请某位同学上黑板写下对偶问题 (4')？对偶规划的对偶规划为原问题对偶规划的对偶规划为原问题
定理2.1 对偶问题 (DP) 的对偶问题为（LP） 证明思路：将对偶问题转化为标准形式原问题，即 “max + 约束” 形式，再用定义求解。两个推论 – 非标准原问题的对偶问题两个推论 – 非标准原问题的对偶问题难点记住：对偶问题约束的符号取决于原问题的变量符号；
对偶问题的变量符号取决于原问题的约束符号。约束为“”的原问题的对偶问题约束为“”的原问题的对偶问题混合形式原问题的对偶问题(书中P56例2)混合形式原问题的对偶问题(书中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取值无限制。
作业作业书P78, 2.1(b)（下周三交）
浙公网安备 33021202002483