§5灵敏度分析 在线性规划问题中，目标函数、约束条件的系数以及资 源的限制量等都当作确定的常数，并在这些系数值的基础 求得最优解。但是实际上，这些系数或资源限制量并非一成 不变的，它们是一些估计或预测的数字，比如价值系数随着 市场的变化而变化，约束系数随着工艺的变化或消耗定额的 变化而变化，计划期的资源限制量也是经常变化的。当这些 系数发生变化时，最优解会受到什么影响？最优解对哪些参 数的变动最敏感？搞清这些问题会使我们在处理实际问题时 具有更大的主动性和可靠性。 分析线性规划模型的某些系数或限制数的变动对最优解。 的影响，被称作灵敏度分析。 灵敏度分析主要解决两个问题： (I)这些系数在什么范围内变化时，原先求出的最优解或 最优基不变？即最优解相对参数变化的稳定性。 (2)如果系数的变化引起了最优解的变化，如何用最简便 的方法求出新的最优解
§5 灵敏度分析 在线性规划问题中，目标函数、约束条件的系数以及资 源的限制量等都当作确定的常数，并在这些系数值的基础上 求得最优解。但是实际上，这些系数或资源限制量并非一成 不变的，它们是一些估计或预测的数字，比如价值系数随着 市场的变化而变化，约束系数随着工艺的变化或消耗定额的 变化而变化，计划期的资源限制量也是经常变化的。当这些 系数发生变化时，最优解会受到什么影响？最优解对哪些参 数的变动最敏感？搞清这些问题会使我们在处理实际问题时， 具有更大的主动性和可靠性。 分析线性规划模型的某些系数或限制数的变动对最优解 的影响，被称作灵敏度分析。 灵敏度分析主要解决两个问题： ⑴这些系数在什么范围内变化时，原先求出的最优解或 最优基不变？即最优解相对参数变化的稳定性。 ⑵如果系数的变化引起了最优解的变化，如何用最简便 的方法求出新的最优解
下面分别介绍各类参数变化的灵敏度分析。 5.1目标函数中价值系数C的分析 分别就非基变量和基变量的价值系数两种情况来讨论： 1.设非基变量x的价值系数c,有增量△c其它参数不 变，求△c的范围使原最优解不变。 由于℃是非基变量的价值系数，因此它的改变仅仅影响 检验数σ的变化，而对其它检验数没有影响。 由o=C;+△C;-CgBP,=o+△c≤0 知，当△C≤-o时，原最优解不变。 2.设基变量Xr的价值系数CBr有增量△Cr,其它参数 变，求△C的范围使原最优解不变。 由于C是基变量的价值系数，因此它的变化将影响所 有非基变量检验数的变化。 由新的非基变量检验数：可=C,C。+0AC0p-, -0(0.△Cr0)B-1P0aj△Cgr≤0，可知，当 max{c,/arj arj>0}≤△Cr≤min{o,/ari arj<0}时，原 最优解不变
下面分别介绍各类参数变化的灵敏度分析。 5.1 目标函数中价值系数C的分析 分别就非基变量和基变量的价值系数两种情况来讨论： ⒈设非基变量xj的价值系数cj,有增量△cj,其它参数不 变，求△cj的范围使原最优解不变。 由于cj是非基变量的价值系数，因此它的改变仅仅影响 检验数σj的变化，而对其它检验数没有影响。 由 σj+△cj≤0 知，当△cj≤-σj 时，原最优解不变。 ⒉设基变量XBr的价值系数CBr有增量△CBr，其它参数不 变，求△CBr的范围使原最优解不变。 由于CBr是基变量的价值系数，因此它的变化将影响所 有非基变量检验数的变化。 由新的非基变量检验数： =σj-（0…△CBr…0）B -1Pj =σj-arj△CBr≤0，可知，当 max｛σj /arj│arj＞0｝≤△CBr≤min｛σj /arj│arj＜0｝时，原 最优解不变。 j j j σ c - C ΔC B P 1 B Br − = + 0 0 = + − = j 1 j j j B σ c Δc -C B P
例3 已知第一章例1的最优解及最优值如下： C 6 4 0 0 CB X B-16 X1 X2 X3 X4 0 X3 100 2 3 1 0 0 X4 120 [4] 2 0 1 0 6 4 0 0 4 X2 20 112 -1/4 6 X 20 0 -1/4 3/8 O 0 0 -112 -5/4 (1)求使原最优解不变的△C,的变化范围。 (2)若C1变为12，求新的最优解。 解：(I)C即C1,是基变量价值系数，用非基变量的检验数 与单纯形表第一行相应元素相比得：
例3 已知第一章例1的最优解及最优值如下： C 6 4 0 0 CB XB B -1b X1 X2 X3 X4 0 0 X3 X4 100 120 2 3 1 0 ［4］ 2 0 1 σ 6 4 0 0 ……………………………………… 4 6 X2 X1 20 20 0 1 1/2 -1/4 1 0 -1/4 3/8 σ 0 0 -1/2 -5/4 ⑴求使原最优解不变的△C2的变化范围。 ⑵若C1变为12，求新的最优解。 解：⑴ C2即CB1 ，是基变量价值系数，用非基变量的检验数 与单纯形表第一行相应元素相比得：
(2)将C,=12代入原最优表，重新计算检验数，原最优解不 再是最优解，用单纯形法继续运算，结果如下： C 4 0 0 CB X B-ib X X2 X3 X4 4 X2 20 0 1 1/2 -1/4 12 X 20 1 0 -1/4 3/8 0 0 0 0 X3 40 12 X 30 新的最优解：X1=30,X3=40,X2=X4=0 最优值：Z=360
⑵将C1=12代入原最优表，重新计算检验数，原最优解不 再是最优解，用单纯形法继续运算，结果如下： C 6 4 0 0 CB XB B -1b X1 X2 X3 X4 4 6 X2 X1 20 20 0 1 1/2 -1/4 1 0 -1/4 3/8 σ 0 0 -1/2 -5/4 12 12 1 -7/2 0 12 X3 X1 40 30 σ 新的最优解：X1=30，X3=40，X2 =X4=0 最优值：Z=360
5.2资源系数b的分析 设b:有增量△b,其它参数不变，则b:的变化将影响基变 量所取的值，但对检验数没有影响，记新的基变量为X。,则 又=B-b+0,ab0=Bb+Bab 这里BB是原最优基逆阵B的第列。如果变化后仍存 X≥0，则原最优基不变。由此可知，当△b满足 B 时，原最优基不变。 结果说明，△b:的变化范围是由原基变量的相反数与B1的 第列元素的比值所确定的。 如果△b:不在上述范围变动，则变化后的基变量所取值 区，肯定会出现负分量，但由于△b:不影响检验数的变化，因 此可以用X取代原最优解XBb，以该解为初始解，用对偶 单纯形法继续求解
5.2 资源系数b的分析 设bi有增量△bi，其它参数不变，则bi的变化将影响基变 量所取的值，但对检验数没有影响，记新的基变量为 ，则 这里 是原最优基逆阵B-1的第i列。如果变化后仍有 ≥0，则原最优基不变。由此可知，当△bi满足 ≤△bi≤ 时，原最优基不变。 结果说明 ，△bi的变化范围是由原基变量的相反数与B-1的 第i列元素的比值所确定的。 如果△bi不在上述范围变动，则变化后的基变量所取值 肯定会出现负分量，但由于△bi不影响检验数的变化，因 此可以用 取代原最优解XB =B -1b ，以该解为初始解，用对偶 单纯形法继续求解。 i -1 mi -1 1i -1 i 1 XB B b 0, ,Δb , ,0 B b B B •Δb − = + = + T T ,, B X T -1 mi -1 1i B ,,B B X − − − − B 0 B B b max 1 1 ki ki k 1 k − − − − B 0 B B b min 1 1 ki ki k 1 k B X B X
例4已知线性规划问题的初始解及最优解见例3。 (1)求△b,的范围，使原最优基不变； (2)若b,变为200，试求新的最优解。 (1/2 20 解：(I)由己知单纯形表可知B1= -1/4 3/8 20 用基变量的负值与B的第一列相应元素去比，得 40≤△b1≤80 时，原最优基不变。 (2)变化后基变量的取值为X=B-6= 1/2-1/4200)(70 -1/4 3/8120 -5 不是可行解，须用区替换原最优表中基变量的值，并采用 对偶单纯形法继续求解，结果如下： C 6 4 0 0 CB XB B-ib X X2 X3 X4 4 X2 20 0 1 1/2-114 6 X1 20 1 0 -114 3/8 g 0 0 -112 -5/4
例4 已知线性规划问题的初始解及最优解见例3。 ⑴求△b1的范围，使原最优基不变； ⑵若b1变为200，试求新的最优解。 解：⑴由已知单纯形表可知 B-1= = − − 20 20 ,X 1/4 3/8 1/2 1/4 B 用基变量的负值与B-1的第一列相应元素去比，得 -40≤△b1≤80 时，原最优基不变。 ⑵变化后基变量的取值为 − − = − − = = 5 70 120 200 1/4 3/8 1/2 1/4 X B b 1 B 不是可行解，须用 替换原最优表中基变量的值，并采用 对偶单纯形法继续求解，结果如下： B X C 6 4 0 0 CB XB B -1b X1 X2 X3 X4 4 6 X2 X1 20 20 0 1 1/2 -1/4 1 0 -1/4 3/8 σ 0 0 -1/2 -5/4
C 6 4 0 0 CB Xs B-ib X X2 X3 X4 4 X2 70 0 1 1/2-1/4 L=2 6 X1 -5 1 0 -1/4 3/8 K=3 O 0 0 -1/2 -5/4 4 X2 60 2 1 0 1/2 0 20 -4 0 -3/2 O -2 0 0 -2 由此得最优解：X1=0,x2=60,x3=20,x40 最优值：Z*=240
C 6 4 0 0 CB XB B -1b X1 X2 X3 X4 4 6 X2 X1 70 -5 0 1 1/2 -1/4 1 0 -1/4 3/8 σ 0 0 -1/2 -5/4 4 0 X2 X3 60 20 2 1 0 1/2 -4 0 1 -3/2 σ -2 0 0 -2 L=2 K=3 由此得最优解：x1=0,x2=60,x3=20,x4=0 最优值：Z﹡=240
5.3系数矩阵A的分析 以下分4种情况讨论系数矩阵的变化。 1.增加一个新变量的分析 设X+1是新增加的变量，其对应的系数列向量为Pn+1, 值系数为C1,试讨论原最优解有无改变？及如何尽快地求 出新的最优解。 如果原问题增加一个新变量，则系数矩阵增加一个列； 注意到新增加的列在以B为基的单纯形表中应变为BPn+1, 所以可先计算BP1及o+=Cn+1CB-Pn1,若oH10,则原最 优解不变，反之可将BP+1增填到原最优表的后面，用单纯 形法继续迭代。 例5设第一章例1的原线性规划问题中考虑生产Ⅲ型计 算机，已知生产每台Ⅲ型计算机所需原料4个单位，工时3 个单位，可获利润8个单位。试问该厂是否应该生产Ⅱ型 计算机？如果生产，应该生产多少？
5.3 系数矩阵A的分析 以下分4 种情况讨论系数矩阵的变化。 1.增加一个新变量的分析 设xn+1是新增加的变量，其对应的系数列向量为Pn+1，价 值系数为Cn+1，试讨论原最优解有无改变？及如何尽快地求 出新的最优解。 如果原问题增加一个新变量，则系数矩阵增加一个列， 注意到新增加的列在以B为基的单纯形表中应变为B -1Pn+1 ， 所以可先计算B -1Pn+1及σn+1 =Cn+1-CBB -1Pn+1，若σn+1≤0，则原最 优解不变，反之可将B -1Pn+1增填到原最优表的后面，用单纯 形法继续迭代。 例5 设第一章例1的原线性规划问题中考虑生产Ⅲ型计 算机，已知生产每台Ⅲ型计算机所需原料4个单位，工时3 个单位，可获利润8个单位。试问该厂是否 应该生产 Ⅲ型 计算机？如果生产，应该生产多少？
解：设生产Ⅲ型计算机x3'台，由原最优基的B逆可得： BP3′= 1/2-1/44_5/4 -1/43/831/8 o3'=C3′-CB-1P3′=8-(4,6) 9/4 1/8 因为o3>0,所以安排生产Ⅲ型计算机有利，将BP3'增填 到原最优表的后面，并用单纯形法继续计算，结果如下： C 6 4 0 0 8 XB B-1b X2 X3 X4 X3' 4 X2 20 0 1 1/2-1/45/4 K- 6 Xi 20 1 0 -1/4 3/81/8 L=1 g 0 0 -112 -5/49/8 8 X3'X1 16 0 4/5 2/5-1/5 1 6 18 -1/10-3/102/5 0 0 0 -9/8-715-4/5 0 最优解；X1=18,X2=0,X3=0,X3=16,X40 最优值：Z*=236
解：设生产Ⅲ型计算机x3 ′台，由原最优基的B -1逆可得： B -1P3 ′= σ3 ′=C3 ′-CBB -1P3′=8-（4，6） 因为σ3 ′＞0，所以安排生产Ⅲ型计算机有利，将B -1P3 ′增填 到原最优表的后面，并用单纯形法继续计算，结果如下： = − − 1/8 5/4 3 4 1/4 3/8 1/2 1/4 9/4 1/8 5/4 = C 6 4 0 0 8 CB XB B -1b X1 X2 X3 X4 X3 ′ 4 6 X2 X1 20 20 0 1 1/2 -1/4 5/4 1 0 -1/4 3/8 1/8 σ 0 0 -1/2 -5/4 9/8 8 6 X3 ′ X1 16 18 0 4/5 2/5 -1/5 1 1 -1/10 -3/10 2/5 0 σ 0 -9/8 -7/5 -4/5 0 K=5 L=1 最优解；X1=18，X2=0，X3=0，X3 ′=16，X4=0 最优值：Z﹡=236
第二章线性规划的对偶理论 与灵敏度分析 *§5灵敏度分析 *5.1目标函数中价值系数C的分析 *5.2资源系数b的分析 *5.3系数矩阵A的分析 分4种情况讨论系数矩阵的变化。 1.增加一个新变量的分析
第二章 线性规划的对偶理论 与灵敏度分析 §5 灵敏度分析 5.1 目标函数中价值系数C的分析 5.2 资源系数b的分析 5.3 系数矩阵A的分析 分4 种情况讨论系数矩阵的变化。 1.增加一个新变量的分析