X1
S2
50
0
1
0
0
0
1
-2
0
1
-1
1
50
50
2
X2 ZJ
CJ -ZJ
100
0 50
0
1 100
0
运 筹
0 50
-50
学
0 0
0
1 50
-50
250 27500
管
理
7
§1
单纯形表的灵敏度分析
对非基变量目标函数系数： C3 我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。 这里δ3=-50，所以当c3的增量Δ c3≤-（-50），最优解不变。 对基变量目标函数系数： c1 再对基变量x1的目标函数的系数c1进行灵敏度分析。 在a11’,a12’,a13’,a14’,a15’中，除了知道a11’和 a13’大于 0， a15
管
理
运
筹
学
17
§1
约束条件 ≤ ≥ =
单纯形表的灵敏度分析
对偶价格的取值
最终单纯形表对于不同约束类型的对偶价格的取值。
等于这个约束条件对应的松弛变量的 等于这个约束条件对应的剩余变量的 等于这个约束条件对应的人工变量的
z j 值,即为 j 的相反数 z j 值的相反数 zj 值
常数项的灵敏度分析-》使对偶价格不变的bj灵敏度分析-》知道对偶价格Zj等于Cb*Pj的转置。 我们知道单纯型法是增广矩阵的行的初等变换，bj的变化并不影响系数矩阵的变化。所以Pj 是不变的。 所以要使对偶价格不变，只要使Cb不变就可以，就是最终单纯形表中的最优基不变，即最终 单纯型表中的基变量还是基变量，怎么保证基变量还是基变量？（即最优基不变，所得 到的基本解是可行解，也就是基变量的值仍然大于等于零） 所以原问题转化为：使最优解的所有基变量不变，且所得的最优解仍然是可行的Bj的变 化范围。
迭代次数 基变量 CB X1 50 X2 100 0 S1 0 1 S2 0 0 S3 0 -1 50 b
2
X1
50
1
S2
X2 ZJ CJ -ZJ
0
100
0
0 50 0
0
1 100 0
-2
0 50
1
0 0
1
1 50 -50
50
250 27500
-50 0
从上表我们可以发现各个松弛变量的Zj值，正好等于相应变量的对偶价格。
Dk d '1k d '2 k ... d' mk b k d' 2k -1 , 则B b b k d' 3k ... b k d' mk
X B1 b k d'1k X B 2 b k d' 2k 新的最优解为 X'B， 有X'B ... ... X b d' mk Bm k
上节回顾
• 4.退化问题（求出基变量过程中存在两个以 上的最小比值，这样在下一次迭代就有一个 或多个基变量等于零，造成的后果是：最优 值在经过了一次或几次迭代而没有改善，降 低了单纯型算法的效率） • 5.针对退化问题，讲解了一个迭代循环的例 子，引出了勃兰特法则： • 按照决策变量、松弛变量、人工变量顺序排 序。不管是检验数相等，还是比值相等，都 选下标最小的为入基变量或出基变量。 • 时间问题，习题没有做。
管 理 运 筹 学
20
§1
允许变化范围是
单纯形表的灵敏度分析
要使X'B 0也就是各个分量均不小于0，用一个数学式子来表示b k的 x x Max Bi | d 'ik 0 b k Min Bi | d 'ik 0 d 'ik d 'ik
由于单纯形表的迭代是约束方程的增广矩阵的行变换，Pk变成Pk’仅仅影响最终单纯形表上第k
列数据，包括Xk的系数列、Zk以及 k，这时最终单纯形表上的Xk的系数列就变成了B-1Pj’,而Zk
管
理
运
筹
学
8
§1
迭代次数 基变量 X1 S2
单纯形表的灵敏度分析
CB X1 1 0 100 0 0 X2 0 0 1 S1 0 1 -2 0 S2 0 0 1 0 0 0 S3 0 -1 1 1 C’1-100
另外一种求最优解不变的C’1变化范围方法 在最终的单纯形表中，用C’1代替原来的C1=50,计算得表
δj δj Max a'kj 0 ΔCk Min a'kj 0（其中 k是某个固定的值， j是1到n的所有数） a' a' kj kj
管 理 运 筹 学
6
§1
单纯形表的灵敏度分析
例： 目标函数：Max z=50X1+100X2 约束条件：X1+X2≤300 2X1+X2≤400 X2≤250 X1，X2≥0 最优单纯形表如下 迭代次数 基变量 CB X1 50 X2 100 S1 0 S2 0 S3 0 b
T
管
理
运
筹
学
5
§1
根据上式可知 检验数
单纯形表的灵敏度分析
K时，有

J
(J=1,2,…..,M)变成了 ’J,只要当J
J
’ J=CJ-Z’ J=
当a'kj 0时, ΔCk 当a'kj 0时, ΔCk δj a'kj δj a'kj
CK a’Kj 。要使最优解不变， ’J <=0
管 理 运 筹 学
1
第六章 单纯形法的灵敏度分析与对偶问题
• §1 • §2 • §3 • §4
单纯形表的灵敏度分析 线性规划的对偶问题 对偶规划的基本性质 对偶单纯形法
管
理
运
筹
学
2
单纯形表
管
理
运
筹
学
3
§1
单纯形表的灵敏度分析
一、目标函数中变量系数Ck灵敏度分析（在什么范围内变化， 最优解不变，与第二章，第三章联系起来） 在线性规划的求解过程中，目标函数系数的变动将会影响检 验数的取值，但是，当目标函数的系数的变动不破坏最优判 别准则时，原最优解不变，否则，原最优解将发生变化，要 设法求出新的最优解。下面我们具体的分析 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。
管
理
运
筹
学
18
§1
单纯形表的灵敏度分析
当bj中的第k项bK 变成 bk bk 时，也就是原来的初始单 纯形表中的b向量变成了b’向量
0 0 ... 则有b' b b 令b bk ... 0
管
理
运
筹
学
19
§1
单纯形表的灵敏度分析
这样在最终单纯形表中基变量XB的解就变成了 X'B B-1.(b b) B-1 b B-1 b。 如要使XB成为可行解，只要使上述等式的右边>0，就可求出 bk 的取值范围，也就是使得第K个约束条件的对偶价格不变的 bk的变化范围。 b k d'1k
δj a'kj δj a'kj 0; 0;
δ j - ΔCk a'kj 0, ΔCk a'kj δ j , 这里 , 这里
当j k时，δ'k C k ΔCk Z k ' C k ΔCk Z k ΔCk a'kk ,因为X K 是基变量， 知δ k 0，a'kk 1，可知δ'k 0。所以j k这种情况最优解不变。 要使得最优解不变，对 于除了a'kk 以外的所有大于 0的a'kj ，满足ΔCk 满足ΔCk δj a'kj ，所以可知ΔCk的变化范围为 δj a'kj ，所有小于0的a'kj
C’1 100 b 50 50 250
2
X2 ZJ CJ -ZJ
C’1 100 C’1+100 0 0
C’1 - C’1
从δ 3≤0，得到-c1’≤0,即c1’≥0，并且从δ 5≤0，得 到c1’≤100。 那么如果c1’取值超出这个范围，必然存在一个检验数 大于0，我们可以通过迭代来得到新的最优解。
实际意义可以描述为：设备台时数在250与325之间变化，则设备台时
数的对偶价格不变，都为每台设备台时50元。
管
理
运
筹
学
22
§1
下面分两种情况讨论
单纯形表的灵敏度分析
三、约束方程系数矩阵A灵敏度分析（约束条件改变，对最优解的影响，比如 有新产品要生产、生产工艺改进等） 1.在最终单纯形表上Xk是非基变量：在初始单纯形表上的变量Xk的系数列Pk 改变为P’k经过迭代后，在最终单纯形表上Xk是非基变量。
’小于0，可知
c1≤50时，也就是x1的 目标函数c1’在0≤c1’≤100时最优解不变。
j ' min a 1 j 0 50 。这样可以知道当-50≤Δ a ' 1 j