灵敏度分析(第三章线性规划)

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

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

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

4、xxxxxxx xx5861222200123123123123设产品设产品A A、B B、C C 的产量分别为的产量分别为x1、x2、x3，则该问题的数学模型为则该问题的数学模型为：编辑ppt7用单纯形法求解结果用单纯形法求解结果最优单纯形表最优单纯形表 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 编辑ppt81.1.价值系数价值系数cj变化变化的分析的分析c

5、 cj j 变动可能由于市场价格的波动，或生产成本的变动变动可能由于市场价格的波动，或生产成本的变动。c cj j 的灵敏度分析是在保证最优解的基变量不变的情况下，的灵敏度分析是在保证最优解的基变量不变的情况下，分析分析c cj j 允许的变动范围。允许的变动范围。c cj j 的变化会引起检验数的变化，有两种情况的变化会引起检验数的变化，有两种情况：非基变量对应的价值系数变化，不影响其它检验非基变量对应的价值系数变化，不影响其它检验数数基变量对应的价值系数变化，影响所有非基变量检验基变量对应的价值系数变化，影响所有非基变量检验数数编辑ppt91.1非基变量非基变量 对应的价值系数对应的价值系

6、数c c3 3的变化的变化在实例在实例1 1中，分析产品丙的利润中，分析产品丙的利润C3的的变化对最优解的变化对最优解的影响影响。 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-8编辑ppt101.2基变量对应价值系数变化基变量对应价值系数变化(1)(1)基变量对应的价值系数基变量对应的价值系数C C1 1的的变化变化5 8 6 0 058C1C1-2 8-2C1 C1-8 -(64+4C

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

8、应的价值系数变化，不影响其它检验数）非基变量对应的价值系数变化，不影响其它检验数（2 2）基变量对应的价值系数变化，影响所有非基变量检）基变量对应的价值系数变化，影响所有非基变量检 验数。验数。要使原来的最优解不变，新的检验数均要使原来的最优解不变，新的检验数均0编辑ppt132.2.约束条件右端项约束条件右端项bi变化变化的分析的分析(1)(1)设设XB=B 1b是最优解，则有是最优解，则有XB=B 1b 0b的变化不会影响检验数的变化不会影响检验数b的变化量的变化量 b可能导致原最优解变为非基可行解可能导致原最优解变为非基可行解设设b=b+ b为保证最优基不变，必须满足为保证最优基不变，必

9、须满足XB=B-1b 0编辑ppt14最优单纯形表最优单纯形表 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 1620124-921. 分析分析b1=16和和b2=20时，最优基和最优解的变化时，最优基和最优解的变化编辑ppt15当当b b1 1=16,b=16,b2 2=20=20时，时，最优基不变，最优基不变，最优解变为：最优解变为：x1=12，x2=4结论结

10、论编辑ppt16最优单纯形表最优单纯形表 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 222024-22. 分析分析b1=22和和b2=20时，最优基和最优解的变化时，最优基和最优解的变化5800-104编辑ppt17 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 最优单

11、纯形表最优单纯形表 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 编辑ppt18当当b1=22,b2=20时，时，最优基改变，最优解变为：最优基改变，最优解变为：x1=20，x4=2结论结论编辑ppt190202022011121111bbbbB解之得：解之得：1010b b1 12020即即: :当当10b10b1 12020时，最优基不变时，最优基不变保持保持b2=20,分析分析b1在什么范围内在什么范围内变化时，最优基不变变化时，最优基不变?编辑ppt20最优单纯形表最优单纯形表 x1

12、 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?5800编辑ppt21012241211122221bbbbB解之得：解之得：1212b b2 22424即即: :当当12b12b2 22424时，最优基不变时，最优基不变保持保持b1=12,分析分析b2在什么范围内在什么范围内变化时，最优基不变变化时，最优基不变?编辑ppt22最优单纯

13、形表最优单纯形表 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编辑ppt23练习练习0,652325max32123211321321xxxbxxxbxxxxxxf最优单纯形表为：最优单纯形表为：求：求：n（1）b1、b2的值；的值；n（2）对偶问题的最优解；）对偶问题的最优解；n（3）表中）表中f、g、h、d、e的值；的

14、值；n（4）在不破坏最优基的情况下，）在不破坏最优基的情况下，能否单独增加能否单独增加b1、b2来增加目标函来增加目标函数数f的值，最多能增加到多少？的值，最多能增加到多少？编辑ppt243.3.系数矩阵系数矩阵A A变化的分析变化的分析系数矩阵系数矩阵A变化变化的分析包括的分析包括 系数列向量系数列向量P Pk k变化的分析变化的分析 增加新约束条件的分析增加新约束条件的分析 增加新变量的分析增加新变量的分析编辑ppt253.1系数列向量Pk变化的分析在初始单纯形表上，变量在初始单纯形表上，变量xk的系数列向量的系数列向量P Pk k变为变为P Pk k，经，经过迭代后，在最终单纯形表上，过

15、迭代后，在最终单纯形表上， xk是非基变量。这时最是非基变量。这时最终单纯形表上终单纯形表上xk的系数列就变成的系数列就变成B B-1 -1 P Pk k。新的判别数为。新的判别数为1kBkkPBCC若若 ，原最优解不变；，原最优解不变；若若 ，则最优解改变，继续迭代可以求出新的最，则最优解改变，继续迭代可以求出新的最优解。优解。0k0k编辑ppt26实例实例1 1产品资源ABC资源拥有量原料甲11112kg原料乙12220kg利润（元/kg）586编辑ppt27在实例在实例1 1中，假设产品中，假设产品C C 的资源消耗量由的资源消耗量由 变为变为 ，试分析最优解的变化情况。试分析最优解的变

16、化情况。2112所有的判别数都非正，故最优解不变所有的判别数都非正，故最优解不变。213-1 5 8 6 0 058-1编辑ppt28在实例在实例1 1中，假设产品中，假设产品C C 的资源消耗量由的资源消耗量由 变为变为 ，试分析最优解的变化情况。试分析最优解的变化情况。2111判别数有正，故最优解变化判别数有正，故最优解变化。1110 5 8 6 0 0581初始表初始表最优表最优表编辑ppt29最优单纯形表如下：最优单纯形表如下：编辑ppt303.23.2 增加新约束条件的分析增加新约束条件的分析产品产品资源资源ABC资源拥有资源拥有量量原料甲原料甲11112kg原料乙原料乙12220k

17、g原料丙原料丙12218kg利润利润（元（元/kg）586编辑ppt31用单纯形法求解结果用单纯形法求解结果编辑ppt32 将原最优解将原最优解x1=4，x2=8代入上式知，原最优解不满足该约代入上式知，原最优解不满足该约束条件，因而原最优解不再是增加约束条件以后的最优解。束条件，因而原最优解不再是增加约束条件以后的最优解。 1822321xxx18226321xxxx这个问题相当于在原问题的基础上增加约束条件这个问题相当于在原问题的基础上增加约束条件 在新的约束条件中引入松驰变量在新的约束条件中引入松驰变量x6，则有，则有将该条件填入最优单纯形表中：将该条件填入最优单纯形表中：编辑ppt33

18、 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编辑ppt34用对偶单纯形方法迭代一次得：用对偶单纯形方法迭代一次得： 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 -f 0 0 -2 -2

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

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

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