【精品】【公务员考试】灵敏度分析（可编辑.ppt

《【精品】【公务员考试】灵敏度分析（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】【公务员考试】灵敏度分析（可编辑.ppt（110页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【公务员考试】灵敏度分析 当线性规划问题中的一个或几个参数变化时可以用单纯形法从头计算，看最优解有无变化但这样做既麻烦又没有必要。因为单纯形法的迭代计算是从一组基向量变换为另一组基向量，表中每步迭代得到的数字只随基向量的不同选择而改变，因此可把个别参数的变化直接在计算得到最优解的单纯形表上反映出来。这样就不需要从头计算，而直接对计算得到最优解的单纯形表进行审查，看一些数字变化后，是否仍满足最优解的条件，如果不满足的话，再从这个表开始进行迭代计算，求得最优解。1.灵敏度分析的基本原理 maxZ=CX;AX=b;(LP)s.t.X0.对于选定的基B，不妨设 B=(P 1,P 2,P m).将问题（

2、LP）化为关于基B的典式 maxZ=CBB-1b+(CN CBB-1N)XN;XB +B-1NXN =B-1b;s.t.XB,XN 0.列出单纯形表 基本解 X=XB =B-1b 是最优解的条件是 XN 0 XB=B-1b 0 （1）称为(原始原始)可行性条件可行性条件 N=CN CBB-1N0 （2）称为(原始原始)最优性条件最优性条件 在实际问题中，下面这些数据或条件是会经常发生变化的：(1)目标函数系数cj的变化；(2)右端常数b的变化；(3)消耗系数aij的变化(包括增加新增变量和增加新的约束条件)灵敏度分析是：(1)为了保持现有的最优解或最优基不变，找出这些数据变化的范围即所谓数据的

3、稳定性区间 (2)当这些数据的变化超出了(1)的范围时，如何在原有最优解或最优基的基础上，作微小的调整，尽快求出新的最优解或最优基 由表可以看出，某些数据只和表中的某些块有关，因而当这些数据发生变化时，只需对上表中的某些块进行修改，便可得到新问题的单纯形表，从而能够进行判别和迭代，而不必从头开始计算线性规划问题，这正是单纯形法的优点之一 下面分别讨论这些变化对最优解或最优解的影响XB=B-1b 0 （1）N=CN CBB-1N0 （2）2.基变量xj的价值系数cj的变化某基变量xr的价值系数cr 改变为cr=cr+cj，因cr CB，则(CB+CB)B-1A=CB B-1A+(0,cr,0)B

4、-1A=CBB-1A+cr(ar1,ar2,ar n)其中(ar1,ar2,ar n)是矩阵B-1A的第r行变化后的检验数为：j=cj CBB-1Pj crarj=j crarj（j=1，2，n）。若要最优解不变，则必须满足，即 j=j crarj 0（j=1，2，n）。由此导出当arj0时，有crj/arj；当arj0时，有crj/arj；因此，c允许变化范围是 j j max arj 0 cr min arj0 cr min arj17/4已经超出了c1的变化范围，最优解要变。新的最优解可用下面的方法求得。首先求出新的检验数 1/4 1=c1 CBB-1P1=5 （0，4，5，）2 =3/

5、4 0故x1应进基。-3/4用新的检验数 1=3/4代替原来的检验数1=1 3/4，其余数据不变，得新的单纯形表,并继续迭代得表。求得新的最优解 X*=(100,175,0,0,75)T 及新的目标函数最优值Z*=1375.例例 巳知线性规划问题用单纯形法求解得最终单纯形表如表所示maxZ=2x1+x2 5x215;6x1+2x224;s.t.x1+x25;x1,x2,0.试确定：(1)当目标函数变为Max z5x11.5x2时最优解会出现什么变化；(2)目标函数变为maxz(21)x1x2时，1在什么范围内变化，最优解不变。原最优解解解(1)将目标函数系数的变化直接反映到最终单纯形表中表中变

6、量x5的检验数为正，继续迭代计算得下表(1)当目标函数变为Max z5x11.5x2时替换原表数据得即新的解为xl4，x20 (2)目标函数变为maxz(21)x1x2时 原最优解原表目标函数变为 maxz(21)x1x2时 将目标函数系数的变化直接反映到最终单纯形表中，见下表所示。即有为使表中解为最优应有替换原表数据得二、约束方程右端常数灵敏度分析由于XB=B-1b，Z=CBB-1b 右端常数b的变化,会影响到原最优解的可行性与目标函数值。XB=B-1b 0 （1）N=CN CBB-1N0 （2）设某一个右端常数变为brbr十br，并假设原问题中的其它系数不变，则使最终表中原问题的解相应地变

7、为 0 .XB=B-1(b+b)=B-1b+B-1b=B-1b+B-1 br .0 b1 a1rbr b1+a1rbr.=bi +airbr =bi+airbr .bm amrbr bm+amrbrXB=B-1b 0 b1 a1rbr b1+a1rbr.XB=bi +airbr =bi+airbr .bm amrbr bm+amrbr 其中（a1r，a2r，amr）T为逆矩阵B-1中的第r列。若要求最优基B不变，则必须XB0,即 bi+airbr 0 (i=1,2,m).由此可以导出 当air 0时,有br-bi/air;当air 0 br min -air 0 br min-air 0即可得

8、出投产有利的结论 前例中，若增加一个变量x6，有c63，P6(3，4，2)T，试 分析最优解的变化。解：原最优解例原表 将其反映到最终单纯形表中，得6=c6YP6 3 =3-（0，1/4，1/2）4 2 1 5/4 -15/2 3 7P6 =B-1P6=0 1/4 -1/2 4 =0 0 -1/4 3/2 2 2=1 0原最优解因620，故用单纯形法继续计算得表由此新的解为即X1=7/2，X6=3/4，Z=27/2+33/4=37/4 2.增加新约束条件的灵敏度分析 增加一个约束条件，在实际问题中相当于增添一道工序。分析的方法是先将原来问题的最优解变量取值代入这个新增的约束条件中，如满足说明新

9、增约束末起到限制作用，原最优解不变。否则，将新增约束直接反映到最终表中再进行分析。若在原线性规划问题中，再增加一个新的约束条件 am+1,1x1+am+1,2x2+am+1,nxnbm+1 其中am+1,j(j=1,2,n)及bm+1均为已知常数，则首先把已求得的原问题的最优解 X=(x1,x2,xn)T 代入新增加的约束条件，如果满足，则问题的最优解X仍为新问题的最优解，计算停止。如果不满足，则将新的约束条件加入系统，继续求解 例例 设在前例中增添一个约束条件3x12x212，试分析最优解的变化。解解 先将原问题最优解变量值代入，因有 3 7/2+23227212 不满足 故将约束条件写成

10、3x12x2+x612 并取x6为基变量，直接反映到原最终单纯形 表中原最终单纯形表maxZ=2x1+x2 5x215;6x1+2x224;s.t.x1+x25;x1,x2,0.原最终单纯形表3x12x2+x612 增加一行一列加入将x1、x2所在列转化为单位向量，即作线性变换 为使x1、x2列系数变换为单位向量，对表进行变换。新表中 行同原表数值不变，新表中第行由以下初等变换得到 32 即作线性变换后得用对偶单纯形法迭代计算用对偶单纯形法迭代计算得表由表知新的最优解为x14，x20，z*248四、技术系数的灵敏度分析（一）个别技术系数的的变化根据变动的系数aij处于矩阵A中的哪一列又可分为两

11、种情况来考虑：aij处于非基变量列中；aij处于基变量列中 1.非基变量aij的系数列向量Pj的变化若对于最优基而盲，非基变量xj的系数列向量Pj改变为Pj=Pj十Pj 则变化后的检验数为 jcjCBB-1Pj=cj CBB-1(Pj+Pj)=jYPj，(j1，n）其中Y CBB-1为对偶可行解要使原最优基保待不变，则必须j 0，即 YPj j(j1，2，m)特别，当Pj(0，aij，0)T时，则可得 2基变量aij的系数列向量Pj的变化 对于最优基B而言，当基变量xj的系数列向量Pj发生变化时，对基及其逆矩阵B-1都有影响，即不仅影响现行最优解的可行性，也影响到它的最优性这种情况建议按具体的

12、最优化表格进行分析 0 .(y1 yi ym)aij yi aij j 0由此可以导出 当yi 0时,有aij j/yi;当yi 0,y30.故 a211/y2=(-13/4)/（1/4）=-13,a311/y3=(-13/4)/1=-13/4;a233/y2=(-11/4)/（1/4）=-11;a333/y3=(-11/4)/1=-11/4.1 1(2)当x3的系数由P3=3 变为 4 时 5 1原最优解maxZ=x1+5x2+3x3+4 x4;2x1+3x2+x3 2 x4 800;5x1+4x2+3x3+4 x4 1200;3x1+4x2+5x3+3 x4 1000;xj 0(j=1.2

13、.3.4)或Y=（0，1/4，1）检验数 13=c3-CBB-1P3=3-（0，-1/4，-1）4 =10。-1故取x3为进基变量再计算 1 1/4 -1 1 1P3=B1P3 =0 1 -1 4 =3 0 -3/4 1 1 -2 1P3=3 -2用P3去替换前最优表中的第3列继续迭代得最优解及最优值Z*41003得表原最优表新表继续迭代。求得最优解 X*=（0，700/3，200/3，0，100/3，0，0）T及最优值Z*=4100/3 在例1中，若基变量x2的技术系数列向量由P2=（3，4，4）T变为P2=（4，5，6）T，而它的目标函数中的系数由c2=5变为c2=6。试求变化后的最优解。

14、解解 为便于利用最优表进行分析，首先要计算在最优表中对应于x2的列向量 1 1/4 -1 4 -3/4 B-1P2.=0 1 -1 5 =-1 0 -3/4 1 6 9/4同时计算出x2的检验数 -3/4 2=c2-CBB-1P2=6-（0，4，6）-1 =-7/2 9/4 注意，由于数据发生变化，在最终表上，原基变量x2的系数列向量不再是单位列向量，检验数2 也不再为0。但如果我们仍然想保持原最优基不变，即还把 x2作为基变量看待，则须将以上计算结果填入最终表x2的列向量位置，得表 这 并不是一个正规的单纯形表，因为没有单位矩阵I。为了得到一个单位短阵，注意到x 2仍为第3个基变量，故必须将

15、x 2所在列变成单位列向量，同时将2一72变为0，即以a32 94为主元进行矩阵的初等变换(这种变换没有换基，x 2仍为基变量)，得表原最优解将 -3/4 B-1P2.=-1 9/42=-7/2 代入得新的最优解 X*B=（0，400/9，0，2200/9，400/3，0，0）T目标函数最优值 Z*=11200/9 例如：11/2（11/9）（7/2）11/9解*假如xij在最终表中为基变量，则aij的变化将使最终表中的B1变 化，因此有可能出现原问题与对偶问题均为非可行解的情况。若基变量系数的变化导致原始可行性条件和对偶可行性条件均被破坏，即产生了对原问题和对偶问题均为非可行性解时，这就需要

16、引入人工变量重新求解。例 若在前例中c23，x2的系数向量变为P2(8，4，1）T，试分析最优解的变化。先将其作为一个新的变量x2列入最终单纯形表中，见表 8 2=3（0，1/4，1/2）4 =3/2 1 1 5/4 -15/2 8 11/2P2=0 1/4 -1/2 4 =1/2 0 -1/4 3/2 1 1/2maxZ=2x1+x2 5x215;6x1+2x224;s.t.x1+x2 5;x1,x2,0.原最优解替换后 因表中原问题与其对偶问题均为非可行解，由前表知，通过引进入工变量原问题转化为可行解，再用单纯形法继续计算。上表的第一行可写成 X3十4X424x5一9 因右端项为负值，故先

17、将等式两端乘“1”，再加上人工变量x6得 一X34x4十24x5十x69 将上式替换上表的第一行，得表用单纯形法迭代计算得表由表知，新的最优解为X1=11/4，X2=15/8，Z=211/4+315/8=89/8 已知线性规划问题 的最优单纯形表试分别就下列情况进行灵敏度分析，并求新的最优解：（1）b295 例maxZ=5 x1+5x2+1 3x3 x1+x2+3x3 20;12 x1+4x2+10 x3 90;xj 0(j=1.2.3)(2)第1个约束条件的右端常数变为61；45(3)目标函数中岛的系数变为Q；8；(4目标函数中均的系数变为263(5)变量cI的系数(包括目标函数)变为 卜1

18、 卜g 卜j(6)变量c，的系数(包括目标函数)变为(7)增加一个新变量x，其系数为(8)tB加一个新约束条件2A十3A代A50l(9)策2个约束条件变为10A十422十12，考I oo4。s 51，2l，5J（1）b295 解 因为 max(一10/1)b2 min(20/0)即 一10b2 现b295905未超出上述范围，故最优基及不变，新的最优解为 bi bi max-air 0 br min-air 0 br min-air 0 cr min arj0 .j arj j arj 序号C-561300CBXBbx1x2x3x4x5I 60 x2x52010-116*103-21-401Z

19、-12010-5-60 6-5x5x1165/85/8011023/8-1/83/4-1/41/161/16Z-965/800-39/8-23/4-1/16由表2（）可知新的最优解为 X*=(5/8,165/8,0,0,0)T及最优值Z*=965/8.表2（5）非基变量的系数变化仅影响最优性故应重新计算x1的检验数 1=c1 CBB-1P1 1 0 0 =2(5,0)=2 0,-4 1 5 所以原最忧解X*(0，20，0，0，10)T不变(6)基变量的系数变化既影响解的可行性，又影响解的最优性.为了便于利用最优表进行分析，首先要计算在最终表中对应于x2的列向量 1 0 2 2 B-1P2=-4

20、 1 5 -3 及相应的检验数 2 2=c1 CBB-1P2=6 (6,0）=6。-3 将上述数据替换原表的第2列，得表3(I).表4.13()C-561300CBXBbx1x2x3x4x560 x2x52010-1162-33-21-401Z-1201-6-5-60由于表3()没有单位矩阵,故应将x2所在的列向量变为 1单位列向量 0 ，得表3（II）。0序号C-561300CBXBbx1x2x3x4x5I 60 x2x51040-1/245/2103/25/21/2-6/201Z-60-204-30 130 x3x520/370/3-1/370/32/3-5/3101/3-10/301Z-

21、260/3-2/3-8/30-13/30表3（）由表3（）再迭代一次，得表3（），则已求得最优解 X*=(0,0,20/3,0,70/3)T及最优值Z*=260/3.(7)增加一个新变量x6以后，应首先求 1 0 3 6c6 CBB-1P610一(5,0)一50，-4 1 5 故原最优解x(0，20，0，0，10)T不变(8)增加一个新约束条件2x1十3x2十5x350，首先将现有最优解X*(0，20，0，0，10)T不变。代入该条件可知，X*不满足新的约束条件故应将新的约束条件添加松弛变量x6后加到原最优表中，继续迭代（见表4）。序号C-5513000CBXBbx1x2x3x4x5x6I 5

22、00 x2x5x6201030-11621033-251-40010001Z-10000-2-500 500 x2x3x62010-10-11651003-2-4*1-4-3010001Z-100-160-2-500 5013x2x5x325/2155/211/427/2-5/4100001-5/4-5/2010-1/2-1/4Z-95-5/200-7/20-1/2表4由表4（III）可知以求得最优解 X*=(0,25/2,5/2,0,15,0)T及最优值 Z*95(9)第2个约束条件变为 10 x1+4x2+12x3 100.相当于改变了a12,a23和b2 这时应首先计算 1 0 1 1c

23、1 CBB-1P1 5 (5,0)0;4 1 10 1 0 3 3c3 CBB-1P313 (5,0)=2 0,4 1 12 故最优性仍保持,再计算 x2*1 0 3 20 XB*=B-1b =x5*4 1 12 20 即新的最优解为 X*=(0,20,0,0,20)T 及最优值 20 Z*=CB XB*=(5,0）=100。20例 某汽车制造厂生产越野车、小型货车和卡车决定该厂产量的主要是人力。汽车生产三个主要工序是铸造、压力加工和装配涂漆。该厂能够支配的这三方面人力有限。下表列出了三种车辆生产需要的各工序工时、可支配工时以及各种车辆单位销售利润。问：三种车辆各生产多少，方使该厂获利最大?现

24、假定基变量取的价值系数x2发生了变化。试问，要保持原最优解不变，c2应在什么范围内变化？设c2为c2的允许增减幅度，则非基变量x1、x4、x6的检验数必须满足由此可得max(一54.1583，一112l2100)c245 5174500即 一0.11c25.17。也就是说小货车每辆利润q减少0.11万元或增加5.17万元不会影响最优解的变化，即越野车不会列入生产计划。例4 假设上例中生产卡车由于管理加强减少了工时，即只发生了如下变化：试问，原来最优生产计划是否需要改变?解 分析这个问题按如下步骤1、2、设改进工艺后的卡车产量用x3表示，用x3代替x3，并用B1P3代替上表中对应x3的列，得表

25、3、重新计算检验数后发现，x3的检验数变成正，说明原来的最优解不再是最优。于是确定新的x3换入，旧的x5换出。4、以212为主元家旋转运算，得新的最终单纯形表从表可以看出，由于管理加强，虽然卡车产量下降(由1250辆降为800071142.86辆)，但小货车产量却增加了(由500辆增加到5000/77143辆)，因此全厂利润也上升了(由7975万元增为5599077998.57万元)。增加新的决策变量 假设新变量为l，则须在4中增加一个新列向量Pl。这时可按上述步骤进行，区别是加入新向量Pl时不必代替别的列向量。现举例。例5 假设例3中汽车厂要增加新车种小轿车。生产小轿车需用的三个工序工时是每

26、辆利润是6万元。问安排小轿车生产后，原来的生产计划将如何变化。解 设生产x7辆小轿车。然后按下述步骤计算。将B1只填入原来最终单纯形表第7列，得计算x7的检验数。结果表明，每辆利润为6万元时，生产小轿车是不利的。但是，若把小轿车利润提高到每辆6.5万元，其检验数为正，说明能增加总利润，是有利的。这时要继续迭代计算。以3335为主元素的旋转运算结果列在最终单纯形表中。这时，得到新的最优解：x*(x1、x2、x3、x4、x5、x6、x7)T(0，0，9500/11，0，231500/33，0，17500/33)T，目标函数值为f（x*）264230338006.97万元例6 汽车厂需在生产过程中增

27、添一道新工序，即汽车上所有机加工工件均由本厂生产，越野车、小货车和卡车需用的机工工时和总机工工时写在一个新增的约束条件中，即新检验数 例例 已知某工厂计划生产、三种产品，各产品需要在A,B,C设备上加工，有关数据见表 试回答:(1)如何充分发挥设备能力，使生产盈利最大?(2)若为了增加产量，可借用别的工厂的设备B，每月可借用60台时，借金1.8万元，问借用B设备是否合算?I II III 设备有效台时（每月）ABC8102251310810300400420单位产品利润（千元）322.9(3)若另有两种新产品、V，其中需用设备A一l2台时，B一5台时，C一l0台时，单位产品盈利2.1千元;新产

28、品V需用设备A一4台时，B一4台时，C一l2台时，单位产品盈利1.87千元，如A,B,C设备台时不增加，分别回答这两种新产品投产在经济上是否合算?(4）对产品工艺重新迸行设计，改进结构，改进后生产每件产品I，需用设备A一9台时，设备B一12台时，设备C一4台时，单位产品盈利4.5千元，问这对原计划有何影响?解（1）设产品、的产量分别为x1，x2，x3，其数学模型为在上述线性规划问题的约束条件中加入松 变量x4，x5，x6。得列出初始单纯形表，并求解maxZ=3 x1十2 x2十2.9 x3 8 x1十2 x2十10 x3 300 10 x1十5 x2十 8 x3 400，st 2x1十13 x

29、2十10 x3 300，x1、x2、x3 0maxZ=3 x1十2 x2十2.9 x3 8 x1十2 x2十10 x3 x4 300 10 x1十5 x2十8 x3 x5 400，st 2x1十13 x2十10 x3 x6 300，x1、x2、x3、x4，x5，x6 0故原线性规划问题的最优解X*=（338/15，116/5,22/3,0,0，0)，目标函数最优值(2)由单纯形表知:设备B的影子价格为4/15(千元/台时)而借用设备的租金为:18/60=0.34/15，故借用B设备并不合算。(3)设及V生产的产量分别为x7，x8，则其各自在最终单纯形表对应的列向量故生产产品在经济上不合算所以生产产品V在经济上合算由单纯性表知:故线性规划最优解X*=（107/4,31/2,0,0,0,0，55/4)T目标函数最优值Z*=136.9625(4)改进后 C1=4.5，P1=(9,12,4)T 故改进技术后能够带来更多的经济效益增加。