第3章线性规划的灵敏度分析

因为灵敏度分析研究的是系数的变化对最优解的影响，所以在进行灵敏度分析之前首先要计算出原线性规划问题的最优解。因此，灵敏度分析有时也被称为后优化分析（postoptimalityanalysis）。我们研究灵敏度分析的方法与第2章中研究线性规划问题的方法相同。首先，我们将介绍如何使用图解法进行双变量线性规划问题的灵敏度分析。灵敏度分析及最优的解释是运用线性规划问题的重要因素。3.1灵敏度分析简介灵敏度分析对于决策者的重要性不言而喻，在真实世界里，周围的环境、条件是在不断变化的。原材料的成本在变，产品的需求在变，公司购买新设备、股票价格波动、员工流动等等这些都在不断发生。如果我们要用线性规划模型去解决实际问题，那模型中的系数就不可能是一成不变的。这些系数的变化会对模型的最优解产生什么样的影响呢？运用灵敏度分析，我们只需改变相应的系数就可以得到答案，而不需建立新的模型。回忆Par公司的问题：我们已经知道这个问题的最优解是袋生产540个，高级袋生产252个，这个最优解的前提是每个标准袋的利润是10美元，每个高级袋的利润是9美元。假设，我们得知由于价格的下降，标准袋的利润由10美元降到8.5美元。这时我们可以用灵敏度分析来确定标准袋生产540个，高级袋生产252个是否还是最优解。如果还是，则不必建立新的模型求解了。灵敏度分析还可以用来分析模型中的系数哪个更能左右最优解。比如，管理层认为高级袋的利润9美元只是一个估计量。如果通过灵敏度分析得到，当高级袋的利润在6.67美元与14.29美元之间变化时，模型的最优解都是540个标准袋和252个高级袋，那么管理层就必须思考每个高级袋获利9美元这个估计量的可信程度有多大了。管理层希望知道如果高级袋的利润下降，最优产量会怎样变化。灵敏度分析的另一个用途是分析约束条件的右端值变化对最优解的影响。还是以Par公司为例，在最优产量的情况下，切割与印染部和成型部的工作时间已经被占用了。如果现在公司增加了这两个部门的生产能力，那么最优解以及总利润的值会发生什么样的变化呢？灵敏度分析可以帮助确定每一个工时的边际价值，以及在利润下降之前部门工时的最大增加量。3.2图解法灵敏度分析对于双变量的线性规划问题，当目标函数的系数或约束条件的右端值变化时，用图解法可以对其进行灵敏度分析。3.2.1目标函数系数让我们思考一下目标函数的系数变化会对Par公司的最优产量产生什么样的影响。选择每个标准袋的利润是10美元，每个高级袋的利润是9美元。很明显，如果其中一种袋子的利润下降，公司就会削减其产量；如果利润上升，公司就会增加其产量。但问题是，究竟利润变化多少时，管理者才应该改变产量呢？现在，模型的最优解是540个标准袋和252个高级袋。每个目标函数系数都有一个最优范围，即目标函数系数在什么范围内变化时，模型的最优解保持不变。我们应该注意那些系数的最优范围比较小，或者系数刚好靠近最优范围边界的情况。在这种情况下，这些系数的微小变动就有可能使最优解发生改变。下面，我们用图解法来求解Par公司的最有范围。200400600800200400600oSD可行域10S+9D=7668图3-1直线A(7/10)S+D=630直线BS+(2/3)D=708③在图3-1中，我们可以看到只要直线B的斜率≤目标函数直线的斜率≤直线A的斜率则最优解不变.容易计算直线A和直线B的斜率，我们来看一看若想保持极点③仍然为最优解点，应满足的条件：（3-1）因此，我们得到目标函数的斜率为－CS／CD。把－CS／CD代入式（3-1），我们看到只要满足下列条件，极点③就仍然是最优解点：现在让我们考虑目标函数直线斜率的一般形式。用CS表示标准袋的利润，CD表示高级袋的利润，P表示目标函数值。使用这些标识，目标函数直线可以写成：P＝CSS＋CDD把上面方程写成斜截式，得到：CDD＝﹣CSS＋P以及从左边的不等式，我们得到（3-2）为了计算标准袋利润最优的范围，我们假设高级袋的利润CD＝9，代入式（3-2），我们得到：因此综合标准袋利润CS的极限，标准袋利润最优范围为：6.3≤CS≤13.5从右边的不等式，我们得到因此，在最初Par公司的问题中，标准袋的利润是10美元。最优解是540个标准袋和252个高级袋。标准袋利润CS的最优范围告诉Par公司的管理者：在其他系数不变的情况下，只要标准袋的利润在6.3美元与13.5美元之间，540个标准袋和252个高级袋总是最优产量。然而值得注意的是，即使产量不变，总的利润也可能由于每一个标准袋利润的变化而变化。这些计算可以重复进行，假设标准袋的利润为常数CS＝10。如此一来，高级袋利润的最优范围就能够被确定出来。验证可得，这个范围为6.67≤CD≤14.29。多系数同时改变目标函数系数的最优范围只能够应用于一次只有一个系数发生改变的情况，其他系数都假定保持初值而不发生变化。如果两个或两个以上目标函数的系数被同时改变，就有必要进一步判断最优解会不会也发生变化。然而对于解决只有两个变量的问题时，式（3-2）给出了一个简单的方法，以判断两个目标函数系数同时发生改变时，最优解是否也发生改变。简单地计算出在新的系数值下目标函数的斜率（-CS/CD）,如果这个比值大于等于目标函数斜率的下限，同时小于等于目标函数斜率的上限，那么系数值的变化就不会使最优解发生变化。在式（3-2）中，我们计算出只要满足下列条件，极点③仍然是最优点如果CS升高到13美元，同时使CD降低到8美元，新的目标函数斜率将变成由于这个值要小于下限，因此当前的解S=540,D=252不再是最优的。把CS=13，CD=8代入，可得出极点②是新的最优解。观察最优范围，我们得出结论，无论是CS升高到13美元还是使CD降低到8美元（当不是同时变化），都不会带来最优解的变化。但当CS与CD同时改变时，目标函数斜率的变化导致了最优解的变化。这个结论强调了这样一个事实：仅仅是通过最优范围，只能用于判断在一次改变一个目标函数系数的情况下最优解的变化。3.2.2约束条件右端值的变化现在让我们来考虑约束条件右端值的变化对可行域带来的影响，及可能对最优解带来的变化。为了阐明敏感度分析的这方面内容，我们假设Par公司的切割与印染部门增加了10小时的生产时间，然后来考虑将会有什么发生。切割与印染约束条件的右端值由630变为640，约束条件可写作又获得了10个小时的切割与印染时间，我们可以扩展问题的可行域，如图3-3所示。可行域变大了，现在我们考虑是否有新的解会使目标函数值更大。运用图解法可以看出，极点S=527.5，D=270.5是最优解点。新的目标函数值为10×527.5+9×270.5=7711.75美元，比原来利润增加了7711.75–7688.00=43.75美元。因此，利润的增加率为43.75/10=4.375美元/小时。200400600800200400600oSD可行域10S+9D=7711.75图3-3直线A(7/10)S+D=640S=527.50D=270.75③约束条件右端值每增加一个单位引起的最优值的改进量称为对偶价格。在这个例子里，切割与印约束条件的对偶价格为4.375美元——换言之，如果我们使得右边切割与印染约束条件增加1小时，目标函数的值会相应的增加4.375美元。相反，如果我们使得右边切割与印染约束条件减少1小时，目标函数的值会相应的减少4.375美元。对偶价格可以用来求出当某个约束条件右端值改变1个单位，目标函数值将会有什么变化。在这里，我们要注意的是，对偶价格可能只适用于在右端值仅发生了很小的变动时的情况。随着所获得的资源越来越多，从而右端值越来越大，其他的约束条件也可能会约束和限制目标函数值的变化。拿Par公司的例子来说，我们最终会找到某一点，从那一点之后，再增加切割与印染的时间也不会使利润增加——在切割与印染约束条件不再是束缚性约束条件是，这就有可能发生。在这一点，对偶价格等于0。下一节中，我们会讨论如何确定右端值变动的有效范围，在这个范围内，通过对偶价格可以精确地预测出目标函数值的变动。最后要指出的是，任何非束缚性约束条件的对偶价格都是0，因为增加这样的约束条件的右端值，只会得到约束条件的剩余或松弛变量。为了在解决最小化问题中正确解释对偶价格，假设我们刚刚解出了一个关于总成本最小化的问题，最优解的值为100美元。此外，假设某个约束条件的对偶价格是-10美元。负的对偶价格告诉我们，如果使右端值增加1，目标函数值不会增加，反而会减少10美元。在最小化问题中，目标函数结果变得更坏意味着总成本的增加。那样的话，如果右端值增加1个单位，目标函数变成110美元。反过来，右端值减少了=1单位，总成本减少10美元。3.3灵敏度分析：计算机求解在第2.4节，我们说明了如何使用管理科学家软件来解决Par公司的线性规划问题。回忆一下，为了使用管理科学家软件，我们必须使用小数来代替分数。Par公司的问题小数形式的系数表示如下：Max10S+9DS.t.0.7S+1D≤630切割与印染0.5S+0.83333D≤600缝合1.0S+0.66667D≤708成型0.1S+0.25D≤135检查与包装S,D≥0我们现在示范如何利用管理科学家软件来进行灵敏度分析，如图3-4所示。ObjectiveFunctionValue=7667.99463VariableValueReducedCosts----------------------------------------S539.998410.00000D252.001130.00000ConstraintSlack/SurplusDualPrices---------------------------------------10.000004.374962120.000000.0000030.000006.93753417.000000.00000OBJECTIVECOEFFICIENTRANGESVaribleLowerLimitCurrentValueUpperLimit------------------------------------------------------------S6.3000010.0000013.49993D6.666709.0000014.28572RIGHTHANDSIDERANGESConstraintLowerLimitCurrentValueUpperLimit-----------------------------------------------------------------1495.59998630.00000682.363162479.99930600.00000NoUpperLimit3580.00146708.00000900.000004117.00012135.00000NoUpperLimit3.3.1计算机输出的解释——第一个例子在第2.4节，我们对图3-4顶部的输出结果进行了讨论。在取近似值之后，我们得到最优解是S=540个标准袋和D=252个高级袋，目标函数最优解是7668美元。如我们在第2.4节讨论的一样，递减成本（ReducedCosts）一栏的信息告诉我们目标函数的每个系数应提高多少，目标函数的变量值才能是正数。对于Par公司的例子，两个变量都已经是正值，所以它们相应的递减成本就是0。在第3.4节，我们将会介绍递减成本，这时决策变量在最优位置上并不是正值。在最优解S,D以及递减成本信息下面，计算机输出了有关约束条件的信息。回忆Par公司的例子，其中有4个小于或等于约束条件的，都是关于各个生产部门的生产时间。在松弛/剩余变量一栏中，可以看到每个部门的松弛变量值。上述信息归总如下： 约束条件序号约束条件名松弛 1切割与印染02缝合1203成型04检查与包装18从上述数据中，我们可以看到束缚性约束条件（切割与印染和成型）在目标函数的最优下，松弛为0。缝合部门有120小时的松弛或未使用的缝合能力：检查与包装部门有18小时的松弛。对偶价格栏的信息是关于目标函数取得最优解时，这4种资源的边际价值。在第3.2节，我们对对偶价格进行了如下的定义：对偶价格就是约束条件右端值每增加一个单位引起的，最优解的增加量。这里，约束条件1（切割与印染）和约束条件3（成型）的非零对偶价格分别为4.37496和6.93753。这告诉我们，每额外增加1小时的切割与印染时间会使最优解增加4.37美元；每增加1小时成型时间将会使最优解增加6.94美元。因此，在其他系数保持不变的情况下，如果有效成型时间从708小时增加到709小时，Par公司的利润会增加4.37，即有7.668美元增加到7668+4.37=7672.37（美元）。成型约束条件与之类似——在其他系数保持不变的情况下，如果有效成型时间从708小时增加到709小时，Par公司的利润将增加到7668+6.94=7674.94（美元）。由于缝合和检查与包装约束条件有松弛或未使用的工作能力，它们的零对偶价格表明，对这两个部门增加额外的工作时间也不会对目标函数的值产生影响。再次看看图3-4的结果，我们看到管理科学家软件除了提供松弛/剩余变量和对偶价格的约束条件信息之外，还给出了目标函数系数和约束条件右端值的变化范围。考虑在输出结果的标题“目标系数范围”（OBJECTIVECOEFFICIENTRANGES）下面给出的信息，我们观察变量S（此时的值是10）有如下的最优化范围：6.30≤CS≤13.50因此，只要标准袋的利润在6.30到13.50之间，生产540个标准袋和252个高级袋都是最优解。仔细观察会发现，这个最优化范围与第3.2节用图解法得出的结论是一致的。再观察一下高级袋的使目标函数值变化的信息，我们看到管理科学家软件计算出如下的最优化范围：6.67≤CS≤14.29这个结果告诉我们，只要高级袋的利润在6.67到14.29之间，生产540个标准袋和252个高级袋都是最优的。计算机输出的结果的最后一部分右端值范围（RIGHTHANDSIDERANGES）给出了对对偶价格适合范围的限制条件。只要约束条件右端值处于系统所给出的上限和下限之间，对偶价格就会给出当右端值增加1时，最优解的增加量。举例来说，我们说每额外增加一小时工作量，目标函数会增加4.37美元。没减少1小时工作量，当然也同样会使目标函数值减少4.37美元。在右端值范围栏的信息中可见，4.37美元的对偶价格在右端值增加到682.36316或减少到495.59998之间的范围内都是有效的。成型约束条件也是一样，在右端值增加到900小时或是减少到580.00146小时之间的范围内，对偶价格6.94美元都是有效地。如前所述，右端值范围给出了一个对偶价格的适用范围。如果右端值的变化超出了这个范围，就需要重解原问题并找出新的对偶价格。我们把这个对偶价格适用的范围叫做可行域。Par公司问题的可行域汇总如下：只要右端值在这些范围之内，系统分析结果中的那些对偶价格就不会改变。右端值如果超出了这些范围，对偶价格的信息就会随之改变。 约束条件最小右端值最大右端值 切割与印染495.6682.4缝合480.0无上限成型580.0900.0检查与包装117.0无上限3.3.2多系数同时变化系统灵敏度分析的输出是基于单函数系数变化的。它假设所有其他的系数都保持不变。因此目标函数系数和约束条件右端值的变化范围只能适用于单个系数发生变化的情况。然而在很多情况下，我们可能更加关注当两个或两个以上系数同时变化时，目标函数将怎样变化。有些多系数同时变化的分析可能会用到100%法则（100percentrule）。我们下面分析100%法则是如何应用于多系数同时变化的情形中的。假设Par公司的会计部门指出，原先对标准袋和高级袋的利润的计算——分别为10美元和9美元有错误，正确的利润是11.50美元和8.25美元。为了确定这样的变化是否会对最优解产生影响，我们先要定义两个术语“允许增加量”（allowableincrease）和“允许减少量”（allowabledecrease）。对于目标函数的系数，允许增加量是在不超过最优范围的情况下，系数可能增加的最大量；而允许减少量是在不低于最优范围下限的情况下，系数可能减少的最大量。从图3-4可以看出目标函数系数S的上限是13.49993，因此，允许增加量就是13.49993-10=3.49993。从百分比变动角度来看，目标函数系数（即标准袋的利润）增加了1.50美元（从10到11.5），D的下限是6.66670，D的允许减少量为2.33330=9-6.66670。从百分比的角度来看，目标函数（高级袋的利润）减少了0.75美元（从9到8.25），允许增加量（42.86%）和允许减少量（32.14%）变化之和为75%。现在我们对将要应用于多个变量同时改变情况中的100%法则进行定义。目标函数系数的100%法则对所有变化的目标函数系数，计算其占允许增加量和允许减少量的百分比之和。如果和没有达到100%，最优解就不会改变。在Par公司的例子中，由于目标函数系数的两项改变的百分率之和为75%，因此最优解不会改变。然而值得注意的是，尽管最优解仍然是S=539.99841，D=252.00113，但最优值可能会因为标准袋的利润增加到11.50美元，高级袋的利润减少到8.25美元而变化。但是，100%法则并没有规定如果各百分比之和达到100%，最优解就一定会发生变化。有可能个百分比之和超过100%，最优解也不变。如果100%法则的条件不能被满足，就必须对问题重新求解，以确定最优解是否发生变化。切割与印染时间的允许增加量为682.36316-630.0=52.36316，成型时间的允许增加量为900.0-708.0=192.0（见图3-4）。新增的20小时切割与印染时间占了约束条件右端值允许增加量的额外的100小时成型占了总允许增加的二者百分比之和为38.19%+52.08%=90.27%，没有超过100%，因此我们可以得到下面的结论：对偶价格在这里是适用的，并且目标函数值将会由此增加20×4.37+100×6.94=781.40。3.3.3计算机输出的解释——第二个例子我们重新考虑第2.5节中讨论的M&D化工公司的问题，以此作为解释计算机输出的第二个例子。M&D公司的目标是为产品A和产品B找出一个成本最低的生产计划。下面是解决这个问题的线性规划模型，其中，A表示产品A的产量，B表示产品B的产量。Min2A+3Bs.t.1A≥125产品A的需求1A+1B≥350总产量2A+1B≤600生产时间A,B≥0利用管理科学家软件对其进行求解，结果展示在图3-5中。计算机输出结果显示，最优解服从于800美元的目标函数。决策变量的值告诉我们，成本最低的生产计划是生产250加仑的产品A和100加仑的产品B。ObjectiveFunctionValue=800.000VariableValueReducedCosts---------------------------------------------A250.0000.000B100.0000.000ConstraintSlack/SurplusDualPrices--------------------------------------1125.0000.00020.000﹣4.00030.0001.000OBJECTIVECOEFFICIENTRANGESVariableLowerLimitCurrentValueUpperLimit----------------------------------------------ANoLowerLimit2.0003.000B2.0003.000NoUpperLimitRIGHTHANDSIDERANGESConstraintLowerLimitCurrentValueUpperLimit----------------------------------------------1NoLowerLimit125.000250.0002300.000350.000475.0003475.000600.000700.000松弛/剩余变量栏显示，其中大于等于的约束条件意味着产品A的需求有125单位的剩余（见约束条件1）。这就是说，当处于最优解时，产品A的产量比需求多125加仑。对于总的生产要求（约束条件2）和生产时间限制（约束条件3），松弛/剩余变量值为0，这意味着这两个约束条件是最优解的束缚性约束条件。对偶价格栏再一次告诉我们，每增加一单位的约束条件右端值时最优解的改进。首先观察生产时间的限制（约束条件3），其对偶价格为1.00。如果我们增加生产时间，使之从600小时变成601小时，目标函数的值就会改进1美元。由于目标的使成本最小，这里的“改进”意味着成本的降低。因此，如果生产时间变成601小时，最优解的值将会减少到800－1=799美元。输出结果的右端值范围（righthandsiderange）部分给出了生产时间限制（约束条件3）的上限。因此，在总的生产时间低于700小时时，1美元的对偶价格都是有效的。再回到输出结果的对偶价格部分，考虑总产量约束（约束条件2）的对偶价格。负的对偶价格表明，如果总产量约束的右端值增加一个单位，最优解不会改进。事实上，-4.00的对偶价格告诉我们，如果总产量约束的右端值从350单位增加到351单位，最优解将会变坏4美元。“变坏”意味着成本的增加，即最优解将变为800＋4=804（美元）。由于对偶价格是关于当右端值增加一个单位时最优解的改进量，有负对偶价格的约束条件就不能再增加其右端值了，而应该努力减少其右端值。如果总产量约束条件的右端值从350单位减少到349单位，总成本就会减少4美元而变成800－4=796（美元）尽管对偶价格表示了右端值每增加一个单位对最优解的改进，然而对目标函数值“改进”的解释取决于所解决的问题是最大化问题还是最小化问题。小于等于型约束条件的对偶价格总是大于或等于0的，因为增加其右端值不会使目标函数值变得更坏。类似地，大于等于型约束条件的对偶价格总是小于或等于0的，因为增加其右端值不会对最优解有所改进。最后，考虑图3-5中的右端值范围部分。M&D化工公司问题的可行域归纳如下：只要右端值在上述范围，计算机输出的结果中的对偶价格就是适用的。 约束条件最小RHS最大RHS 产品A的需求无上限250总产量300475生产时间4757003.3.4关于对偶价格解释的注释如前所述，对偶价格是右端值每增加一个单位时对最优值的改进。当约束条件的右端值表示某中资源的可利用量时，对偶价格通常可以解释为公司对额外支付一单位这种资源所愿意提供的金额。然而这种解释也并非总是正确的。要理解这个问题，问你先要理解沉没成本和相关成本的区别。沉没成本不会受决策影响，无论决策变量为何值，这种成本都会发生。相关成本则取决于决策的制定，这种成本依赖于决策变量值的变化而变化。让我们重新考虑Par公司的例子。切割与印刷的总时间的630小时。如果说无论生产标准袋或是高级袋，都是按照时间来付出工资的，那么时间成本就是一种沉没成本。如果Par公司只需要为那些切割和印染高尔夫球袋的时间补偿工资，那么时间成本就是一种相关成本。所有的相关成本都要在线性规划的目标函数中有所反映。对Par公司而言，我们一直假设公司必须按照工作时间来向工人发工资，不管他们的工作时间是否有效率地被利用。因此，Par公司的劳动时间资源的成本就属于沉没成本而不在目标函数中反映出来。当某种资源的成本属于沉没成本，对偶价格就可以被解释为公司愿意为得到额外一个单位这种资源而付出的金额。当某种资源的成本属于相关成本，对偶价格则可以被解释为这种资源的价值超过其成本的数额，也就是增加一个单位这种资源时，公司能付出的最大成本量。3.4多于两个决策变量的情况图解法只能应用于解决双决策变量的线性规划问题，而计算机软件是用来处理多变量和约束条件的线性规划问题的。在现实生活中，用线性规划解决的问题经常包含大量的变量和约束条件。在本节中，我们讨论在两个线性规划问题中，三决策变量问题的方程和计算机求解。在讨论过程中，我们会解释计算机输出结果中的递减成本部分的含义，同时阐述如何解释带有百分数的约束条件的对偶价格。3.4.1修正的Par公司问题Par公司原来问题的模型如下：Max10S＋9Ds.t.0.7S＋1D≤630切割与印染0.7S＋0.83333D≤600缝合1S＋0.66667D≤708成型0.1S＋0.25D≤135检查与包装S,D≥0回忆一下，S是标准袋的产量，D是高级袋的产量。假设管理者希望生产一种轻便的、可以被球手随身携带的球袋模型。设计部门估计每个新型球袋将需要0.8小时的切割与印染的时间，1小时的缝合时间，1小时的成型时间和0.25小时的检查与包装时间。由于这种设计是独一无二的，管理者认为在当前销售期内每个轻便袋可以获利12.58美元。我们来考虑对原来线性规划模型进行修改，修改后的模型需要加入新的决策变量的影响。令L为轻便袋的产量，将其加入目标函数以及4个约束条件，可以得到如下修改后的模型：max10S＋9D＋12.58Ls.t.0.7S＋1D＋0.8L≤630切割与印染0.5S＋0.83333D＋1L≤630缝合1S＋0.66667D＋1L≤708成型0.25D＋0.25L≤135检查与包装S,D,L≥0图3-6是使用管理科学家软件对新问题进行求解的结果。最优解为280个标准袋，0个高级袋和428个轻便袋，最优值近似为8299.80美元。ObjectiveFunctionValue=8299.80078VariableValueReducedCosts--------------------------------------------S280.000000.00000D0.000001.15003L428.000000.00000ConstraintSlack/SurplusDualPrices----------------------------------------------191.000000.00000232.000000.0000030.000008.1000040.0000019.00000OBJECTIVECOEFFICIENTRANGESVariableLowerLimitCurrentValueUpperLimit----------------------------------------------------------------S5.1400010.0000012.07007DNoLowerLimit9.0000010.15003L11.9090712.8500025.00000RIGHTHANDSIDERANGESConstraintLowerLimitCurrentValueUpperLimit------------------------------------------------1538.40002630.00000NoUpperLimit2568.00000600.00000NoUpperLimit3540.00000708.00000852.63159470.80000135.00000144.60001图3-6使用管理科学家软件对修改后的Par公司问题的求解现在来看递减成本栏的信息。回忆前面对递减成本的解释，表示使得变量为正数时相应目标函数的增加量。计算机输出结果表明，S和L的递减成本都是0，这是因为相应的决策变量值在最优解处已经是正值。变量D的递减成本为1.15003，表明高级袋的利润至少增加到9＋1.15003＝10.15003美元时，D才能变为一个正值。假设我们使D的系数正好增加1.15003美元，再用科学家管理软件来重解原问题。如图3-7所示，注意到尽管D的值已经是正数，最优解的值仍然没有变。换言之，当D利润的增量正好等于其递减成本时，能得到多重最优解。但是，如果D的利润增加超过1.15003美元，它在最优解处就不再是0。ObjectiveFunctionValue=8299.80078VariableValueReducedCosts--------------------------------------------S403.783170.00000D222.811980.00000L155.674760.00000ConstraintSlack/SurplusDualPrices----------------------------------------------10.000000.00000256.757760.0000030.000008.1000040.0000019.00000OBJECTIVECOEFFICIENTRANGESVariableLowerLimitCurrentValueUpperLimit----------------------------------------------------------------S10.0000010.0000012.51072D10.1500310.1500315.40790L10.6531312.8500012.85000RIGHTHANDSIDERANGESConstraintLowerLimitCurrentValueUpperLimit----------------------------------------------------------------1538.40002630.00000628.363162543.24225600.00000NoUpperLimit3580.00140708.00000852.631594117.00012135.00000151.15410图3-7Par公司问题中的系数D的值增加了1.15003美元后的解3.4.2牧草农场问题为了提高我们对多变量问题的求解能力，我们来考虑一种三决策变量的最小化问题。牧草农场公司位于肯塔基州列克星敦市，一直在试验一种特殊的赛马食品。该食品的成分包括标准的马饲料产品，一种富含维生素的燕麦，以及一种新型维生素和矿物质饲料添加剂。表3-1中归纳了每磅食品的营养价值以及各种成分的成本。比如，每磅标准饲料包含0.8单位的成分A，1单位的成分B和0.1单位的成分C。每匹马每天的营养价值最低为3单位成分A，6单位成分B和4单成C。此外，为了控制马匹的体重，每匹马每天进食不得超过6磅。牧场农场要在满足每天的食品需求的情况下确定出成本最低的配料方案。表3-1牧草农场饲料的营养价值和成本 饲料成分标准高营养燕麦饲料添加 成分A0.8 0.20.0成分B1.01.53.0成分C0.10.62.0每磅成本0.250.503.003.4.3建立牧草农场问题的模型建立牧草农场的线性规划模型之前，我们需要引进如下3个变量：S——标准马饲料的量；E——高营养燕麦的量；A——维生素和矿物质饲料添加剂的量；运用表3-1中的数据，总成本最小的目标函数可以表示如下：min0.25S+0.50E+3A对每天3磅需求的成分A，有如下约束：0.8S+0.2E≥3成分B的约束： 1.0S+1.5E+3.0A≥6成分C的约束：0.1S+0.6E+2.0A≥4最后是最多6磅的混合重量约束：S+E+A≤6合并所有的约束条件，再加上非负约束，完整的牧草农场问题的线性规划模型表述如下：min0.25S+0.50E+3As.t.0.8S+0.2E≥3成分A1.0S+1.5E+3.0A≥6成分B 0.1S+0.6E+2.0A≥4成分CS+E+A≤6加权S,E,A≥03.4.4牧草农场问题的计算机求解和解释用管理科学家软件解决农场问题的结果如图3-10所示，取近似后，最优解为每天的食品中包含3.51磅的标准马饲料，0.95磅的高营养燕麦和1.54磅维生素和矿物质饲料添加剂。因此，各成分的单位成本分别为0.25美元、0.50美元、3.00美元，因此总的成本为：3.51*0.25=0.88（美元）0.95*0.50=0.47（美元）1.54*3.00=4.62（美元） 总成本=5.97(美元)取近似后，该结果与计算机输出（见图3-10结果一致）ObjectiveFunctionValue=8299.80078VariableValueReducedCosts--------------------------------------------S3.5140.000E0.9460.000A1.5410.000ConstraintSlack/SurplusDualPrices----------------------------------------------10.000-1.21623.5540.00030.000-1.9594 0.000 0.919OBJECTIVECOEFFICIENTRANGESVariableLowerLimitCurrentValueUpperLimit----------------------------------------------------------------S-0.3930.250NoUpperLimitENoLowerLimit0.5000.925A1.5223.000NoUpperLimitRIGHTHANDSIDERANGESConstraintLowerLimitCurrentValueUpperLimit----------------------------------------------------------------11.1433.0003.3682NoLowerLimit6.0009.55432.1004.0004.8754 5.562 6.000 8.478图3-10使用管理科学家软件对牧草农场问题求解观察计算机输出地松弛/剩余部分，约束条件2的值为3.554。由于约束2是大于等于型的，因此，3.554是剩余值。由于约束1和约束3的剩余值都是0，因而我们看到最优混合中，成分A和成分C刚好满足最低要求。此外，约束4的剩余值也是0，说明最优解中每天的饲料重量正好为6磅。成分A的约束条件（约束条件1）的对偶价格为-1.22.合理解释这个值，首先我们看它的符号为负，因此我们知道如果增加其右端值，将使得最优解变得更坏。在最小化问题中，“更坏”意味着总成本的增加，因此，右端值一单位的增加会使总成本上升1.22美元。反过来，也可以说右端值每减少一个单位，总成本下降1.22美元。观察右端值范围部分，我们看到只要右端值在1.143到3.368之间，上述解释就是合理的。假设牧草农场的管理者想重新考虑马匹的最大进食量。约束条件的对偶价格为0.92，表明右端值每增加一个单位，总成本就会减少0.92美元。右端值范围部分显示，在右端值增加到8.478磅之前，这种解释都是正确的。所以约束条件4的右端值由6增加到8，总成本就会减少2*0.92或者说1.84美元。切记，这种变化可能导致可行域的变化。，由此可以获得新的最优解。从图3-10的目标函数系数范围部分可以看出，S的下限是-0.393.很明显，在实际问题中，目标函数系数S（标准饲料的量）不可能为负值。所以，从实际的角度来看，我们可以认为S的下限为0.我们有此可以得到，无论标准饲料的价格下降多少，最优解都不会改变。即使牧草农场可以免费获得标准饲料，最优解仍然是3.51磅的标准饲料，0.95磅的高营养燕麦和1.54磅维生素和矿物质饲料添加剂。然而，标准饲料单位成本的减少，都会引起总成本的减少。注意目标函数系数S和A是没有上限限制的。如果增加A的值，比如，从每磅3美元增加到每磅13美元，最优解释不会变化的，而总成本则会增加10倍，即从1.541美元变为15.41美元。切记，我们对计算机输出结果所做的灵敏度分析的解释，只有在问题中其他的系数不变的情况下才是有效的。为了解决多系数变化的情况，我们必须用100%规则或是重新求解问题。3.5电子通信公司问题本节讨论的电子通信公司是一个最大化问题，这个问题包括4个决策变量，2个小于等于形式的约束条件，1个等于形式的约束条件和1个大于等于形式的约束条件。我们的目标是建立一个简单的数学模型，使用管理科学家软件求出模型的最优解，对求出的解进行解释，并进行灵敏度分析。在下一章。我们会向读者介绍线性规划在营销、金融、生产管理等方面的应用。一旦你能够对电子通信公司这样的问题进行建模、求解和分析，你就会明白线性规划能够解决多么复杂的问题。让我们来看这个例子，电子通信公司主要生产双向便携式无线双向便携式无线电报话机。该公司最近开发了一种新产品，这种产品的通信范围可以覆盖25英里，适合企业和个人使用。该新产品的分销渠道是：·航海器材经销商。·商用器材经销商。·全国范围的连锁零售店。·直接邮购。由于分销和促销成本的差异，产品的利润也因销售渠道的不同而不同。此外，广告费用和人力成本也与销售渠道有关，表3-2简要地将电子通信公司不同销售渠道的销售利润、广告费用、人工成本列了出来。公司的广告费用预算是5000美元，每个销售渠道的最大个人销售时间是1800个小时。公司现阶段决定制造的产品数为600件，此外，全国连锁零售店要求最少销售150件产品。表3-2电子通信公司的利润、广告费用和个人销售时间电子通信面临的问题是如何制定一个分销策略，使其总的销售利润最大。公司必须决定如何分配各渠道的销售量、销售时间以及广告预算。 分销渠道 单位已售产品的利润（美元） 单位已售产品的广告费用（美元） 单位已售产品的销售时间（小时） 航海器材经销店商用器材经销店全国连锁零售店直接邮购 90847060 108915 233无3.5.1建模我们首先写出电子通信公司的目标函数和约束条件。目标函数是：目标函数:利润最大化这个模型有4个约束条件，分别是（1）广告预算约束；（2）销售时间约束；（3）生产数量约束；（4）销售约束。约束条件1广告支出≤广告预算约束条件2销售时间≤最大可用时间约束条件3产品生产数量=公司要求的产量约束条件4零售分销量≥≤合同要求的最低分销量以上是对目标函数和约束条件的描述，下面我们来定义决策变量。对于这个模型，我们定义如下4个决策变量:M——航海器材经销店销售的产品数量；B——商用器材经销商销售的产品数量；R——全国连锁零售店销售的产品数量；D——直接邮购销售的产品数量。参照表3-2所示数据，目标函数可以写成：max90M+84B+70R+60D现在设立约束条件。因为广告的预算为5000美元，所以广告预算的约束条件是10M+8B+9R+15D≤5000同样，销售时间限制是1800小时，约束方程如下2M+3B+3R≤1800现阶段公司要求生产600件产品，所以，M+B+R+D=600最后，因为全国连锁零售店要求至少有150件产品在此渠道销售，于是有R≥150综合一、所有的约束条件以及非负约束，电子通信公司问题的完整线性规划模型如下Max90M+84B+70R+60Ds.t.10M+8B+9R+15R≤5000广告预算2M+3B+3R≤1800可用销售时间M+B+R+D=600产量R≥150全国连锁零售店合同约束M,B,R,D≥03.5.2计算机求解及其解释使用管理科学家软件对电子通信公司模型进行求解的部分结果如图3-11所示。图中的目标函数值告诉我们模型的最大利润为48450美元。最优解为M=25，B=425，R=150和D=0，即电子通信公司的最优策略是将25件产品通过航海器材经销店销售出去，将425件产品通过商用器材经销店销售出去，将150件产品通过全国连锁零售店销售出去，不通过直接邮购进行销售。再来看一下递减成本栏。回忆一下，递减成本是告诉我们目标函数的系数应该提高多少，其所对应的决策变量的值才能是正数。前3个递减成本为零，这是因为它们对应的决策变量已经是正值了。而直接邮购的递减成本是45，这表明通过直接邮购渠道销售的产品利润必须由现在的60美元增加45美元，达到105美元，才可以使用这种渠道来销售产品。ObjectiveFunctionValue=8299.80078VariableValueReducedCosts--------------------------------------------M25.0000.000B425.0000.000R150.0000.000D0.00045.000ConstraintSlack/SurplusDualPrices----------------------------------------------10.0003.000225.0000.00030.00060.00040.000 -17.000图3-11使用管理科学软件对电子通信公司的问题求解广告预算约束条件的松弛为零，表明所有广告预算即5000美元都被使用了。广告预算约束的对偶价格为3，表明每增加1美元广告预算，目标函数的值（利润）可以增加3美元。因此公司应该认真考虑是否因该增加广告预算。可用销售时间约束条件的松弛是25小时，表明1800小时的是大销售时间足够卖出产品，而且还与25小时没有使用。因为产量约束是一个等于约束，所以其松弛/剩余是零，表明这一约束条件可以满足。其对偶价格为60，表明如果公司的产量增加一单位，利润就可以增加60美元。连锁零售店约束条件的松弛为零，表明它是一个束缚性约束条件。其对偶价格为负值，表明连锁零售店每多销售一单位产品，利润减少17美元。所以公司可能会减少通过连锁零售店销售的数量，因为销售数量每减少一单位，利润就增加17美元。我们现在对有关灵敏度方面的信息加以分析，如图3-12所示。目标函数系数的最优范围如下：84≤CM<无上限50≤CB≤90无下限<CB≤87无下限<CD≤105只要系数的变化在这个范围之内，当前的解或者策略仍然是最优的。这里有个比较特殊的系数CD，它的最优范围表明的信息与松弛/剩余中表明的信息是一致的，都表明了若想使变量D改变，即变为正值，单位利润必须增加到105。OBJECTIVECOEFFICIENTRANGESVariableLowerLimitCurrentValueUpperLimit----------------------------------------------------------------M84.00090.000NoUpperLimitB50.00084.00090.000RNoUpperLimit70.00087.000DNoUpperLimit60.000105.000RIGHTHANDSIDERANGESConstraintLowerLimitCurrentValueUpperLimit----------------------------------------------------------------14950.0005000.0005850.00021775.0001800.000NoUpperLimit3515.000600.000603.00040.000150.000200.000图3-12用管理科学家软件分析电子通信公司问题得出的目标系数和右端值范围关于范围，其实还有其它一些解释方法。回忆一下广告预算约束的对偶价格，我们得知增加1美元的广告投入可以使利润增加3美元。而广告预算右端值范围表明广告投入增加1美元使利润增加3美元的适用条件是广告预算必须小于5850美元。如果预算超过这个数值，公司就不一定能获利了。同时，我们注意到连锁零售店合同约束的对偶价格是-17，这表明公司应该尽量降低这种承诺。连锁零售店合同约束的右端范围是0~200，在这个范围内，销售数量每降低一单位，利润增加17美元。这里由计算机提供的灵敏度分析和最优化分析只适用于单一参数变化，其他参数保持不变的情况。正如前面提到的遇到参数同时改变的情况，如果参数的累计变化没有违背100%定理，则不必对其进行重解。最后，我们来完整的看一下电子通信公司问题的求解。这道问题不仅要求求出各个分销渠道的销售数量，而且还需要知道不同渠道的广告费用以及产品的销售时间。我们已经知道最优解为M=25,B=425,R=150以及D=0，通过它们我们可以很容易地了解资源的分配情况。比如，广告预算的约束条件是：10M+8B+9R+15D≤5000从上式我们可以计算出各个渠道的广告费用分别是10M=10×25=250(美元)，8R=8×425=3400(美元)，9R=9×150=1350(美元),以及15D=15×0=0美元。用同样的方法，我们可以计算出销售时间的分配，如表3-3所示。精品！精品课件！表3-3电子通信公司的最大利润策略 分销渠道 产量 广告预算分配（美元） 销售时间分配（小时） 航海器材经销店商用器材经销店全国连锁零售店直接邮购总计总利润=48450（美元） 254251500600 2503400135005000 50127545001775