1、Lec. 8 Operational Research对偶问题 dualZHU TongChangan University E-mail:Oct. 2012HomeOperational Research提纲 引入对偶问题 对偶问题的实际意义 原问题如何转化为对偶问题2Operational Research引入对偶问题前面的问题：自己用设备生产最大效益对偶问题：把设备租赁出去最低费用3Operational Research引入对偶问题l 对偶问题不能从字面理解为镜像问题l 更好的翻译方法是 伴随问题4Operational Research引入对偶问题：举例某汽车配件厂生产 甲、乙 两种
2、产品。两种产品都需要在 A、 B两种不同的设备上加工，每种产品在不同的设备上加工的工时、设备工时限制、这些产品销售收入如下表： 每生产 1个甲产品，需要 A设备工作 15个单位时间， B设备工作 9个单位时间。 每生产 1个乙产品，需要 A设备工作 6个单位时间， B设备工作 9个单位时间。 1个甲产品利润 200元 /个； 1个乙产品利润 150元 /个 A设备最多工作 540小时 ; B设备最多工作 405小时甲 乙 有效工时A 15 6 540B 9 9 405利 润 （元 /个） 200 1505Operational Research引入对偶问题：举例某汽车配件厂生产 甲、乙 两种产
3、品。两种产品都需要在 A、 B两种不同的设备上加工，每种产品在不同的设备上加工的工时、设备工时限制、这些产品销售收入如下表：甲 乙 有效工 时A 15 6 540B 9 9 405利 润 （元 /个） 200 150解为（解为（ 30,15,0,0），最优值为），最优值为 82506Operational Research引入对偶问题：举例 第一个问题：生产问题 另一个问题：出租问题 将 A、 B设备出租，在合理的利润条件下，消耗的资源至少是？（ 1）变量： y1、 y2为 A、 B两种设备对外加工时，单位工时的价格。（ 2）约束条件（ 生产者接受生产者接受 ）： “ 合理 ” 的利润条件是指
4、，如果把 A、 B设备 租出去生产甲 ，所得收入不应少于 200元；把 A、 B设备 租出去生产 乙 ，所得收入不应小于 150元。（ 3）目标函数（ 收购方意愿收购方意愿 ）：要租 A、 B设备 ，收购费用最少是多少。解为（解为（ 50/9， 350/27， 0， 0），值为），值为 82507Operational Research对偶问题的实际意义：影子价格Y*为影子价格，用于估计设备资源转让的费用。 当某种资源的市场价格低于影子价格时，应该买进 当某种资源的市场价格高于影子价格时，可以卖出8Operational Research对偶问题的形式总结：优化目标大变小，常数价值互相换，系数矩阵要转置，约束变量捉对变。9Operational Research对偶问题的形式原 问题 对 偶 问题原目 标 函数 max Z 对 偶目 标 函数 min w原 约 束条件变 量个数 m 个第 i 个 约 束对 偶 变 量变 量个数 m 个第 i 个 约 束yi 0yi 0yi 自由 变 量原 变 量变 量个数 n 个第 j 个 约 束Xj 0Xj 0Xj 自由 变 量对 偶 约 束条件变 量个数 n 个第 j 个 约 束优化目标大变小，常数价值互相换，系数矩阵要转置，约束变量捉对变。优化目标大变小，常数价值互相换，系数矩阵要转置，约束变量捉对变。10
