灵敏度分析_61402320

1、第四节第四节 灵敏度分析（优化后分析）灵敏度分析（优化后分析）一、参数的可变性一、参数的可变性 (cj ,bi ,aij)二、灵敏度分析的内容二、灵敏度分析的内容1、参数的变化对原最优解有什么影响？原最优解是否、参数的变化对原最优解有什么影响？原最优解是否 仍为最优解。仍为最优解。2、参数在什么范围变化时，原最优解保持不变？、参数在什么范围变化时，原最优解保持不变？3、当原最优解已不再最优时，应如何利用原单纯形表，、当原最优解已不再最优时，应如何利用原单纯形表， 以最简捷的方法求得新的最优解。以最简捷的方法求得新的最优解。三、最优性分析三、最优性分析最优性（对偶可行）可行性 0 011CABC

2、bBB一、价值系数向量一、价值系数向量c的变化的变化设设(L)的最优解为的最优解为xB=B-1b, xN=0, fmin=cBB-1b min. .0cxLstAxbx1、非基变量、非基变量xk的系数的系数ck改变为改变为ck考虑检验数：考虑检验数：zj-cj=cBB-1Pj-cj j为非基变量下标为非基变量下标11,000jjBjjjjkkBkkkkkkkkkkkjkzcc B Pczczcc B PczccczcBzcx若有若，则 仍为最优基；若，改变后 为进基变量。 在原单纯形表中将在原单纯形表中将zk-ck换成换成zk-ck, 然后在然后在原表中用单纯性法求新问题的解。原表中用单纯性法

3、求新问题的解。2、基变量、基变量xr的系数的系数cr改变为改变为cr=cr+cr1111111,00;0000jjBjjBBjjBjjBjjjjjBjjjjjjjrjjjrrjrrrrrjrrrrBBBBzccB PcccB Pcc B Pcc B Pcczcc yccjrzczccyzcc yzczccyccccccB bc B bc B bc若有目标函数值1BrrB bc bcr变为变为cr 后，只要把原单纯形表中后，只要把原单纯形表中xr所在的行乘以所在的行乘以(cr-cr)加到加到判别数行，并使判别数行，并使xr对应的判别数为对应的判别数为0，既可用单纯形法继续做下去。，既可用单纯形法

4、继续做下去。12312312min2 4 326 0 1,2,3jxxx s.t xxxxxxj例：引入松弛变量引入松弛变量x4，得它的最优单纯形表为，得它的最优单纯形表为x1 x2 x3 x4x2x41 1 1 05 0 2 1 -3 0 -3 0414-81. c3由由1变为变为-3时时x1 x2 x3 x4x2x41 1 1 05 0 2 1 -3 0 -3 0414-8由于由于z3-c3=cBB-1P3- c3 =z3-c3+(c3- c3)=-3+(1+3)=1x1 x2 x3 x4x2x41 1 1 05 0 2 1 -3 0 1 0414-81 1 1 03 -2 0 1-4 -

5、1 0 0 x3x446-12min*0, 0, 4, 612Txf 问题：问题：c3在什么范围变化时，最优解不变？在什么范围变化时，最优解不变？rrrccc令1rBrrc B Pc则1Brrrc B Pccrrc若要保持最优性不变若要保持最优性不变00rrrrrcc 则一般情况：一般情况：2. c2由由-2变为变为3, 此时此时 c2 =3-(-2)=5x1 x2 x3 x4x2x41 1 1 05 0 2 1 -3 0 -3 0414-8x1 x2 x3 x4x2x41 1 1 05 0 2 1 -3+5 0 -3+5 0414-8+201 1 1 03 -2 0 10 -2 0 0 x3

6、x4464min*0, 0, 4, 64Txf问题：问题：c2在什么范围变化时，最优解不变？在什么范围变化时，最优解不变？二、改变右端向量二、改变右端向量b设设bb,设改变前的最优基为设改变前的最优基为B。111111111min1min1.0,0BNBBBBBB bbbbxB bBbbB bBbxfc B bc Bbbc B bc Bbfc Bb此时，原来的最优基仍为最优基，但基变量的取值、目标函数最优值将发生变化。设则二、改变右端向量二、改变右端向量b设设bb,设改变前的最优基为设改变前的最优基为B。1112.00BB bB bc B b。 此时，原来的最优基对于新问题来说，不再是可行的，

7、但由于所有的判别数，所以是对偶可行的，此时，只要把原问题最优表的右端列加以修改，代之以，就可用对偶单纯性法求解新问题。例：某工厂在计划期内要安排生产两种产品，已知生产例：某工厂在计划期内要安排生产两种产品，已知生产单位产品所需的设备台时及单位产品所需的设备台时及A、B两种原材料的消耗为：两种原材料的消耗为：产品产品1 产品产品2设备设备原材料原材料A原材料原材料B1 24 00 48台时台时16kg12kg该工厂每生产一件产品该工厂每生产一件产品1可获利可获利2元，每生产一件产品元，每生产一件产品2可获利可获利3元，问应如何安排计划，使该工厂获利最多？元，问应如何安排计划，使该工厂获利最多？

8、121212max 23 28 416412 0 1,2jxx s.t xxxxxj121231425min23 28 416412 0 1,2,3,4,5jxx s.t xxxxxxxxj最优表为：最优表为：x1 x2 x3 x4 x5x1x5x21 0 0 1/4 00 0 -2 1/2 10 1 1/2 -1/8 00 0 -3/2 -1/8 0442-14max*4, 214Txfx1 x2 x3 x4 x5x1x5x21 2 1 0 04 0 0 1 00 4 0 0 12 3 0 0 0816120若该厂又从别处抽出若该厂又从别处抽出4台时用于生产产品台时用于生产产品1和和2，求这

9、时该厂生产产品求这时该厂生产产品1和和2的最优方案。的最优方案。 11111110044012108202110284044842240142 038202BBBbB bB bBbfc B bc Bb x1 x2 x3 x4 x5x1x5x21 0 0 1/4 00 0 -2 1/2 10 1 1/2 -1/8 00 0 -3/2 -1/8 04-44-20 x1x3x21 0 0 1/4 00 0 1 -1/4 -1/20 1 0 0 1/40 0 -1/2 -3/4 0423-17-2max*4,3, 217Txf问题：问题：b1在什么范围变化时，最优基不变？在什么范围变化时，最优基不变？

10、3、一般情况、一般情况 rrrbbb设111,.,., TBrrmxB bBbbbb11( ,.,.,)(0,.,.,0)TTrmrBbbbb110,.,.,00TrB bBb-11 ()()0 1,.iirriB bBbim对任意1)iiB bb令（11)0, ()iirrirbBb B 当（ ）11)0, ()iirrirbBb B 当（ ）0)()(min0)()(max1111iriririririBBbbBBb三改变约束矩阵三改变约束矩阵A1. 非基列非基列PjPj，影响，影响yj= =B-1 1Pj及及zj- -cj12312312min2 4 326 0 1,2,3jxxx s.

11、t xxxxxxj最优表为：最优表为：x1 x2 x3 x41 1 1 05 0 2 1-3 0 -3 0 x2x4414-8x1 x2 x3 x41 1 1 03 -2 0 10 3 0 0 x3x4464max*0, 4, 0,148Txf x1 x2 x3 x41 1 1 05 0 2 1-3 0 -3 0 x2x4414-81111112,3110220150211BPPc B Pc 若则所以，最优基、最优解保持不变。所以，最优基、最优解保持不变。max*0, 4, 0,148Txf x1 x2 x3 x41 1 1 03 -2 0 10 3 0 0 x3x4464x1 x2 x3 x

12、41 1 1 05 0 2 1-3 0 -3 0 x2x4414-81111111112,311022013021110222113BPPc B PcyB P 若则x1 x2 x3 x4-2 1 1 0-3 0 2 13 0 -3 0 x2x4414-8无界！无界！一般的，当非基列一般的，当非基列PjPj， 若若zj-cj0，则原最优解也是新问题的最优解。，则原最优解也是新问题的最优解。 若若zj-cj 0，则把，则把yjyj, zj-cj zj-cj 迭代。迭代。 2. 基列基列PjPj重新计算重新计算四增加新的约束四增加新的约束 min. .0cxLstAxbx增加新的约束：增加新的约束：

13、1111mmmPxbPn为阶向量1. 若原最优解满足新增加的约束，则它也是若原最优解满足新增加的约束，则它也是新问题的最优解。新问题的最优解。 11min. .0mmcxstAxbLPxbx2. 若原最优解不满足新增加约束若原最优解不满足新增加约束设原问题最优基为设原问题最优基为B，则有，则有1111111min. .,0BBNmmBNNnmncxstxB NxB bLPxPxxbx xxB xN xn+1I B-1N 0111mmBNPP0 cBB-1N-cN 0B-1bbm+1cBB-1b11111111111111111100,11010mmBBBmmmnmBBBBBBBBBPPBxbB

14、 bBBbbxbPB bPBfc BbcBbc B bxB xN xn+1I B-1N 011101mmNBPPB N0 cBB-1N-cN 011111mmBBB bbPB bc B b12312312min2. .43260,1,2,3ixxxstxxxxxxi引入松弛变量引入松弛变量x4，得最优表，得最优表x1 x2 x3 x41 1 1 05 0 2 1-3 0 -3 0 x2x4414-8增加新约束：增加新约束：12322xxx max*0, 4, 0,148Txf x1 x2 x3 x41 1 1 05 0 2 1-3 0 -3 0 x2x4414-8引入松弛变量引入松弛变量x5x

15、1 x2 x3 x4 x51 1 1 0 05 0 2 1 0-3 0 -3 0 0 x2x4x5414-2-8-1 1 2 0 11 1 1 0 05 0 2 1 0-3 0 -3 0 0 x2x4x5414-6-8-2 0 2 0 10 1 3/2 0 1/20 0 9/2 1 5/2-3 0 -3 0 0 x2x4x11-1311 0 -1/ 2 0 -1/2无可行解！无可行解！-212312312 min1016 s.t 222 4 LPzxxxxxxxx 练习题一个问题为 0,1,2,30,10 2jxjLP其中求：）当时，求解上述问题；） 在什么范围内变化，原问题的最优性不变。有两

16、个有两个LP问题如下：问题如下： min(1) 0zcxLPAxb xmin(2) 0 (0,0)zcxLPAx b x分析分析LP1与与LP2最优解之间的关系。最优解之间的关系。*12,12x xLPLP设为、的最优解*111 0 () 0BxB bBc B Ac则为最优基*111 0,0 0 ()0BxB bc B Ac*111 0 0BxBbc B Ac即：（）*21 2 BLP xx得：也是的最优基*21zz企业生产计划企业生产计划 奶制品的生产与销售奶制品的生产与销售 空间层次空间层次工厂级：根据外部需求和内部设备、人力、原料等工厂级：根据外部需求和内部设备、人力、原料等条件，以最大

17、利润为目标制订产品生产计划；条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划用参数等，以最小成本为目标制订生产批量计划.时间层次时间层次若短时间内外部需求和内部资源等不随时间变化，可若短时间内外部需求和内部资源等不随时间变化，可制订制订单阶段生产计划单阶段生产计划，否则应制订多阶段生产计划，否则应制订多阶段生产计划.本节课题本节课题例例1 加工奶制品的生产计划加工奶制品的生产计划1桶桶牛奶牛奶 3公斤公斤A1 12小时小时 8小时小时 4公斤公斤A2 或或获利获利24元元/

18、公斤公斤 获利获利16元元/公斤公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到的获利增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？ 每天：每天：问问题题1桶桶牛奶牛奶 3公斤公斤A1 12小时小时 8小时小时 4公斤公斤A2 或或获利获利24元元/公斤公斤 获利获利16元元/公斤公斤

19、x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 216472xxzMax每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天基本基本模型模型模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx约约束

20、束条条件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目标目标函数函数 Z=0Z=2400Z=3600z=c (常数常数) 等值线等值线c在在B(20,30)点得到最优解点得到最优解模型求解模型求解 软件实现软件实现 LINDO 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.00

21、0000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生产桶牛奶生产A1, 30桶生产桶生产A2，利润，利润3360元。元。 结果解释结果解释 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000

22、 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源” 剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束） 原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40结果解释结果解释 OBJECTIVE FUNCTION VA

23、LUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增的增量量 影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗桶牛奶，要买吗?35 48, 应该买！应该买！ 聘用临时工人付出

24、的工资最多每小时几元聘用临时工人付出的工资最多每小时几元? 2元！元！原料增加原料增加1单位单位, 利润增长利润增长48 时间增加时间增加1单位单位, 利润增长利润增长2 加工能力增长不影响利润加工能力增长不影响利润RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHT

25、HAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000最优解不变时目标函最优解不变时目标函数系数允许变化范围数系数允许变化范围 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系数范围系数范围(64,96) x2系数范围系数范围(48,72) A1获利增加到获利增加到 30元元/公斤，应否改变生

26、产计划公斤，应否改变生产计划? x1系数由系数由24 3=72增加增加为为30 3=90，在在允许范围内允许范围内 不变！不变！(约束条件不变约束条件不变)结果解释结果解释 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW

27、CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围 原料最多增加原料最多增加10 时间最多增加时间最多增加53 35元可买到元可买到1桶牛奶桶牛奶, 每天最多买多少每天最多买多少?最多买最多买10桶桶!(目标函数不变目标函数不变)例例2 奶制品的生产销售计划奶制品的生产销售计划 在例

28、在例1基础上深加工基础上深加工1桶桶牛奶牛奶 3公斤公斤A1 12小时小时 8小时小时 4公斤公斤A2 或或获利获利24元元/公斤公斤 获利获利16元元/公斤公斤 0.8公斤公斤B12小时小时,3元元1公斤公斤获利获利44元元/公斤公斤 0.75公斤公斤B22小时小时,3元元1公斤公斤获利获利32元元/公斤公斤 制订生产计划，使每天净利润最大制订生产计划，使每天净利润最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，应否投小时时间，应否投资？现投资资？现投资150元，可赚回多少？元，可赚回多少？50桶牛奶桶牛奶, 480小时小时 至多至多100公斤公斤A1 B1，B2的

29、获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？1桶桶牛奶牛奶 3kg A1 12小时小时 8小时小时 4kg A2 或或获利获利24元元/kg 获利获利16元元/kg 0.8kg B12小时小时,3元元1kg获利获利44元元/kg 0.75kg B22小时小时,3元元1kg获利获利32元元/kg 出售出售x1 kg A1, x2 kg A2， x3 kg B1, x4 kg B2原料原料供应供应 劳动劳动时间时间 加工能力加工能力 决策决策变量变量 目标目标函数函数 利润利润约束约束条件条件非负约束非负约束 0,61xx x5 kg A1加工加工B1， x6 kg

30、 A2加工加工B26543213332441624xxxxxxzMax50436251xxxx48022)(2)(4656251xxxxxx10051 xx附加约束附加约束 5380 x.x64750 x.x 基本模型基本模型模型求解模型求解 软件实现软件实现 LINDO 6.1 5043) 26251xxxx48022)(2)(4)3656251xxxxxx OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200

31、001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2600334) 26521xxxx44804624) 36521xxxxDO RANGE (SENSITIVITY) ANALYSI

32、S? No OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5)

33、0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2结果解释结果解释每天销售每天销售168 kgA2和和19.2 kgB1， 利润利润3460.8（元）（元）8桶牛奶加工成桶牛奶加工成A1，42桶牛奶加工成桶牛奶加工成A2，将得到的将得到的24kgA1全部全部加工成加工成B1 除加工能力外除加工能力外均为紧约束均为紧约束结果解释结果解释 OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.