运筹学教学资料运筹学第2章第7节.ppt

《运筹学教学资料运筹学第2章第7节.ppt》由会员分享，可在线阅读，更多相关《运筹学教学资料运筹学第2章第7节.ppt（37页珍藏版）》请在优知文库上搜索。

1、-1-运筹学-2-运筹学 灵敏度分析灵敏度分析=对于市场的变化，我们的决策究竟怎样变化对于市场的变化，我们的决策究竟怎样变化 （不需要将它当成一个新问题）（不需要将它当成一个新问题）灵敏度分析的重要性在于：灵敏度分析的重要性在于：1.向决策者提供线性规划问题的最优解所能适应的环境向决策者提供线性规划问题的最优解所能适应的环境条件变化的范围；条件变化的范围；2.环境条件变化时可能对经营状况带来何种影响；环境条件变化时可能对经营状况带来何种影响；3.产生影响后的解决途径。产生影响后的解决途径。灵敏度分析灵敏度分析-3-运筹学 灵敏度分析的类型：灵敏度分析的类型：1.模型中各个参数在什么范围变化时，

2、最优基不发生改变。模型中各个参数在什么范围变化时，最优基不发生改变。2.模型中参数变化已经超出上述范围时，如何快速确定新的最模型中参数变化已经超出上述范围时，如何快速确定新的最优基和最优解优基和最优解新的最优决策方案。新的最优决策方案。模型中参数变化主要指：模型中参数变化主要指：1.目标函数的系数变化；目标函数的系数变化；2.约束条件右边的值变化；约束条件右边的值变化；3.约束条件中约束条件中aij 的变化；的变化；4.可决策变量增减的变化；可决策变量增减的变化；5.约束条件增减的变化。约束条件增减的变化。灵敏度分析灵敏度分析-4-运筹学 灵敏度分析的任务：灵敏度分析的任务：1.当系数当系数A

3、、b、C中的某个发生变化时中的某个发生变化时,目前的最优基是否仍目前的最优基是否仍最优（即目前的最优生产方案是否要变化）最优（即目前的最优生产方案是否要变化）?(称为模型参数的称为模型参数的灵敏度分析灵敏度分析)2.增加一个变量或增加一个约束条件时，目前的最优基是否仍增加一个变量或增加一个约束条件时，目前的最优基是否仍最优（即目前的最优生产方案是否要变化）？最优（即目前的最优生产方案是否要变化）？(称为模型结构称为模型结构的灵敏度分析的灵敏度分析)灵敏度分析灵敏度分析-5-运筹学 线性规划问题线性规划问题 I 表与表与 B 表的关系表的关系对给定符合典式的线性规划问题中，初始基矩阵为对给定符合

4、典式的线性规划问题中，初始基矩阵为 I，基变量为，基变量为 XS，即松，即松弛变量。其对应的初始单纯形表如下：弛变量。其对应的初始单纯形表如下：I 表（初始表）表（初始表）对初始单纯形表进行迭代之后得到对初始单纯形表进行迭代之后得到 B 为最优基矩阵，最终典式所对应的单为最优基矩阵，最终典式所对应的单纯形表：纯形表：B 表（最终表）表（最终表）基基解解 X XS XSb A I j C 0 基基解解 XB XN XS XBB-1b I B-1N B-1 j 0 CN CB B-1N -CB B-1 灵敏度分析灵敏度分析-6-运筹学 原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算

5、的步骤可行解可行解可行解可行解非可行解非可行解非可行解非可行解可行解可行解非可行解非可行解可行解可行解非可行解非可行解问题的最优解或最优基不变问题的最优解或最优基不变可以用单纯形法继续迭代求最优解可以用单纯形法继续迭代求最优解可以用对偶单纯形法继续迭代求最优解可以用对偶单纯形法继续迭代求最优解引进人工变量，编制新的单纯形表重新计算引进人工变量，编制新的单纯形表重新计算线性规划原问题单纯形法对应的线性规划原问题单纯形法对应的 I 表表中参数的变化将引起中参数的变化将引起B 表表中对应中对应参数的变化情况如下：参数的变化情况如下：灵敏度分析灵敏度分析基基解解X XS XSbA I j C 0 基基

6、解解XB XN XS XBB-1b I B-1N B-1 j 0 CN CB B-1N -CB B-1 I 表（初始表）表（初始表）B 表（最终表）表（最终表）-7-运筹学 灵敏度分析的方法：灵敏度分析的方法：灵敏度分析方法的关键是从单纯形法对应的灵敏度分析方法的关键是从单纯形法对应的 I 表表中参中参数的变化来分析数的变化来分析B 表表中对应参数的变化情况来回答决策者中对应参数的变化情况来回答决策者所关心问题。所关心问题。灵敏度分析的方法是在目前最优基灵敏度分析的方法是在目前最优基B下进行的。即当下进行的。即当参数参数A、b、c中的某一个或几个发生变化时，考察是否影中的某一个或几个发生变化时

7、，考察是否影响以下两式的成立？响以下两式的成立？0011ABCCbBB灵敏度分析灵敏度分析-8-运筹学 1.对于参数对于参数b的灵敏度分析的灵敏度分析基基解解 XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB-1b I B-1N B-1 j 0 CN CB B-1 -CB B-1I 表表B 表表当当I 表中表中b变化为变化为b时，在时，在B 表中将只有解列表中将只有解列 B-1b发生变化。发生变化。灵敏度分析灵敏度分析-9-运筹学 bXXBB-1bB-1AZC BB-1bC-C BB-1Ab变化的时候，仅对变化的时候，仅对B-1b有影响有影响仅关心仅关

8、心B-1b0?若新的若新的B-1b不满足不满足0，最优基发生，最优基发生变化，此时需用对偶单纯形法进行变化，此时需用对偶单纯形法进行计算，调整可行性可能计算，调整可行性可能当当B-1b0时，最优基不变（即时，最优基不变（即生产产品的品种不变，但数量生产产品的品种不变，但数量及最优值会变化），此时可以及最优值会变化），此时可以简单求出新最优解。简单求出新最优解。所以，所以，b的变化只影响最优解的变化和最优值的变化。的变化只影响最优解的变化和最优值的变化。灵敏度分析灵敏度分析-10-运筹学 若若B-1b0，其，其是一个不等式组，从中可以解得是一个不等式组，从中可以解得b的变化范围的变化范围（此时，

9、需保证当前最优基变化后仍为最优基）（此时，需保证当前最优基变化后仍为最优基）若若B-1b中有小于中有小于0的分量，则需用对偶单纯形法迭代，以求出的分量，则需用对偶单纯形法迭代，以求出新的最优方案新的最优方案。（此时，基变量不变，因为（此时，基变量不变，因为基变量只需要相应的基变量只需要相应的B可可逆就可以了逆就可以了）bXXBB-1bB-1AZC BB-1bC-C BB-1A 0011ABCCbBB灵敏度分析灵敏度分析-11-运筹学 I 表表Cj21000CB基基解解X1X2X3X4X50X315051000X424620100X5511001检验数检验数 j21000B 表表Cj21000C

10、B基基解解X1X2X3X4X50X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2检验数检验数 j000-1/4-1/2灵敏度分析灵敏度分析-12-运筹学 若若b2增加到增加到30，最优解如何变化？，最优解如何变化？53015b 2/34/102/14/102/154/511B00515530152/34/102/14/102/154/511 bB最优基不变，最优解变为（最优基不变，最优解变为（5，0，15，0，0）。）。灵敏度分析灵敏度分析-13-运筹学 I 表表Cj21000CB基基解解X1X2X3X4X50X315051000X424620

11、100X5511001检验数检验数 j21000B 表表Cj21000CB基基解解X1X2X3X4X50X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2检验数检验数 j000-1/4-1/2灵敏度分析灵敏度分析-14-运筹学 若若b2增加到增加到32，最优解如何变化？，最优解如何变化？53215b 2/34/102/14/102/154/511B02/12/112/35532152/34/102/14/102/154/511 bB最优基发生变化，用对偶单纯形法求解。最优基发生变化，用对偶单纯形法求解。灵敏度分析灵敏度分析-15-运筹学 B 表表

12、Cj21000CB基基解解X1X2X3X4X50X315051002X15110010X420-401-6检验数检验数 j0-100-2B 表表Cj21000CB基基解解X1X2X3X4X50X335/20015/4-15/22X111/21001/4-1/21X2-1/2010-1/43/2检验数检验数 j000-1/4-1/2灵敏度分析灵敏度分析-16-运筹学 已知某生产计划问题的数学模型，为使最优方案不变，已知某生产计划问题的数学模型，为使最优方案不变，试讨论第二个约束条件试讨论第二个约束条件b2的变化范围。的变化范围。0,)(2623)(2432.34max21212121xxxxxx

13、tsxxZ工时约束工时约束材料约束材料约束 cj 4 3 0 0 CBXBb x1 x2 x3 x4 34x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36 0 0 1/5 6/5 解：生产计划问题的数学模型和最优单纯形表为：解：生产计划问题的数学模型和最优单纯形表为：灵敏度分析灵敏度分析-17-运筹学 从矩阵形式的单纯形表中可知，从矩阵形式的单纯形表中可知，b2的变化只影响解的可行性的变化只影响解的可行性B-1b0，因此，为使最优解不变，只需变化以后的，因此，为使最优解不变，只需变化以后的B-1b0即可。即可。05354852572245/35/25/25/32221

14、bbbbB 05354805257222bb由由解得：解得：36162 b当数据量十分当数据量十分大的时候，十大的时候，十分麻烦分麻烦写为写为B-1(24,26)+B-1b灵敏度分析灵敏度分析-18-运筹学 若若b2变化超过范围，则需用对偶单纯形法进行求解。如变化超过范围，则需用对偶单纯形法进行求解。如b2=6，则则06126245/35/25/25/31 bB 12612431 bBCB cj 4 3 0 0 CBXBb x1 x2 x3 x4 34x2x112-6 0 1 3/5 -2/5 1 0 -2/5 3/5 Z12 0 0 1/5 6/5 将上述数字替换最优单纯形表中相应位置的数据

15、得：将上述数字替换最优单纯形表中相应位置的数据得：灵敏度分析灵敏度分析-19-运筹学 cj 4 3 0 0 CBXBb x1 x2 x3 x4 30 x2x3315 3/2 1 0 1/2-5/2 0 1 -3/2 Z9 1/2 0 0 3/2 用对偶单纯形法迭代，求出的最优单纯形表如下：用对偶单纯形法迭代，求出的最优单纯形表如下：得到新的最优解为：得到新的最优解为：x1=0，x2=3;max z=9灵敏度分析灵敏度分析-20-运筹学 当当 Cj 是非基变量是非基变量 X 的价值系数的价值系数时，若要保持最优解（或基）不时，若要保持最优解（或基）不变，则必须满足：变，则必须满足：CN CB B

16、-1N 0基基 解解 XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB-1b I B-1N B-1 j 0 CN CB B-1N -CB B-1I 表表B 表表2.对价值系数对价值系数Cj变化的分析变化的分析(1)当当 Cj 变化使得非基变变化使得非基变量的量的Cj Zj 0，即最，即最优解（或基）发生变优解（或基）发生变化，则在原单纯形化，则在原单纯形B表表的基础上，继续求解的基础上，继续求解模型。模型。灵敏度分析灵敏度分析-21-运筹学 max z=2x1+x2 5x2 15s.t.6x1+2x2 24 x1+x2 5 x1，x2 0I 表表Cj21000CB基基解解X1X2X3X4X50X315051000X424620100X5511001检验数检验数 j21000灵敏度分析灵敏度分析-22-运筹学 B 表表Cj21000CB基基解解X1X2X3X4X50X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2检验数检验数 j000-1/4-1/2B 表表CjC11000CB基基解解X1X2X3