运筹学 对偶问题概念转换方法讲稿.ppt

《运筹学 对偶问题概念转换方法讲稿.ppt》由会员分享，可在线阅读，更多相关《运筹学 对偶问题概念转换方法讲稿.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于运筹学 对偶问题概念转换方法第一页，讲稿共十六页哦Operational Research2提纲提纲 引入对偶问题引入对偶问题 对偶问题的实际意义对偶问题的实际意义 原问题如何转化为对偶问题原问题如何转化为对偶问题第二页，讲稿共十六页哦Operational Research3引入对偶问题前面的问题：自己用设备生产最大效益前面的问题：自己用设备生产最大效益对偶问题：把设备租赁出去最低费用对偶问题：把设备租赁出去最低费用第三页，讲稿共十六页哦Operational Research4引入对偶问题l l 对偶问题不能从字面理解为镜像问题对偶问题不能从字面理解为镜像问题l l 更好的翻译方法是更

2、好的翻译方法是 伴随问题伴随问题第四页，讲稿共十六页哦Operational Research5引入对偶问题：举例引入对偶问题：举例某汽车配件厂生产某汽车配件厂生产甲、乙甲、乙两种产品。两种产品都需要在两种产品。两种产品都需要在A A、B B两种不同的设备上加工，每种产品两种不同的设备上加工，每种产品在不同的设备上加工的工时、设备工时限制、这些产品销售收入如下表：在不同的设备上加工的工时、设备工时限制、这些产品销售收入如下表：每生产每生产1 1个甲产品，需要个甲产品，需要A A设备工作设备工作1515个单位时间，个单位时间，B B设备工作设备工作9 9个单位时间。个单位时间。每生产每生产1 1

3、个乙产品，需要个乙产品，需要A A设备工作设备工作6 6个单位时间，个单位时间，B B设备工作设备工作9 9个单位时间。个单位时间。1 1个甲产品利润个甲产品利润200200元元/个；个；1 1个乙产品利润个乙产品利润150150元元/个个 A A设备最多工作设备最多工作540540小时小时;B;B设备最多工作设备最多工作405405小时小时甲甲乙乙有效工时有效工时A A15156 6540540B B9 99 9405405利润（元利润（元/个）个）200200150150第五页，讲稿共十六页哦Operational Research6引入对偶问题：举例引入对偶问题：举例某汽车配件厂生产某汽

4、车配件厂生产甲、乙甲、乙两种产品。两种产品都需要在两种产品。两种产品都需要在A A、B B两种不同的设备上加工，每种产品两种不同的设备上加工，每种产品在不同的设备上加工的工时、设备工时限制、这些产品销售收入如下表：在不同的设备上加工的工时、设备工时限制、这些产品销售收入如下表：甲甲乙乙有效工时有效工时A A15156 6540540B B9 99 9405405利润（元利润（元/个）个）200200150150解为（解为（30,15,0,030,15,0,0），最优值为），最优值为82508250第六页，讲稿共十六页哦Operational Research7引入对偶问题：举例 第一个问题：生

5、产问题第一个问题：生产问题 另一个问题：出租问题另一个问题：出租问题 将将A A、B B设备出租，在合理的利润条件下，消耗的资源至少是？设备出租，在合理的利润条件下，消耗的资源至少是？（1 1）变量：）变量：y1y1、y2y2为为A A、B B两种设备对外加工时，单位工时的价格。两种设备对外加工时，单位工时的价格。（2 2）约束条件（）约束条件（生产者接受生产者接受）：）：“合理合理”的利润条件是指，如果把的利润条件是指，如果把A A、B B设备设备租出去生产租出去生产甲甲，所得收入不应，所得收入不应少于少于200200元；把元；把A A、B B设备设备租出去生产租出去生产乙乙，所得收入不应小

6、于，所得收入不应小于150150元。元。（3 3）目标函数（）目标函数（收购方意愿收购方意愿）：要租）：要租A A、B B设备设备，收购费用最少是多少。，收购费用最少是多少。解为（解为（50/950/9，350/27350/27，0 0，0 0），值为），值为82508250第七页，讲稿共十六页哦Operational Research8对偶问题的实际意义：影子价格对偶问题的实际意义：影子价格Y*Y*为影子价格，用于估计设备资源转让的费用。为影子价格，用于估计设备资源转让的费用。当某种资源的市场价格低于影子价格时，应该买进 当某种资源的市场价格高于影子价格时，可以卖出第八页，讲稿共十六页哦Op

7、erational Research9对偶问题的形式对偶问题的形式总结：总结：优化目标大变小，常数价值互相换，优化目标大变小，常数价值互相换，系数矩阵要转置，约束变量捉对变。系数矩阵要转置，约束变量捉对变。第九页，讲稿共十六页哦Operational Research10对偶问题的形式对偶问题的形式原问题原问题对偶问题对偶问题原目标函数原目标函数 max Zmax Z对偶目标函数对偶目标函数 min wmin w原约束条件原约束条件变量个数变量个数 m m 个个第第 i i 个约束个约束对偶变量对偶变量变量个数变量个数 m m 个个第第 i i 个约束个约束yi yi 0 0yiyi 0 0y

8、iyi 自由变量自由变量原变量原变量变量个数变量个数 n n 个个第第 j j 个约束个约束Xj Xj 0 0XjXj 0 0XjXj 自由变量自由变量对偶约束条件对偶约束条件变量个数变量个数 n n 个个第第 j j 个约束个约束优化目标大变小，常数价值互相换，系数矩阵要转置，约束变量捉对变。优化目标大变小，常数价值互相换，系数矩阵要转置，约束变量捉对变。优化目标大变小，常数价值互相换，系数矩阵要转置，约束变量捉对变。优化目标大变小，常数价值互相换，系数矩阵要转置，约束变量捉对变。第十页，讲稿共十六页哦Operational Research11练习一第十一页，讲稿共十六页哦Operational Research12练习一练习一第十二页，讲稿共十六页哦Operational Research13练习二第十三页，讲稿共十六页哦Operational Research14练习二练习二第十四页，讲稿共十六页哦Operational Research15练习三练习三提示：min！第十五页，讲稿共十六页哦Operational Research感谢大家观看第十六页，讲稿共十六页哦