图解法的灵敏度分析课件.ppt

1、线性规划的标准形式为：线性规划的标准形式为：目标函数：目标函数：,max2211nnxcxcxcz约束条件：约束条件：,min2211nnxcxcxcf（或（或 ）.0,2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa其中其中 为第为第 个决策变量个决策变量 的系数；的系数；jcjjxija为第为第 个约束条件中的第个约束条件中的第ij个决策变量个决策变量 的系数；的系数；jxib为第为第 个约束条件的常数项，个约束条件的常数项，i.0jb且且1所谓所谓灵敏度分析灵敏度分析 就是在建立数学模型和求得最优解之后，就是在建立数学模型

2、和求得最优解之后，究线性规划的一些系数究线性规划的一些系数 变化时，变化时，iijjbac、对最优解有什么影响？对最优解有什么影响？研研 jc设目标函数为设目标函数为:,max2211xcxcz改写为改写为:,zcxccx212121显然显然,目标函数等直线的斜率为目标函数等直线的斜率为:,21cc对于前面的例对于前面的例 1,如左图如左图:1002003004001002003004001x2x250,50直线直线E(设备台时约束条件设备台时约束条件)直线直线G(原料原料A的约束条件的约束条件)直线直线F(原料原料B的约束条件的约束条件)目标函数直线目标函数直线ABCD2110050 xxz

3、0Fk1Ek22）当）当 时，时，121ccBC上任一点都是其最优解。上任一点都是其最优解。3)当当 时时,01cAB上任意一点都是最优解上任意一点都是最优解.1）当）当 时时,0121cc250,5021xx仍是最优解。仍是最优解。B点，即点，即为了计算出为了计算出 在什么范围内变化时顶点在什么范围内变化时顶点B仍是其最优解，仍是其最优解，1c单位产品单位产品的利润为的利润为100元不变，元不变，假设假设即即,1002c则有则有010011c解不等式得解不等式得.10001 c即单位产品即单位产品的利润为的利润为100元，单位产品元，单位产品的利润在的利润在0与与100元之间元之间变化时，变

4、化时，250,5021xx仍是最优解。仍是最优解。3即即要计算出要计算出 在什么范围内变化时顶点在什么范围内变化时顶点B仍是其最优解，仍是其最优解，2c单位产品单位产品的利润为的利润为50元不变，元不变，假设假设,501 c则有则有,05012c解不等式得解不等式得,502c且且.02 c即即.502 c也即单位产品也即单位产品的利润为的利润为50元，单位产品元，单位产品的利润只要大于等于的利润只要大于等于50元时，元时，250,5021xx仍是最优解。仍是最优解。同样，在同样，在 和和 中一个值确定不变时，中一个值确定不变时，可以求出另一个值可以求出另一个值的变化范围，的变化范围，2c1c使

5、其最优解在使其最优解在C点（或在点（或在D点，或在点，或在A点）。点）。若若 和和 都变化时，可通过目标函数的斜率都变化时，可通过目标函数的斜率 判断判断B点、点、2c1c21ccC点、点、D点或点或A点为最优解。点为最优解。4ib当约束条件右边系数当约束条件右边系数 发生变化时发生变化时,ib线性规划的可行域也将线性规划的可行域也将发生变化，发生变化，就可能引起最优解的变化。就可能引起最优解的变化。将例将例1中的约束条件中的约束条件,30021 xx改为改为,31021 xx最优解为最优解为 点，点，B解解250310221xxx得得.250,6021xx即增加了即增加了1010个台时的设备

6、。个台时的设备。1002003004001002003004001x2x250,50ABCD2110050 xx 1002003004001002003004001x2xABCDBC2110050 xx 5此时的最大利润为：此时的最大利润为：.280002501006050元元 比原来增加了：比原来增加了：.5002750028000元这主要是由于这主要是由于增加了增加了1010个设备台时个设备台时而获得的。而获得的。即每增加一个台时的设备就可多获得即每增加一个台时的设备就可多获得元5010500的利润。的利润。对偶价格：对偶价格：在约束条件右边常数增加一个单位，在约束条件右边常数增加一个单位

7、，而使最优目标函而使最优目标函值得到改进的数量，值得到改进的数量，称为称为这个约束条件的对偶价格这个约束条件的对偶价格。30021 xx约束条件：约束条件：的对偶价格。的对偶价格。若将例若将例1中的原料中的原料A增加增加10千克，千克，,400221 xx改为改为,410221 xx则约束条件则约束条件6最优解仍为最优解仍为 点，点，B1002003004001002003004001x2x250,50ABCD2110050 xx 1002003004001002003004001x2xABCD2110050 xx 最优值还是最优值还是27500元。元。原料原料A的对偶价格为：的对偶价格为：.

8、0102750027500即最优解仍为：即最优解仍为：250,5021xx即原料即原料A 增加增加10千克，只增加了库存，千克，只增加了库存，没有转化为利润。没有转化为利润。原料原料 A 只用了：只用了：,350250502千克还有：还有：千克50350400没用。没用。72110050maxxxz,30021 xx,400221 xx.0,021xx,2502x约束条件约束条件(设备台时的限制条件设备台时的限制条件)(原料原料A 的限制条件的限制条件)(原料原料B 的限制条件的限制条件)(决策变量非负约束条件决策变量非负约束条件)目标函数目标函数当某约束条件中的松弛变量（或剩余变量）不为零，

9、当某约束条件中的松弛变量（或剩余变量）不为零，则这个条件的对偶价格为零。则这个条件的对偶价格为零。总结如下，当约束条件右边常数增加一个单位时：总结如下，当约束条件右边常数增加一个单位时：1）如果对偶价格大于零，则其最优目标函数值变得更好，即）如果对偶价格大于零，则其最优目标函数值变得更好，即 求最大值时，变得更大；求最小值是变得更小。求最大值时，变得更大；求最小值是变得更小。2）如果对偶价格小于零，则其最优目标函数值变坏，即求最）如果对偶价格小于零，则其最优目标函数值变坏，即求最 大值时变小了；求最小值时变大了。大值时变小了；求最小值时变大了。3）如果对偶价格等于零，则其最优目标函数值不变。）

10、如果对偶价格等于零，则其最优目标函数值不变。8输入中注意以下两点：输入中注意以下两点：解决线性规划问题的软件包分两种：解决线性规划问题的软件包分两种：(1)大规模的软件包：可解决包含数千个决策变量和约束条件大规模的软件包：可解决包含数千个决策变量和约束条件的大型线性规划问题。的大型线性规划问题。(2)用于微型计算机的软件包用于微型计算机的软件包:可解决包含数百个决策变量的可解决包含数百个决策变量的线性规划问题。线性规划问题。(1)输入的系数可以是整数、小数，但不能是分数。输入的系数可以是整数、小数，但不能是分数。(2)输入前先要合并同类项。输入前先要合并同类项。注：注：本软件可解决本软件可解决

11、100个决策变量个决策变量50个约束方程的线性规划问题个约束方程的线性规划问题.9目标函数最优值为目标函数最优值为:27500变量变量 最优解最优解 相差值相差值21xx2505000约束约束 松弛松弛/剩余变量剩余变量 对偶价格对偶价格321050050050目标函数系数范围目标函数系数范围:变量变量 下限下限 当前值当前值 上限上限21xx50010050无上限无上限100常数范围常数范围:约束约束 下限下限 当前值当前值 上限上限321200350250250400300300325无上限无上限10目标函数最优值为目标函数最优值为:27500变量变量 最优解最优解 相差值相差值21xx2

12、505000目标函数最优值为目标函数最优值为:27500表示表示:这个问题的最优解可得到利润这个问题的最优解可得到利润 27500元元;变量变量:即决策变量即决策变量;最优解最优解:使目标函数达到最优值的解使目标函数达到最优值的解:.250,5021xx即生产即生产产品产品50单位、单位、产品产品250单位才能使利润达到最大值单位才能使利润达到最大值;相差值相差值:表示表示:相应的决策变量的目标系数需要改进的数量相应的决策变量的目标系数需要改进的数量,使该决策使该决策变量有可能取正值变量有可能取正值,当决策变量已经取正值当决策变量已经取正值,则相差值为零则相差值为零.如如 它们的相差值都为零。

13、它们的相差值都为零。,250,5021xx如果如果,01x1x的相差值为的相差值为30，则只有当，则只有当产品的利润再提高产品的利润再提高30元元,即达到即达到50+30=80元时元时,产品才可能生产产品才可能生产,即即.01x11约束约束 松弛松弛/剩余变量剩余变量 对偶价格对偶价格321050050050约束约束1:表示设备台时的限制表示设备台时的限制.其剩余量其剩余量(松弛变量松弛变量)为为0,即设备台时数全部用完即设备台时数全部用完.松弛变量松弛变量:没有用完的资源数没有用完的资源数剩余变量剩余变量:超出资源数超出资源数.对偶价格为对偶价格为50:表示每增加一个设备台时表示每增加一个设

14、备台时,可使总利润增加可使总利润增加50元元.约束约束2:是对原料是对原料A 的限制的限制.其剩余量其剩余量(松弛变量松弛变量)为为50,即原料即原料A 还有还有50千克没有使用千克没有使用.对偶价格为对偶价格为0:因为再增加原料因为再增加原料A 只能增加库存只能增加库存,不能增加利润不能增加利润.约束约束3:是对原料是对原料B 的限制的限制.其剩余量其剩余量(松弛变量松弛变量)为为0,即原料即原料B 全部用完全部用完.对偶价格为对偶价格为50:即每增加一千克的原料即每增加一千克的原料B可使总利润增加可使总利润增加50元元.12目标函数系数范围目标函数系数范围:变量变量 下限下限 当前值当前值

15、 上限上限21xx50010050无上限无上限100常数范围常数范围:约束约束 下限下限 当前值当前值 上限上限321200350250250400300300325无上限无上限研究目标函数的系数、右端常数及约束方程中的研究目标函数的系数、右端常数及约束方程中的 系数发生变化时，对最优解的影响。系数发生变化时，对最优解的影响。（1）为了保持现有的最优解或最优基不变，找出这些数据变化）为了保持现有的最优解或最优基不变，找出这些数据变化 的范围；的范围；（2）这些数据超出了（）这些数据超出了（1）的范围时，如何尽快求出新的最优解）的范围时，如何尽快求出新的最优解 或最优基。或最优基。13变量变量

16、下限下限 当前值当前值 上限上限21xx50010050无上限无上限100当前值当前值:表示目标函数中决策变量当前的系数表示目标函数中决策变量当前的系数:2110050maxxx 100.50;21的的系系数数为为的的系系数数为为xx上限、下限：上限、下限：指目标函数的决策变量的系数在此范围内变化时，指目标函数的决策变量的系数在此范围内变化时，其线性规划的最优解不变。其线性规划的最优解不变。对于此问题：对于此问题：只要只要 ,50 ,10002211的的系系数数的的系系数数xcxc其最优解不变。其最优解不变。如：若如：若 ,801c其最优解仍为其最优解仍为 ,250,5021xx目标函数目标函

17、数最优值为最优值为 ;290002501005080元元优解就要发生变化。优解就要发生变化。,1101c但若但若 其最其最 对于对于c2有同样的道理。有同样的道理。如何调整生产计划如何调整生产计划 目标函数系数范围目标函数系数范围:TP1714约束约束 下限下限 当前值当前值 上限上限321200350250250400300300325无上限无上限当前值当前值:表示约束条件右边现在的值表示约束条件右边现在的值:.250 ;400 ;300321bbb上限、下限：上限、下限：是指当约束条件在此范围内变化时，则与其对应的是指当约束条件在此范围内变化时，则与其对应的 约束条件的对偶价格不变。约束条

18、件的对偶价格不变。对于此问题：对于此问题：设备台时在设备台时在250325之间变化时，其对偶价格都为之间变化时，其对偶价格都为50元；元；原料原料A 在在350+之间变化时，其对偶价格都为之间变化时，其对偶价格都为0；原料原料B 在在200300之间变化时，其对偶价格都为之间变化时，其对偶价格都为50元元。如：若如：若 而而 ,250 ;40032bb,2801b设备台时的对偶价设备台时的对偶价 格仍为格仍为50元，元，但设备台时比原来减少了但设备台时比原来减少了20个台时，利润减少，个台时，利润减少，此时目标函数的最优值为：此时目标函数的最优值为：27500-2050=26500（元）。（元

19、）。TP18常数范围常数范围:15注：注：计算机输出的关于目标函数及约束条件的灵敏度分析都是计算机输出的关于目标函数及约束条件的灵敏度分析都是 基于假设：基于假设：只有一个系数值发生变化，而其它系数值保持不变。只有一个系数值发生变化，而其它系数值保持不变。问题：问题：若有两个或更多个的系数同时发生变化时，如何进行灵敏若有两个或更多个的系数同时发生变化时，如何进行灵敏 度分析？度分析？以例以例1为例：为例：原来原来产品的利润为每件产品的利润为每件50元、元、产品的利润为每件产品的利润为每件100元，元，现在由于市场情况的变化每件现在由于市场情况的变化每件产品产品产品的利润分别变为产品的利润分别变

20、为74元元 和和78元，最优解发生变化吗？元，最优解发生变化吗？允许增加值：允许增加值：对一个目标函数的决策变量系数：对一个目标函数的决策变量系数：该系数在上限范围内的最大增加量；该系数在上限范围内的最大增加量；允许减少值：允许减少值：该系数在下限范围内的最大减少量。该系数在下限范围内的最大减少量。16对于例对于例1：c1的允许增加量为：上限的允许增加量为：上限 当前值当前值=100-50=50；c2的允许减少量为：当前值的允许减少量为：当前值-下限下限=100-50=50。ci允许增加（减少）百分比：允许增加（减少）百分比：减减少少量量的的允允许许增增加加量量减减少少量量的的增增加加量量百百

21、分分比比减减少少的的允允许许增增加加iiicccc1允许增加百分比为允许增加百分比为：(74-50)/50=48%;c2允许减少百分比为允许减少百分比为：(100-78)/50=44%;c1允许增加百分比与允许增加百分比与c2允许减少百分比之和为允许减少百分比之和为:48%+44%=92%.此线性规划的最优解不变，仍为：此线性规划的最优解不变，仍为：,250,5021xx此时最大利润为：此时最大利润为：7450+78250=23200（元）。（元）。TP18TP14 17对于所有变化的目标函数决策变量系数对于所有变化的目标函数决策变量系数,当其所允许增加百分当其所允许增加百分 比和允许减少百分

22、比之和不超过比和允许减少百分比之和不超过100%时时,最优解不变最优解不变.对于所有变化的约束条件的右边常数值对于所有变化的约束条件的右边常数值,当其所允许增加百分当其所允许增加百分 比和允许减少百分比之和不超过比和允许减少百分比之和不超过100%时时,其对偶价格不变其对偶价格不变.对于例对于例1：若三个约束条件的变化为：若三个约束条件的变化为：设备台时数：从设备台时数：从300台时增加为台时增加为315台时；台时；原料原料A：从从400千克减少到千克减少到390千克；千克；原料原料B：从从250千克减少到千克减少到240千克千克。它们的允许增加（减少）百分比分别为：它们的允许增加（减少）百分

23、比分别为：TP1515/25=60%；10/50=20%；10/50=20%。允许增加百分比和允许减少百分比之和为：允许增加百分比和允许减少百分比之和为：1860%+20%+20%=100%。所以此线性规划的对偶价格不变。所以此线性规划的对偶价格不变。利润的增加值为：利润的增加值为：5015-015-5010=250（元）（元）利润由原来的利润由原来的27500元增加到元增加到27750元。元。使用百分之一百法则进行灵敏度分析时，要注意以下三点：使用百分之一百法则进行灵敏度分析时，要注意以下三点：1）当允许增加量（减少量）为）当允许增加量（减少量）为 时，则对于任一个增加量时，则对于任一个增加

24、量 （减少量），其允许增加（减少）百分比都看成（减少量），其允许增加（减少）百分比都看成 0。2）百分之一百法则是判断最优解或对偶价格不变的充分条）百分之一百法则是判断最优解或对偶价格不变的充分条 件，但不是必要条件。件，但不是必要条件。即当其允许增加和减少百分比之和超过即当其允许增加和减少百分比之和超过 百分之一百时，我们不能判断其最优解或对偶价格是否发生变化。百分之一百时，我们不能判断其最优解或对偶价格是否发生变化。3）若百分之一百法则不能应用于目标函数决策变量系数和）若百分之一百法则不能应用于目标函数决策变量系数和 约束条件右边常数值同时变化的情况，在这种情况下，只能重新约束条件右边常数

25、值同时变化的情况，在这种情况下，只能重新 求解。求解。19目标函数：目标函数：,32min21xxf约束条件：约束条件：,35021 xx,1251x,600221 xx.0,021xx以以 P15 例例2为例：为例：20目标函数最优值为目标函数最优值为:800（万元）（万元）变量变量 最优解最优解 相差值相差值 21xx10025000约束约束 松弛松弛/剩余变量剩余变量 对偶价格对偶价格 321012501 0 4目标函数系数范围目标函数系数范围:变量变量 下限下限 当前值当前值 上限上限 21xx2无无下下限限32无无上上限限3常数范围常数范围:约束约束 下限下限 当前值当前值 上限上限

26、 321475300无无下下限限600125350700250475211.购进购进A 原料原料250吨吨,B 原料原料100吨时吨时,购进成本最低为购进成本最低为800万元。万元。2.约束条件约束条件(对所有原料的总需要量对所有原料的总需要量)的剩余变量为零的剩余变量为零;若把加工时数从若把加工时数从600小时增加到小时增加到601小时小时,总成本将得到改进总成本将得到改进,价格为价格为-4,约束条件约束条件(对加工时数的限制对加工时数的限制)的松弛变量值为的松弛变量值为0.若把购进原料若把购进原料A 和和B 的总量从下限的总量从下限350吨增加到吨增加到351吨吨,总成本总成本 增加到增加

27、到:800+4=804万元万元;若购进原料总量从若购进原料总量从350吨减少到吨减少到349吨吨,总成本将会得到改进总成本将会得到改进,减少到减少到:800 4=796万元万元;约束条件约束条件的剩余变量为的剩余变量为125;其对偶价格为其对偶价格为0,若把购进原料若把购进原料A 的下限由的下限由125吨增加到吨增加到126吨吨,总成本的最优值总成本的最优值 (最低价最低价)不会发生变化不会发生变化 .其对偶其对偶 价格为价格为1,变为变为:800-1=799万元万元.其对偶其对偶 22当约束条件右端常数项增加一个单位时，最优目标当约束条件右端常数项增加一个单位时，最优目标函数值增加的数量，称为函数值增加的数量，称为这个约束条件的影子价格这个约束条件的影子价格.影子价格与对偶价格的关系：影子价格与对偶价格的关系：(1)当求目标函数值最大值时，增加的数量就是改进的数量，当求目标函数值最大值时，增加的数量就是改进的数量，此时影子价格就等于对偶价格此时影子价格就等于对偶价格.(2)当求目标函数值最小值时，改进的数量就是减少的数量，当求目标函数值最小值时，改进的数量就是减少的数量，此时影子价格就是负的对偶价格此时影子价格就是负的对偶价格.影子价格：影子价格：23