《管理运筹学教学课件PPT对偶问题.ppt》由会员分享，可在线阅读，更多相关《管理运筹学教学课件PPT对偶问题.ppt（16页珍藏版）》请在三一文库上搜索。
1、对偶问题,一、对偶问题的提出 二、原问题与对偶问题的数学模型 三、原问题与对偶问题的对应关系 四、对偶问题的性质 五、对偶问题的经济意义 六、对偶单纯形法,例：某家电厂家利用现有资源生产两种产品， 有关数据如下表：,一、对偶问题的提出,如何安排生产， 使获利最多？,厂 家,设 产量 产量,设：设备A 元时 设备B 元时 调试工序 元时,收 购,付出的代价最小， 且对方能接受。,出让代价应不低于 用同等数量的资源 自己生产的利润。,厂家能接受的条件： 收购方的意愿：,出让代价应不低于 用同等数量的资源 自己生产的利润。,厂 家,对 偶 问 题,原 问 题,收 购,3个约束 2个变量,2个约束 3
2、个变量,一般规律,特点： 1 2限定向量b 价值向量C （资源向量） 3一个约束 一个变量。 4 的LP约束“ ” 的 LP是“ ”的约束。 5变量都是非负限制。,其它形式 的对偶 ?,例:,对偶问题为,12,解：对偶规划：,写出下列线性规划的对偶问题,13,写出下列线性规划的对偶问题,解：上述问题的对偶规划：,性质1 对称性定理：对偶问题的对偶是原问题,性质2 弱对偶原理(弱对偶性)：设 和 分别是问题(P)和(D)的可行解，则必有,推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值的下届；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。,推论2: 在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。,16,原问题与对偶问题可能出现的情况 （1）两者都有最优解，且最优值相等； （2）一个有可行解，但无界，则另一个无可行解； （3）两者都无可行解。,