02运筹学-对偶理论与灵敏度分析.ppt

对偶与灵敏度 1、对偶问题的提出 引例——俩家具制造商间的对话： 线性规划的对偶理论 王老板按（D）的解 y1 、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。 2、线性规划的对偶理论 例2.1某工厂拥有A、B、C三种类型的原料，生产甲、乙两种产品。每件产品在生产中消耗的原料数量，每件产品的价格以及三种原料可利用的数量如下表所示： 线性规划的对偶模型 线性规划的对偶理论 对称形式下对偶问题的一般形式 例2.3 写出线性规划问题的对偶问题 3、一般形式的对偶问题 非对称形式下对偶问题的一般形式 —原始（对偶）对偶（原始）关系表 例2. 5 写出下列线性规划问题的对偶问题. 习题2.4（3） 解：由非对称形式的对应关系，得对偶规划 课堂练习 性质4 强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。 性质5的应用： 该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y＊求X＊或已知X＊求Y＊ 对偶问题： Max w= 4y1 + 3y2 s.t. y1 + 2y2 ? 2 y1 - y2 ? 3 2y1+ 3y2 ? 5 y1+ y2 ? 2 3y1+ y2 ? 3 y1 ? 0, y2 ? 0 例2. 10 已知线性规划 设对偶问题最优解为Y＊＝(y1，y2),由互补松弛性定理可知，X＊和 Y＊满足： 例2.11 已知线性规划 设对偶问题最优解为X＊＝(x1，x2 ，x3)T ,由互补松弛性定理可知，X＊和 Y＊满足： 线性规划的对偶理论 原问题与对偶问题解的对应关系表 线性规划的对偶理论 对偶问题的基本性质 对称性——原始问题与对偶问题是两个互为对偶的问题。 弱对偶性——两个问题的可行解对应的目标函数值互为上下界。 最优性——两个问题最优解的目标函数值必相等。 强对偶性——两个问题都有可行解时则两个问题必都有最优解。 互补松弛性——两个问题最优解中，一个问题中某个变量取值非零，则该变量在对偶问题中对应的某个约束条件必为紧约束；反之，如果约束条件为松约束，则其对应的对偶变量一定取值为零。因此，该定理又称为松紧定理。 如果把线性规划约束看成广义资源约束，右边项代表资源的可用量，其经济含义是资源对经济目标的边际贡献。 目标函数值通常用价值量衡量，对偶解也具有价值内涵，被称为影子价格。 影子价格是对偶解十分形象的名称，它既表明对偶解是对资源的一种客观估价，又表明它是虚拟而不是真实的价格。因此，从另一个角度说，它是一种机会成本。 影子价格在资源利用中的应用 根据对偶理论的互补松弛性定理: Y*Xs=0 , YsX*=0 表明生产过程中：如果某种资源bi未得到充分利用时（松），该种资源的影子价格为0（紧）；若当资源资源的影子价格不为0（松）时，表明该种资源在生产中已耗费完（紧）。 影子价格对单纯形表计算的解释 对偶单纯形法 因此可得入基变量的检验条件为： 原问题单纯形表的检验数行 对应其对偶问题的一个基解 证：设B是原问题的一个可行基，于是A=(B,N); 原问题可以改写为 相应地对偶问题可表示为 当求得原问题的一个解 基相应的检验数为 现分析这些检验数与对偶解之间的关系 令 ,将它代入（1）、（2）得 原问题最优时，对偶基本解为可行解，LP、LD同时最优。 最优表中 （1）对偶决策变量的值与原问题松弛变量检验数对应。（相反） （2）对偶松弛变量的值与原问题决策变量检验数对应。（0，相反） 思考题 判断下列结论是否正确，如果不正确，应该怎样改正？ 本章小结 课堂练习 使用LP求解管理问题时，管理者需要了解当环境和数据发生变化时，线性规划得出的结论还是否有效； 资源供应发生变化会有什么影响? 成本变化后利润会发生什么变化? 如果模型使用的数据不精确会有什么影响，数据允许在什么范围内变化? §2.5 、灵敏度分析 一、 价值系数cj的变化分析 例2.14 某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划 问题： （1）确定x2的系数c2的变化范围，使原最优解保持最优； （2）若c2=6，求新的最优计划。 -3 2 -1 -5 x5 0 -1 0 0 0 σj -1 0 1 0 10 x2 4 1 0 0 1 35 x1 5 2 1 0 0