文档介绍：1
第六章单纯形法的灵敏度分析与对偶
§1 单纯形表的灵敏度分析
§2 线性规划的对偶问题
§3 对偶规划的基本性质
§4 对偶单纯形法
2
§1 单纯形表的灵敏度分析
一、目标函数中变量Ck系数灵敏度分析
,X k是非基变量
由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系,
所以当Ck变成Ck+ Ck时,在最终单纯形表中其系数的增广矩阵不变,又因为Xk是非
基变量,所以基变量的目标函数的系数不变,即CB不变,可知Zk也不变,只是Ck变
成了Ck+ Ck。这时 K= Ck-Zk就变成了Ck+ Ck- Zk= K+ Ck。要使原来的最优解
仍为最优解,只要 K+ Ck≤0即可,也就是Ck的增量 Ck≤- K。
, X k是基变量
当Ck变成Ck+ Ck时,最终单纯形表中约束方程的增广矩阵不变,但是基变量的目
标函数的系数CB变了,则ZJ(J=1,2,…..,N)一般也变了,不妨设CB=(CB1, CB2。。。, Ck,
…, CBm),当CB变成=(CB1, CB2。。。,Ck+ Ck,…,CBm),则:
ZJ=(CB1, CB2。。。, Ck,…,CBm)(a’1j , a’2j ,…, a’Kj ,…, a’mj)
Z’J=(CB1, CB2。。。, Ck+ Ck,…,CBm)(a’1j , a’2j ,…, a’Kj ,…, a’mj) = ZJ + Ck a’Kj
3
§1 单纯形表的灵敏度分析
根据上式可知
检验数 J (J=1,2,…..,M)变成了’J,有
’ J=CJ-Z’J= J+ CK a’Kj 。要使最优解不变,只要当J K时, ’J <=0
4
§1 单纯形表的灵敏度分析
例:
目标函数:Max z=50X1+100X2
约束条件:X1+X2≤300
2X1+X2≤400
X2≤250
X1,X2≥0
最优单纯形表如下
迭代次数
基变量
CB
X1 X2 S1 S2 S3
b
50 100 0 0 0
2
X1
50
1 0 1 0 -1
50
S2
0
0 0 -2 1 1
50
X2
100
0 1 0 0 1
250
ZJ
50 100 50 0 50
27500
CJ -ZJ
0 0 -50 0 -50
5
§1 单纯形表的灵敏度分析
我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。
这里δ3=-50,所以当c3的增量Δc3≤50,最优解不变。
再对基变量x1的目标函数的系数c1进行灵敏度分析。
在a11’,a12’,a13’,a14’,a15’中,除了知道a11’和 a13’大于
0, a15’小于0,可知,有。同样有
。这样可以知道当-50≤Δc1≤50时,也就是x1的
目标函数c1’在0≤c1’≤100时最优解不变。
在最终的单纯形表中,用C’1代替原来的C1=50,计算得表
6
§1 单纯形表的灵敏度分析
迭代次数
基变量
CB
X1 X2 S1 S2 S3
b
50 100 0 0 0
2
X1
C’1
1 0 1 0 -1
50
S2
0
0 0 -2 1 1
50
X2
100
0 1 0 0 1
250
ZJ
C’1 100 C’1 0 -C’1+100
CJ -ZJ
0 0 - C’1 0 C’1-100
从δ3≤0,得到-c1’≤0,即c1’≥0,并且从δ5≤0,得到c1’≤100。
那么如果c1’取值超出这个范围,必然存在一个检验数大于0,我们可以通过迭代来得到新的最优解。
7
§1 单纯形表的灵敏度分析
二、约束方程中常数项的灵敏度分析
从上表我们可以发现各个松弛变量的Zj值,正好等于相应变量的对偶价格。在最
优解中S2 =50是基变量,即为,原料A有50千克没用完,再增加A原料是不会增
加利润的, A的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的
对偶价格为0。
迭代次数
基变量
CB
X1 X2 S1 S2 S3
b
50 100 0 0 0
2
X1
50
1 0 1 0 -1
50
S2
0
0 0 -2 1 1
50
X2
100
0 1 0 0 1
250
ZJ
50 100 50 0 50
27500
CJ -ZJ
0 0 -50 0 -50
8
§1 单纯形表的灵敏度分析
可以看出,上题中对于设备台时数约束来说,当其松弛变量在目标函数
中从0变到Z3=50时,也就是只要当前余下一台时数设备从不能获利变成获利
50元时,譬如有人愿意出50元