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