第2章 对偶理论和灵敏度分析-第5,6节.ppt

文档介绍：运筹学
(第三版)
《运筹学》教材编写组编
清华大学出版社
第2章
对偶理论和灵敏度分析

第5节
对偶问题的经济解释——影子价格

第6节
对偶单纯形法
钱颂迪制作
第2章对偶理论和灵敏度分析
第5节对偶问题的经济解释
——影子价格
在单纯形法的每步迭代中,目标函数取值z=CBB-1b,-CBB-1N中都有乘子Y=CBB-1,那么Y的经济意义是什么?
设B是{max z=CX|AX≤b,X≥0}的最优基,由-Yb= -CB B-1b (2-12)式可知
z*=CBB-1b=Y*b 。
对z求偏导数,得
由上式可知,变量yi*的经济意义是在其他条件不变的情况下,单位资源变化所引起的目标函的最优值的变化。
cj
2
3
0
0
0
θ
CB
XB
b
x1
x2
x3
x4
x5
2
x1
4
1
0
0
1/4
0
0
x5
4
0
0
-2
1/2
1
3
x2
2
0
1
1/2
-1/8
0
-z
-14
0
0
-3/2
-1/8
0
y1*=,y2*=,y3*=0。
这说明是其他条件不变的情况下,若设备增加一台时,;原材料A增加1kg,;原材料B增加1kg,对获利无影响。
从图2-1可看到,设备增加一台时,代表该约束条件的直线由①移至①′,相应的最优解由(4,2)变为(4,),目标函数z=2×4+3×=,。又若原材料A增加1kg时,代表该约束方程的直线由②移至②′,相应的最优解从(4,2)变为(,),目标函数z=2×+3×=。。原材料B增加1kg时,该约束方程的直线由③移至③′,这时的最优解不变。
图2-1
yi*的值代表对第i种资源的估价-影子价格。
这种估价是针对具体工厂的具体产品而存在的一种特殊价格,称它为“影子价格”。在该厂现有资源和现有生产方案的条件下,,,1kg原材料B可按原成本出让,这时该厂的收入与自己组织生产时获利相等。影子价格随具体情况而异,在完全市场经济的条件下,当某种资源的市场价低于影子价格时,企业应买进该资源用于扩大生产;而当某种资源的市场价高于企业影子价格时,则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。
第6节   偶单纯形法
前节讲到原问题与对偶问题的解之间的对应关系时指出:在单纯形表中进行迭代时,在b列中得到的是原问题的基可行解,而在检验数行得到的是对偶问题的基解。
通过逐步迭代,当在检验数行得到对偶问题的解也是基可行解时,根据性质(2)、(3)可知,已得到最优解。即原问题与对偶问题都是最优解。
根据对偶问题的对称性
可以这样考虑:若保持对偶问题的解是基可行解,即cj-CBB-1Pj≤0,而原问题在非可行解的基础上,通过逐步迭代达到基可行解,这样也得到了最优解。
其优点是原问题的初始解不一定是基可行解,可从非基可行解开始迭代。
方法如下:
设原问题max z=CXAX=bX≥0
又设B是一个基。
不失一般性,令B=(P1,P2,…,Pm),它对应的变量为 XB=(x1,x2,…,xm)
当非基变量都为零时,可以得到XB=B-1b。若在B-1b中至少有一个负分量,设(B-1b)i<0,并且在单纯形表的检验数行中的检验数都为非正,即对偶问题保持可行解,它的各分量是