运筹学_8 对偶问题概念+转换方法

Lec.8OperationalResearch对偶问题dualZHUTongChang’anUniversityE-mail:[e-mail].2012HomeHomeOperationalResearch2提纲•引入对偶问题•对偶问题的实际意义•原问题如何转化为对偶问题OperationalResearch3引入对偶问题前面的问题：自己用设备生产最大效益对偶问题：把设备租赁出去最低费用OperationalResearch4引入对偶问题对偶问题不能从字面理解为镜像问题更好的翻译方法是伴随问题OperationalResearch5引入对偶问题：举例某汽车配件厂生产甲、乙两种产品。两种产品都需要在A、B两种不同的设备上加工，每种产品在不同的设备上加工的工时、设备工时限制、这些产品销售收入如下表：每生产1个甲产品，需要A设备工作15个单位时间，B设备工作9个单位时间。每生产1个乙产品，需要A设备工作6个单位时间，B设备工作9个单位时间。1个甲产品利润200元/个；1个乙产品利润150元/个A设备最多工作540小时;B设备最多工作405小时甲乙有效工时A156540B99405利润（元/个）200150OperationalResearch6引入对偶问题：举例某汽车配件厂生产甲、乙两种产品。两种产品都需要在A、B两种不同的设备上加工，每种产品在不同的设备上加工的工时、设备工时限制、这些产品销售收入如下表：甲乙有效工时A156540B99405利润（元/个）2001500,40599540615..150200max21212121xxxxxxtsxxZ解为（30,15,0,0），最优值为8250OperationalResearch7引入对偶问题：举例第一个问题：生产问题另一个问题：出租问题•将A、B设备出租，在合理的利润条件下，消耗的资源至少是？（1）变量：y1、y2为A、B两种设备对外加工时，单位工时的价格。（2）约束条件（生产者接受）：“合理”的利润条件是指，如果把A、B设备租出去生产甲，所得收入不应少于200元；把A、B设备租出去生产乙，所得收入不应小于150元。（3）目标函数（收购方意愿）：要租A、B设备，收购费用最少是多少。21212121405540min0,15096200915..xxwyyyyyyts150150200200利润（元利润（元//个）个）4054059999BB540540661515AA有效工时有效工时乙乙甲甲150150200200利润（元利润（元//个）个）4054059999BB540540661515AA有效工时有效工时乙乙甲甲解为（50/9，350/27，0，0），值为8250OperationalResearch8对偶问题的实际意义：影子价格Y*为影子价格，用于估计设备资源转让的费用。•当某种资源的市场价格低于影子价格时，应该买进•当某种资源的市场价格高于影子价格时，可以卖出OperationalResearch9对偶问题的形式nixbxaxaxabxaxaxabxaxaxatsxcxcxcZimnmnmmnnnnnn1,0..max221122222121112121112211mjycyayayacyayayacyayayatsybybybwjnmmnnnmmmmnn1,0..min221122222112112211112211总结：优化目标大变小，常数－价值互相换，系数矩阵要转置，约束－变量捉对变。OperationalResearch10对偶问题的形式原问题对偶问题原目标函数maxZ对偶目标函数minw原约束条件变量个数m个第i个约束≤≥＝对偶变量变量个数m个第i个约束yi≥0yi≤0yi自由变量原变量变量个数n个第j个约束Xj≥0Xj≤0Xj自由变量对偶约束条件变量个数n个第j个约束≥≤＝优化目标大变小，常数－价值互相换，系数矩阵要转置，约束－变量捉对变。OperationalResearch11练习一0,720394505554093..3070max2121212121xxxxxxxxtsxxZOperationalResearch12练习一0,720394505554093..3070max2121212121xxxxxxxxtsxxZ3,2,1,03035970953..720450540max321321321iyyyyyyytsyyywiOperationalResearch13练习二3,2,1,0426323..23max321321321ixxxxxxxtsxxxZiOperationalResearch14练习二为自由变量2121212121,2312233..46minyyyyyyyytsyyw3,2,1,0426323..23max321321321ixxxxxxxtsxxxZiOperationalResearch15练习三无约束；；40,0642253..532min32143242143214321xxxxxxxxxxxxxxtsxxxxZ提示：min！！！OperationalResearch16练习三无约束；；3213213213121321001523322..645maxyyyyyyyyyyyyytsyyyZ