管理运筹学 第五章灵敏度分析

1、管理运筹学 第五章灵敏度分析第1页，共41页，2022年，5月20日，8点11分，星期二概 述 在所有的线性规划问题中，变量在目标函数中的系数cj和约束方程中的系数aij以及右端值bi都是固定的，但在实际工作中，很可能不知道这些参数的确切值。此外，管理人员如想知道，稍微改变一下参数，能否使目标值有较大的变化，以判断这些改变是否有利。 灵敏度分析就是在线性规划问题已经求出最优解以后，某一参数变化时，不必将问题从头到尾重算一遍，就知道最优解以及目标函数会发生什么变化，使决策者可以得到比一组最优解更为多的信息，以处理上述问题。2第2页，共41页，2022年，5月20日，8点11分，星期二一、边际值的

2、定义 第i种资源的边际值就是将1单位的第i种资源从现在的用途中抽取出来而使利润减少的数字，用qi表示。 跟上一章当中我们讨论的影子价格的概念在一定程度上是统一的： 边际值(影子价格)qi 是指在最优解的基础上，当第 i 个约束行的右端项 bi 减少一个单位时，目标函数的变化量3第3页，共41页，2022年，5月20日，8点11分，星期二二、边际值的求解以(max,)型为例： 前面讨论过 =(CBb-1)i Zn+i=CBb-1Pn+i =(CBb-1)i 所以qi=Zn+i 其中Zn+i=CBb-1Pn+i表示松弛变量每增加一个单位时损失的利润。n为题目原有的变量数。 在引进边际值的概念后，Z

3、j可以直接使用Zj=4第4页，共41页，2022年，5月20日，8点11分，星期二三、例题求下列问题中各个资源的边际值5第5页，共41页，2022年，5月20日，8点11分，星期二设 x5，x6，x7 分别为资源1，2，3的松弛变量，此问题达到最优解时的单纯形表为：Cj 1 5 3 4 0 0 0CBXBb X1 X2 X3 X4 X5 X6 X70X51000.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

4、0 0.25 1因为qi=Zn+i，n=4,所以q1=z4+1=0；q2=z4+2=0.25；q3=z4+3=100.2516第6页，共41页，2022年，5月20日，8点11分，星期二 利用边际值qi可得出: 1.在一定范围内，资源i增加一单位，利润就增加qi。 如资源2，3各增加一单位，利润分别增加0.25及1元，资源1增加一单位，利润不增加。Cj 1 5 3 4 0 0 0CBXBb X1 X2 X3 X4 X5 X6 X70X51000.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

5、-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第7页，共41页，2022年，5月20日，8点11分，星期二 2.在己求得最优表后，如建议生产一种新产品，不必重新计算，就能回答生产这种产品是否有利 如在本例中，若建议生产新产品，产量为 x8，问是否生产？已知 c8=9, a18=5, a28=4, a38=3从上表中得知q1=0 q2=0.25 q3=1 所以：结论：生产x8有利。8第8页，共41页，2022年，5月20日，8点11分，星期二第五章 线性规划问题的灵敏度分析5.2 对cj 值的灵敏度分析第9

6、页，共41页，2022年，5月20日，8点11分，星期二概 述cj 变动可能由于市场价格的波动，或生产成本的变动cj 的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj 允许的变动范围cj cj 的变化会引起检验数的变化，有两种情况非基变量对应的价值系数变化，不影响其它检验数基变量对应的价值系数变化，影响所有非基变量检验数10第10页，共41页，2022年，5月20日，8点11分，星期二一、非基变量对应的价值系数的灵敏度分析非基变量对应的系数的变化仅影响其对应的检验数，当Cj变化为Cj+ Cj后若要使最优解不变，则：11第11页，共41页，2022年，5月20日，8点11分，星期二例题:

7、求C1C3的变动范围12第12页，共41页，2022年，5月20日，8点11分，星期二二、基变量对应的价值系数的灵敏度分析 由于基变量对应的价值系数在CB中出现，因此它会影响所有非基变量的检验数。 设当只有一个基变量的cj生变化，变化量为 cj。可令 cj在CB中的第r行，研究非基变量xk机会成本的变化。为保证所有非基变量检验数仍满足最优条件，有：其中xj为第r个约束条件方程对应的基变量13第13页，共41页，2022年，5月20日，8点11分，星期二设x4的价值系数增加c4，对应r=2例题：求X4的C值的变动范围14第14页，共41页，2022年，5月20日，8点11分，星期二第五章 线性规

8、划问题的灵敏度分析5.3 对 bi 值的灵敏度分析第15页，共41页，2022年，5月20日，8点11分，星期二概 述b的灵敏度分析就是研究最优解基变量保持不变但基变量的取值可以变化的条件下b的取值范围设 XB=B1b 是最优解，则有XB=B1b0b 的变化不会影响检验数b 的变化量 b 可能导致原最优解变为非可行解（不满足非负约束）16第16页，共41页，2022年，5月20日，8点11分，星期二在将“”形式的约束条件变为“=”形式时，对第i行的约束条件方程左端要加一个松弛变量Xn+i，因此，最优解表中B-1可表示为右端项 bi 的灵敏度分析17第17页，共41页，2022年，5月20日，8

9、点11分，星期二18第18页，共41页，2022年，5月20日，8点11分，星期二19第19页，共41页，2022年，5月20日，8点11分，星期二XN为新的解向量 X0为原来的解向量Pn+k为最优单纯形表中Xn+k对应的列向量20第20页，共41页，2022年，5月20日，8点11分，星期二例题求b2的灵敏度范围，并求出新的最优解21第21页，共41页，2022年，5月20日，8点11分，星期二因为 x6是对应b2的初始基变量，所以有b2原始等于120022第22页，共41页，2022年，5月20日，8点11分，星期二23第23页，共41页，2022年，5月20日，8点11分，星期二第五章

10、线性规划问题的灵敏度分析5.4 对aij 值的灵敏度分析第24页，共41页，2022年，5月20日，8点11分，星期二对aij的灵敏度分析是在不改变最优解基变量及其取值的情况下求aij的允许变动范围系数aij变化的影响比较复杂对应基变量的 aij ，且资源bi已全部用完对应基变量的 aij ，但资源bi未用完 对应非基变量的 aij ，且资源bi全用完或未用完概 述25第25页，共41页，2022年，5月20日，8点11分，星期二1、对应基变量的 aij ，且资源bi已全部用完 aij=02、对应基变量的 aij ，但资源bi未用完 aij26第26页，共41页，2022年，5月20日，8点1

11、1分，星期二3、对应非基变量的 aij27第27页，共41页，2022年，5月20日，8点11分，星期二例题求aij的灵敏度范围28第28页，共41页，2022年，5月20日，8点11分，星期二根据上节的知识可知q1= 0, q2= 0.25, q3= 1, 边际值为0时表示对应资源未用完，边际值不为0时表示对应资源全部用完对应基变量且资源全部用完的情况aij=0 所以：a22=0 ；a24=0 ；a32=0 ；a34=0对应基变量且资源未用完的情况利用公式 aijx2, x4为基变量， b1未用完、b2b3全部用完故有：29第29页，共41页，2022年，5月20日，8点11分，星期二x1

12、x3为非基变量，利用公式 故有： 30第30页，共41页，2022年，5月20日，8点11分，星期二第五章 线性规划问题的灵敏度分析5.5 灵敏度分析应用举例第31页，共41页，2022年，5月20日，8点11分，星期二例 某工厂生产三种产品 A, B, C，有五种生产组合方案。下两表给出有关数据。规定每天供应 A产品至少110 个，求收益最大的生产方案。32第32页，共41页，2022年，5月20日，8点11分，星期二解：设xj为已选定各种组合方案的组数(j=1,2,5)， x6为A产品的剩余变量， x7，x8分别为工人工时和机器工时的松弛变量。33第33页，共41页，2022年，5月20日

13、，8点11分，星期二 我们考虑如下几种互相独立的情况，看一看如何应用上面几节讨论的结论如果第2种生产方法的每批成本提高到21元,问是否会改变最优解?解: 据题意c2 = -2,超出范围,所以最优解改变. 将新的cj值代替表中的cj值, 解得最优解为:34第34页，共41页，2022年，5月20日，8点11分，星期二解: B的单位售价增加,五种生产方法的cj值都要变1.求出新的cj值: c1=26, c2=31, c3=42,c4=6, c5=492.将新的cj值代替表中的cj值, 重新计算检验数得上表未达最优,用单纯形法继续求解.如果产品B的单位售价增加到6元,是否影响最优解?35第35页，共

14、41页，2022年，5月20日，8点11分，星期二 解:q2=0.5,即工时增加1小时,利润将增加0.5元加班成本0.3 ,故加班能使利润增加. 如果加班要另付加班费每小时1.5元,问加班能否使利润增加?36第36页，共41页，2022年，5月20日，8点11分，星期二对b2进行灵敏度分析为:37第37页，共41页，2022年，5月20日，8点11分，星期二如果新购一台机器,购价300,000元,每天可增加8个机器时间,机器可使用5年,每年工作250工作日,问是否有利? 解:从表可知机器小时的边际值为44元,从题目中算得每机器小时的成本为 38第38页，共41页，2022年，5月20日，8点11分，星期二问增加3台新机器是否有利?对b3进行灵敏度分析为: 增加3台机器即每天增加3*8=24小时,在上述范围内,每天可增加(40-33)*24=336元39第39页