运筹学 第2章 对偶理论和 (第三版) 灵敏度分析 《运筹学》教材编写组编 第7节 灵敏度分析 第8节 参数线性规 划 钱颂迪制作 清华大学出版社
（第三版） 《运筹学》教材编写组 编 清华大学出版社 运筹学 第2章 对偶理论和 灵敏度分析 第7节 灵敏度分析 第8节 参数线性规 划 钱颂迪 制作
第7节灵敏度分析 以前讨论线性规划问题时,假定α.,b,c都是常数 但实际上这些系数往往是估计值和预测 如市场条件一变,c1值就会变化;a,往往是因工艺条 件的改变而改变;b是根据资源投入后的经济效果决 定的一种决策选择。 因此提出这样两个问题: (1)当这些系数有一个或几个发生变化时,已求得的线性 规划问题的最优解会有什么变化; (2)或者这些系数在什么范围内变化时,线性规划问题的 最优解或最优基不变。后一个问题将在第8节参数线 性规划中讨论
第7节 灵敏度分析 • 以前讨论线性规划问题时，假定αij，bi ,cj都是常数。 但实际上这些系数往往是估计值和预测值。 • 如市场条件一变，cj值就会变化；αij往往是因工艺条 件的改变而改变；bi是根据资源投入后的经济效果决 定的一种决策选择。 • 因此提出这样两个问题： (1)当这些系数有一个或几个发生变化时，已求得的线性 规划问题的最优解会有什么变化； (2)或者这些系数在什么范围内变化时，线性规划问题的 最优解或最优基不变。后一个问题将在第8节参数线 性规划中讨论
线性规划问题中某一个或几个系数发生变化 显然,当线性规划问题中某一个或几个系数发 生变化后,原来已得结果一般会发生变化。当 然可以用单纯形法从头计算,以便得到新的最 优解。这样做很麻烦,而且也没有必要。因在 单纯形法迭代时,每次运算都和基变量的系数 矩阵B有关,因此可以把发生变化的个别系数, 经过一定计算后直接填入最终计算表中,并进 行检查和分析,可按表2-9中的几种情况进行 处理
线性规划问题中某一个或几个系数发生变化 • 显然，当线性规划问题中某一个或几个系数发 生变化后，原来已得结果一般会发生变化。当 然可以用单纯形法从头计算，以便得到新的最 优解。这样做很麻烦，而且也没有必要。因在 单纯形法迭代时，每次运算都和基变量的系数 矩阵B有关，因此可以把发生变化的个别系数， 经过一定计算后直接填入最终计算表中，并进 行检查和分析，可按表2-9中的几种情况 进行 处理
表29 原问题对偶问题结论或继续计算的步骤 可行解可行解表中的解仍为最优解 可行解 非可行解用单纯形法继续迭代求最优解 非可行解|可行解用对偶单纯形法继续迭代求最优解 非可行解|非可行解引进人工变量,编制新的单纯形表,求最优解 下面就各种情况分别按节进行讨论
表 2-9 原问题 对偶问题 结论或继续计算的步骤 可行解 可行解 表中的解仍为最优解 可行解 非可行解 用单纯形法继续迭代求最优解 非可行解 可行解用 对偶单纯形法继续迭代求最优解 非可行解 非可行解 引进人工变量，编制新的单纯形表，求最优解 下面就各种情况分别按节进行讨论
7.1资源数量变化的分析 资源数量变化是指资源中某系数b发生变化, 即b′=b+△b。并假设规划问题的其他系数 都不变。这样使最终表中原间题的解相应地变 化为 Xa′=B1(b+△b 这里△b=(0,…,△b,0,…,0)。只要Ⅹ≥0, 因最终表中检验数不变,故最优基不变,但最 优解的值发生了变化,所以XB′为新的最优解 新的最优解的值可允许变化范围用以下方法确 定
7.1 资源数量变化的分析 • 资源数量变化是指资源中某系数br发生变化， 即br ′=br +Δbr。并假设规划问题的其他系数 都不变。这样使最终表中原问题的解相应地变 化为 XB′=B-1(b+Δb) • 这里Δb=(0,…，Δbr ,0,…，0) T 。只要XB ′≥0， 因最终表中检验数不变，故最优基不变，但最 优解的值发生了变化，所以XB ′为新的最优解。 新的最优解的值可允许变化范围用以下方法确 定
B是最终计算表中的最优基的逆 B(b+△b)=Bb+B△b=Bb+B△b O 1△b air B△b a:△b △b a…△b
B-1 是最终计算表中的最优基的逆 = = + = + = + − − − − − − m r i r r r m r r i r r r r r r a a a b a b a b a b B b B b b B b B b B b B b 1 1 1 1 1 1 1 1 0 0 0 0 ( )
b列的元素变化 在最终表中求得的经过变化后的b列的所有元素, 要求b+ar△b≥0,i=1,2,…,m。由此可得 a1△b+≥-b,i=1,2,…,m 当ax>0时,Δb≥-b;/air; 当a10}≤△b≤mm<0
b列的元素变化 在最终表中求得的经过变化后的 b 列的所有元素， 要求b i+ a i rΔbr≥0，i=1,2,…,m。由此可得 a i rΔbr≥- b i，i=1,2，…，m 当a i r＞0 时，Δbr≥- b i/ a i r； 当a i r＜0 时，Δbr≤- b i/ a i r；于是得到 max 0 min i r 0 i r i i i r r i r i i a a b a b a b
例如求第1章例1中第二个约束条件b2的变化范围。 解:可以利用第1章例1的最终计算表中的数据: 02|83000 CE XB b XI X2 X3 XXs6 4 1/40 x40021/21 3x220112-1/80 Z 1400 /2|-1/80
例如求第1章例1中第二个约束条件b2的变化范围。 • 解：可以利用第1章例1的最终计算表中的数据： cj→ 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 θ 2 x1 4 1 0 1 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
01/400 可计算△Bb//+-21/21△b 2)(1/2-1/80人0 /4 0 =4+1/2b2≥0 1/8 0 由上式,可得 △b,≥-4/0.25=-16,△b2≥-4/0.5=-8,b≤2/0.125=16 所以△b2的变化范围是[8,16];显然原b=16,加它 的变化范围后,b2的变化范围是[8,32]
可计算Δb2： − + = − + − = + − − 0 0 0 1/ 8 1/ 2 1/ 4 2 4 4 0 0 1/ 2 1/8 0 2 1/ 2 1 0 1/ 4 0 2 4 4 0 0 2 2 2 1 1 b B b B b b 由上式，可得 Δb2≥-4/0.25=-16，Δb2≥-4/0.5=-8，b2≤2/0.125=16。 所以Δb2的变化范围是［-8，16］；显然原b2 =16，加它 的变化范围后， b2的变化范围是［8，32］
例7从表1-5得知第1章例1中,每设备台时的影子价 格为1.5元,若该厂又从其他处抽调4台时用于生产产 品I,Ⅱ。求这时该厂生产产品Ⅰ,Ⅱ的最优方案 C CB XB b XI X2 X3 X5 41|0 40 0 X5400 21/21 3 11/2-1/80 Z 1400|-3/2-1/80
例7 从表1-5得知第1章例1中，每设备台时的影子价 格为1.5元，若该厂又从其他处抽调4台时用于生产产 品Ⅰ，Ⅱ。求这时该厂生产产品Ⅰ，Ⅱ的最优方案。 cj→ 2 3 0 0 0 CB XB b x1 x2 x3 X4 x5 θ 2 x1 4 1 0 1 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