《管理运筹学03对偶问题ppt课件》由会员分享，可在线阅读，更多相关《管理运筹学03对偶问题ppt课件（16页珍藏版）》请在金锄头文库上搜索。
1、 对对偶偶偶偶问题问题n一、对偶问题的提出一、对偶问题的提出n二、原问题与对偶问题的数学模二、原问题与对偶问题的数学模型型n三、原问题与对偶问题的对应关三、原问题与对偶问题的对应关系系n四、对偶问题的性质四、对偶问题的性质n五、对偶问题的经济意义五、对偶问题的经济意义n六、对偶单纯形法六、对偶单纯形法例：某家电厂家利用现有资源消费例：某家电厂家利用现有资源消费两种产品，两种产品， 有关数据如下表：有关数据如下表： 设备设备A 设备设备B调试工序调试工序利润元利润元0612521115时时24时时 5时时产品品产品品D一、对偶问题的提出一、对偶问题的提出如何安排消如何安排消费，使使获利最多？利最
2、多？厂厂家家设 产量量 产量量 设：设备A A 元元时 设备B B 元元时 调试工序工序 元元时收收购购 付出的代价最小，付出的代价最小， 且且对方能接受。方能接受。出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源本人消费的利润。本人消费的利润。 设备设备A 设备设备B调试工序调试工序利润元利润元0612521115时时24时时 5时时Dn厂家能接受的条件：厂家能接受的条件：n收买方的志愿：收买方的志愿：单位位产品品出租出租收入不低于收入不低于2 2元元单位位产品品出租出租收入不低于收入不低于1 1元元出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源本人消费的利
3、润。本人消费的利润。厂厂家家对对偶偶问问题题原原问问题题收收购购3 3个约束个约束2 2个变量个变量2 2个约束个约束 3 3个变量个变量原问题原问题对偶问题对偶问题普通规律 特点：特点： 1 2限定向量限定向量b 价价值向量向量C 资源向量源向量 3一个一个约束束 一个一个变量。量。 4 的的LP约束束“ 的的 LP是是“ 的的约束。束。 5变量都是非量都是非负限制。限制。 其它方式其它方式的的对偶偶? ?原问题或对偶问题对偶问题或原问题约束条件右端项目的函数变量的系数目的函数变量的系数约束条件右端项目的函数 max目的函数 min约束条件m个m个变量00=无约束变量n个n个约束条件00无约
4、束=n例例:对偶问题为对偶问题为12解：解：对偶偶规划：划：写出以下写出以下线性性规划的划的对偶偶问题13写出以下线性规划的对偶问题写出以下线性规划的对偶问题解：上述解：上述问题的的对偶偶规划：划：性质性质1 1 对称性定理：对偶问题的对偶是原问题对称性定理：对偶问题的对偶是原问题 min W= Y bs.t. YA C Y 0nmax Z=C Xns.t. AXbn X 0性质性质2 2 弱对偶原理弱对偶原理( (弱对偶性弱对偶性) )：设：设 和和 分别是问题分别是问题(P)(P)和和(D)(D)的可行解，那么必有的可行解，那么必有推论推论1: 原问题任一可行解的目的函数值是其对偶问标题的函数值原问题任一可行解的目的函数值是其对偶问标题的函数值的下届；反之，对偶问题恣意可行解的目的函数值是其原问标题的下届；反之，对偶问题恣意可行解的目的函数值是其原问标题的函数值的上界。的函数值的上界。推论推论2: 在一对对偶问题在一对对偶问题P和和D中，假设其中一个问题可行中，假设其中一个问题可行但目的函数无界，那么另一个问题无可行解；反之不成立。这也但目的函数无界，那么另一个问题无可行解；反之不成立。这也是对偶问题的无界性。是对偶问题的无界性。16原问题与对偶问题能够出现的情况1两者都有最优解，且最优值相等；2一个有可行解，但无界，那么另一个无可行解；3两者都无可行解。
