第3章线性规划的灵敏度分析与最优解的解释

第三章线性规划的灵敏度分析与最优解的解释讲授人：朱玉春教授单位：经济管理学院

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+9D

s.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%法则相似的定理也可以用来解决多个约束条件右端值同时发生变化的情况：约束条件右端值的100%法则

对所有变化的右端值，计算其占允许增加量和允许减少量的百分比之和。如果和没有达到100%，对偶价格就不会改变。下面我们说明在Par公司问题中，多个右端值发生变化时，约束条件右端值的100%法则。3.3灵敏度分析：计算机求解

例如，假设切割与印染部门能获得额外的20个小时时间，同时成型部门能获得额外的100小时的时间，切割与印染时间的允许增量是52.36316，成型时间允许增量是192.0，新增的20小时切割与印染时间占约束条件右端值允许增加量的38.19%，额外的100小时成型占了总允许增加量的52.8%。二者百分比和为90.27%，没有超过100%，因此我们可以得出结论：对偶价格在这里是适用的，并且目标函数值将由此增加20*4.37+100*6.94=781.40.3.3灵敏度分析：计算机求解

3.3.4关于对偶价格解释的注释

如前所述，对偶价格是右端值每增加一个单位时对最优值的改进。当约束条件的右端值表示某种资源的可利用量时，对偶价格通常可以解释为公司对额外支付一单位这种资源所愿意提供的金额。然而这种解释也并非总是正确的。要理解这个问题，我们先要理解沉没成本和相关成本的区别。沉没成本不会受决策影响，无论决策变量为何值，这种成本都会发生。相关成本则取决于决策的制定，这种成本决定于决策变量值的变化。3.3灵敏度分析：计算机求解

重新考虑Par公司的例子。切割印染总时间是630小时，无论生产标准袋还是高级袋，都是按照时间来付工资的，那么时间成本就是一种沉没成本。如果Par公司只需要为那些切割与印染高尔夫球袋的时间偿付工资，那么时间成本就是一种相关成本。所有的相关成本都要在线性规划的目标函数中有所反映。3.3灵敏度分析：计算机求解

对Par公司而言，我们一直假设公司必须按照工作时间来向工人发工资，不管他们的工作时间是否有效率地被利用。因此，Par公司的劳动时间资源的成本就属于沉没成本而不在目标函数中反映出来。当某种资源的成本属于沉没成本，对偶价格就可以被解释为得到额外一个单位这种资源而付出的金额。当某种资源的成本属于相关成本，对偶价格则可以被解释为这种资源的价值超过其成本的数额，也就是增加一个这种资源时，公司能付出的最大成本量。3.4多于两个决策变量的情况

图解法只能应用于解决双决策变量的线性规划问题，而计算机软件是用来处理多变量和约束条件的线性规划问题的。在现实生活中，用线性规划解决的问题经常包含大量的变量和约束条件。

Par公司原来的问题模型如下：3.4多于两个决策变量的情况

假设管理者希望生产一种轻便的、可以被球手随身携带的球袋模型。设计部门估计每个新球袋将需要0.8小时的切割印染，1小时缝合，1小时成型和0.25小时检查包装。管理者认为每个轻便袋可以获利12.85美元。修改模型，加入新的决策变量，得模型：Max10S+9D+12.85Ls.t.0.7S+D+0.8L≤6300.5S+0.83333D+L≤630S+0.66667D+L≤7080.1S+0.25D+0.25L≤135S,D,L≥03.4多于两个决策变量的情况3.4多于两个决策变量的情况3.4多于两个决策变量的情况3.4多于两个决策变量的情况

计算机输出结果表明，S和L的减少的成本都为0，这是因为相应的决策变量值在最优解处已经是正值。变量D的减少的成本为1.15003，表明高级袋的利润至少增加到9+1.15003=10.15003美元，D才能变成一个正值。假设我们使D的系数正好增加1.15003美元，在用管理科学家软件来重解原问题。3.4多于两个决策变量的情况3.4多于两个决策变量的情况

我们注意到，尽管D的值已经是正数最优解的值仍然没有变。换言之，当D利润的增量正好等于其减少的成本时，能得到多重最优解。如果换一个软件解决问题，目标函数中D的系数正好是10.15003，D将不再是正值。这是因为软件得出了一个不同的最优解。但是，如果D的利润增加量超过1.15003美元，它在最优解处就不再是0。3.4多于两个决策变量的情况

假设管理者审核了解决方案后发现，他们会放弃所有不生产高级袋的方案，并要求高级袋的产量至少达到标准袋的30%。表示如下：D≥0.3S或者-0.3S+D≥0

把这个新的约束条件加入Par公司的模型中运用管理科学家软件进行重解，我们得到下图的最优解。3.4多于两个决策变量的情况3.4多于两个决策变量的情况

我们来解释约束条件的对偶价格，这一约束要求高级袋产量至少要达到标准袋产量30%。其对偶价格为-1.38，表明如果右端值增加一个单位，将使利润减少1.38美元。因此，-1.38的对偶价格告诉我们，如果约束条件变为如下形式，最优解将会怎么变化。D≥0.3S+13.4多于两个决策变量的情况

对-1.38的对偶价格比较正确的解释可以表述如下：如果高级袋的产量由30%的标准袋产量提高一个单位，总利润会减少1.38美元。相反，如果使得30%的最低要求减少一个单位(D≥0.3S-1)，总利润会增加1.38美元。3.4多于两个决策变量的情况

3.4.2牧草农场问题

我们来看一个三决策变量的最小化问题。牧草农场公司一直在试验一种特殊的赛马食品。该食品的成分包括标准的马饲料产品，一种富含维生素的燕麦，以及一种新型维生素和矿物质饲料添加剂。下表归纳了每磅食品的营养价值和各种成分的成本。3.4多于两个决策变量的情况3.4.3建立牧草农场问题的模型建立牧草农场的线性规划模型之前，我们需要引入如下3个变量：S——标准马饲料的量E——高营养燕麦的量

A——维生素和矿物质饲料添加剂的量运用数据，总成本最小的目标函数可以表示如下：Min0.25S+0.50E+3A成分A的约束：0.8S+0.2E≥3成分B的约束：S+1.5E+3A≥6成分C的约束：S+0.6E+2A≥4最多6磅的混合重量的约束：S+E+A≤63.4多于两个决策变量的情况

合并所有约束条件，加上非负约束，完整的牧草农场问题的线性规划模型表述如下：3.4多于两个决策变量的情况

3.4.4牧草农场问题的计算机求解和解释

用管理科学家软件解决牧草农场问题的结果如图所示。取近似后最优解为每天的食品中包含3.51磅的标准马饲料，0.95磅的高营养燕麦和1.54磅维生素和矿物质饲料添加剂。因此，各成分的单位成本分别为0.25美元、0.5美元、3.00美元，因此总的成本为：3.4多于两个决策变量的情况3.4多于两个决策变量的情况

观察计算机输出的松弛/剩余部分，约束条件2的值为3.554.由于约束2是大于等于型的，因此3.554是剩余值。由于约束1和约束3的剩余值都是0，因而我们看到最优混合中，成分A和成分C刚好满足最低要求。此外，约束4的剩余值也是0，说明最优解中每天的饲料重量正好是6磅。3.4多于两个决策变量的情况

成分A的约束条件（约束条件1）的对偶价格为-1.22.合理解释这个值，首先我们看它的符号为负，因此我们知道如果增加其右端值，将使得最优解变得更坏。在最小化问题中，“更坏”意味着总成本的增加，因此，右端值一单位的增加会使总成本上升1.22美元。反过来，也可以说右端值每减少一个单位，总成本下降1.22美元。观察右端值范围部分，我们看见只要右端值在1.143到3.368之间，上述解释就是合理的。3.4多于两个决策变量的情况

假设牧草农场的管理者想重新考虑马匹的最大进食量，约束条件的对偶价格为0.92，表明右端值每增加一个单位，总成本就会减少0.92美元。右端值范围部分显示，在右端值增加到8.478之前，这种解释都是正确的。所以，如果约束条件4的右端值由6增加到8，总成本就会减少2*0.92或者说1.84美元。切记，这种变化可能导致可行域的变化，由此可以获得新的最优解。3.4多于两个决策变量的情况

结果输出目标函数系数范围S下限-0.393，在实际问题中，我们认为S下限为0。由此得到，无论标准饲料的价格下降多少，最优解都不会改变。即使牧草农场免费获得标准饲料，最优解仍然是3.51磅的标准饲料，0.95磅的高营养燕麦和1.54磅维生素和矿物质饲料添加剂。然而，标准饲料单位成本的减少，都会引起总成本的减少。目标函数系数S和A是没有上限限制的，如果增加A的值，比如从每磅3美元增加到每磅13美元，最优解不变，总成本增加10倍。我们对计算机输出结果所做的灵敏度分析的解释，只有在问题中其他系数不变的情况下才有效。3.5电子通信公司问题

这里我们讨论的电子通信公司问题是一个最大化问题，这个问题包括4个决策变量，2个小于等于形式的约束条件，1个等于形式的约束条件和1个大于等于形式的约束条件。我们的目标是建立一个简单的数学模型，使用管理科学家软件求出模型最优解，对求出的解进行解释，并进行灵敏度分析。3.5电子通信公司问题

让我们来看这个例子，电子通信公司主要生产双向便携式无线报话机。该公司最近开发了一种新产品，这种产品的通信范围可以覆盖22英里，适合企业和个人使用。该新产品的分销渠道是：航海器材经销店商用器材经销店全国范围的连锁零售店直接邮购3.5电子通信公司问题

由于分销和促销成本的差异，产品的利润也因销售渠道的不同而不同。此外，广告费用和人力成本也与销售渠道有关。下表介绍了电子通信公司不同销售渠道的销售利润、广告费用和人工成本。广告预算5000美元，每个销售渠道的最大个人销售时间是1800小时，公司现阶段决定制造的产品数600件，此外，全国连锁零售店要求最少销售150件产品。电子通信面临的问题是如何制定一个分销策略，使其总的销售利润最大。表3-2电子通信公司的利润、广告费用和销售时间3.5电子通信公司问题

3.5.1建模

我们首先写出电子通信公司的目标函数和约束条件。约束条件1广告支出≤广告预算约束条件2销售时间≤最大可用时间约束条件3产品生产数量=公司要求产量约束条件4零售分销量≥合同要求的最低分销量下面定义决策变量M——航海器材经销店销售产品数量B——商用器材经销店销售产品数量R——全国连锁零售店销售产品数量D——直接邮购产品数量3.5电子通信公司问题目标函数：Mas90M+84B+70R+60D现在设立约束条件。广告预算5000美元10M+8B+9R+15D≤5000销售时限1800小时2M+3B+3R≤1800现阶段公司要求生产600件产品，所以M+B+R+D=600最后全国连锁零售店至少卖出150件产品R≥1503.5电子通信公司问题综合所有约束条件，电子通信公司问题的完整线性规划模型如下：Max90M+84B+