运筹学 第二章 灵敏度分析

第二章线性规划的灵敏度分析在根据一定数据求得最优解后，当这些数据中某一个或某几个发生变化时，对最优解会产生什么影响。或者说，要使最优解保持不变，各个数据可以有多大的幅度的变动。这种研究线性规划模型的原始数据变化对最优解产生的影响就叫做线性规划的灵敏度分析。①这些系数在什么范围内发生变化时，最优基不变（即最优解或最优解结构不变）？②系数变化超出上述范围时，如何用最简便的方法求出新的最优解？回答两个问题：例1.1maxz=300x1+500x2x14s.t.2x2123x1+2x218x1,x20下列模型中，对最优值有影响的因素有哪些？灵敏度分析的内容（单个变化和多个变化）目标函数系数变化的灵敏度分析jc约束右端值变化的灵敏度分析ib（单个变化和多个变化）约束条件系数变化的灵敏度分析ija约束条件数量变化的灵敏度分析变量变化的灵敏度分析jx2.2单个目标函数系数变化的灵敏度分析jc只有一个系数发生变化，即其他条件均不变，把300改成500jc12121212max3005004212..3218,0zxxxxstxxxx12121212max5004212..3218,0500zxxxxstxxxx最优解没有改变用Excel求解2.2.1敏感性报告几个基本概念递减成本：它的绝对值表示目标函数中决策变量的系数必须改进多少，才能得到该决策变量的正数解。0表示不需再改进。目标式系数：指目标函数中的系数允许增量、允许减量：表示目标函数中的系数在允许的增量与减量范围内变化时，原问题的最优解不变。450和1E+30的含义是什么？2.2.2图解法2x1x2468246871531753（2,6）是最优解可行域c1=0(z=0x1+500x2)c1=750(z=750x1+500x2)c1=300(z=300x1+500x2)0=c1=7502.3多个目标函数系数同时变化多个系数发生变化，即其他条件均不变，把300改成450，把500改成400jc12121212max3005004212..3218,0zxxxxstxxxx12121212max4212..3218,0450400zxxxxstxxxx最优解没有改变敏感性报告不能反映多个目标函数系数改变时带来的影响敏感性报告——百分之百法则定义如果目标函数系数同时变化，计算出每一系数变化量占该系数允许变化量的百分比，然后将各个系数变化的百分比相加。如果所得的变化的百分比总和不超过100%，则最优解不会改变；如果超过了100%，则不能确定最优解是否改变，可通过重新运行“规划求解”命令来判断敏感性报告——百分之百法则作用1.可用于确定在保持最优解不变的条件下，目标函数系数的变化范围；2.百分之百法则通过将允许的增加量或减少量在各个系数之间进行分摊，从而可以直接显示出每个系数允许的变化值；3.线性规划求解后，如果将来条件变化，致使目标函数中一部分或所有系数都发生变化，那么百分之百法则可以直接表明最初最优解是否保持不变例1.1——百分比总和100%——最优解不变门的单位利润c1=300c1=450，占允许增加量的百分比窗的单位利润c2=500c2=400，占允许减少量的百分比500400100%33.33%300变化的百分比总和为66.66%，所以最优解不变450300100%33.33%450例1.1百分比总和100%——最优解变化与否不确定门的单位利润c1=300c1=600，占允许增加量的百分比窗的单位利润c2=500c2=300，占允许减少量的百分比600300100%66.67%450500300100%66.67%300变化的百分比总和为133.34%，所以最优解变化与否不确定，需通过“规划求解”重新计算重新“规划求解”得到最优解改变，最大利润改变例1.1百分比总和=100%——最优解不变门的单位利润c1=300c1=525，占允许增加量的百分比窗的单位利润c2=500c2=350，占允许减少量的百分比525300100%50%450500350100%50%300变化的百分比总和为100%，所以最优解不变2.6约束条件系数变化的灵敏度分析约束条件中的技术（工艺）系数，往往涉及车间生产能力、产品消耗资源数等比较确定的数据，这些参数变化的时候也会对最优解产生影响。ija1212121231.max300500412..32,518,0zxxxxstxxxxx12121212max3005004212..3218,0zxxxxstxxxx规划求解得到2.7增加一个新变量在例1.1中，如果增加一个变量x3，比如考虑增加一种新产品：防盗门，单位利润400元，生产一扇防盗门会占用车间1、车间2、车间3各2、1、1小时，此时，新的线性规划模型变为：1212121233333max3005004212..321840,002,xxxzxxxxsxxxxtxx12121212max3005004212..3218,0zxxxxstxxxx规划求解得到2.8增加一个约束条件增加一个约束条件，比如增加电力供应限制时，最优解是否会发生变化？假设生产一扇门和窗需要消耗电力分别为20kw和10kw，工厂可供电量最多为90kw，此时应该在原有的模型中加入新的约束条件：12201090xx模型12121212max3005004212..3218,0zxxxxstxxxx1212111222max3005004212..3220109108,0xxzxxxxstxxxx2.4单个约束右端值变化的灵敏度分析只有一个约束右端值发生变化，即如果其他条件均不变，把12改成13ib12121212max3005004212..3218,0zxxxxstxxxx12121212max30050042..3218,013zxxxxstxxxx最优解改变，利润增加最优解不改变，利润不变如果车间2的可用工时不断增加，会出现什么情况？为什么？2.4.1敏感性报告阴影价格，显示了约束右端值每增加（或减少）1个单位，目标函数值（或最优值）相应的增加量（减少量）可从敏感性报告中获得的信息？？影子价格的解释：1.线性规划的对偶问题例1.1的线性规划问题为补充说明：影子价格12121212max3005004212..3218,0zxxxxstxxxx现从另一角度提出问题。假定某A公司想把该工厂的资源收购过来，它至少应付出多大代价，才能使该工厂愿意放弃生产活动，出让自己的资源？显然该工厂愿意出让自己资源的条件是：出让代价应不低于用同等数量资源由自己组织生产活动时获取的赢利。设分别用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公司希望用最小的代价把该工厂的全部资源收买过来，故有minz=4y1+12y2+18y3显然，yi≥0(i=1,2,3)综上，现在的问题为：该问题为原问题的对偶问题该问题的最优解的意义：代表资源最优利用条件下对单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而做的估价，为区别起见，称为影子价格（阴影价格）1231323123min412183300..22500,,0zyyyyystyyyyy影子价格资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。影子价格是一种边际价格资源的影子价格实际上又是一种机会成本2.4.1敏感性报告阴影价格，显示了约束右端值每增加（或减少）1个单位，目标函数值（或最优值）相应的增加量（减少量）基本概念约束限制值：允许的增量：针对影子价格不变允许的减量：针对影子价格不变可从敏感性报告中获得的信息？？2.4.2图解法——改变车间2的约束2x1x2468246871531753（2,6）是最优解可行域2x2=182x2=122x2=6改变车间1的约束又会是如何的？但此时敏感性报告是否有效？2.5多个约束右端值同时变化的灵敏度分析分析1小时的工时从车间3移到车间2，对总利润所产生的影响。那么，根据影子价格，可知总利润变化量如下：车间2:12--13，利润增加？元车间3:18--17，利润减少？元因此，总利润增加？元2.5.1敏感性报告——百分之百法则含义：如果约束右端值同时变化，计算每一右端值变化量占该约束右端值允许变化量的百分比，然后将每个约束右端值变化的百分比相加。如果所得的变化的百分比总和不超过100%，那么影子价格依然有效；如果超过了100%，那就无法确定影子价格是否依然有效，可通过重新运行“规划求解”命令来判断。灵敏度分析的应用举例课本P50，例2.3，回答五个问题1.产品甲的单位利润将会在3.8万元~5.2万元之间波动，公司该如何应对这种情况，提前对生产格局做好调整预案？2.当资源A的限额（储备量）在42~46之间变化时，对线性规划的影响？3.材料B在最优生产格局中出现了12.5单位的剩余，那么应如何重新制定限额，做好节约工作？4.若公司停止生产，把各种原材料变卖。该如何决策？影子价格与线性规划的对偶问题课本P54