kok电子竞技

1、第十五章线性规划的灵敏度分析15.1边际值（影子价格）q以（max,©为例，边际值（影子价格其实指在最优解的基础上，当第i个约束行的右端项bi减少一个单位时，目标函数的变化量mf（x）=CbB*（CbBj）ibi4q=£f（x）/=（CBB）i,偏导数，机会成本Zn+=CbBPe=（CbB）i因此"Zn1L松弛变量，人工变量nTrqi=L-Zn+剩余变量mm机会成本的另外表达形式Zj=CBBPj（CBB）*日='qiaij旧i=4例15.1.1maxf（x）=x45x23x34x4'2x1+3x2+x3+2x4<8005x1+4x2+3x3+

2、4x4<1200其最优单纯表形式如下：st3x14x25x33x4"000xi,x2,x3,x40表15.1.1xix2x3x4x5x6*CBXBb15340000x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251Z-Cj3.2502.75000.251关丁影子价的一些说明影子价是资源最优配置下资源的理想价格，资源的影子价与资源的紧缺度有关松弛变量增加一个单位等丁资源减少一个单位剩余变量增加一个单位等丁资源增加一个单位资源有剩余，在最优解中就有对应松弛变量存在，且其影子价为

3、0影子价为0,资源并不一定有剩余15.2价值系数Cj的灵敏度分析cj变动可能由丁市场价格的波动，或生产成本的变动q的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj允许的变动范围gQ的变化会引起检验数的变化，有两种情况：非基变量对应的价值系数变化，不影响其它检验数基变量对应的价值系数变化，影响所有非基变量检验数15.2.1非基变量对应的价值系数的灵敏度分析要保持-(g+Aq)芝0故有*<cj<zj-cj例15.2.1maxf(x)=x15x23x34x4'2x1+3x2+x3+2x48005x1+4x2+3x3+4x4<1200st<3x14x25x33x

4、4_1000为法2法3法4一0表15.2.1CbXbbx11x25x33x44x50x60X700x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251Zj-Cj3.2502.75000.251表15.2.2x1x2x3x4x5x6x7CbXbb15340000x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251Zj-Cj3.2502.75000.251X，x3为非基变量，所以要保持Zj-(

5、Cj+ACj)芝0故有-00CCj<Zj-Cj15.2.2基变量对应的价值系数的灵敏度分析由丁基变量对应的价值系数Cj在Cb中出现，因此它会影响所有非基变量的检验数。只有一个基变量的cj发生变化，变化量为Agkk即Cj在Cb中的k分量，研究非基变量xj机会成本的变化：kmmZj"Zj=L(CjkfCjki)aj=七Cjk%."Cjkakj(=Zj"Zj)i注izi要满足（zj+AzDCj芝0,贝U有czakcjkW-4-二akjakj：0、-一，.CjZjI1n.一._当3kj>0,有ACjkm或国0当akj<0,有ACjmax-min为保证所有

6、非基变M检验数仍满足最优条件，有CbXbbxi1x25x33x44x50x60x700x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251Zj-Cj3.2502.75000.251Cj-Zj.akjakj0akj<0cj-Zj_akj表15.2.3rCjZj_-'.CjZj_c'由maxj±akj>0修Ag<minj_jakj<0j-遍_kj_akj_设X4的价值系数增加Ac4,对应k=2,-3.25-0.25.-2.75-1max,_C4_

7、min,_21_-2-1一0.25三上6三1,3.75三C4三5?有一边为空集如何处理(右：+8,或左：-8)?为什么akj=0不出现在任何一边的集合中?与对偶单纯型法找入基变量的公式类似。15.3右端项bi的灵敏度分析?设XB=B”b是最优解，则有XB=B1b0?b的变化不会影响检验数；?b的变化量可能导致原最优解变为非可行解。七11gm设B=:'-.gm1gmmb'=(n,b2,，(bs+Abs),bmT,第s个分量发生变化。为保证最优解的基变量'&+侦9估不发生变化，必须满足XB=B#b%0即B-1b=Bb+Abs:=:lgms.)bm*Absgms当bk

8、+gksAbs'0(k=1,2,m)时，B仍是新问题的最优基矩阵。当gk,s>0，贝U有Abs业玉gk,sb当gk,s<0，则有Ab要求对所有k都成立，从而有max&gk,s0bs三现nk_gk,sk此时，基变量的解值和目标函数会发生变化：XNew=x0|d+AbsPs,OBJNew=OBJ0|d+AbsCBPs即表15.3.1CbXbbx11x25x33x44x50x60x700x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251Zj-Cj3.2502.7500

9、0.251还是对前面的例分析，以b2为例，xs是对应的初始基变量,z100'11/4-r800'Bb=200_1,B=(P5,R,P7),B=01-1,b=1200J00>L°-3/41JJ000?A=1200b2有变化,s=1，即取基矩阵B中第二列计算max-稣力乂匕kok电子竞技min<°kgLkbk,s-100-200人.-100max,_b2已min-_0.251_-0.75-200一b2£133.3,1000%b2£1333.3令Ab2=100,则有100'Z0.25'"125'fxvNewX=

10、200+1001.00=300=x4<100>375/<25><x2)OBJNew=CBXNew=12503004255=1325(XNew=X0|d：bsPs,OBJNeW=OBJ0|dWCbPs)15.4技术系数aij的灵敏度分析技术系数aij变化的影响比较复杂对应基变量的aij，且资源bi已全部用完对应基变量的aij，但资源bi未用完对应非基变量的aij，且资源bi全用完或未用完1）对应基变量的aij，且资源bi已全部用完Aaj=02）对应基变量的aij，但资源bi未用完-D团？兰上述两个公式不充分，为什么？引起B"发生变化，从而引起非基变量的检验

11、数z-Q的变化3）对应非基变量的aij-只影响对应非基变量xj的检验数Zj-Q-若：aij>0,不会破坏最优解-若Aaij<0,必须保证0zi-Cjm设Xj为非基变量，则有Z0=£akjQj设aj变动Aa,j,则有kAzj=z0+Aajq,gz；=gz0Aaq壬0即膈四芝勺一z0对丁第i行约束苴型，q>0,所以C<Aa,牛qi表15.4.1CbXbbX11X25X33X44X50X60X700X51001/40-13/4011/4-14X420020-2101-15X2100-3/4111/400-3/4113004.2555.75400.251zj-Cj3.

12、2502.75000.251q2=0.25,q3=1,故有-二八馅13xi,X3为非基变量，qi=0,-2.75._11=-a23:0.25-275-2.75=-、.a33-b1有剩余，故有100=0.5200-二-an<二-3.25.-13=-心21-0.25-325一3.25=于5£a31立二X2,X4为基变量,X5=100,-二土柘121-二三.治14三10010015.5新增决策变量的分析例15.1.1中，若新增产品X8,单位产品的资源消耗量分别是：5,4,3,单位产品的利润是：9,问是否生产？-已知C8=9,a18=5,a28=4,a38=3-计算x8的检验数可知生产

13、是否有利3z8-c8='qm-c8=（5040.2531）-9=50i4结论：生产X8有利。将B1P8加入最优单纯型表中，以X8为入基变量进行迭代。（过程学生完成）15.6新增约束条件的分析1）将最优解代入新的约束条件，若满足，则最优解不变2）若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯型表，并变换为标准型3、利用对偶单纯型法继续迭代为什么可以利用对偶单纯型法例15.6.1续前例15.1.1,如果生产中为提高产品性能，增加一种原料，已知各产品单件生产的该原料消耗量为：1,2,3,3,该原料总量为：650。应该如何调整生产计划？解：先把新增加的条件添加到表格中，再典范化：

14、表15.6.1X1X2X3X4X5X6X7X8CBXbb153400000X51001/40-13/4011/4-104X420020-2101-105X2100-3/4(1)11/400-3/4100X865012330001X1X2X3X4X5X6X7X8CbXbb153400000X51001/40-13/4011/4-104X420020-2101-105X2100-3/4(1)11/400-3/4100X8650123300010X51001/40-13/4011/4-104X420020-2(1)01-105X2100-3/4111/400-3/4100X84505/20-5/23

15、01.5-210X51001/40-13/4011/4-104X420020-2101-105X2100-3/4111/400-3/4100X8-150-7/207/200-1.511(以上为典范化的过程。下面先计算判别数，可以发现是对偶可行的，因此利用对偶单纯形方法求解。)表15.6.2CbXbbX11X25X33X44X50X60X70X800X51001/40-13/4011/4-104X420020-2101-105X2100-3/4111/400-3/4100X8-150-7/207/200(-1.5)1113004.2555.75400.2510Zj-Cj3.2502.75000.

16、25100X575-0.330-2.67010-0.830.174X4100-0.3300.33100-0.330.675X21751110000.5-0.50X61002.330-2.33001-0.67-0.6712753.6756.334001.170.17Zj-Cj2.6703.330001.170.17注意：最优解的目标函数减少了25个单位15.7灵敏度分析举例例15.7.1某工厂生产三种产品A,B,C,有五种生产组合方案。下两表给出有关数据。规定每天供应A产品至少110个，求收益最大的生产方案。表15.7.1别IIIIIIIVV单位售价（元）A产品数量3244010B产品数量612

17、145C产品数量265184耗费乂别IIIIIIIVV资源限制工人工时（小时）0461280小时/天机器工时（小时）1121150小时/天每组生产费用（元）481930407解：设为为已选定各种组合方案的组数（j=1,2,5）X6为A产品的剩余变量，X7,X8分别为工人工时和机器工时的松弛变量。maxf（x）=20x130x240x35x445x53x1+2x2+4x3+4x4-x6=1104x2+6冷十七十2x5+x7=80st<X+x2+2x3+x4+冷+冷=50、xj>0,j=1,2，8表15.7.2x1x2x3x4x5x6x7x8CbXbb20304054500020x12

18、61100.410-0.2-0.20.430x216011.40.50-0.20.3-0.645x58000.2-0.510.4-0.11.213602030594080.544zj-cj00190080.544例15.7.2?最优解的B"是什么?产品A的影子价为多少?第II组方案的生产费用提高2元，是否要调整生产组别?若工人加班费为1元/小时，是否要采取加班措施?若通过租借机器增加工时，租费的上限应为多少?A产品的订购合同是否有利，A产品的变动范围多大?若要选用第IV组方案，该组的生产费用应降低多少?若工人加班费为0.3元/小时，最多允许加班时间多少?若机器租费低丁44元/小时，问

19、租几部机器才合适(每天8小时计)?若第III组方案使机器工时减少0.5小时，能否被选入15.8参数线性规划前面只考虑aij,bi,cj一个发生变化，如果多个同时发生变化则很难解析。但在一些特殊情况下，用参数表示变化量，也可以用来进行多个系数的灵敏度分析。15.8.1参数Cj的变化分析q第i种资源的单位费用变化量，q土不限ajq变化对Cj的影响率nmaxf(x)=、gy尸iXjj4.nI-'ajXj一(=,-)bji=1,2;,ms.tE为油j=1,2，n例15.8.1资源b1变化量01,otj=a1jmaxf(x)=(1_2u1)x(5-3斗)x2(3r)x(4-2"x4&#

20、39;2x1+3x2+x3+2x4壬8005x1+4x2+3x3+4x41200s.t<3x1+4x2+5x3+3x4壬1000、x1,x2,x3,x0表15.8.1CbXbbx11-2,1x25-3%x331x44-261x50x60x700x51001/40-13/4011/4-14-281x420020-2101-15-3Sx2100-3/4111/400-3/411300-700S4.25-15-3e15.75-44-2%00.25+1-%.75%.25610.25%Cj-zj-3.25-0-2.75+00-0.25-1+s0.25*3.25S0.25S例15.8.2资源b1变化

21、量，与任5-0.2501-133.25壬01壬0.8462-0.25一0"-1-1101要求(cj-zj)<0,由上单纯型表-3.25-2.75-0.25一1三"三0.8462e1在此范围内不会影响最优解15.8.1有(X5,X4,X2)=(100,200,100)maxf(x)=1300-700时1=-1,X6的检验数=0e1=0.8462,X3的检验数=0出现多重解现象研究X5松弛变量价值系数5maX匚3.250.25-0.250.25C5的变化范围-2.75-1,-3.25-1-1<:c5壬0.8462结果与91的一致。15.8.2参数b的变化分析例15.

22、8.1中，将b1,b2,b3理解为三个车间的周工时资源。假设从第1向2车间调动工人臼个，每个工人的周工时为40小时，问调动多少工人不会破坏最优产品组合。解：maxf(x)=CXs.t.，40P=-400要保证X；=B"(b"")_0即XN=XB0B七芯二0/N>乂5门00r30e>N乂4=200+-409>0N2)100l30叽解得100308-06200-40e-0e100300-00-3.33土5-3.33-3.33主)三5OBJ=CBB一1(b，：)=1300-10口从目标函数中看出什么?习题151.已知线性规划问题和它的最优单纯形表15.

23、9.1.maxz=4xiX>2x38x13x2x3三2s.t«6x1+x2+x3苴8/芝0,x2占0,x3占0表15.9.1xix2x3x4x右边1250204831102-2-20-116(1)求原问题和对偶问题的最优解(2) 确定最优基不改变的前提下变量X1和X3的目标函数系数的变化范围确定最优基不改变的前提下两个右边项系数的变化范围2.已知线性规划问题maxz=(q11)x1c2x2c3x30x40x5aiixi*ai2x2*ai3x3*x4=加*3t2S.t<a2x*&22乂2*&23乂3*乂5=b?*t?xj河(j=1,2,.5)当t1=t2=0

24、时求解得最终单纯形表如表15.9.2.确定aii,ai2,ai3,a2i,a22,a23,G,C2,c和bb的值；当t2=0时，ti值在什么范围内变化，上述最优值不变;当ti=0时，t2值在什么范围内变化，上述最优值不变;表15.9.2x1x2x3x4x右边04042*z01/211/205/21-1/20-1/61/35/23.某厂生产I,II,III三种产品，其所需劳动力、材料等数据见表15.9.3.要求：(1)确定获利最大的产品生产计划；(2) 产品I的利润在什么范围内变动时，上述最优计划不变；(3) 若设计一种新产品IV,单件劳动力消耗为8单位，材料消耗为2单位，每件获利3元，问该产品

25、是否值得生产？(4) 若劳动力数量不增，材料不足时从市场购买，问该厂是否购进原材料扩大生产，如果可以购买，则最多应购入多少？表15.9.3IIIIII可用量(单位)万动力63545材料34530产品利润(元/件)3144.已知线性规划问题:maxz=3x1+2x2x1+2x2<62x1+x2M8(2)st*_x1+x2苴1(3)x22(4)x1N0,x2N0已知用单纯形法求得最优解的单纯形表如表15.9.4所示试分析在下列各种条件单独变化的情况下，最优解将如何变化。表15.9.4迭代BV.Eq.zXx2x3x4xx6右边最优z(D1001/34/300*zx2(2)0012/3-1/3004/3x(3)010-1/32/30010/3x(4)000-11103x(5)000-2/31/3012/3(1) 第(1),(2)个约束条件右端项分别由6变成乙由8变成4;目标函数变为maxz=2毛+5x2;(3)增加一个变量x3,其在目标函数中系数c3=4,在约束系数矩阵中列P3=(12,3,2)T问题中变量X2的系数变为(4,3,2,1,2)T;增加一个新的约束x4o