灵敏度分析(第三章线性规划4)课件.ppt

1、一一、灵敏度分析概述灵敏度分析概述 Max f=CXAX=bX 0 0 系数矩阵系数矩阵A、约束条件右端项、约束条件右端项b和价值系数和价值系数C给定以后，这个线性规划问题就确定了。给定以后，这个线性规划问题就确定了。1.当这些系数中的一个或几个发生变化时，已求得的最优解当这些系数中的一个或几个发生变化时，已求得的最优解 会有什么变化；会有什么变化；2.这些系数在什么范围内变化时，线性规划问题的最优解或这些系数在什么范围内变化时，线性规划问题的最优解或 最优基不变；最优基不变；3.若最优解变化，如何用最简便的方法找到新的最优解。若最优解变化，如何用最简便的方法找到新的最优解。为了回答这些问题，

2、可以在变化了的条件下重新求解为了回答这些问题，可以在变化了的条件下重新求解线性规划问题。但是这样做太麻烦，也不必要。本节的目线性规划问题。但是这样做太麻烦，也不必要。本节的目的是讲，的是讲，如何在已经得到的最优解的基础上，进行适当的如何在已经得到的最优解的基础上，进行适当的修改计算，即可回答上面的问题。修改计算，即可回答上面的问题。这就是灵敏度分析的基这就是灵敏度分析的基本内容。本内容。二、灵敏度分析的定义二、灵敏度分析的定义灵敏度分析灵敏度分析就是研究就是研究cj、bi、aij等参数在等参数在什么范围内变化时最优解不变，若最优什么范围内变化时最优解不变，若最优解发生变化，如何用简便的方法求出

3、新解发生变化，如何用简便的方法求出新的最优解。的最优解。三、灵敏度分析的内容三、灵敏度分析的内容v价值系数价值系数cj的变化的分析的变化的分析v约束条件右端项约束条件右端项bi变化的分析变化的分析v系数矩阵系数矩阵A变化变化的分析的分析 系数列向量系数列向量P Pk k变化的分析变化的分析 增加新约束条件的分析增加新约束条件的分析 增加新变量的分析增加新变量的分析 实例实例1 1产品资源ABC资源拥有量原料甲11112kg原料乙12220kg利润（元/kg）586实例实例1 1的数学模型的数学模型max,fxxxxxxxxxx xx5861222200123123123123设产品设产品A A

4、、B B、C C 的产量分别为的产量分别为x1、x2、x3，则该问题的数学模型为则该问题的数学模型为：用单纯形法求解结果用单纯形法求解结果最优单纯形表最优单纯形表 x1 x2 x3 x4 x5 bi x1 1 0 0 2 1 4 x2 0 1 1 1 1 8 f 0 0 2 2 3 84 初始单纯形表初始单纯形表 x1 x2 x3 x4 x5 bi x4 1 1 1 1 0 12 x5 1 2 2 0 1 20 f 5 8 6 0 0 0 1.1.价值系数价值系数cj变化变化的分析的分析c cj j 变动可能由于市场价格的波动，或生产成本的变动变动可能由于市场价格的波动，或生产成本的变动。c

5、cj j 的灵敏度分析是在保证最优解的基变量不变的情况下，的灵敏度分析是在保证最优解的基变量不变的情况下，分析分析c cj j 允许的变动范围。允许的变动范围。c cj j 的变化会引起检验数的变化，有两种情况的变化会引起检验数的变化，有两种情况：非基变量对应的价值系数变化，不影响其它检验非基变量对应的价值系数变化，不影响其它检验数数基变量对应的价值系数变化，影响所有非基变量检验基变量对应的价值系数变化，影响所有非基变量检验数数1.1非基变量非基变量 对应的价值系数对应的价值系数c c3 3的变化的变化在实例在实例1 1中，分析产品丙的利润中，分析产品丙的利润C3的的变化对最优解的变化对最优解

6、的影响影响。x1 x2 x3 x4 x5 bi x1 1 0 0 2 1 4 x2 0 1 1 1 1 8 f 0 0 2 2 3 84 由上表可知：当由上表可知：当C3-8 0，即即 0 C38时，最优解不变。时，最优解不变。3x5 8 6 0 058C3C3-81.2基变量对应价值系数变化基变量对应价值系数变化(1)(1)基变量对应的价值系数基变量对应的价值系数C C1 1的的变化变化5 8 6 0 058C1C1-2 8-2C1 C1-8 -(64+4C1)由上表可知：当由上表可知：当 8-2C1 0，同时同时 C1-8 0，即即 4 C18时，最优解不变。时，最优解不变。(2)基变量对

7、应的价值系数基变量对应的价值系数C2的的变化变化5 8 6 0 058C2C26-C2 C2-10 5-C2 -(20+8C2)由上表可知：当由上表可知：当 6-C2 0，C2-10 0，同时同时 5-C2 0，即即 6 C210时，最优解不变。时，最优解不变。价值系数价值系数cj变化变化的分析总结的分析总结c cj j 的变化会引起检验数的变化，有两种情况的变化会引起检验数的变化，有两种情况：（1 1）非基变量对应的价值系数变化，不影响其它检验数）非基变量对应的价值系数变化，不影响其它检验数（2 2）基变量对应的价值系数变化，影响所有非基变量检）基变量对应的价值系数变化，影响所有非基变量检

8、验数。验数。要使原来的最优解不变，新的检验数均要使原来的最优解不变，新的检验数均02.2.约束条件右端项约束条件右端项bi变化变化的分析的分析(1)(1)设设XB=B 1b是最优解，则有是最优解，则有XB=B 1b 0b的变化不会影响检验数的变化不会影响检验数b的变化量的变化量 b可能导致原最优解变为非基可行解可能导致原最优解变为非基可行解设设b=b+b为保证最优基不变，必须满足为保证最优基不变，必须满足XB=B-1b 0最优单纯形表最优单纯形表 x1 x2 x3 x4 x5 bi x1 1 0 0 2 1 4 x2 0 1 1 1 1 8 f 0 0 2 2 3 84 初始单纯形表初始单纯形

9、表 x1 x2 x3 x4 x5 bi x4 1 1 1 1 0 12 x5 1 2 2 0 1 20 f 5 8 6 0 0 0 1620124-921.分析分析b1=16和和b2=20时，最优基和最优解的变化时，最优基和最优解的变化当当b b1 1=16,b=16,b2 2=20=20时，时，最优基不变，最优基不变，最优解变为：最优解变为：x1=12，x2=4结论结论最优单纯形表最优单纯形表 x1 x2 x3 x4 x5 bi x1 1 0 0 2 1 4 x2 0 1 1 1 1 8 f 0 0 2 2 3 84 初始单纯形表初始单纯形表 x1 x2 x3 x4 x5 bi x4 1 1

10、 1 1 0 12 x5 1 2 2 0 1 20 f 5 8 6 0 0 0 222024-22.分析分析b1=22和和b2=20时，最优基和最优解的变化时，最优基和最优解的变化5800-104 x1 x2 x3 x4 x5 B-1b x1 1 0 0 2 1 24 x2 0 1 1 1 1-2 f 0 0 2 2 3-104 最优单纯形表最优单纯形表 x1 x2 x3 x4 x5 B-1b x1 1 2 2 0 1 20 x4 0-1-1 1-1 2-f 0-2-4 0-5-100 当当b1=22,b2=20时，时，最优基改变，最优解变为：最优基改变，最优解变为：x1=20，x4=2结论结

11、论0202022011121111bbbbB解之得解之得：1010b b1 12020即即:当当10b10b1 12020时，最优基不变时，最优基不变保持保持b2=20,分析分析b1在什么范围内在什么范围内变化时，最优基不变变化时，最优基不变?最优单纯形表最优单纯形表 x1 x2 x3 x4 x5 bi x1 1 0 0 2 1 4 x2 0 1 1 1 1 8 f 0 0 2 2 3 84 初始单纯形表初始单纯形表 x1 x2 x3 x4 x5 bi x4 1 1 1 1 0 12 x5 1 2 2 0 1 20 f 5 8 6 0 0 0 b1202b1-20-b1+20?58000122

12、41211122221bbbbB解之得解之得：1212b b2 22424即即:当当12b12b2 22424时，最优基不变时，最优基不变保持保持b1=12,分析分析b2在什么范围内在什么范围内变化时，最优基不变变化时，最优基不变?最优单纯形表最优单纯形表 x1 x2 x3 x4 x5 bi x1 1 0 0 2 1 4 x2 0 1 1 1 1 8 f 0 0 2 2 3 84 初始单纯形表初始单纯形表 x1 x2 x3 x4 x5 bi x4 1 1 1 1 0 12 x5 1 2 2 0 1 20 f 5 8 6 0 0 0 12b224-b2-12+b2?5800练习练习0,65232

13、5max32123211321321xxxbxxxbxxxxxxf最优单纯形表为：最优单纯形表为：求：求：n（1）b1、b2的值；的值；n（2）对偶问题的最优解；）对偶问题的最优解；n（3）表中）表中f、g、h、d、e的值；的值；n（4）在不破坏最优基的情况下，）在不破坏最优基的情况下，能否单独增加能否单独增加b1、b2来增加目标函来增加目标函数数f的值，最多能增加到多少？的值，最多能增加到多少？3.3.系数矩阵系数矩阵A A变化的分析变化的分析系数矩阵系数矩阵A变化变化的分析包括的分析包括 系数列向量系数列向量P Pk k变化的分析变化的分析 增加新约束条件的分析增加新约束条件的分析 增加新

14、变量的分析增加新变量的分析3.1系数列向量Pk变化的分析在初始单纯形表上，变量在初始单纯形表上，变量xk的系数列向量的系数列向量P Pk k变为变为P Pk k，经，经过迭代后，在最终单纯形表上，过迭代后，在最终单纯形表上，xk是非基变量。这时最是非基变量。这时最终单纯形表上终单纯形表上xk的系数列就变成的系数列就变成B B-1-1 P Pk k。新的判别数为。新的判别数为1kBkkPBCC若若 ，原最优解不变原最优解不变；若若 ，则最优解改变，继续迭代可以求出新的最则最优解改变，继续迭代可以求出新的最优解。优解。0k0k实例实例1 1产品资源ABC资源拥有量原料甲11112kg原料乙1222

15、0kg利润（元/kg）586在实例在实例1 1中，假设产品中，假设产品C C 的资源消耗量由的资源消耗量由 变为变为 ，试分析最优解的变化情况。试分析最优解的变化情况。2112所有的判别数都非正，故最优解不变所有的判别数都非正，故最优解不变。213-1 5 8 6 0 058-1在实例在实例1 1中，假设产品中，假设产品C C 的资源消耗量由的资源消耗量由 变为变为 ，试分析最优解的变化情况。试分析最优解的变化情况。2111判别数有正，故最优解变化判别数有正，故最优解变化。1110 5 8 6 0 0581初始表初始表最优表最优表最优单纯形表如下：最优单纯形表如下：3.23.2 增加新约束条件

16、的分析增加新约束条件的分析产品产品资源资源ABC资源拥有资源拥有量量原料甲原料甲11112kg原料乙原料乙12220kg原料丙原料丙12218kg利润利润（元（元/kg）586用单纯形法求解结果用单纯形法求解结果 将原最优解将原最优解x1=4，x2=8代入上式知，原最优解不满足该约代入上式知，原最优解不满足该约束条件，因而原最优解不再是增加约束条件以后的最优解。束条件，因而原最优解不再是增加约束条件以后的最优解。1822321xxx18226321xxxx这个问题相当于在原问题的基础上增加约束条件这个问题相当于在原问题的基础上增加约束条件 在新的约束条件中引入松驰变量在新的约束条件中引入松驰变

17、量x6，则有则有将该条件填入最优单纯形表中将该条件填入最优单纯形表中：x1 x2 x3 x4 x5 x6 B-1b x1 1 0 0 2-1 0 4 x2 0 1 1-1 1 0 8 x6 0 0 0 0-1 1-2-f 0 0-2-2-3 0-84 将该单纯形表标准化将该单纯形表标准化：18226321xxxx将将 填入最优单纯形表中填入最优单纯形表中6x6x 1 2 2 0 0 1 18000用对偶单纯形方法迭代一次得用对偶单纯形方法迭代一次得：x1 x2 x3 x4 x5 x6 B-1b x1 1 0 0 2 0-1 6 x2 0 1 1-1 0 1 6 x5 0 0 0 0 1-1 2

18、-f 0 0-2-2 0-3-78 增加约束条件以后的最优解为：x1=6，x2=6增加新约束条件的分析总结增加新约束条件的分析总结1、将最优解代入新的约束条件，若满足，则最优解不变。、将最优解代入新的约束条件，若满足，则最优解不变。2 2、若不满足，则当前最优解要发生变化；将新增约束条、若不满足，则当前最优解要发生变化；将新增约束条 件加入最优单纯形表，并变换为标准型。件加入最优单纯形表，并变换为标准型。3 3、利用对偶单纯形法继续迭代。、利用对偶单纯形法继续迭代。为什么可以利用对偶单纯形法为什么可以利用对偶单纯形法?3.33.3增加新的决策变量的分析增加新的决策变量的分析假如要增加一个新的决

19、策变量假如要增加一个新的决策变量xn+1，其对应的系数列向量为其对应的系数列向量为Pn+1，价值系数为价值系数为cn+1。在原最优单纯形表中在原最优单纯形表中xn+1对应的检验对应的检验数为数为1111nBnnpBCc若若 ，则原最优解不变则原最优解不变。从经济学的观点来看，增加该从经济学的观点来看，增加该项活动（或产品）是不利的。项活动（或产品）是不利的。01n 若若 ，则原来的最优解不再是最优解则原来的最优解不再是最优解，表明增加该活动是表明增加该活动是有利的有利的。n10这时把这时把xn+1对应于原最优基对应于原最优基B B的系数列向量的系数列向量 加入到加入到原最优表中，并以原最优表中

20、，并以xn+1作为换入变量按单纯形法进行迭代，作为换入变量按单纯形法进行迭代，即可得到新的最优解。即可得到新的最优解。11/1nnpBP产品产品资源资源ABCD资源拥资源拥有量有量原料甲原料甲111212kg原料乙原料乙122120kg利润利润（元（元/kg）5868在实例在实例1 1中，如果该厂还计划生产一种中，如果该厂还计划生产一种新产品新产品D D，问生产产品，问生产产品D D是否有利是否有利？用单纯形法求解结果用单纯形法求解结果初始表初始表原最优原最优表变成表变成 5 8 6 0 0 8583-11 x1 x2 x3 x4 x5 x6 bi x6 1/3 0 0 2/3 1/3 1 4

21、/3 x2 1/3 1 1 1/3 2/3 0 28/3 f 1/3 0 2 8/3 8/3 0 85.33 新的最优解为新的最优解为X=(0 28/3 0 0 0 4/3)T继续迭代，找到新的最优解继续迭代，找到新的最优解课后习题课后习题36(1、2)最优单纯形表：最优单纯形表：3 1 4 0 0 04C1 C1-24/5 课后习题课后习题36(3)最优单纯形表：最优单纯形表：3 1 4 0 0 30462/57/5课后习题课后习题37最优单纯形表最优单纯形表：10 6 4 0 0 06100C3C3-20/3课后习题课后习题37（续）（续）最优单纯形表最优单纯形表：10 6 4 0 0 0

22、610025/35/3课后习题课后习题37(续）续）10 6 4 0 0 061000 x7 O 0 -1 0 0 0 1 -10 X70000课后习题课后习题37(续）续）10 6 4 0 0 0 061004作业作业n线性规划问题线性规划问题n maxf=2X1+3X2+X3n X1+X2+X33n X1+3X2+5X37n X1，X2,X20n（1）用单纯形方法求出最优解和最优目标函数值；）用单纯形方法求出最优解和最优目标函数值；n（2）写出上述问题的对偶问题，并求对偶规划的最优解和最）写出上述问题的对偶问题，并求对偶规划的最优解和最优目标函数值；优目标函数值；n（3）保持）保持X1的系数的系数C1=2，X3的系数的系数C3=1不变，确定不变，确定X2的的n系数系数C2的变化范围，使原最优解保持最优；的变化范围，使原最优解保持最优；n（4）求出要使原来的最优基不变的）求出要使原来的最优基不变的b1的变化范围，的变化范围，n（5）若）若b13，b2=11，求出新的最优解。，求出新的最优解。