运筹学 第二章 灵敏度分析课件

1、第二章第二章 线性规划的线性规划的灵敏度分析灵敏度分析在根据一定数据求得最优解后，当这些数据中某在根据一定数据求得最优解后，当这些数据中某一个或某几个发生变化时，对最优解会产生什么影响。一个或某几个发生变化时，对最优解会产生什么影响。或者说，要使最优解保持不变，各个数据可以有多大或者说，要使最优解保持不变，各个数据可以有多大的幅度的变动。这种研究线性规划模型的原始数据变的幅度的变动。这种研究线性规划模型的原始数据变化对最优解产生的影响就叫做线性规划的灵敏度分析。化对最优解产生的影响就叫做线性规划的灵敏度分析。这些系数在什么范围内发生变化时，最优基不变（即最这些系数在什么范围内发生变化时，最优基

2、不变（即最优解或最优解结构不变）？优解或最优解结构不变）？系数变化超出上述范围时，如何用最简便的方法求出新系数变化超出上述范围时，如何用最简便的方法求出新的最优解？的最优解？回答两个问题：回答两个问题：例例1.1 max z = 300 x1 + 500 x2 x1 4 s.t. 2x2 12 3x1 + 2x2 18 x1, x2 0下列模型中，对最优值有影响的因素有哪些？ 灵敏度分析的内容灵敏度分析的内容（单个变化和多个变化）目标函数系数目标函数系数 变化的灵敏度分析变化的灵敏度分析jc约束右端值约束右端值 变化的灵敏度分析变化的灵敏度分析ib（单个变化和多个变化）约束条件系数约束条件系数

3、 变化的灵敏度分析变化的灵敏度分析ija约束条件数量变化的灵敏度分析约束条件数量变化的灵敏度分析变量变量 变化的灵敏度分析变化的灵敏度分析jx2.2 单个目标函数系数变化的灵敏度分析单个目标函数系数变化的灵敏度分析jc只有一个系数只有一个系数 发生变化，即其他条件均不变，把发生变化，即其他条件均不变，把 300 改成改成 500jc12121212max3005004212. .3218,0zxxxxstxxx x12121212max5004212. .3218,0500zxxxxstxxx x最优解没有改变最优解没有改变用用Excel求解求解2.2.1 敏感性报告敏感性报告几个基本概念几个

4、基本概念递减成本：递减成本： 它的绝对值表示目标函数中决策变量的系数必须改进多少，才能得到该决策变量的正数解。0表示不需再改进。表示不需再改进。目标式系数：目标式系数： 指目标函数中的系数允许增量、允许减量：允许增量、允许减量：表示目标函数中的系数在允许的增量与减量范围内变化时，原问题的最优解不变。450450和和1E+301E+30的含义是什么？的含义是什么？2.2.2 图解法图解法 2x1x2 4 6 82468 71531753可行域c1=0(z=0 x1+500 x2)c1=750(z=750 x1+500 x2)c1=300(z=300 x1+500 x2)0=c1=7502.3 多

5、个目标函数系数同时变化多个目标函数系数同时变化多个系数多个系数 发生变化，即其他条件均不变，把发生变化，即其他条件均不变，把300改成改成450，把把500改成改成400jc12121212max3005004212. .3218,0zxxxxstxxx x12121212max4212. .3218,0450400zxxxxstxxx x最优解没有改变最优解没有改变 敏感性报告敏感性报告不能反映多个目标函数系数改变时带来的影响不能反映多个目标函数系数改变时带来的影响 敏感性报告敏感性报告百分之百法则百分之百法则p定义定义 如果目标函数系数同时变化，计算出每一系数变化量占该系数允许变化量的百分

6、比，然后将各个系数变化的百分比相加。 如果所得的变化的百分比总和不超过如果所得的变化的百分比总和不超过100%，则最优，则最优解不会改变；如果超过了解不会改变；如果超过了100%，则不能确定最优解，则不能确定最优解是否改变，可通过重新运行是否改变，可通过重新运行“规划求解规划求解”命令来判命令来判断断 敏感性报告敏感性报告百分之百法则百分之百法则p作用作用 1. 可用于确定在保持最优解不变的条件下，目标函数系数的变化范围； 2. 百分之百法则通过将允许的增加量或减少量在各个系数之间进行分摊，从而可以直接显示出每个系数允许的变化值； 3. 线性规划求解后，如果将来条件变化，致使目标函数中一部分或

7、所有系数都发生变化，那么百分之百法则可以直接表明最初最优解是否保持不变例例1.1百分比总和百分比总和100% 最优解变化与否不确定最优解变化与否不确定p门的单位利润c1=300 c1=600，占允许增加量的百分比p窗的单位利润c2=500 c2=300 ，占允许减少量的百分比600300100%66.67%450500300100%66.67%300变化的百分比总和为变化的百分比总和为133.34%，所以所以最优解变化与否不确定，需通过最优解变化与否不确定，需通过“规划求解规划求解”重新计算重新计算重新重新“规划求解规划求解”得到得到最优解改变，最大利润改变最优解改变，最大利润改变例例1.1

8、百分比总和百分比总和=100% 最优解不变最优解不变p门的单位利润c1=300 c1=525，占允许增加量的百分比p窗的单位利润c2=500 c2=350 ，占允许减少量的百分比525300100%50%450500350100%50%300变化的百分比总和为变化的百分比总和为100%，所以所以最优解不变最优解不变2.6 约束条件系数变化的灵敏度分析约束条件系数变化的灵敏度分析p约束条件中的技术（工艺）系数 ，往往涉及车间生产能力、产品消耗资源数等比较确定的数据，这些参数变化的时候也会对最优解产生影响。ija1212121231.max300500412. .32,518,0zxxxxstxx

9、x x x12121212max3005004212. .3218,0zxxxxstxxx x规划求解得到规划求解得到2.7 增加一个新变量增加一个新变量在例1.1中，如果增加一个变量x3，比如考虑增加一种新产品：防盗门，单位利润400元，生产一扇防盗门会占用车间1、车间2、车间3各2、1、1小时，此时，新的线性规划模型变为： 1212121233333max3005004212. .321840,002,xxxzxxxxsxxxxtxx12121212max3005004212. .3218,0zxxxxstxxx x规划求解得到规划求解得到2.8 增加一个约束条件增加一个约束条件p增加一个

10、约束条件，比如增加电力供应限制时，最优解是否会发生变化？p假设生产一扇门和窗需要消耗电力分别为20kw和10kw，工厂可供电量最多为90kw，此时应该在原有的模型中加入新的约束条件： 12201090 xx模型模型12121212max3005004212. .3218,0zxxxxstxxx x1212111222max3005004212. . 3220109108,0 xxzxxxxstxxx x2.4 单个约束右端值变化的灵敏度分析单个约束右端值变化的灵敏度分析p只有一个约束右端值 发生变化，即如果其他条件均不变，把12改成13ib12121212max3005004212. .321

11、8,0zxxxxstxxx x12121212max30050042. .3218,013zxxxxstxxx x最优解改变，利润增加最优解改变，利润增加最优解不改变，利润不变最优解不改变，利润不变如果车间如果车间2的可用工时不断增加，会出现什么情况？的可用工时不断增加，会出现什么情况？为什么？为什么？2.4.1 敏感性报告敏感性报告阴影价格阴影价格，显示了约束右端值每增加（或减少），显示了约束右端值每增加（或减少）1个单位，目标函数值（或最优值）相应的增加个单位，目标函数值（或最优值）相应的增加量（减少量）量（减少量）可从敏感性报告中获得的信息？可从敏感性报告中获得的信息？p影子价格的解释：

12、影子价格的解释：1. 线性规划的对偶问题线性规划的对偶问题例例1.1的线性规划问题为的线性规划问题为 补充说明：补充说明： 影子价格影子价格12121212max3005004212. .3218,0zxxxxstxxx x现从另一角度提出问题。假定某现从另一角度提出问题。假定某A公司想把该工厂的资源收购过公司想把该工厂的资源收购过来，它至少应付出多大代价，才能使该工厂愿意放弃生产活动，来，它至少应付出多大代价，才能使该工厂愿意放弃生产活动，出让自己的资源？显然该工厂愿意出让自己资源的条件是：出让自己的资源？显然该工厂愿意出让自己资源的条件是：出让出让代价应不低于用同等数量资源由自己组织生产活

13、动时获取的赢利代价应不低于用同等数量资源由自己组织生产活动时获取的赢利。设分别用设分别用y1、y2、y3代表单位时间车间代表单位时间车间1、车间、车间2、车间、车间3的出让代的出让代价，因该价，因该工厂用工厂用1小时车间小时车间1和和3小时车间小时车间3可生产可生产1扇门，赢利扇门，赢利300元；分别用元；分别用2小时车间小时车间2和车间和车间3可生产可生产1扇窗，赢利扇窗，赢利500元，元，由此，由此，y1、y2、y3的取值应满足：的取值应满足： y1 + 3y3 3002y2 + 2y3 500A公司希望用最小的代价把该工厂的全部资源收买过来，故有公司希望用最小的代价把该工厂的全部资源收买

14、过来，故有 min z = 4y1 + 12 y2 + 18y3 显然，显然，yi 0 (i=1,2,3)综上，现在的问题为：综上，现在的问题为： 该问题为原问题的该问题为原问题的对偶问题对偶问题该问题的最优解的意义：该问题的最优解的意义： 代表资源最优利用条件下对单位第代表资源最优利用条件下对单位第i种资源的估价。种资源的估价。这种这种估价不是资源的市场价格，而是根据资源在生产中作出的贡估价不是资源的市场价格，而是根据资源在生产中作出的贡献而做的估价，为区别起见，称为献而做的估价，为区别起见，称为影子价格（阴影价格）影子价格（阴影价格）1231323123min412183300. . 22

15、500,0zyyyyystyyy yy影子价格影子价格p资源的市场价格是其价值的客观体现，相对比较资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于稳定，而它的影子价格则有赖于资源的利用情况资源的利用情况，是未知数。是未知数。p影子价格是一种边际价格影子价格是一种边际价格p资源的影子价格实际上又是一种机会成本资源的影子价格实际上又是一种机会成本2.4.1 敏感性报告敏感性报告阴影价格阴影价格，显示了约束右端值每增加（或减少），显示了约束右端值每增加（或减少）1个单位，目标函数值（或最优值）相应的增加个单位，目标函数值（或最优值）相应的增加量（减少量）量（减少量）基本概念基本

16、概念约束限制值：允许的增量：针对影子价格不变允许的减量：针对影子价格不变可从敏感性报告中获得的信息？可从敏感性报告中获得的信息？2.4.2 图解法图解法改变车间改变车间2的约束的约束 2x1x2 4 6 82468 71531753可行域2x2=182x2=122x2=6改变车间改变车间1的约束又会是如何的？的约束又会是如何的？但此时敏感性报告是否有效？但此时敏感性报告是否有效？2.5 多个约束右端值同时变化的灵敏度分析多个约束右端值同时变化的灵敏度分析p分析1小时的工时从车间3移到车间2，对总利润所产生的影响。p那么，根据影子价格，可知总利润变化量如下： 车间2: 12-13，利润增加？元 车间3: 18-17，利润减少？元因此，总利润增加？元2.5.1 敏感性报告敏感性报告百分之百法则百分之百法则p含义：如果约束右端值同时变化，计算每一右端值变化量占该约束右端值允许变化量的百分比，然后将每个约束右端值变化的百分比相加。如果所得的变化的百分比总和不如果所得的变化的百分比总和不超过超过100%，那么影子价格依然有效，那么影子价格依然有效；如果超过了如果超过了100%，那就无法确定影子价格是否依然有效，那就无法确定影