管理运筹学6单纯形法的灵敏度分析与对偶1

第六章 单纯形法的灵敏度分析与对偶

§1 §2 §3 §4

单纯形表的灵敏度分析 线性规划的对偶问题 对偶规划的基本性质 对偶单纯形法

管

理

运

筹

学

§1 单纯形表的灵敏度分析一、目标函数中变量C 系数灵敏度分析k

1.在最终的单纯形表里，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。 2.在最终的单纯形表中， 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) T T

Z’J=(CB1, CB2。。。, Ck+ Ck,…,CBm)(a’1j , a’2j ,…, a’Kj ,…, a’mj)管 理 运 筹 学

= ZJ + Ck a’Kj2

§1 单纯形表的灵敏度分析根据上式可知 检验数

J

(J=1,2,…..,M)变成了 ’J,有J

’ J=CJ-Z’J= 当a'kj 0时, ΔC k 当a'kj 0时, ΔC k δj a'kj δj a'kj

+ CK a’Kj 。要使最优解不变，只要当J δj a'kj δj a'kj

K时， ’J <=0

δ j ΔC k a'kj 0, ΔC k a'kj δ j , 这里 , 这里 0; 0;

当j k时，δ'k C k ΔC k Z k ' C k ΔC k Z k ΔC k a'kk ,因为X K 是基变量， 知δ k 0,a'kk 1,可知δ'k 0。 要使得最优解不变，对于除了a'kk 以外的所有大于0的a'kj ,满足ΔC k 满足ΔC k δj a'kj ,所以可知ΔC k的变化范围为 δj a'kj ,所有小于0的a'kj

δj δj Max a'kj 0 ΔC k Min a'kj 0 a'kj a'kj 管 理 运 筹 学3

§1 单纯形表的灵敏度分析例： 目标函数：Max z=50X1+100X2 约束条件：X1+X2≤300 2X1+X2≤400 X2≤250 X1,X2≥0 最优单纯形表如下 迭代次 数 基变量 X1 S2 X2 ZJ CJ -ZJ管

CB 50 0 100

X1 50 1 0 0 50 0理

X2 100 0 0 1 100 0运

S1 0 1 -2 0 50

S2 0 0 1 0 0 0

S3 0 -1 1 1 50 -50

b 50 50 250 27500

2

-50筹 学

§1 单纯形表的灵敏度分析我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。 这里δ3=-50,所以当c3的增量Δ c3≤50,最优解不变。 再对基变量x1的目标函数的系数c1进行灵敏度分析。 在a11’,

a12’,a13’,a14’,a15’中，除了知道a11’和 a13’大于 0, a15’小于0,可知- 3 50 50 a13 1

,有

j ' max a 1 j 0 50 a '1 j 。这样可以知道当-50≤Δ

j ' min a 1 j 0 50 a '1 j

。同样有

c1≤50时，也就是x1

的 目标函数c1’在0≤c1’≤100时最优解不变。 在最终的单纯形表中，用C’1代替原来的C1=50,计算得表管 理 运 筹 学5

§1 单纯形表的灵敏度分析迭代次数 基变量 X1 S2 X2 ZJ CB C’1 0 100 X1 50 1 0 0 C’1 X2 100 0 0 1 100 S1 0 1 -2 0 C’1 S2 0 0 1 0 0 S3 0 -1 1 1 -C’1+100 b 50 50 250

2

CJ -ZJ

0

0

- C’1

0

C’1-100

从δ 3≤0,得到-c1’≤0,即c1’≥0,并且从δ 5≤0,得 到c1’≤100。 那么如果c1’取值超出这个范围，必然存在一个检验数 大于0,我们可以通过迭代来得到新的最优解。

管

理

运

筹

学

§1 单纯形表的灵敏度分析二、增加一个约束条件的灵敏度分析 在原线性规划中增加一个约束条件时,先将原问 题的最优解的变量值代入新增的约束条件，如满足 则说明新增的条件没有起到限制作用，故原最优解 不变，否则将新增的约束添入原最终单纯形表上进 一步求解。 下面仍以第三章例1为例来加以说明。 例：假如该工厂除了在设备台时，原材料A、B 上对该厂的生产有限制外，还有电力供应上的限制。 最高供应电量为5000度，而生产一个Ⅰ产品需要用 电10度，而生产一个Ⅱ产品需要用电30度。试分析 此时该厂获得最大利润的生产计划？管 理 运 筹 学7

§1 单纯形表的灵敏度分析解：先将原问题的最优解 x1 =50,x 2 =250代入用电量的约束条件

10 x1 30 x2 5000得：10×50+30×250=500+7500>5000,所以原题的最优解不是本题的最优解。 在用电量的约束条件中加入松驰变量S4后得：

10 x1 +30x 2 +s 4 =5000把这个约束条件加入到原最终单纯形表上，其中S4为基变量，得表如下：迭代 次数 基变量

CB50 0 100

x1501 0 0 0 0 1

x2100 01

s100 1 0

s20

s300 0 0 -1 1 1

s4

b 50 50 250

比值

x1 s2 x2

-2 0

s4zj

0

1050 0

30100 0 管 理

050 -50 运 筹

00 0 学

050 -50

10 0

50002750 0

j cj zj

§1 单纯形表的灵敏度分析在上表中的X1,X2不是单位向量，故进行行的线性变换，得迭代 次数 基变量 CB x1 50 x1 s2 x2 s4 zj 50 0 100 0 1 0 0 0 50 0 x2 100 0 0 1 0 100 0 s1 0 1 -2 0 -10 50 -50 s2 0 0 1 0 0 0 0 s3 0 -1 1 1 -20 50 -50 s4 0 0 0 0 1 0 0 50 50 250 -3000 27500 b 比值

j cj zj

把上表中的S4行的约束可以写为： 10s1 20s3 s4 3000

10 上式两边乘以(-1) …… 此处隐藏：3028字，全部文档内容请下载后查看。喜欢就下载吧 ……