Chapter02.线性规划的对偶理论.ppt

2005-10 中国科技网到中国电信网络线路使用分析报告 §1 对偶问题的提出 设备租赁问题假定有四海机器厂想扩大生产规模想租赁常山机器厂的三种设备，常山方面应如何决定出租价格呢？ 设常山机器厂对三种设备的出租定价分别为y1,y2,y3元/小时。 常山机器厂的考虑：不能比自己组织生产获利少(约束条件)； 四海机器厂的考虑：租金尽可能少(目标函数) 租赁问题形成的新规划模型 写出原问题和新问题的约束矩阵，右端项和目标函数系数 §1 原问题和对偶问题之间的关系 原问题和对偶问题A, b 和 c 的对应关系： A ~ AT, bT ~ c , cT ~ b ; 原问题是极大化问题，对偶问题是极小化问题； 原问题 vs. 对偶问题：约束条件个数 = 决策变量个数，反之依然； 原问题的约束为“?”号，对偶问题的约束为“?”号。 对称形式的对偶规划 定义2.1 原问题 (LP) 的对偶问题为（DP）其中 y = (y1,y2,…,ym)T 为对偶问题的决策变量，称(LP)为标准形式原问题。注：在对偶理论中，一般不再要求x和 b 非负。 例2.1 求下述问题的对偶问题。 对偶问题的对偶问题为原问题 定理2.1 对偶问题 (DP) 的对偶问题为（LP） 证明思路：将对偶问题转化为标准形式原问题，即 “max + 约束?” 形式，再用定义求解。 两个推论 – 非标准原问题的对偶问题 约束为“?”的原问题的对偶问题 混合形式原问题的对偶问题(书中P56例2) 设对偶问题的决策变量为 y = (y1,y2,y3)T， 对偶问题目标函数，约束矩阵，右端项容易写出；关键是约束符号和变量符号问题。 第1约束：min + x1 ? 0, 如果x1?0, 对偶问题约束该取“?”，此处相反取 “?”； 第2约束取“=”；第3约束为 min + x3 ? 0，约束取“?”； 对偶问题第1变量y1: 由 min+第1约束“?” 决定，y1 ?0 ;变量y2: 由 min+第2约束“?” 决定，y2 ? 0 ; 原问题第3个等式决定了变量y3取值无限制。 §3 对偶问题的基本性质(书P58) 始终规定 原问题 (LP) 对偶问题为（DP）其中 A为m ? n 阶约束矩阵，x和y 分别为原问题和对偶问题的决策变量。 强对偶定理(书P58，性质3,性质4) 原问题 (LP) 对偶问题为（DP）其中 A为m ? n 阶约束矩阵，x和y 分别为原问题和对偶问题的决策变量。 互补松紧定理(书P59，性质5) 原问题 (LP) 对偶问题为（DP）其中 A为m ? n 阶约束矩阵，x和y 分别为原问题和对偶问题的决策变量。 松紧定理的应用 基解互补原理(书P59，性质6) 原问题 (LP) 对偶问题为（DP）其中 A为m ? n 阶约束矩阵，x和y 分别为原问题和对偶问题的决策变量。 推论2.4 (LP)和(DP)存在一对互补的（最优）基解： 原问题的剩余变量对应对偶问题的变量，对偶问题的松弛变量对应原问题的变量 原问题解的基变量（非基变量）对应对偶问题的非基变量（基变量) 互补的基解对应原问题和对偶问题的目标函数值相同 推论2.4的应用 – 如果原问题不方便求解，求其对偶问题最优解，利用对偶问题最终单纯形表的检验数行获得原问题最优解。 基解互补应用的例子(书P60.例3) 问题1：原问题和对偶问题哪个更容易求解？为什么？ 问题2：不容易求解的问题用什么方法求解？ 两个问题最终单纯形表(注意对应关系) §4 影子价格 bi : 第i种资源的拥有量； yi : 第i种资源的单位估价，不是市场价格，是生产贡献估价，称为影子价格(shadow price)；影子价格是边际价格。 影子价格的经济学含义 影子价格和资源利用的关系(1) 若Ai x bi, 则yi = 0 ;(2) 若 yi 0, 则Ai x = bi ; 结论：资源消耗完毕，影子价格大于零；未充分利用，影子价格为0 单纯法中检验数的含义： §5 对偶单纯形法 单纯形法的思想：保持原问题是可行解，在目标函数值不减的条件下迭代求解，直至检验数满足最优性标准。 原问题 vs. 对偶问题:根据基解互补原理，原问题检验数非正时，其对偶问题达到可行解，此时相应解为两个问题的最优解。 对偶单纯形法的基本思想：保持对偶问题为可行解(检验数非正，此时