图解法的灵敏度分析课件

1、3 图解法的灵敏度分析线性规划的标准形式为：目标函数：约束条件：（或 ）其中 为第 个决策变量 的系数；为第 个约束条件中的第个决策变量 的系数；为第 个约束条件的常数项，且13 图解法的灵敏度分析线性规划的标准形式为：目标函数：约束所谓灵敏度分析就是在建立数学模型和求得最优解之后，究线性规划的一些系数 变化时，对最优解有什么影响？研 3.1 目标函数中的系数 的灵敏度分析设目标函数为:改写为:显然,目标函数等直线的斜率为:对于前面的例 1,如左图:100200300400100200300400直线E(设备台时约束条件)直线G(原料A的约束条件)直线F(原料B的约束条件)目标函数直线ABCD

2、P162所谓灵敏度分析就是在建立数学模型和求得最优解之后，究线性规划2）当 时，BC上任一点都是其最优解。3)当 时,AB上任意一点都是最优解.1）当 时,仍是最优解。B点，即为了计算出 在什么范围内变化时顶点B仍是其最优解，单位产品的利润为100元不变，假设即则有解不等式得即单位产品的利润为100元，单位产品的利润在0与100元之间变化时，仍是最优解。32）当 时，BC上任一点都是即要计算出 在什么范围内变化时顶点B仍是其最优解，单位产品的利润为50元不变，假设则有解不等式得且即也即单位产品的利润为50元，单位产品的利润只要大于等于50元时，仍是最优解。同样，在 和 中一个值确定不变时，可以

3、求出另一个值的变化范围，使其最优解在C点（或在D点，或在A点）。若 和 都变化时，可通过目标函数的斜率 判断B点、C点、D点或A点为最优解。4即要计算出 在什么范围内变化时顶点B仍是其最优解，单3.2 约束条件中右边系数 的灵敏度分析当约束条件右边系数 发生变化时,线性规划的可行域也将发生变化，就可能引起最优解的变化。将例1中的约束条件改为最优解为 点，解得最优解即增加了10个台时的设备。100200300400100200300400ABCD100200300400100200300400ABCD53.2 约束条件中右边系数 的灵敏度分析当约束条件右边系此时的最大利润为：比原来增加了：这主要

4、是由于增加了10个设备台时而获得的。即每增加一个台时的设备就可多获得的利润。对偶价格：在约束条件右边常数增加一个单位，而使最优目标函值得到改进的数量，称为这个约束条件的对偶价格。约束条件：的对偶价格。若将例1中的原料A增加10千克，改为则约束条件6此时的最大利润为：比原来增加了：这主要是由于增加了10个设备最优解仍为 点，100200300400100200300400ABCD100200300400100200300400ABCD最优值还是27500元。原料A的对偶价格为：即最优解仍为： 即原料A 增加10千克，只增加了库存，没有转化为利润。原因：原料 A 只用了：还有：没用。7最优解仍为

5、点，1002003004001002003约束条件(设备台时的限制条件)(原料A 的限制条件)(原料B 的限制条件)(决策变量非负约束条件)目标函数由此可知：当某约束条件中的松弛变量（或剩余变量）不为零， 则这个条件的对偶价格为零。总结如下，当约束条件右边常数增加一个单位时：1）如果对偶价格大于零，则其最优目标函数值变得更好，即 求最大值时，变得更大；求最小值是变得更小。 2）如果对偶价格小于零，则其最优目标函数值变坏，即求最 大值时变小了；求最小值时变大了。 3）如果对偶价格等于零，则其最优目标函数值不变。 8约束条件(设备台时的限制条件)(原料A 的限制条件)(原料B第三章 线性规划问题的

6、计算机求解输入中注意以下两点：解决线性规划问题的软件包分两种：(1)大规模的软件包：可解决包含数千个决策变量和约束条件的大型线性规划问题。(2)用于微型计算机的软件包: 可解决包含数百个决策变量的线性规划问题。(1)输入的系数可以是整数、小数，但不能是分数。(2)输入前先要合并同类项。 注：本软件可解决100个决策变量50个约束方程的线性规划问题. 9第三章 线性规划问题的计算机求解输入中注意以下两点：解决线目标函数最优值为: 27500变量 最优解 相差值约束 松弛/剩余变量 对偶价格目标函数系数范围:变量 下限 当前值 上限常数范围:约束 下限 当前值 上限10目标函数最优值为: 2750

7、0变量 目标函数最优值为: 27500变量 最优解 相差值目标函数最优值为: 27500表示:这个问题的最优解可得到利润 27500元;变量:即决策变量;最优解:使目标函数达到最优值的解:即生产产品50单位、产品250单位才能使利润达到最大值;相差值:表示:相应的决策变量的目标系数需要改进的数量, 使该决策变量有可能取正值, 当决策变量已经取正值, 则相差值为零.如 它们的相差值都为零。如果的相差值为30，则只有当产品的利润再提高30元, 即达到50+30=80元时,产品才可能生产, 即11目标函数最优值为: 27500变量 约束 松弛/剩余变量 对偶价格约束1:表示设备台时的限制.其剩余量(

8、松弛变量)为0, 即设备台时数全部用完.松弛变量:没有用完的资源数剩余变量:超出资源数. 对偶价格为50: 表示每增加一个设备台时, 可使总利润增加50元.约束2:是对原料A 的限制.其剩余量(松弛变量)为50, 即原料A 还有50千克没有使用. 对偶价格为0: 因为再增加原料A 只能增加库存, 不能增加利润.约束3:是对原料B 的限制.其剩余量(松弛变量)为0, 即原料B 全部用完. 对偶价格为50: 即每增加一千克的原料B可使总利润增加50元.12约束 松弛/剩余变量 目标函数系数范围:变量 下限 当前值 上限常数范围:约束 下限 当前值 上限灵敏度分析：研究目标函数的系数、右端常数及约束

9、方程中的 系数发生变化时，对最优解的影响。灵敏度分析所研究的问题：（1）为了保持现有的最优解或最优基不变，找出这些数据变化 的范围；（2）这些数据超出了（1）的范围时，如何尽快求出新的最优解 或最优基。 灵敏度分析 13目标函数系数范围:变量 下限变量 下限 当前值 上限当前值:表示目标函数中决策变量当前的系数:上限、下限： 指目标函数的决策变量的系数在此范围内变化时， 其线性规划的最优解不变。 对于此问题：只要 其最优解不变。 如：若 其最优解仍为 目标函数最优值为 优解就要发生变化。 但若 其最 对于c2有同样的道理。如何调整生产计划 ?目标函数系数范围:TP17-对目标函数的系数进行灵敏

10、度分析 14变量 下限 约束 下限 当前值 上限当前值: 表示约束条件右边现在的值: 上限、下限： 是指当约束条件在此范围内变化时，则与其对应的 约束条件的对偶价格不变。 对于此问题： 设备台时在250325之间变化时，其对偶价格都为50元； 原料A 在350+之间变化时，其对偶价格都为0 ； 原料B 在200300之间变化时，其对偶价格都为50元 。 如：若 而 设备台时的对偶价 格仍为50元， 但设备台时比原来减少了20个台时，利润减少， 此时目标函数的最优值为：27500-2050=26500（元）。TP18常数范围:-对右端常数进行灵敏度分析 15约束 下限 注： 计算机输出的关于目标

11、函数及约束条件的灵敏度分析都是 基于假设：只有一个系数值发生变化，而其它系数值保持不变。 问题： 若有两个或更多个的系数同时发生变化时，如何进行灵敏 度分析？百分之一百法则： 以例1为例： 原来产品的利润为每件50元、产品的利润为每件100元， 现在由于市场情况的变化每件产品产品的利润分别变为74元 和78元，最优解发生变化吗？允许增加值： 对一个目标函数的决策变量系数： 该系数在上限范围内的最大增加量； 允许减少值： 该系数在下限范围内的最大减少量。 16注： 计算机输出的关于目标函数及约束条件的灵敏度分析都是 对于例1：c1的允许增加量为：上限 当前值=100-50=50； c2的允许减少

12、量为：当前值- 下限 =100-50=50。 ci允许增加（减少）百分比： c1允许增加百分比为 ： (74-50) /50=48%; c2允许减少百分比为 ： (100-78) /50=44%; c1允许增加百分比与c2允许减少百分比之和为: 48%+44%=92%. 此线性规划的最优解不变，仍为： 此时最大利润为：7450+78250=23200（元）。 TP18TP14 17对于例1：c1的允许增加量为：上限 当前值=100-50目标函数决策变量系数的百分之一百法则: 对于所有变化的目标函数决策变量系数,当其所允许增加百分 比和允许减少百分比之和不超过100%时, 最优解不变. 约束条件

13、右边系数的百分之一百法则: 对于所有变化的约束条件的右边常数值,当其所允许增加百分 比和允许减少百分比之和不超过100%时, 其对偶价格不变. 对于例1： 若三个约束条件的变化为：设备台时数：从300台时增加为315台时； 原料A ：从400千克减少到390千克； 原料B ：从250千克减少到240千克 。 它们的允许增加（减少）百分比分别为： TP1515/25=60%； 10/50=20%； 10/50=20%。 允许增加百分比和允许减少百分比之和为： 18目标函数决策变量系数的百分之一百法则: 对于所有变化的目60%+20%+20%=100%。所以此线性规划的对偶价格不变。 利润的增加值

14、为： 5015 - 015 - 5010=250（元） 利润由原来的27500元增加到27750元。 使用百分之一百法则进行灵敏度分析时，要注意以下三点： 1）当允许增加量（减少量）为 时，则对于任一个增加量 （减少量），其允许增加（减少）百分比都看成 0 。 2）百分之一百法则是判断最优解或对偶价格不变的充分条 件，但不是必要条件。 即当其允许增加和减少百分比之和超过 百分之一百时，我们不能判断其最优解或对偶价格是否发生变化。 3）若百分之一百法则不能应用于目标函数决策变量系数和 约束条件右边常数值同时变化的情况，在这种情况下，只能重新 求解。 1960%+20%+20%=100%。所以此线

15、性规划的对偶价格不目标函数： 约束条件： 以 P15 例2为例： 20目标函数： 约束条件： 以 P15 例2为例： 20目标函数最优值为: 800（万元） 变量 最优解 相差值 约束 松弛/剩余变量 对偶价格 目标函数系数范围:变量 下限 当前值 上限 常数范围:约束 下限 当前值 上限 21目标函数最优值为: 800（万元） 变量 1. 购进A 原料250吨, B 原料100吨时, 购进成本最低为800万元。 2.约束条件(对所有原料的总需要量)的剩余变量为零; 若把加工时数从600小时增加到601小时, 总成本将得到改进,价格为- 4, 约束条件(对加工时数的限制)的松弛变量值为0. 若把购进原料A 和B 的总量从下限350吨增加到351吨,总成本 增加到: 800+4=804万元; 若购进原料总量从350吨减少到349吨,总成本将会得到改进, 减少到: 800 4=796万元; 约束条件的剩余变量为125; 其对偶价格为0, 若把购进原料A 的下限由125吨增加到126吨, 总成本的最优值 (最低价)不会发生变化 .其对偶 价格为1, 变为: 800-1=