《管理运筹学》课件04-灵敏度分析

1、,第 4 章,Sensitivity Analysis,SA,灵敏度分析,第4章 灵敏度分析,2,4.1 引言 4.2 参数的影响范围 4.3 灵敏度分析的程序,第4章 灵敏度分析,第4章 灵敏度分析,3,4.1 引言,灵敏度分析就是分析研究模型参数的取值 变化对最优解或最优基的影响。 模型参数在什么范围内变化将不致影响 最优基？ 若最优解随参数的变化而变，则应如何 用最简方法找到新最优解？,第4章 灵敏度分析,4,4.1 引言,灵敏度分析的特点或优点：充分利用 模型的原始数据: aij , bi , cj 最优单纯形表中的数据:,i = 1, 2, , m,k = 1, 2, , m,j =

2、 1, 2, , n,j = 1, 2, , n,(1),第4章 灵敏度分析,5,4.1 引言,aij = aij +aij bi = bi +bi cj = cj +cj,k = 1, 2, , m,j = 1, 2, , n,j = 1, 2, , n,(2),则最优单纯形表中的数据也有如下增量：,设,第4章 灵敏度分析,6,4.2 参数的影响范围,考虑问题(P1)及其标准形(Ps) ：,在保持问题(Ps)的最优基不变的条件下，该参数 单独变化的最大范围。,问题(P1)的某个参数的影响范围是指：,第4章 灵敏度分析,7,4.2 参数的影响范围,4.2.1 参数bi的影响范围,设参数 br发

3、生br的变化，则br的影响范围是： brbr-，br+ 其中：,br- = max -bk*/skr* skr* 0 br+= min -bk*/skr* skr* 0 ,相应地，参数 br的影响范围是： br br+br-，br+br+ 其中： br 参数br的原始数值,第4章 灵敏度分析,8,4.2 参数的影响范围,例1 范例的最优单纯形表如下：, b1的影响范围 b1- = - 4/1 = -4 b1+= ,又知参数的原始数值b1= 8 , 则 b1 8 -4，8 +）= 4, ),第4章 灵敏度分析,9,4.2 参数的影响范围, b2的影响范围,又已知参数的原始值b2 =12, 则 b

4、2 12 -6，12 + 6 = 6,18,第4章 灵敏度分析,10,4.2 参数的影响范围, b3的影响范围,又已知参数的原始值b3 = 36, 则 b3 36 -12，36 +12 = 24, 48 ,第4章 灵敏度分析,11,4.2 参数的影响范围,4.2.2 参数 cj的影响范围 一、cj是非基变量的系数,设问题(P1)的某一非基变量 xr 的系数cr变化cr , 其余cj 及一切bi,aij 均不变。则 cr 的影响范围是 ： (-, r* 相应地, cr的影响范围是：,其中:,cr 参数cr的原始数据,cr ( -, cr +r* ,第4章 灵敏度分析,12,4.2 参数的影响范围

5、,第2.4节的例5,cr (-, cr +r*,c1 (-, 3 + 3/4 ,第4章 灵敏度分析,13,4.2 参数的影响范围,设基变量xr的系数 cr = cBl 发生 cr 的变化，则有: cr- = max -j*/al j*al j* 0 cr+ = min -j*/al j*al j* 0 alj* 基变量 xr 所在第l 行中的非基变量的系数， 则cr的影响范围是： cr cr + cr-，cr + cr+ 其中： cr 参数cr的原始数值,二、cj是基变量的系数,第4章 灵敏度分析,14,4.2 参数的影响范围,而 c1 = 3 故： c1 3 - 3 ,3 + 3/4= 0

6、, 15/4 ,又有：,故： c2 5 -1,）=4 , ）,范例：c1, c2 的影响范围,第4章 灵敏度分析,15,4.2 参数的影响范围,z = 3x1 + c2x2,2x2 = 12,0 x1 +,3x1 + 4x2 = 36,c2 = 4,斜率为0,= 0,c2 = ,-,c2 4, ),图解法,第4章 灵敏度分析,16,4.2 参数的影响范围,4.2.3 参数aij的影响范围,设某一非基变量的参数 akr 单独变化akr , 则有：,akr -r*/yk* , ), 当 yk* 0 (-，+) , 当 yk* = 0,其中： akr 参数akr的原始数值,第4章 灵敏度分析,17,

7、4.2 参数的影响范围,第2.4节的例5 ：a11 , a31的影响范围,a31 a31 -1*/y3*, ),因 y1* = 0, 故a11的影响范围是： a11 ( -, ) 而 y3* = 5/4, 故a31的影响范围是：,= 12 /5, ),第4章 灵敏度分析,18,4.3 灵敏度分析的程序,b* = B-1b w * = (Y*)Tb (*)T = (Y*)TA -CT 或 j* = (Y*)Taj -cj A* = B-1A, 或 aj* = B-1aj ,(7),基本公式,第4章 灵敏度分析,19,4.3 灵敏度分析的程序,1根据变化的参数值（b,C,A)选择有关公式算出变化后

8、 的数据(b*, w*, *, A*), 用以取代原最优单纯形表中的相应数 据, 必要时添行添列，得到新表。 2若新表中基向量改变了单位向量的形式（包括该列检验数 不再为0）, 则用换基运算恢复基向量为单位向量（包括该列 检验数也须化为0）；否则转3。 3这时新表中解列的数据b与检验矢 有以下四种可能情况：, 若b0且 0，则当前解即最优解，停止运算；,基本程序,第4章 灵敏度分析,20,4.3 灵敏度分析的程序,4.3.1 改变各bi 若有一个参数bi的变化超出其影响范围，或有几个bi同时变化，则须按 灵敏度分析的基本程序进行分析。这时*和A*均未变，仅b*, w* 有变。 例3 若范例中参

9、数b2变为24, 最优解有何变化？ 解：由于b2= 24已超出b2的影响范围6, 18, 因此最优基必然改变。 按之式得：,b*,B-1,b,YT,第4章 灵敏度分析,21,4.3 灵敏度分析的程序,-2/3,x3 x2 x4,0 5 0,6 -3/2 0 0 1 -1/2,9 3/4 1 0 0 1/4,8 1 0 1 0 0,45 3/4 0 0 0 5/4,X*= (0, 9, 8, 6, 0)T, z* = 45,第4章 灵敏度分析,22,4.3 灵敏度分析的程序,4.3.2 改变一个非基变量的系数,例4 因表中基列没有x1，即x1=0，这表明不生产甲产品故工厂决策者考虑: 若改革甲产

10、品的生产工艺，能减少一个C工时/件, 从而增加其利润0.5百元/件, 则能否导致重新安排甲产品的生产？ 解 : 非基变量的系数变为：,a1* =,第4章 灵敏度分析,23,4.3 灵敏度分析的程序,1 1/2 -1,-1,3.5,0,1,x1 x2 x4,3.5 5 0,8 0 0 1 1 -1/2,8 1 0 1 0 0,5 0 1 -1/2 0 1/4,53 0 0 1 0 5/4,X*= (8, 5, 0, 8, 0)T z* = 53,(a),(b),第4章 灵敏度分析,24,4.3 灵敏度分析的程序,例5 承例4。假定还有一种新产品丙, 每件消耗A，B，C 工时数分别为 1，1.5，

11、1 , 利润为3百元/件。则在现有生产能 力下，是否安排生产丙产品？ 解 设丙产品产量为 x6 件，这时原最优单纯形表为表4-5 (b)，且知,第4章 灵敏度分析,25,4.3 灵敏度分析的程序,1 -1/4 2,-3/4,3,2,x1 x2 x6,3.5 5 3,4 0 0 1/2 1/2 -1/4 1,4 1 0 1/2 -1/2 1/4 0,8 0 1 -3/8 1/8 3/16 0,56 0 0 11/8 3/8 17/16 0,X*= (4, 6, 0, 0, 0, 4)T, z* = 56,x6,第4章 灵敏度分析,26,4.3 灵敏度分析的程序,4.3.3 改变一个非基变量的系数

12、 一. 改变一个基变量的系数 例6 考虑范例。若甲产品因故不能投产，但另有丙、丁两种新产品都 能取代甲产品。其中每件丙产品需A, B, C工时数1, 1, 2, 创利4百元, 每件丁产品需A, C工时各2, 也创利4百元。则应以丙还是丁取代甲？ 若用丙取代甲，则把 x1改为丙的日产量。,第4章 灵敏度分析,27,4.3 灵敏度分析的程序,x3 x2 x5,0 5 0,12 0 0 0 -2 1,6 1/2 1 0 1/2 0,8 1 0 1 0 0,30 -3/2 0 0 5/2 0,x1 x2 x5,4 5 0,12 0 0 0 -2 1,42 0 0 3/2 5/2 0,8 1 0 1 0

13、 0,2 0 1 -1/2 1/2 0,1,1/3,4,1 1/2 0,-3/2,4,X*= (8,2)T z* = 42,第4章 灵敏度分析,28,4.3 灵敏度分析的程序,若用丁取代甲，则把 x1 改为丁的日产量。,第4章 灵敏度分析,29,4.3 灵敏度分析的程序,4,4,4/3 0 2/3,- 2,2/3,x3 x2 x1,0 5 4,6 1 0 0 -1 1/2,6 0 1 0 1/2 0,- 4 0 0 1 2 -1,54 0 0 0 -3/2 2,x5 x2 x1,0 5 4,4 1 0 1/2 0 0,46 0 0 2 5/2 0,4 0 0 -1 -2 1,6 0 1 0 1

14、/2 0,-1,X*= (4, 6)T z* = 46,第4章 灵敏度分析,30,4.3 灵敏度分析的程序,二. 基变量某一系数aij的影响范围确定,例7 试确定范例LP原型中参数a32的影响范围。 解: 设a32发生的变化, 则“优表”中相应的增量为:,=,把它加给“优表”中的a2列, 得,第4章 灵敏度分析,31,4.3 灵敏度分析的程序,x3 x2 x1,0 5 3,4 -2 1 0 0 2/3 - 1/6 1/3,4+2 0 0 1 2/3+1/6 -1/3,6 0 1 0 1/2 0,42-6 0 0 0 1/2 - 1/2 1,1,第4章 灵敏度分析,32,4.3 灵敏度分析的程序,由表可见：若要保证当前解为最优，必须满足：,解得 -2 a32 1,因 a32 原值为4, 故 a32 4 -2,4 +1 = 2, 5 ,4 + 2 0 4 - 2 0 - 0,第4章 灵敏度分析,33,4.3 灵敏度分析的程序,4