管理运筹学 第五章灵敏度分析精选文档.ppt

管理运筹学管理运筹学 第五章灵敏度分析第五章灵敏度分析本讲稿第一页，共四十一页概概 述述 在所有的线性规划问题中，变量在目标函数中的系数在所有的线性规划问题中，变量在目标函数中的系数cj和和约束方程中的系数约束方程中的系数aij以及右端值以及右端值bi都是固定的，但在实际都是固定的，但在实际工作中，很可能不知道这些参数的确切值。此外，管理人工作中，很可能不知道这些参数的确切值。此外，管理人员如想知道，稍微改变一下参数，能否使目标值有较大的员如想知道，稍微改变一下参数，能否使目标值有较大的变化，以判断这些改变是否有利。变化，以判断这些改变是否有利。灵敏度分析就是在线性规划问题已经求出最优解以后，灵敏度分析就是在线性规划问题已经求出最优解以后，某一参数变化时，不必将问题从头到尾重算一遍，就知道某一参数变化时，不必将问题从头到尾重算一遍，就知道最优解以及目标函数会发生什么变化，使决策者可以得到最优解以及目标函数会发生什么变化，使决策者可以得到比一组最优解更为多的信息，以处理上述问题。比一组最优解更为多的信息，以处理上述问题。2本讲稿第二页，共四十一页一、边际值的定义一、边际值的定义 第第i i种资源的边际值种资源的边际值就是将就是将1 1单位的第单位的第i i种资源从种资源从现现在的用途在的用途中抽取出来而使利润减少的数字，用中抽取出来而使利润减少的数字，用qiqi表示。表示。跟上一章当中我们讨论的影子价格的概跟上一章当中我们讨论的影子价格的概念在一定程度上是统一的：念在一定程度上是统一的：边际值边际值(影子价格影子价格)qi)qi 是指在最优解的基础上，是指在最优解的基础上，当第当第 i i 个约束行的右端项个约束行的右端项 bi bi 减少一个单位时，减少一个单位时，目标函数的变化量目标函数的变化量3本讲稿第三页，共四十一页二、边际值的求解二、边际值的求解以以(max,)型为例：型为例：前面讨论过前面讨论过 =(CBb-1)i Zn+i=CBb-1Pn+i=(CBb-1)i 所以所以qi=Zn+i 其中其中Zn+i=CBb-1Pn+i表示松弛变量每增加一个单位表示松弛变量每增加一个单位时损失的利润。时损失的利润。n为题目原有的变量数。为题目原有的变量数。在引进边际值的概念后，在引进边际值的概念后，ZjZj可以直接使用可以直接使用Zj=Zj=4本讲稿第四页，共四十一页三、例题三、例题求下列问题中各个资源的边际值求下列问题中各个资源的边际值5本讲稿第五页，共四十一页设设 x x5 5，x x6 6，x x7 7 分别为资源分别为资源1 1，2 2，3 3的松弛变量，此问题达到最优的松弛变量，此问题达到最优解时的单纯形表为：解时的单纯形表为：Cj 1 5 3 4 0 0 0CBXBb X1 X2 X3 X4 X5 X6 X70X5100 0.25 0 -3.25 4 0 0 04X4200 2 0 -2 1 0 1 -15X2100-0.75 1 2.75 0 0 0.75 1Cj-Zj-3.25 0 -2.75 0 0 -0.25 -1Zj4.25 0 5.75 4 0 0.25 1因为因为q qi=i=Z Zn+in+i，n=4,n=4,所以所以q q1 1=z=z4+14+1=0=0；q q2 2=z=z4+24+2=0.25=0.25；q q3 3=z=z4+34+3=1=100.2516本讲稿第六页，共四十一页 利用边际值利用边际值q qi i可得出可得出:1.1.在一定范围内，资源在一定范围内，资源i i增加一单位，利润就增加增加一单位，利润就增加q qi i。如资源如资源2 2，3 3各增加一单位，利润分别增加各增加一单位，利润分别增加0.250.25及及1 1元，资源元，资源1 1增加一单位，利润不增加。增加一单位，利润不增加。Cj 1 5 3 4 0 0 0CBXBb X1 X2 X3 X4 X5 X6 X70X5100 0.25 0 -3.25 4 0 0 04X4200 2 0 -2 1 0 1 -15X2100-0.75 1 2.75 0 0 0.75 1Cj-Zj-3.25 0 -2.75 0 0 -0.25 -1Zj4.25 0 5.75 4 0 0.25 1q1=0；q2=0.25；q3=17本讲稿第七页，共四十一页 2.2.在己求得最优表后，如建议生产一种新产品，不必重新计算，在己求得最优表后，如建议生产一种新产品，不必重新计算，就能回答生产这种产品是否有利就能回答生产这种产品是否有利 如在本例如在本例中，若建议生产新产品，产量为中，若建议生产新产品，产量为 x8，问是否生产，问是否生产？已知已知 c8=9,a18=5,a28=4,a38=3从上表中得知从上表中得知q1=0 q2=0.25 q3=1 所以：所以：结论：结论：生产生产x8有利。有利。8本讲稿第八页，共四十一页第五章第五章 线性规划问题的灵敏度分析线性规划问题的灵敏度分析5.2 5.2 对c cj j 值的灵敏度分析值的灵敏度分析本讲稿第九页，共四十一页概 述cj 变动可能由于市场价格的波动，或生产成本的变动变动可能由于市场价格的波动，或生产成本的变动c cj j 的灵敏度分析是在保证最优解的基变量不变的情的灵敏度分析是在保证最优解的基变量不变的情况下，分析况下，分析c cj j 允许的变动范围允许的变动范围 c cj j c cj j 的变化会引起检验数的变化，有两种情况的变化会引起检验数的变化，有两种情况非基变量对应的价值系数变化，不影响其它检非基变量对应的价值系数变化，不影响其它检验数验数基变量对应的价值系数变化，影响所有非基基变量对应的价值系数变化，影响所有非基变量检验数变量检验数10本讲稿第十页，共四十一页一、非基变量对应的价值系数的灵敏度分析一、非基变量对应的价值系数的灵敏度分析非非基基变变量量对对应应的的系系数数的的变变化化仅仅影影响响其其对对应应的的检检验验数数，当当C Cj j变化为变化为C Cj j+C+Cj j后若要使最优解不变，后若要使最优解不变，则：则：11本讲稿第十一页，共四十一页例题例题:求求C1C3的变动范围的变动范围12本讲稿第十二页，共四十一页二、二、基变量对应的价值系数的灵敏度分析基变量对应的价值系数的灵敏度分析 由于由于基变量对应的价值系数在基变量对应的价值系数在CB中出现，因此它会影中出现，因此它会影响所有非基变量的检验数。响所有非基变量的检验数。设当只有一个基变量的设当只有一个基变量的c cj j生变化，变化量为生变化，变化量为 c cj j。可令可令 c cj j在在CB中的第中的第r r行，研究非基变量行，研究非基变量xk机会成本的变化。为机会成本的变化。为保证所有非基变量检验数仍满足最优条件，有：保证所有非基变量检验数仍满足最优条件，有：其中其中x xj j为第为第r r个约束条件方程对应的基变量个约束条件方程对应的基变量13本讲稿第十三页，共四十一页设设x4的价值系数增加的价值系数增加 c4，对应，对应r=2例题：例题：求求X X4 4的的C C值的变动范围值的变动范围14本讲稿第十四页，共四十一页第五章第五章 线性规划问题的灵敏度分析线性规划问题的灵敏度分析5.3 5.3 对 b bi i 值的灵敏度分析值的灵敏度分析本讲稿第十五页，共四十一页概概 述述b的灵敏度分析就是研究最优解基变量保的灵敏度分析就是研究最优解基变量保持不变但基变量的取值可以变化的条件持不变但基变量的取值可以变化的条件下下b的取值范围的取值范围设设 XB=B 1b 是最优解，则有是最优解，则有XB=B 1b 0b 的变化不会影响检验数的变化不会影响检验数b 的变化量的变化量 b 可能导致原最优解变为非可能导致原最优解变为非可行解（不满足非负约束）可行解（不满足非负约束）16本讲稿第十六页，共四十一页在将在将“”形式的约束条件变为形式的约束条件变为“=”形式时，对第形式时，对第i行的约束条件方程左端要加一个松弛变量行的约束条件方程左端要加一个松弛变量Xn+i，因此，因此，最优解表中最优解表中B-1可表示为可表示为右端项右端项 bi 的灵敏度分析的灵敏度分析17本讲稿第十七页，共四十一页18本讲稿第十八页，共四十一页19本讲稿第十九页，共四十一页XN为新的解向量为新的解向量 X0为原来的解向量为原来的解向量Pn+k为最优单纯形表中为最优单纯形表中Xn+k对应的列向量对应的列向量20本讲稿第二十页，共四十一页例题例题求求b2b2的灵敏度范围，并求出新的最优解的灵敏度范围，并求出新的最优解21本讲稿第二十一页，共四十一页因为因为 x6是对应是对应b b2 2的初始基变量，所以有的初始基变量，所以有b2原始等于原始等于120022本讲稿第二十二页，共四十一页23本讲稿第二十三页，共四十一页第五章第五章 线性规划问题的灵敏度分析线性规划问题的灵敏度分析5.4 5.4 对对aij 值值的灵敏度分析的灵敏度分析本讲稿第二十四页，共四十一页对对aij的灵敏度分析是在不改变最优解基变量的灵敏度分析是在不改变最优解基变量及其取值的情况下求及其取值的情况下求aij的允许变动范围的允许变动范围系数系数aij变化的影响比较复杂变化的影响比较复杂对应基变量的对应基变量的 aij，且资源，且资源bi已全部用完已全部用完对应基变量的对应基变量的 aij，但资源，但资源bi未用完未用完 对应非基变量的对应非基变量的 aij，且资源，且资源bi全用完或未用全用完或未用完完概概 述述25本讲稿第二十五页，共四十一页1、对应基变量的、对应基变量的 aij，且资源，且资源bi已全部用完已全部用完 aij=02、对应基变量的、对应基变量的 aij，但资源，但资源bi未用完未用完 aij 26本讲稿第二十六页，共四十一页3、对应非基变量的、对应非基变量的 aij27本讲稿第二十七页，共四十一页例题例题求求aij的灵敏度范围的灵敏度范围28本讲稿第二十八页，共四十一页根据上节的知识可知根据上节的知识可知q1=0,q2=0.25,q3=1,边际值为边际值为0时时表示对应资源未用完，边际值不为表示对应资源未用完，边际值不为0时表示对应资源全部用时表示对应资源全部用完完对应基变量且资源全部用完的情况对应基变量且资源全部用完的情况 aij=0 所以：所以：a22=0；a24=0；a32=0；a34=0对应基变量且资源未用完的情况利用公式对应基变量且资源未用完的情况利用公式 aij x2,x4为基变量，为基变量，b1未用完、未用完、b b2b b3全部用完故有：全部用完故有：29本讲稿第二十九页，共四十一页x1 x3为非基变量，利用公式为非基变量，利用公式 故有故有：30本讲稿第三十页，共四十一页第五章第五章 线性规划问题的灵敏度分析线性规划问题的灵敏度分析5.5 5.5 灵敏度分析应用举例本讲稿第三十一页，共四十一页例例 某工厂生产三种产品某工厂生产三种产品 A,B,C，有五种生产组合方，有五种生产组合方案。下两表给出有关数据。规定每天供应案。下两表给出有关数据。规定每天供应 A产品至少产品至少110 个，求收益最大的生产方案。个，求收益最大的生产方案。32本讲稿第三十二页，共四十一页解：设解：设xj为已选定各种组合方案的组数为已选定各种组合方案的组数(j=1,2,5)，x6为为A产品产品的剩余变量，的剩余变量，x7，x8分别为工人工时和机器工时的松弛变量。分别为工人工时和机器工时的松弛变量。33本讲稿第三十三页，共四十一页 我们考虑如下几种互相独立的情况，看一看如何我们考虑如下几种互相独立的情况，看一看如何应用上面几节讨论的结论应用上面几节讨论的结论如果第如果第2种生产方法的每批成本提高到种生产方法的每批成本提高到21元元,问是否会问是否会改变最优解改变最优解?解解:据题意据题意c2=-2,超出范围超出范围,所以最优解改变所以最优解改变.将新的将新的cj值代替表中的值代替表中的cj值值,解得最优解为解得最优解为:34本讲稿第三十四页，共四十一页解解:B的单位售价增加的单位售价增加,五种生产方法的五种生产方法的cj值都要变值都要变1.求出新的求出新的cj值值:c1=26,c2=31,c3=42,c4=6,c5=492.将新的将新的cj值代替表中的值代替表中的cj值值,重新计算检验数得重新计算检验数得上表未达最优上表未达最优,用单纯形法继续求解用单纯形法继续求解.如果产品如果产品B B的单位售价增加到的单位售价增加到6 6元元,是否影响最优解是否影响最优解?35本讲稿第三十五页，共四十一页 解解:q2=0.5,即工时增加即工时增加1小时小时,利润将增加利润将增加0.5元元加班成本加班成本0.3,故加班故加班能使利润增加能使利润增加.如果加班要另付加班费每小时如果加班要另付加班费每小时1.51.5元元,问加班能否使利问加班能否使利润增加润增加?36本讲稿第三十六页，共四十一页对对b2b2进行灵敏度分析为进行灵敏度分析为:37本讲稿第三十七页，共四十一页如果新购一台机器如果新购一台机器,购价购价300,000300,000元元,每天可增加每天可增加8 8个个机器时间机器时间,机器可使用机器可使用5 5年年,每年工作每年工作250250工作日工作日,问是问是否有利否有利?解解:从表可知机器小时的边际值为从表可知机器小时的边际值为4444元元,从题目中算得每机器小时从题目中算得每机器小时的成本为的成本为 38本讲稿第三十八页，共四十一页问增加问增加3 3台新机器是否有利台新机器是否有利?对对b3进行灵敏度分析为进行灵敏度分析为:增加增加3台机器即每天增加台机器即每天增加3*8=24小时小时,在上述范围内在上述范围内,每天可增加每天可增加(40-33)*24=336元元39本讲稿第三十九页，共四十一页解解:第第4 4种生产方法的成本要降低种生产方法的成本要降低7.57.5元以上就可采用元以上就可采用,使利润增加使利润增加.第第4 4种生产方法的成本要降低到什么程度才能增加利润种生产方法的成本要降低到什么程度才能增加利润?40本讲稿第四十页，共四十一页如果采取一些措施如果采取一些措施,使第使第3 3种生产方法每批产品所消耗的机器小种生产方法每批产品所消耗的机器小时由时由2 2降至降至1.5,1.5,而增加的费用和减少机器小时而节约的数字恰好而增加的费用和减少机器小时而节约的数字恰好相等相等,问是否要采纳这个建议问是否要采纳这个建议?解解:41本讲稿第四十一页，共四十一页