搜索
第三章线性规划的灵敏度分析与最优解的解释讲授人：朱玉春教授单位：经济管理学院2011年西北农林科技大学引言灵敏度分析是研究当一个线性规划问题中的系数发生变化时，其对函数最优解的影响程度。运用灵敏度分析，我们可以回答以下问题：1.如果目标函数的系数发生了变化，对最优解会产生什么影响？2.如果改变约束条件的右端值，对最优解会产生什么影响？首先我们将介绍如何使用图解法进行双变量线性规划问题的灵敏度分析，然后介绍如何使用管理科学家软件得到灵敏度分析报告。本章主要内容3.1灵敏度分析简介3.2图解法灵敏度分析3.3灵敏度分析：计算机求解3.4多于两个决策变量的情况3.5电子通信公司问题3.1灵敏度分析简介灵敏度分析对于决策者的重要性不言而喻。在真实世界里，周围的环境，条件是在不断变化的。原材料的成本在变，产品的需求在变，公司购买新设备、股票价格的波动，员工流动等等这些都在不断发生。如果我们要用线性规划模型去解决实际问题，那模型中的系数就不可能是一成不变的。这些系数的变化会对模型的最优解产生什么样的影响呢？运用灵敏度分析，我们只需要改变相应的系数就可以得到答案，而不需要建立新的模型。3.1灵敏度分析简介回忆Par公司的问题：我们已经知道这个问题的最优解是标准袋生产540个，高级袋生产252个，这个最优解的前提是每个标准袋的利润是10美元，每个高级袋的利润是9美元。3.1灵敏度分析简介假设，我们得知由于价格的下降，标准袋的利润由10美元下降到8.5美元。这时我们可以用灵敏度分析来确定标准袋生产540个，高级袋生产252个是否还是最优解。如果还是，则不必建立新的模型求解了。灵敏度分析还可以用来分析模型中的系数哪个更能左右最优解。比如，管理层认为高级袋的利润9美元只是一个估计量，如果通过灵敏度分析得到高级袋的利润在6.67和14.29美元之间变化时，模型的最优解都是540个标准袋和252个高级袋，那么管理层就对9美元这个估计量和模型所得出的最优产量比较满意。但是，如果灵敏度分析告诉我们只有当高级袋的利润在8.9和9.25美元之间，模型的最优解才是540个标准袋和252个高级袋，那么管理层就必须思考9美元这个估计量的可信程度有多大了。3.1灵敏度分析简介灵敏度分析的另一个用途是分析约束条件的右端值变化对最优解的影响。还是以Par公司为例，在最优产量的情况下，切割与印染部门和成型部门的工作时间已经完全被占用了。如果现在公司增加了这两个部门的生产能力，那么最优解以及总利润的值会发生什么样的变化呢？灵敏度分析可以帮助确定每一个工时的边际价值，以及在利润下降之前部门工时的最大增加量。3.2图解法灵敏度分析对于双变量的线性规划问题，当目标函数的系数或约束条件的右端值变化时，用图解法对其进行灵敏度分析。我们先思考目标函数的系数变化会对Par公司的最优产量产生什么样的影响。选择每个标准袋的利润是10美元，每个高级袋的利润是9美元，如果其中一种袋子利润下降，公司就会削减其产量，如果利润上升，公司就会增加其产量。究竟利润变化多少，管理者才应该改变产量呢？现在，模型的最优解540个标准袋和252个高级袋。每个目标函数系数都有一个最优范围，即目标函数系数在什么范围内变化，模型的最优解保持不变。3.2图解法灵敏度分析3.2.1目标函数系数认真观察图发现，只要目标函数直线的斜率处于直线A（和切割与印染约束线重合）的斜率与直线B（与成型约束线重合）的斜率之间，极点3（S=540，D=252）就是最优解的点。改变目标函数里S和D的系数，引起目标函数直线斜率的变化，即绕着极点3旋转。只要目标函数直线仍在阴影区域内，极点3仍是最优解。3.2图解法灵敏度分析逆时针转动目标函数直线，使其斜率变成一个绝对值更小的负数，从而斜率变大了。直到与A重合，我们就获得了多重最优解——在极点3和极点4之间的点都是最优点。因此A的斜率是目标函数直线的上限。顺时针转动目标函数直线，使其斜率变成一个绝对值更大的负数，从而斜率变小了。直到与B重合，我们又获得了多重最优解——极点3和极点2之间都是最优点。因此B的斜率是目标函数直线斜率的下限。因此，极点3总是最优解点，只要直线B的斜率≤目标函数直线的斜率≤直线A的斜率3.2图解法灵敏度分析根据直线A和直线B的表达式，可以算出A的斜率是-7/10，截距是630。B的斜率是-3/2，截距是1062。则直线A和直线B的斜率都已经计算出来了，我们来看保持极点3仍然为最优解点，应满足条件：-3/2≤目标函数的斜率≤-7/103.2图解法灵敏度分析现在让我们考虑目标直线斜率的一般形式。用CS表示标准袋的利润，CD表示高级袋的利润，P表示目标函数值。使用这些标识，目标函数直线可以写成：P=CSS+CDD把上面方程写成斜截式，得到CDD=-CSS+P以及D=-S(CS/CD)+P/CD因此我们看到只要满足下列条件，极点3就仍然为最优解点：-3/2≤-CS/CD≤-7/103.2图解法灵敏度分析为了计算标准袋利润最优的范围，我们假设高级袋的利润CD=9，代入上式得-3/2≤-CS/9≤-7/10从左边的不等式得到-3/2≤-CS/9或者3/2≥CS/9从右边的不等式得到-CS/9≥-7/10或者CS/9≥7/10综合标准袋利润CS的极限，标准袋最优范围为6.3≤CS≤13.53.2图解法灵敏度分析因此，只要标准袋的利润在6.3美元与13.5美元之间，540个标准袋和252个高级袋总是最优产量。值得注意的是，即使产量不变，总的利润也可能由于每一个标准袋利润的变化而变化。这些计算可以重复进行，假设标准袋的利润为常数CS=10，如此一来，高级袋的利润的最优范围就能够确认，这个范围是6.67≤CD≤14.29。3.2图解法灵敏度分析当目标函数绕最优点旋转，使之与坐标轴垂直时，像式中出现的那种斜率的上限或下限就不存在了。为了说明这种特殊情况，我们设Par公司的目标函数为18CS+9CD；这样，图中，极点2是最优解点，绕着极点2逆时针旋转目标函数，当目标函数与直线B重合时，就得到了斜率的上限-3/2。所以目标函数斜率上限一定是-3/2。最后当目标函数垂直于坐标轴时，其斜率接近负无穷大，在这种情况下，目标函数的斜率没有下限，只有上限-3/2。-CS/CD≤-3/23.2图解法灵敏度分析按照前面假定的CD的值，仍为常数9，我们得到-CS/9≤-3/2或者CS/9≥3/2解出CS，得CS≥27/2=13.5我们注意到，只要CS的值大于等于13.5，极点2仍然是最优解点，因此我们得到以极点2为最优解的CS的范围，如下13.5≤CS＜∞3.2图解法灵敏度分析多系数同时改变目标函数系数的最优范围只能够应用于一次只有一个系数发生改变的情况，其他系数都假定保持初值而不发生改变。如果两个或两个以上目标函数的系数被同时改变，就有必要进一步判断最优解会不会也发生变化。对于解决只有两个变量的问题时，简单的计算出在新的系数值下目标函数的斜率（-CS/CD），如果这个比值大于等于目标函数斜率的下限，同时小于等于目标函数斜率的上限，那么系数值的变化不会使最优解发生变化。3.2图解法灵敏度分析观察最优范围，我们得出结论，无论是CS升高到13美元还是使CD降低到8美元（但不是同时改变），都不会带来最优解的变化。但当CS与CD同时改变时，目标函数斜率的变化导致了最优解的变化。这个结论强调了这样一个事实：仅仅是通过最优范围，只能用于判断在一次改变一个目标函数系数的情况下最优解的变化。3.2图解法灵敏度分析3.2.2约束条件右端值的变化现在让我们来考虑约束条件右端值的变化对可行域带来的影响，及其可能对最优解带来的变化。为了阐明敏感度分析的这方面内容，我们假设Par公司的切割与印染部门增加了10个小时的生产时间，然后来考虑将会有什么发生。切割与印染约束条件的右端值由630变为640，约束条件可写作7/10S+D≤6403.2图解法灵敏度分析获得10小时的切割与印染时间，我们可以扩展问题的可行域。运用图解法可以看出，极点S=527.5，D=270.5是最优解点。新的目标函数值为10*527.5+9*270.5=7711.75美元，比原先利润增加了43.75美元。约束条件右端值每增加一个单位引起的最优值的变化量称为对偶价格。在这个例子里，切割与印染约束条件的对偶价格为4.375美元。约束条件增加或减少一小时，目标函数值会相应增加或减少4.375美元。3.2图解法灵敏度分析在这里，我们要注意的是，对偶价格可能只适用于在右端值仅发生了很小的变动时的情况。随着所获得的资源越来越多，从而右端值越来越大，其他的约束条件也可能会约束和限制目标函数值的变化。3.3灵敏度分析：计算机求解为了使用管理科学家软件，我们使用小数代替分数。Par公司的问题用小数形式的系数表示如下：Max10S+9Ds.t.0.7S+D≤630切割与缝合0.5S+0.83333D≤600缝合1.0S+0.66667D≤708成型0.1S+0.25D≤135检查与包装S,D≥03.3灵敏度分析：计算机求解3.3.1计算机输出的解释——第一个例子回忆Par公司的例子，其中有4个小于或等于约束条件的，都是关于各个生产部门的生产时间。在松弛/剩余变量一栏中，可以看到每个部门的松弛变量值。信息归总如下：从上述数据中，我们可以看到束缚性约束条件（切割与印染和成型）在目标函数的最优下，松弛为0。缝合部门有120小时的松弛或未使用的缝合能力，检查与包装部门有18小时的松弛。3.3灵敏度分析：计算机求解3.3灵敏度分析：计算机求解这里，约束条件1（切割与印染）和约束条件3（成型）的非零对偶价格分别为4.37496和6.93753。这告诉我们，每额外增加1小时的切割与印染时间会使最优解增加4.37美元，每增加1小时成型时间会使最优解增加6.94美元。看上图结果，我们看到管理科学家软件除了提供松弛/剩余变量和对偶价格的约束信息之外，还给出了目标函数系数和约束条件右端值的变化范围。变量S的最优化范围是：6.3≤CS≤13.5变量D的最优化范围是：6.67≤CD≤14.29这个最优化范围与图解法得出的结论是一致的。3.3灵敏度分析：计算机求解计算机输出结果的最后一部分右端值范围给出了对偶价格适用范围的限制条件。只要约束条件右端值处于系统所给出的下限和上限之间，对偶价格就会给出当右端值增加1时，最优解的增加量。右端值范围给出了一个对偶价格的适用范围。如果右端值的变化超出了这个范围，就需要重解原问题并找出新的对偶价格。我们把这个对偶价格适用的范围称作可行域。Par公司问题的可行域汇总如下。只要右端值在这些范围之内，系统分析结果中的那些对偶价格就不会改变。右端值如果超过了这些范围，对偶价格信息会随之改变。3.3灵敏度分析：计算机求解3.3.2多系数同时变化系统灵敏度分析的输出是基于单函数系数变化的。它假设所有其他系数都保持不变。因此目标函数系数和约束右端值的变化范围只能适用于单个系数发生变化的情况。然而很多情况下，我们可能更关注两个或两个以上系数同时变化时，目标函数将怎样变化。有些多系数同时变化的分析可能会用到100%法则。下面分析如何应用100%法则。3.3灵敏度分析：计算机求解假设Par公司的会计部门指出原先的标准袋和高级袋利润计算有误，应该是11.5美元和8.25美元。为了确定这样的变化是否会对最优解产生影响，我们先要定义两个术语“允许增加量”和“允许减少量”。对于目标函数的系数，允许增加量是在不超过最优范围的情况下，系数尽可能增加的最大量；而允许减少量是在不低于最优范围下限的情况下，系数可能减少的最大量。3.3灵敏度分析：计算机求解目标函数系数的100%法则对所有变化的目标函数系数，计算其占允许增加量和允许减少量的百分比之和。如果和没有达到100%，最优解就不会改变。但是，100%法则并没有规定如果各百分比之和达到100%，最优解一定会发生变化。如果100%法则的条件不能被满足，就必须对问题重新求解，以确定最优解是否发生变化。3.3灵敏度分析：计算机求解下面100%法则