运筹学模型与软件实践
中国科学院研究生院
Models and Software Practice of the Operations Research
第三章 对偶规划,灵敏度分析与实验
对偶理论简介
对偶线性规划应用
单纯形方法的灵敏度分析
LINDO软件求解与灵敏度分析
投资的收益和风险组合问题
WinQSB软件的应用
DUAL
引入对偶问题
(1)说法:
一般,我们把下面的两个现象称为对偶现象,例如
"在周长一定的四边形中,以正方形的面积为最大",
或者
"在面积为一定的四边形中,以正方形的周长为最小",
这实际上是一个现象的两种提法.
引入对偶问题
(2)实际的例子(汽车生产):
某汽车工厂生产大轿车和载重汽车两种型号的汽车,已知生产每辆汽车所用的钢材都是2吨/辆,该工厂每年供应的钢材是1600吨;工厂的生产能力是每2.5小时可生产一辆载重汽车,每5小时可生产一辆大轿车,工厂全年的有效工时为2500小时;已知供应给该厂大轿车用的座椅每年可装配400辆.出售一辆大轿车可获利4千元,出售一辆载重汽车可获利3千元.问工厂如何安排生产才能获利最大
引入对偶问题
现在提一个新的问题:

如果工厂不再打算生产汽车,而是把钢材和座椅以比买价高的价格卖出,把工厂的生产能力以更高的工时费来接受外协加工,那么材料和工时的定价应该是多少才划算
在考虑定价时,肯定要和生产汽车时的情况进行比较,起码应当使两种情况下的总利润相等.
设y1表示出售单位钢材的利润,y2表示外协加工的工时利润,y3表示出售每套大轿车座椅的利润,那么,用于生产一辆载重汽车的材料销售利润和工时利润之和不应该低于出售一辆载重汽车所得的利润,即
2y1+2.5y2 >=3
用于生产一辆大轿车的材料销售利润,工时利润和座椅利润之和不低于出售一辆大轿车所得的利润
W>=1600y1+2500y2+400y3
为了使材料的价格和工时费在市场上有竞争力,对工厂来说最佳的决策是,在满足上述的约束条件的基础上,售价越低越好,这就是总利润最小值.
显然工厂决策者认为当minW=maxZ时,这两种方案具有相同的结果,都是最优解
一,对偶的定义
原始问题
min z=CTX
s.t. AX≥b
X ≥0
对偶问题(旋转90°)
max y=bTW
s.t. ATW≤C
W ≥0

下一页