运筹学灵敏度分析

§7灵敏度分析前述线性规划问题,假定aij,bi,cj都是常数，但这些系数往往是估计值和预测值。市场值cj就会变；aij因工艺条件的改变也改变；b也如此。•这些系数有一个或几个发生变化时，在什么范围内，已求得的线性规划问题的最优解会有什么变化？(最优基不变)•或者这些系数在什么变化范围内变化时，线性规划问题的最优解和最优基保持不变，此问题是参数规划内容。要求掌握b和c的灵敏度变化分析。当某一个资源系数br发生变化，亦即br′=br+△br，其他系数不变，这样最终的单纯形表中原问题的解相应地变化为XB′=B-1(b+△b)，其中△b=(0,…,△br,0,…,0)T只要XB′≥0，最终表中检验数不变，则最优性不变，但最优解的值发生变化,XB′成为新的最优解.新的最优解允许范围是:B-1(b+△b)=B-1b+B-1△b≥01、资源系数br的灵敏度变化分析mrirrrrmrrirrrraaabbabababB11100进一步得，最终表中b列元素bbairirB-1bB-1的第r列,0babriri+i=1，2，…，mi=1，2，…，miririrabba;/0iririrabba/01210010160100480012154321bxxxxx得到公式:例：求第一章例题中当第二个约束条件b2变化范围△b2。}0min{}0max{iriririririaabbaab可得△b2≥-4/0.25=-16,△b2≥-4/0.5=-8,△b2≤2/0.125=16由公式知△b2变化范围[-8,16],显然b2变化范围[8,32]++000125.05.025.0244002211bbBbB例题:将上面例题进行实际应用。每台设备台时的影子价格为1.5元。若该厂又从别处抽出4台时用于生产两种产品，求这时该厂生产两种产品的最优方案。2800040125.05.015.02025.001bB将这个结果放到最终表中得解：先计算B-1△b23000cj203x1x2x54+04-82+2CBXBbx1x2x3x4x51000.25000[-2]0.51010.5-0.1250cj-zj000-1.5-0.125表中b列中有负数，即解答列有负数，故可用对偶单纯形法求最优解。最优解见下表最优生产方案应改为第一种产品4件，第二种产品3件，获利z=17元。23000cj203x1x2x3423CBXBbx1x2x3x4x51000.250001-0.25-0501000.25cj-zj000-0.5-0.752、目标函数中价值系数C的变化（1）当cj是非基底变量xj的系数，检验数为mijijjjjBjjyacPBCc11或当cj变化cj后，检验数应要小于或等于零，即jjjjjjjBjjjcYPcYPccPBCcc++01'（2）当cr是基底变量xr的系数，即crCB，cr变化cr后，有最优解不变0'j0,;0,,1,2,,jrjrrjjrjrrjacaacjnan,1,2,j),,,(0,,,,0j1'211111+++rjrrjrBjjrnrrrBrBBBaCaCABCcaaaCABCABCABCABCCcr的变化范围}0{min}0{maxrjrjjjrrjrjjjaacaa例8：仍以第一章例1的最终表为例。设基变量x2的系数c2变化△c2，在原最优解不变的条件下，确定△c2的变化范围。解：这时最终计算表为cj23+△c2000CBXBbx1x2x3x4x5203x1x5x24421000010-20.50.250.5–0.125010cj-zj0△c2-1.5-0.1250为了保持原最优解不变，则x2的检验数应当为零。这时可用行的初等变化实现，得到可见–1.5-△c2/2≤0和△c2/8-1/8≤0即△c2≥-1.5/0.5;△c2≤1故△c2的变化范围:-3≤△c2≤1即x2的价值系数c2可在[0,4]之间变化，不影响原最优解。cj23+△c2000CBXBbx1x2x3x4x5203x1x5x24421000010-20.50.250.5–0.125010cj-zj00-1.5-△c2/2△c2/8-1/80解题步骤：先用单纯形法解题，然后考虑参数变化，最后确定变化范围。进行ci灵敏度分析的意义：1、代表产品的单位利润或单位售价时，灵敏度分析可用于预先确定保持现有生产规模条件下单位产品利润或单价的可变范围。2、代表单位原料单价时，灵敏度分析用于预先确定保持现有配方条件下，原料单价的可变动范围。作业：maxZ=2x1+3x2+c3x3s.t1/3x1+1/3x2+1/3x311/3x1+4/3x2+7/3x33x1,x2,x30试求：1、确定c3的变化范围。2、确定c1的变化范围。解题思路：先将c3取成1，求解，然后在考虑c的变化。答案为1、c342、3/4c13其它参数的灵敏度分析：1、新增变量的灵敏度分析添加一种新的原料等2、新增加约束条件的灵敏度分析增加资金约束，对产品质量有新要求等3、aij的灵敏度分析当设计或工艺改进后，aij会发生变化