运筹学课件 灵敏度分析及参数规划

1、2021-10-20灵敏度分析与参数规划5-15 灵敏度分析与参数规划灵敏度分析与参数规划u 灵敏度分析灵敏度分析u 参数规划参数规划x2x1zo2021-10-20灵敏度分析与参数规划5-2概概 述述 在定义线性规划问题的数学模型时，假定在定义线性规划问题的数学模型时，假定 aij ， bi , , cj 都是常数，但实际上这些数据往往是估计值和预测值。都是常数，但实际上这些数据往往是估计值和预测值。如市场条件一变，如市场条件一变，cj 值就会变化；值就会变化；aij 往往因为工艺条件往往因为工艺条件的改变而改变；的改变而改变；bi 是根据资源投入后的经济效果决定的是根据资源投入后的经济效果

2、决定的一种决策选择。一种决策选择。 对数据资料可能的波动作进一步的研究和分析一般对数据资料可能的波动作进一步的研究和分析一般称之为称之为灵敏度分析灵敏度分析(sensitivity analysis)。 当有关数据的变化被看作是某个参数的函数时，这当有关数据的变化被看作是某个参数的函数时，这样的分析就是样的分析就是参数分析参数分析(parametric analysis)。2021-10-20灵敏度分析与参数规划5-35.1 灵敏度分析灵敏度分析 线性规划灵敏度分析的方法与一般经济计量线性规划灵敏度分析的方法与一般经济计量模型采用的方法有所不同，它的特点是在建立数模型采用的方法有所不同，它的特

3、点是在建立数学模型和求得最优解之后，再考察解对数据变化学模型和求得最优解之后，再考察解对数据变化的敏感程度。因此这种分析方法又称为的敏感程度。因此这种分析方法又称为优化后分优化后分析析(postoptimal analysis)。 线性规划问题中涉及的数据很多，决策者既线性规划问题中涉及的数据很多，决策者既希望知道个别数据变化的影响、还希望了解若干希望知道个别数据变化的影响、还希望了解若干数据同时发生变化所产生的后果。本节仅讨论前数据同时发生变化所产生的后果。本节仅讨论前一种情形。一种情形。2021-10-20灵敏度分析与参数规划5-4生产计划问题生产计划问题 cj23000CBXBbx1x2

4、x3x4x50 x381210040 x41640010-0 x512040013-1z023000j0 x321010-1/220 x4164001043x2301001/4-1z-92000-3/4j2x121010-1/2-0 x4800-41243x2301001/412-1z-1300-201/4j2x141001/400 x5400-21/213x22011/2-1/80-1z-1400-3/2 -1/80j max z=2x1+3x2 s.t. x1+2x2 8 4x1 16 4x2 12 x1 , x2 0 max z =2x1+3x2 s.t. x1+ 2x2 +x3 = 8

5、 4x1 +x4 = 16 4x2 +x5 = 12 x1, x2 , , x502021-10-20灵敏度分析与参数规划5-5灵敏度分析的意义灵敏度分析的意义 在生产计划问题的一般形式中，在生产计划问题的一般形式中，A 代表企业的技术状代表企业的技术状况，况，b 代表企业的资源状况，而代表企业的资源状况，而 C 代表企业产品的市场状代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。利润由线性规划的最优解和最优值决定。 在实际生产过程中，上述三类因素均是在不断变化的，在实际生产过程中，上述

6、三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓来不及随时对其变化作出反应，即所谓“计划不如变化计划不如变化快快”，企业应当预先了解，当各项因素变化时，应当作出，企业应当预先了解，当各

7、项因素变化时，应当作出什么样的反应。什么样的反应。2021-10-20灵敏度分析与参数规划5-6灵敏度分析的内容灵敏度分析的内容 本节将分析下列模型要素变化所产生的影响：本节将分析下列模型要素变化所产生的影响：n 模型数据发生变化模型数据发生变化F 目标函数系数目标函数系数(价值系数价值系数) cj F 右端常数右端常数(限定系数）限定系数）bi F 组成系数组成系数(工艺系数工艺系数) aij n 模型规模参数发生变化模型规模参数发生变化F 阶数阶数m，即约束条件有增减，即约束条件有增减F 维数维数n，即决策变量有增减，即决策变量有增减2021-10-20灵敏度分析与参数规划5-7灵敏度分析

8、的基础与依据灵敏度分析的基础与依据 灵敏度分析是在线性规划问题求解后进灵敏度分析是在线性规划问题求解后进行的，因此必有一个最优基行的，因此必有一个最优基 B及其最优解作及其最优解作为分析的基础。所以灵敏度分析就是检验一为分析的基础。所以灵敏度分析就是检验一 下要素改变后，当前解是否仍然满足下述两下要素改变后，当前解是否仍然满足下述两个条件：个条件： ( i ) 可行性条件可行性条件 B-1b 0 (ii ) 最优性条件最优性条件 CN - CBB-1N 02021-10-20灵敏度分析与参数规划5-8灵敏度分析的任务灵敏度分析的任务 线性规划的灵敏度分析要解决两个问题：线性规划的灵敏度分析要解

9、决两个问题：n一个或几个系数或要素变化后，当前的一个或几个系数或要素变化后，当前的最优解或最优基是否有变。最优解或最优基是否有变。n这些系数在什么范围内变动时，当前的这些系数在什么范围内变动时，当前的最优解或最优基不变。最优解或最优基不变。 另外，一旦当前解受影响就要运用适当另外，一旦当前解受影响就要运用适当方法对其进行调整，以便得到新的最优解。方法对其进行调整，以便得到新的最优解。2021-10-20灵敏度分析与参数规划5-9灵敏度分析的结果灵敏度分析的结果 通过灵敏度分析可以发现，系数或要素通过灵敏度分析可以发现，系数或要素变化后会对线性规划问题产生下列程度不同变化后会对线性规划问题产生下

10、列程度不同的影响：的影响：F 当前最优解不变；当前最优解不变；F 当前最优基不变；当前最优基不变；F 当前最优解变为可行解当前最优解变为可行解(可行性不变可行性不变)；F 当前最优解变为正则解当前最优解变为正则解(最优性不变最优性不变)；F 当前最优解变为非可行非正则解。当前最优解变为非可行非正则解。2021-10-20灵敏度分析与参数规划5-10分析结果的处理方法分析结果的处理方法 针对上述五种不同的分析结果，可按下列相针对上述五种不同的分析结果，可按下列相应的调整方法进行处理。应的调整方法进行处理。 分析结果分析结果 处理方法处理方法 最优解不变最优解不变 计算计算 CN - CBB-1N

11、 最优基不变最优基不变 计算计算 XB(*) = B-1b 变为可行解变为可行解 原始解法求最优解原始解法求最优解 变为正则解变为正则解 对偶解法求最优解对偶解法求最优解 变为普通解变为普通解 混合解法求最优解混合解法求最优解2021-10-20灵敏度分析与参数规划5-11灵敏度分析的算例灵敏度分析的算例生产计划问题生产计划问题 max z =2x1+3x2 s.t. x1+ 2x2 +x3 = 8 4x1 +x4 = 16 4x2 +x5 = 12 x1, x2 , , x50其中，其中， x1, x2 分别为产品分别为产品 P1, P2的产量，的产量， x3 , x4 , x5 分别分别为

12、原料为原料M1, M2 , M3的非生产的非生产用量。用量。 问题的初始表和求解后问题的初始表和求解后的最终表如下。以此为例作的最终表如下。以此为例作有关的灵敏度分析。有关的灵敏度分析。 表表 5.1 初始表和最终表初始表和最终表 cj23000CBXBbx1x2x3x4x50 x38121000 x416400100 x51204001-1z0230002x141001/400 x5400-21/213x22011/2-1/80-1z-1400-3/2-1/802021-10-20灵敏度分析与参数规划5-125.1.1 价值系数价值系数 cj 的变化分析的变化分析 价值系数变化是指目标函数系

13、数价值系数变化是指目标函数系数 cs 发生发生变化，即变化，即 cj= cj+ cj。 价值系数价值系数 cj 变化时，会使求解问题的变化时，会使求解问题的最终表里的相关检验数改变，解的性质也可最终表里的相关检验数改变，解的性质也可能因此改变。下面分别就能因此改变。下面分别就 cj 是非基变量还是是非基变量还是基变量的系数两种情况来讨论。基变量的系数两种情况来讨论。2021-10-20灵敏度分析与参数规划5-131. 非基变量系数非基变量系数 cs 的变化分析的变化分析 若若 cs 是非基变量是非基变量 xs 的系数，这时它在计算表的系数，这时它在计算表中所对应的检验数是中所对应的检验数是 s

14、 = cs - CBB-1Ps 当当 cs增加增加 cs后，要保证这个检验数仍小于或等于后，要保证这个检验数仍小于或等于零，即零，即 s = (cs+ cs ) - CBB-1Ps 0 那么那么(cs+ cs)CBB-1Ps，即，即 cs-(cs-CBB-1Ps)=- s。 综上所述，可以得出结论：综上所述，可以得出结论： 若若 cs- s ，则，则 s0，当前解仍是最优解；，当前解仍是最优解； 若若 cs - s ，则，则 s 0，当前解只是可行解。，当前解只是可行解。2021-10-20灵敏度分析与参数规划5-14非基变量系数非基变量系数cs变化的分析算例变化的分析算例 由上述讨论可知，生

15、产计由上述讨论可知，生产计划问题中变量划问题中变量 x3 和和 x4 的系数的系数 c3 和和c4 分别不大于分别不大于1.5和和0.125时，问题的最优解不变。时，问题的最优解不变。 经营问题经营问题：假若生产计划：假若生产计划问题中，原料问题中，原料 M1 既可用于生既可用于生产又可按单位利润为产又可按单位利润为2 的价格的价格直接出售，原料直接出售，原料 M2的单位储的单位储存费用为存费用为0.125，那么问题的，那么问题的目标函数变为目标函数变为 z =2x1+3x2+2x3 - 0.125 x4问题的最优解也随之改变。问题的最优解也随之改变。 cj23000CBXBbx1x2x3x4

16、x52x141001/400 x5400-21/213x22011/2-1/80-1z-1400-3/2-1/80 cj232-1/80CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2 -1/80-1z-14001/2-1/402x141001/400 x512040012x34021-1/40-1z-160-10-1/802021-10-20灵敏度分析与参数规划5-152. 基变量系数基变量系数 cr 的变化分析的变化分析 当基变量当基变量 xr 的系数的系数 cr ( CB)变化变化 cr 时，就会引起时，就会引起 CB的变化，从而影响到各非

17、基变量的变化，从而影响到各非基变量 xj 对应的对应的 j 。 设设 CB=( 0, , cr , ,0 )，若要求原最优解不变，则，若要求原最优解不变，则新的检验数必须满足新的检验数必须满足 j = cj - (CB + CB )B-1Pj = cj - CBB-1Pj - CB B-1Pj = j - (0, , cr , ,0)(b1j, , brj, , bmj)T = j - cr brj 0 于是得到于是得到 cr jbrj , brj 0 cr的变化范围为是的变化范围为是 max j /brj | brj 0 cr min j /brj | brj 0 cr min -bi0/b

18、ir | bir 0 2021-10-20灵敏度分析与参数规划5-18资源数量变化范围确定的算例资源数量变化范围确定的算例 cj23000CBXBbx1x2x3x4x50 x38121000 x416400100 x51204001-1z0230002x141001/400 x5400-21/213x22011/2-1/80-1z-1400-3/2 -1/80B-1b+B-1b=B-1b +B-1(b1,0,0)T 例如求例例如求例 5.1中第一个中第一个约束条件约束条件 b1的增量的增量 b1 的的取值范围时，按可行性条取值范围时，按可行性条件确定如右。由此可得件确定如右。由此可得 b1 -

19、( 4/-2 ) = 2 b1 -( 2/0.5)= -4 所以，所以， b1 的取值范围是的取值范围是 -4 , 2；相应地，；相应地，b1 的变的变化范围是化范围是 4 ,10。若取。若取 b1=2 B-1(b+ b)= ( 4, 0, 3 )T z* = 17。4= 4 +20-20.5b10002021-10-20灵敏度分析与参数规划5-19资源数量变化的分析算例资源数量变化的分析算例 在生产问题中，若该企在生产问题中，若该企业增加业增加 4 个单位的原料个单位的原料 M1 ，求这时的最优生产方案。求这时的最优生产方案。 计算计算将计算结果反映到最终表中，将计算结果反映到最终表中，见右

20、表。由于表中见右表。由于表中 b 列有负列有负数，用对偶解法求新的最优数，用对偶解法求新的最优解。从表中看出解。从表中看出 x3=2 ，即有，即有2个单位的个单位的 M1 未被利用。未被利用。 cj23000CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80-1z-1400-3/2-1/80 cj232-1/80CBXBbx1x2x3x4x52x14+01001/400 x54 -800-21/213x22+2011/2-1/80-1z-2000-3/2-1/802x141001/400 x32001-1/4 -1/23x2301001/

21、4-1z-17000-1/2-3/4 0 1/4 0 -2 1/2 1 1/2 -1/8 04000= -8 2B-1b =2021-10-20灵敏度分析与参数规划5-205.1.3 工艺系数的变化分析工艺系数的变化分析 关于工艺系数的变化分析可分为两种情况来关于工艺系数的变化分析可分为两种情况来讨论：一是单个系数讨论：一是单个系数aij的变化；一是某个系数列的变化；一是某个系数列向量向量Pj=(a1j , a2j , ,am j )T的改变。的改变。 另一方面，根据变化的另一方面，根据变化的 aij 或改变的或改变的 Pj 是否处是否处在基在基 B 中又需分别考虑。中又需分别考虑。aij 或

22、或 Pj不在基不在基 B 中时，中时，它的改变不会影响到当前解它的改变不会影响到当前解 XB(*) = B-1b0 的可行的可行性，只可能影响到当前解的最优性；反之，当前性，只可能影响到当前解的最优性；反之，当前解的可行性和最优性都可能受到影响。解的可行性和最优性都可能受到影响。 鉴于两个方面的前一种情况都比较简单，本鉴于两个方面的前一种情况都比较简单，本节不予讨论。对于后一种情况也不作一般性讨论，节不予讨论。对于后一种情况也不作一般性讨论，仅以具体例子来说明。仅以具体例子来说明。2021-10-20灵敏度分析与参数规划5-21工艺系数列向量变化的分析算例工艺系数列向量变化的分析算例 cj23

23、000CBXBbx1x2x3x4x52x141000.2500 x5400-20.513x22010.5-0.1250-1z-1400-3/2-1/80 x141000.250 x5402-20.51x2200.750.5-0.1250-1z-1400.75-1.5-0.12502x141000.2500 x5-1.33300-3.333 0.83313x22.667010.667 -0.1670-1z-1600-2-0.2502x141000.2500 x30.4001-0.25-0.33x22.401000.2-1z-15.2000-0.75-0.6 在生产问题中产品在生产问题中产品P2的

24、工的工艺系数向量由艺系数向量由P2=(2,0,4)T变为变为P2=(1.5, 0, 5)T, ,试分析对原最试分析对原最优计划的影响优计划的影响.设改进后的产设改进后的产品产量为品产量为 x2,计算计算 x2 在最终在最终表中对应的列向量和检验数表中对应的列向量和检验数. 0 1/4 0-2 1/2 1 1/2 -1/8 03/2050 = 2 3/4B-1P2 = 2 = c2 - CBB-1P2 = 3-(1.5, 0.125, 0)(1.5, 0, 5)T = 3 - 2.25 = 0.752021-10-20灵敏度分析与参数规划5-22工艺系数和价值系数变化的分析算例工艺系数和价值系数

25、变化的分析算例 若工艺系数列向量和相若工艺系数列向量和相应的价值系数应的价值系数 P1= (1, 4, 0)T ， c1=2 变化为变化为 P1= (2, 5, 2)T ， c1= 4 计算计算 cj23000CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80-1z-1400-3/2 -1/80 cj43000CBXBbx1x2x3x4x5x145/4001/40 x541/20-21/21x223/811/2-1/80-1z-143/80-3/2 -1/804x13.21000.200 x52.400-20.413x30.8010.5-

26、0.20-1z-15.200-1.5-0.20 0 1/4 0-2 1/2 1 1/2 -1/8 02525/4 = 1/2 3/8B-1P1 = 1= c1 - CBB-1P1 = 4 - (1.5, 0.125, 0)(2, 5, 2)T = 4 - 3.625 = 0.3752021-10-20灵敏度分析与参数规划5-23运用混合算法调整当前解运用混合算法调整当前解 若工艺系数列向量若工艺系数列向量和相应的价值系数和相应的价值系数 P1= (1,4,0)T ， c1=2 变化为变化为 P1=(4,5,2)T ， c1=4 计算计算1.25 = -3.5 1.375B-1P1 1= c1

27、- CBB-1P1 = -2.625 cj43000CBXBbx1x2x3x4x52x141.25000.2500 x54-3.50-20.513x221.37510.5-0.1250-1z-14-2.6250-3/2-1/80j4x13.21000.20160 x515.200-21.2138/33x2-2.4011/2-0.406-1z-5.600-1.50.40j4x1210.50.250040 x5803-0.5018/30 x460-2.5 -1.2510-1z-801-100j4x10.667100.330-0.333x22.66701-0.16700.330 x412.66700

28、1.66710.83-1z-10.6700-0.830-0.33j2021-10-20灵敏度分析与参数规划5-245.1.4 决策变量增减的分析决策变量增减的分析 若企业在计划期内，有新的产品可以生产，若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前可以在最优表中补充一列，其中的前m行可以由行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种最优解仍为