常见的运筹学灵敏度分析课件.ppt

1、精品课件1灵敏度分析=对于市场的变化，我们的决策究竟怎样变化（不需要将它当成一个新问题）BNXbIB-1NB-1b-Z0Cj-ZjCB-CBB-1B精品课件2灵敏度分析njjjxcz1max),2,1(0),2,1(1njxmibxajnjijj或maxz=cx0XbAX精品课件3灵敏度分析（灵敏度分析（2）面对市场变化，灵敏度分析的任务是须解决以下两类问题面对市场变化，灵敏度分析的任务是须解决以下两类问题一、当系数一、当系数A、b、C中的某个发生变化时中的某个发生变化时,目前的最优基是目前的最优基是否仍最优（即目前的最优生产方案是否要变化）否仍最优（即目前的最优生产方案是否要变化）?(称为模

2、称为模型参数的灵敏度分析型参数的灵敏度分析)二、增加一个变量或增加一个约束条件时，目前的最优基二、增加一个变量或增加一个约束条件时，目前的最优基是否仍最优（即目前的最优生产方案是否要变化）是否仍最优（即目前的最优生产方案是否要变化）(称为称为模型结构的灵敏度分析模型结构的灵敏度分析)灵敏度分析的方法是在目前最优基灵敏度分析的方法是在目前最优基B下进行的。即当参下进行的。即当参数数A、b、c中的某一个或几个发生变化时，考察是否影响中的某一个或几个发生变化时，考察是否影响以下两式的成立？以下两式的成立？0CABC0bB1B1精品课件41、对于参数、对于参数b的灵敏度分析的灵敏度分析从矩阵形式的单纯

3、形表中可以看出，从矩阵形式的单纯形表中可以看出，b的变化只影响最优的变化只影响最优解的变化和最优值的变化。解的变化和最优值的变化。bXXBB-1bB-1AZC BB-1bC BB-1A-C因此，当因此，当 时，最优基不变（即生产产品的品种时，最优基不变（即生产产品的品种不变，但数量及最优值会变化）。不变，但数量及最优值会变化）。0bB1 0bB1 是一个不等式组，从中可以解得是一个不等式组，从中可以解得b的变化范围的变化范围若若B-1b中有小于中有小于0的分量，则需用对偶单纯形法迭代，以的分量，则需用对偶单纯形法迭代，以求出新的最优方案。求出新的最优方案。b变化的时候，仅对B-1b有影响此时，

4、基变量不变精品课件5P33 例题16 对于生产计划问题，为使最优方案不变，试讨论第二个约束条件b2的变化范围。0,)(2623)(2432.t.s34Zmaxxxxxxxxx21212121工时约束材料约束 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 解：生产计划问题的数学模型和最优单纯形表为：精品课件6 从矩阵形式的单纯形表中可知，从矩阵形式的单纯形表中可知，b2的变化只影响解的的变化只影响解的可行性可行性B-1b0,因此，为使最优解不变，只需变化以后的因此，为使最优解不变，只

5、需变化以后的 B-1b0即可。即可。05354852572245/35/25/25/3bbbbB2221053548052572bb22由解得：3616b2写为B-1（24,26）+B-1 b精品课件7若若b2变化超过范围，则需用对偶单纯形法进行求解。如变化超过范围，则需用对偶单纯形法进行求解。如b2=6，则，则06126245/35/25/25/3bB11261243bBC1B 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 将上述数字替换最优单纯形表中相应位置的数据得：精品课

6、件8 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;maxz=9精品课件92.对价值系数对价值系数Cj变化的分析变化的分析（1）当）当CN（非基变量的目标函数系数非基变量的目标函数系数）中某个）中某个Cj发生变发生变化时，只影响到非基变量化时，只影响到非基变量xj的检验数的检验数jjjjjBjCCCPBC )()(1由于由于所以所以,当当0j 即当即当 jjC时时,最优解不变（最小值）最优解不变（最小

7、值）反之反之,当当 时时,最优解改变最优解改变,需要用单纯形法重新进需要用单纯形法重新进行迭代行迭代,以求得新的最优解以求得新的最优解.0j 精品课件10例题17 对于下列线性规划模型,为使最优解不变，讨论非基变量y1的目标函数系数c3的变化范围。0,)(26223)(2432.t.s234Zmaxxxyxxyxxyxx21121121121工时约束材料约束用单纯形法求得其最优表为：cj 4 3 2 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146 0 1 -1/5 3/5 -2/5 1 0 4/5 -2/5 3/5 Z36 0 0 3/5 1/5 6/5 精品课件11解：因

8、为解：因为y1为非基变量，其目标函数系数为非基变量，其目标函数系数c3的变化只会影响的变化只会影响到到y1的检验数，因此为使最优解不变，只需的检验数，因此为使最优解不变，只需03即5/135/32C3若C3=3,则523代入最优单纯形表中相应位置继续迭代以求出新的最优解。cj 4 3 2 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146 0 1 -1/5 3/5 -2/5 1 0 4/5 -2/5 3/5 Z36 0 0 -2/5 1/5 6/5 精品课件12（2）当）当CB(即基变量的目标函数系数即基变量的目标函数系数)中某个中某个Cj发生变化时发生变化时则会影响到所有变量

9、的检验数则会影响到所有变量的检验数=CBB-1AC解不等式组解不等式组0CABC1B的范围就可得到Cj例例18 设基变量设基变量x1的系数的系数C1变化为变化为 ，在最优性不变，在最优性不变的条件下，试确定的条件下，试确定 的范围的范围CC11C1解：解：003C45/35/2015/25/310C43CABC111B 00345356525134CCCC1111精品课件1305356525100CC115.422120535605251CCCC1111即42636b585100CA,5CBCBCC11B1B1则若将上述数字替换单纯形表中相应位置的数字得：将上述数字替换单纯形表中相应位置的数字

10、得：cj 4 3 0 0 CBXBb x1 x2 x3 x4 35x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 Z42 0 0 -1/5 8/5 精品课件14用单纯形法迭代得最优解表如下：cj 4 3 0 0 CBXBb x1 x2 x3 x4 05x3x120/326/3 0 5/3 1 -2/3 1 2/3 0 1/3 Z130/3 0 1/3 0 16/15 （3）技术系数）技术系数aij变化的分析变化的分析 第一种情况（当第一种情况（当j JN）：即）：即aij为非基变量为非基变量xj的技术系数的技术系数时，它的变化只影响时，它的变化只影响xj的系数列的系数列B-1

11、Pj和检验数和检验数 ，为使最，为使最优方案不变，只需优方案不变，只需 j0j精品课件150,)(26223)(2432.t.s234Zmaxxxyxxyxxyxx21121121121工时约束材料约束 cj 4 3 2 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146 0 1 -1/5 3/5 -2/5 1 0 4/5 -2/5 3/5 Z36 0 0 3/5 1/5 6/5 例18 对于下列规划问题的最优解，若由于工艺改进，y1的技术系数改为p3=(1,1)T，试讨论最优解的变化。解：532115/65/1CPBC331B3最优解改变。此时其系数列改为：精品课件16 第二

12、种情况（当第二种情况（当j JB）：由于）：由于B中元素的改变影响到中元素的改变影响到B-1的变化，因此也影响到整个单纯形表的变化，因此也影响到整个单纯形表T(B)的变化。目前的的变化。目前的基基B对应的解有可能既不是原始可行，也不是对偶可行。对应的解有可能既不是原始可行，也不是对偶可行。于是不如重新求解于是不如重新求解5/15/1115/35/25/25/3PB31将上述数据替换最优表中相应位置的数据，然后再用单将上述数据替换最优表中相应位置的数据，然后再用单纯形法求得新的最优解。纯形法求得新的最优解。cj 4 3 2 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146 0

13、1 1/5 3/5 -2/5 1 0 1/5 -2/5 3/5 Z36 0 0 -3/5 1/5 6/5 精品课件17（4）对增加新产品的分析）对增加新产品的分析设某企业在计划期内，拟议生产新产品设某企业在计划期内，拟议生产新产品Xn+1，并已知新产，并已知新产品 的 单 位 利 润 为品 的 单 位 利 润 为 Cn+1，消 耗 系 数 向 量 为，消 耗 系 数 向 量 为Pn+1=(a1,n+1,a2,n+1,am,n+1)T，此时应如何分析才能确定该新，此时应如何分析才能确定该新产品是否值得投产？产品是否值得投产？增加新产品应在不影响企业目前计划期内最优生产的前增加新产品应在不影响企业

14、目前计划期内最优生产的前提下进行。因此可从现行的最优基提下进行。因此可从现行的最优基B出发考虑：出发考虑：若若n+1=CBB-1Pn+1Cn+10，则不应投入则不应投入。即新产品的机会成本小于目前的市场价格时，应投产即新产品的机会成本小于目前的市场价格时，应投产否则不应投产。否则不应投产。例例19 现有一新产品丙，经预测其单位利润为现有一新产品丙，经预测其单位利润为3，技术消耗，技术消耗系数为系数为P5=（2，2）T，问该产品是否值得投产？，问该产品是否值得投产？精品课件18解：5/1322)5/65/1(CPBC551B5值得投产。cj 4 3 0 0 3CBXBb x1 x2 x3 x4

15、y5 34x2x146 0 1 3/5 -2/5 2/5 1 0 -2/5 3/5 2/5 Z36 0 0 1/5 6/5 -1/5将此变量加入最优单纯形表中得：其系数列为：52522252535352PB51精品课件19 在企业生产过程中，经常有新情况发生，造成原本不在企业生产过程中，经常有新情况发生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响紧缺的某种资源变成为紧缺资源，对生产计划造成影响，如水、电和资源的供应不足等，对生产过程提出了新，如水、电和资源的供应不足等，对生产过程提出了新约束等。约束等。对增加新约束条件的分析方法步骤是：对增加新约束条件的分析方法步骤是：（5）对

16、增加新约束条件的分析）对增加新约束条件的分析 cj 4 3 0 0 3CBXBb x1 x2 x3 x4 y5 34y5x1102 0 5/2 3/2 -1 1 1 -1 -1 1 0 Z38 0 1/2 1/2 1 0用单纯形法迭代求得最优解为：精品课件20 第一步：将目前的最优解代入新增加的约束，若能满足第一步：将目前的最优解代入新增加的约束，若能满足约束条件，则说明新增约束对目前的最优解（即最优生产约束条件，则说明新增约束对目前的最优解（即最优生产方案）不构成影响（称此约束为不起作用约束），可暂时方案）不构成影响（称此约束为不起作用约束），可暂时不考虑新增约束条件。否则转下一步；不考虑新

17、增约束条件。否则转下一步；第二步：把新增约束添加到原问题最终表中，并作初等第二步：把新增约束添加到原问题最终表中，并作初等行变换，构成对偶可行的单纯形表，并用对偶单纯形法迭行变换，构成对偶可行的单纯形表，并用对偶单纯形法迭代，求出新的最优解。代，求出新的最优解。例例19 对于生产计划问题，设增加电力约束，生产对于生产计划问题，设增加电力约束，生产1单位甲单位甲产品需耗电产品需耗电3个单位，生产个单位，生产1单位乙产品需耗电单位乙产品需耗电4个单位，且个单位，且每天供电量不超过每天供电量不超过30单位。试分析此时最优解的变化情况单位。试分析此时最优解的变化情况。精品课件21 解：将最优解解：将最

18、优解x1=6,x2=4代入约束条件代入约束条件 ，不不满足，说明约束条件起作用。满足，说明约束条件起作用。3043xx21将约束条件加入松驰变量，化为等式将约束条件加入松驰变量，化为等式 ，加入最优单纯形表中。，加入最优单纯形表中。30 xx4x3521 cj 4 3 0 0 0 CBXBb x1 x2 x3 x4 x5340 x2x1x54630 0 1 3/5 -2/5 0 1 0 2/5 3/5 0 3 4 0 0 1 Z36 0 0 1/5 6/5 0在这个表中，由于在这个表中，由于x1,x2是基变量，必须为单位向量，因此是基变量，必须为单位向量，因此将将x1,x2化为单位向量得化为单

19、位向量得精品课件22 cj 4 3 0 0 0 CBXBb x1 x2 x3 x4 x5340 x2x1x546-4 0 1 3/5 -2/5 0 1 0 2/5 3/5 0 0 0 -6/5 -1/5 1 Z36 0 0 1/5 6/5 0再用对偶单纯形法求得新的最优表如下：再用对偶单纯形法求得新的最优表如下：cj 4 3 0 0 0 CBXBb x1 x2 x3 x4 x5340 x2x1x3222/310/3 0 1 0 -1/2 1/2 1 0 0 2/3 -1/3 0 0 1 1/6 -5/6 Z106/3 0 0 0 6/7 1/6精品课件23对于增加新产品和新约束的灵敏度分析，在

20、计算机软件中对于增加新产品和新约束的灵敏度分析，在计算机软件中是用是用Modify Program 来完成的来完成的1、增加新产品的灵敏度分析、增加新产品的灵敏度分析Final tableau(Total iteration=3)BasisC(j)X1X2X3S1S2B(i)B(i)4.0003.0003.00000A(i,j)X3X13.0004.00001.0002.500-1.0001.00001.500-1.000-1.0001.00010.0002.00000C(j)-Z(j)*Big M00-0.5000000-0.50000-1.000038.0000精品课件242、增加新约束的

21、灵敏度分析、增加新约束的灵敏度分析Final tableau(Total iteration=3)BasisC(j)X1X2S1S2S3B(i)B(i)4.0003.000000A(i,j)S1X1X203.0004.00001.0000001.0001.000000.1670.667-0.500-0.833-0.3330.5003.3337.3332.00000C(j)-Z(j)*Big M000000-1.1700-0.167035.3330精品课件25练习练习1：一家企业制造三种产品，需三种资源，技术服务、劳力：一家企业制造三种产品，需三种资源，技术服务、劳力、行政管理，下表列出了三种产

22、品每单位数量对每种资源的需要、行政管理，下表列出了三种产品每单位数量对每种资源的需要量量产品ABC资源限量技术服务111100劳力1045600行政管理226300单位利润1064（1）问如何安排生产，可使利润最大？）问如何安排生产，可使利润最大？（2）C产品的单位利润为多少时才值得生产？产品的单位利润为多少时才值得生产？（3）若劳力资源增加到）若劳力资源增加到800小时，问最优计划是否要改变，若要改小时，问最优计划是否要改变，若要改变，应如何改变？变，应如何改变？（4）制造部门提出要生产一种产品，需要技术服务）制造部门提出要生产一种产品，需要技术服务1小时、劳力小时、劳力4小小时、行政管理时

23、、行政管理3小时，问其单位利润为多少方可否投产？小时，问其单位利润为多少方可否投产？（5）若有一种原材料，如今受到限制，限制条件为）若有一种原材料，如今受到限制，限制条件为 ，问最优计划是否受到影响？，问最优计划是否受到影响？400523xxx321精品课件26 cj 10 6 4 0 0 0 CBXBb x1 x2 x3 x4 x5 x66100 x2x1x6200/3100/3100 0 1 5/6 5/3 -1/6 0 1 0 1/6 -2/3 1/6 0 0 0 4 -2 0 1 Z2200/3 0 0 8/3 10/3 2/3 0解：（1）用单纯形法求得最优表为才值得投产时,3/20

24、065103/23/10CCCPBC33331B3（2）01003/2003/10030080010010206/13/206/13/5bB1（3）最优基不变精品课件27（4）设新产品为x702834103/23/10CPBC771B7值得投产。（5）将x1=100/3,x2=200/3,x3=0代入约束条件 左边得400523xxx32140034001003200231003因此，最优计划不变。精品课件28练习2、某企业生产甲、乙两种产品，需消耗A、B、C三种资源，产品的单位利润和单位消耗如下表所示：产品 单位产品消耗资源甲乙丙资源限量A31330B22140C13450产品单位利润436

25、（1）该企业如何安排生产，才能获得最大利润？（2）产品甲、的单位利润在多大范围内变化，可保持最优基解不变？（3）写出资源A、B的影子价格，并解释其经济意义。若资源B、C的限量不变，资源A不够可从市场购买，价格1元/单位，问是否要购进A资源扩大生产？精品课件29（4）若现有一新产品丁，据市场预测，丁的单位价格5元/单位，对A、B、C三种资源的单位消耗量为2，1，5，问是否值得生产？其最优单纯形表如下：cj 4 3 6 0 0 0 CBXBb x1 x2 x3 x4 x5 x6600 x3x5x282068/5 0 1 3/5 0 -1/5 4 0 0 1 1 -1-9/5 1 0 -4/5 0

26、3/5 Z661/5 0 0 6/5 0 3/5练习3、已知某线性规划的最终单纯形表如下：其中X1，X2，X3表示生产的三种产品。0,)2(30543)1(45536t.s53zmaxxxxxxxxxxxx21321321321种资源约束第种资源约束第精品课件30 cj 3 1 5 0 0 CBXBb x1 x2 x3 x4 x5 05x4x3156 3 -1 0 1 -1 3/5 4/5 1 0 1/5 Z30 0 3 0 0 1 （1）根据表中数据进行经济分析。（2）若有一新产品X6，其价值系数为C6=4，消耗系数为P6=（1，2）T，问该产品是否值得投产？（3）若增加新约束条件 ，问最优

27、方案是否改变？1032xxx321精品课件31练习4、甲、乙两厂竞争A、B两种产品的市场，目前甲厂这两种产品的销量都只是乙厂销量的三分之一。两家工厂都已完成这两种产品更新换代的研制，但要投产上市则还需要一段时间。若同时投产两种新产品上市，每厂都需一年；若只投产一种抢先上市，则甲有厂需10个月，乙厂需9个月，而另一种产品对每厂都再需9个月才能上市。对任一种新产品，若两厂产品同时上市，估计甲厂该产品的市场占有率将增加8个百分点（即由25%增至33%）；若甲厂产品抢先2，6个月上市，则其市场占有率将分别增加20，30个百分点；若甲厂产品落后1，3，7个月上市，则其市场占有率将分别下降4，10，12个

28、百分点。假设每厂都以其两种产品市场占有率增加的百分点数之和的一半作为赢得指标，试建立此对策的模型并求解。精品课件32练习5、某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为s1,s2,s10，相应的钻探费用为c1,c2，,c10，并且井位选择上要满足下列限制条件：（1）或选择s1和s7，或选择钻探s8；（2）选择了s3或s4就不能选择s5，或反过来也一样；（3）在s5，s6，s7，s8中最多只能选两个。试建立这个问题的数学模型。练习6、（生产管理问题）某工厂生产A、B两种产品，这两种产品都需要经过加工和装配两道工序。已知每道工序在每个作业班内可

29、利用的生产能力分别为210小时和120小时，每件产品加工和装配的定额工时和单件产品提供的毛利如下表所示：精品课件33（工厂领导提出下列目标：（1）每个作业班的毛利不少于9800元；（2）充分利用两个工序的工时，且已知加工工时费是装配工时费的二倍；（3）尽量减少加班。问：该工厂应如何生产，才能使这些目标依序实现？试建立其数学模型。产品 工时定额 工序AB生产能力加工109210装配56120毛利（元/件）400500感谢亲观看此幻灯片，此课件部分内容来源于网络，感谢亲观看此幻灯片，此课件部分内容来源于网络，如有侵权请及时联系我们删除，谢谢配合！如有侵权请及时联系我们删除，谢谢配合！感谢亲观看此幻灯片，此课件部分内容来源于网络，感谢亲观看此幻灯片，此课件部分内容来源于网络，如有侵权请及时联系我们删除，谢谢配合！如有侵权请及时联系我们删除，谢谢配合！