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

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

2、 bi , cj 最优单纯形表中的数据最优单纯形表中的数据:i = 1, 2, , mk = 1, 2, , mj = 1, 2, , nj = 1, 2, , n(1) m m m4.1 引言引言k = 1, 2, , mj = 1, 2, , nj = 1, 2, , n(2)则最优单纯形表中的数据也有如下增量：则最优单纯形表中的数据也有如下增量： 设设4.2 参数的影响范围参数的影响范围考虑问题考虑问题(P1)及其标准形及其标准形(Ps) ：(P1): max z=CTX AXb X0s.t.(Ps): max z=CTX +0TXs AX +ITXs= b X0， Xs 0s.t. 在

3、保持问题在保持问题(Ps)的最优基不变的条件下，该的最优基不变的条件下，该参数参数单独变化的最大范围。单独变化的最大范围。问题问题(P1)的某个参数的影响范围是指：的某个参数的影响范围是指：4.2 参数的影响范围参数的影响范围 设参数设参数 br发生发生br的变化，那么的变化，那么br的影响范围是：的影响范围是： brbr-，br+ 其中：其中：br- = max -bk*/skr* skr* 0 br+= min -bk*/skr* skr* 0 cr+ = min -j*/al j*al j* 0(-，+) , 当当 yk* = 0 其中：其中： akr 参数参数akr的原始数值的原始数值

4、4.2 参数的影响范围参数的影响范围cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0 x3x4x2 00 50 -3/2 0 0 1 -1/28 1 0 1 0 0 6 3/4 1 0 0 1/430 3/4 0 0 0 5/4第第2.42.4节的例节的例5 5 ：a11 , a31a11 , a31的影响的影响范围范围因因 y1* = 0, 故故a11的影响范围是：的影响范围是： a11 ( -, )而而 y3* = 5/4, 故故a31的影响范围是：的影响范围是： 3/45/4=3 - , ) = 12 /5, )4.3 灵敏度分析的程序灵敏度分析的程序 b* = B-1

5、b w * = (Y*)Tb (*)T = (Y*)TA -CT 或或 j* = (Y*)Taj -cj A* = B-1A, 或或 aj* = B-1aj (7) 基本公式基本公式4.3 灵敏度分析的程序灵敏度分析的程序1根据变化的参数值根据变化的参数值b,C,A)选择有关公式算出变化后选择有关公式算出变化后 的数据的数据(b*, w*, *, A*), 用以取代原最优单纯形表中的相应数用以取代原最优单纯形表中的相应数 据据, 必要时添行添列，得到新表。必要时添行添列，得到新表。2若新表中基向量改变了单位向量的形式包括该列检验数若新表中基向量改变了单位向量的形式包括该列检验数 不再为不再为0

6、）, 则用换基运算恢复基向量为单位向量包括该列则用换基运算恢复基向量为单位向量包括该列 检验数也须化为检验数也须化为0）；否则转）；否则转3。3这时新表中解列的数据这时新表中解列的数据b与检验矢与检验矢 有以下四种可能情况：有以下四种可能情况： 若若b0且且 0，则当前解即最优解，停止运算；，则当前解即最优解，停止运算； 若若b0但但 0，则用单纯形法继续迭代；，则用单纯形法继续迭代； 若若b0而而 0，则用对偶单纯形法继续迭代；，则用对偶单纯形法继续迭代； 若若b0且且 0，则用交替单纯形法继续迭代。，则用交替单纯形法继续迭代。 基本程序基本程序4.3 灵敏度分析的程序灵敏度分析的程序b1*

7、b2*b3*w* 2/3 -1/30 1/2 00 -2/3 1/30 1/2 11212-448= 82436=cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0 x3x2x1 05 3 6 0 1 0 1/2 0 4 0 0 1 2/3 -1/3 4 1 0 0 -2/3 1/342 0 0 0 1/2 14.3 灵敏度分析的程序灵敏度分析的程序 cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0 x3x2x1 05 3 6 0 1 0 1/2 0 4 0 0 1 2/3 -1/3 4 1 0 0 -2/3 1/342 0 0 0 1/2 1-2/3 -2/

8、3 x3x2x4 05 0 6 -3/2 0 0 1 -1/2 9 3/4 1 0 0 1/4 8 1 0 1 0 045 3/4 0 0 0 5/4X*= (0, 9, 8, 6, 0)T, z* = 451212-4484.3 灵敏度分析的程序灵敏度分析的程序 例例4 因表中基列没有因表中基列没有x1，即，即x1=0，这表明不生产甲产品故工厂，这表明不生产甲产品故工厂决策者考虑决策者考虑: 若改革甲产品的生产工艺，能减少一个若改革甲产品的生产工艺，能减少一个C工时工时/件件, 从而增加其利从而增加其利润润0.5百元百元/件件, 则能否导致重新安排甲产品的生产？则能否导致重新安排甲产品的生产

9、？ 解解 : 非基变量的系数变为：非基变量的系数变为：123= (1, 0, 2)T1*= (0,0,5/4) - = -1 0102123a1* =1 0 00 0 1/40 1 -1/2 11/2-1102=4.3 灵敏度分析的程序灵敏度分析的程序x3x2x4 05 0 6 -3/2 0 0 1 -1/2 9 3/4 1 0 0 1/4 8 1 0 1 0 045 3/4 0 0 0 5/4 x1 x2 x3 x4 x5cj解解 基基 3 5 0 0 0 11/2 -1-1-13.501x1x2 x4 3.5 5 0 8 0 0 1 1 -1/28 1 0 1 0 05 0 1 -1/2

10、0 1/453 0 0 1 0 5/4(a)4.3 灵敏度分析的程序灵敏度分析的程序 例例5 承例承例4。假定还有一种新产品丙。假定还有一种新产品丙, 每件消耗每件消耗A，B，C工时数分别为工时数分别为 1，1.5，1 , 利润为利润为3百元百元/件。则在现有生产能件。则在现有生产能力下，是否安排生产丙产品？力下，是否安排生产丙产品？ 解解 设丙产品产量为设丙产品产量为 x6 件，这时原最优单纯形表为表件，这时原最优单纯形表为表4-5 (b)，且知，且知c6 = c6 = 332a6 = a6 = (1， ，1)6*= (1, 0, 5/4) - 3 = -3/4 0 13/2 1 1 0 0

11、-1/2 0 1/4 1 1 -1/2 1-1/4 2 13/2 1=4.3 灵敏度分析的程序灵敏度分析的程序x1x2x4 3.55 0 8 0 0 1 1 -1/2 5 0 1 -1/2 0 1/4 8 1 0 1 0 053 0 0 1 0 5/4 x1 x2 x3 x4 x5cj解解 基基 3.5 5 0 0 0 1-1/4 2-3/4-3/4x1x2 x6 3.5 5 3 4 0 0 1/2 1/2 -1/4 14 1 0 1/2 -1/2 1/4 08 0 1 -3/8 1/8 3/16 056 0 0 11/8 3/8 17/16 04.3 灵敏度分析的程序灵敏度分析的程序=1 2

12、/3 -1/30 1/2 00 -2/3 1/3 11211/20=1* = (Y*)Ta1 -c1112= (0,1/2,1) - 4 = - 3/2 a1*= B-1a14.3 灵敏度分析的程序灵敏度分析的程序x3x2 x5 050 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 x1x2x5 4 5 0 12 0 0 0 -2 142 0 0 3/2 5/2 0 8 1 0 1 0 0 2 0 1 -1/2 1/2 01 cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0 0 0 1 2/3 -1/3

13、x3x2 x1 4 6 4 0 1 0 1/2 0 0 5 3 1 0 0 -2/3 1/3 42 0 0 0 1/2 11/3411/20-3/2-3/2 4 X*= (8,2)Tz* = 424.3 灵敏度分析的程序灵敏度分析的程序 若用丁取代甲，则把 x1 改为丁的日产量。 a1* = B-1a1 =1 2/3 -1/30 1/2 00 -2/3 1/3 2024/3 02/3=1* = (Y*)Ta1 -c1 = (0,1/2,1) - 4 = - 22024.3 灵敏度分析的程序灵敏度分析的程序 cj 基基 解解 x1 x2 x3 x4 x5 3 5 0 0 0 0 0 1 2/3

14、-1/3x3x2 x1 4 6 4 0 1 0 1/2 0 0 5 3 1 0 0 -2/3 1/3 42 0 0 0 1/2 1444/3 02/3- - 2 22/3x3x2 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 2x5x2x1 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/2 0-1-1X*= (4, 6)Tz* = 464.3 灵敏度分析的程序灵敏度分析的程序 例例7 7 试确定范例试确定范例LPLP原型中参数原型中参数

15、a32a32的影响范围。的影响范围。 解解: : 设设a32a32发生的变化发生的变化, , 那么那么“优表中相应的增量为优表中相应的增量为: := 1 2/3 -1/3 0 1/2 0 0 -2/3 1/3 0 1/2 1-1/3 01/3 a12*a22*a32*2*把它加给把它加给“优表中的优表中的a2列列, 得得= 0 0 4.3 灵敏度分析的程序灵敏度分析的程序x3x2 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 042-6 0 0 0 1/2 - 1/2 1x3x2x1 05 3 4 1

16、0 0 -2/3 1/3 4 0 0 1 2/3 -1/3 42 0 0 0 1/2 1 x1 x2 x3 x4 x5cj解解 基基 3 5 0 0 0 6 0 1 0 1/2 0- -1/31/31 1 1/31/314.3 灵敏度分析的程序灵敏度分析的程序由表可见：若要保证当前解为最优，必须满足：由表可见：若要保证当前解为最优，必须满足： 解得解得 -2 a32 1因因 a32 原值为原值为4, 故故 a32 4 -2,4 +1 = 2, 5 4 + 2 0 4 - 2 0 - 04.3 灵敏度分析的程序灵敏度分析的程序 例例8 考虑范例。若该厂对甲、乙产品又增加用电不超过考虑范例。若该厂

17、对甲、乙产品又增加用电不超过24百度的限制，而每件甲、乙产品分别耗电百度的限制，而每件甲、乙产品分别耗电2、3百度，则原最优百度，则原最优生产方案是否需要改变？生产方案是否需要改变？ 解：这意味着增加一个约束：解：这意味着增加一个约束： 把最优解把最优解 X*= (4, 6)T 代入上式左端：代入上式左端：24 + 36 = 26 24 故最优解必然改变。故最优解必然改变。 cj 基基 解解 x1 x2 x3 x4 x5 x6 3 5 0 0 0 0 0 0 1 2/3 -1/3 0 x3x2 x1 x6 4 6 4 0 1 0 1/2 0 0 0 5 3 0 1 0 0 -2/3 1/3 0 42 0 0 0 1/2 1 0 24 2 3 0 0 0 11 1x3x2 x1 x6 0 5 3 0 4 6 4 0 0 1 2/3