运筹学 第二章线性规划的对偶理论与灵敏度分析课件.pptVIP

对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？ …… 线性规划的对偶理论 引例——俩家具制造商间的对话： 线性规划的对偶理论 线性规划的对偶理论 王老板按（D）的解 y1 、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。 思考题 如何理解对偶问题的基本性质？ 讨论题 用例子说明互补松弛性的实际应用。 小结 对偶问题的基本性质。 对偶定理。 作业: 2.1(1),2.3,2.7 二、对偶问题的基本性质 对偶基本性质揭示 原问题的解与对偶问题的解之间关系 补充:对称性定理 对偶问题的对偶是原问题。 定理1 弱对偶定理——若一对对称形式的对偶线性规划 （L） 和 （D） 均有可行解，分别为 和 ，则C ≤ b。 证明思路： 由（L） 左乘 ，得 由（D） 右乘 ，得 该结论对非对称形式的对偶问题同样成立。 ? 推论:关于“界”的结果； 极小化问题有下界—— 推论1 原问题 (极大化问题) 的任意一个可行解所对应的目标函数值是其对偶问题目标函数值的一个下界。 ?极大化问题有上界—— 推论1 对偶问题(极小化问题) 的任意一个可行解所对应的目标函数值是其原问题目标函数值的一个上界。 ?关于最优解无界情况与对偶问题的关系； 推论2 若原问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。 推论3 原问题可行，且目标函数值无界==对偶问题不可行 对偶问题可行，且目标函数值无界==原问题不可行 若对偶问题不可行，其原问题或没有可行解或无界解。 原问题有可行解而其对偶问题没有可行解， 则原问题的目标函数无界； 对偶问题有可行解而其原问题没有可行解，则对偶问题的目标函数无界； 定理 2 最优性定理 若 、 分别为对称形式对偶线性规划的可行解，且两者目标函数的相应值相等，即 C =b ，则 ， 分别为原问题和对偶问题的最优解。 CX’=Y’ b CX*≤Y*b 弱对偶 定 理 已 知 结论 Y*b≤Y’ b 因为X’Y’可行解 CX’ ≤CX* 证明思路 设X*,Y*分别为原问题和对偶问题的最优解; X’,Y’分别为原问题和对偶问题的可行解 CX’ ≤CX* ≤ Y*b≤Y’ b=CX’ CX’ =CX* = Y*b=Y’ b 3、 强对偶性 若原问题和对偶问题两者均具有可行解，则两者均有最优解，且此时目标函数值相同。 都有可行解 各自有上下界 都有最优解 目标函数值相等 证明要点： 定理4 互补松弛性 在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零。 证明 弱对偶性 最优性 此定理适用于 非对称形式 (1)式应取= 例:已知线性规划 其最优解为x=(6,2,0)T,求对偶问题的最优解 2×6+2×2+0=16;y20 6+2×2+0=10;y10 x1=60;约束条件为= x2=20;约束条件为= x3=0;约束条件为 求解结果为Y=(1,1)T Min W=26 * 运筹学教程 * 第二章 线性规划的对偶理论与灵敏度分析 一、对偶问题的提出 1、? 对偶思想举例 周长一定的矩形中，以正方形面积最大；面积一定的矩形中，以正方形周长最小； 第一节 LP的对偶问题 唉!我想租您的木工和油漆工一 用。咋样？价格嘛……好说， 肯定不会让您兄弟吃亏讪。 王老板做家具赚了 大钱，可惜我老李有 高科技产品，却苦于没有 足够的木工和油漆工 咋办？只有租咯。 Hi：王老板，听说 近来家具生意很好， 也帮帮兄弟我哦! 家具生意还真赚钱，但 是现在的手机生意这么好， 不如干脆把我的木工和油漆 工租给他，又能 收租金又可做生意。 价格嘛……好商量， 好商量。只是…... 家具-王 总 李 总 30 50 价格 50 1 2 漆工 120 3 4 木工 能力 椅子 桌子 王老板的家具生产模型： x1 、 x2是桌、椅生产量。 Z是家具销售总收入（总利润）。 max Z = 50x1 + 30x2 s.t. 4x1+3x