《线性规划的灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《线性规划的灵敏度分析.ppt（94页珍藏版）》请在三一办公上搜索。
1、第3章线性规划的灵敏度分析,灵敏度分析是研究当一个线性规划问题中的系数发生变化时，其对函数最优解的影响程度。运用灵敏度分析，我们可以回答一下问题：1.如果目标函数的系数发生了变化，对最优解会产生什么影响？2.如果改变约束条件的右端值，对最优解会产生什么影响？,因为灵敏度分析研究的是系数的变化对最优解的影响，所以在进行灵敏度分析之前首先要计算出原线性规划问题的最优解。因此，灵敏度分析有时也被称为后优化分析（postoptimality analysis）。我们研究灵敏度分析的方法与第2章中研究线性规划问题的方法相同。首先，我们将介绍如何使用图解法进行双变量线性规划问题的灵敏度分析。灵敏度分析及最
2、优方案的解释是运用线性规划问题的重要因素。,3.1灵敏度分析简介,灵敏度分析对于决策者的重要性不言而喻，在真实世界里，周围的环境、条件是在不断变化的。原材料的成本在变，产品的需求在变，公司购买新设备、股票价格波动、员工流动等等这些都在不断发生。如果我们要用线性规划模型去解决实际问题，那模型中的系数就不可能是一成不变的。这些系数的变化会对模型的最优解产生什么样的影响呢？运用灵敏度分析，我们只需改变相应的系数就可以得到答案，而不需建立新的模型。,回忆Par公司的问题：,我们已经知道这个问题的最优解是标准袋生产540个，高级袋生产252个，这个最优解的前提是每个标准袋的利润是10美元，每个高级袋的利
3、润是9美元。假设，我们得知由于价格的下降，标准袋的利润由10美元降到8.5美元。这时我们可以用灵敏度分析来确定标准袋生产540个，高级袋生产252个是否还是最优解。如果还是，则不必建立新的模型求解了。,灵敏度分析还可以用来分析模型中的系数哪个更能左右最优解。比如，管理层认为高级袋的利润9美元只是一个估计量。如果通过灵敏度分析得到，当高级袋的利润在6.67美元与14.29美元之间变化时，模型的最优解都是540个标准袋和252个高级袋，那么管理层就必须思考每个高级袋获利9美元这个估计量的可信程度有多大了。管理层希望知道如果高级袋的利润下降，最优产量会怎样变化。,灵敏度分析的另一个用途是分析约束条件
4、的右端值变化对最优解的影响。还是以Par公司为例，在最优产量的情况下，切割与印染部和成型部的工作时间已经被占用了。如果现在公司增加了这两个部门的生产能力，那么最优解以及总利润的值会发生什么样的变化呢？灵敏度分析可以帮助确定每一个工时的边际价值，以及在利润下降之前部门工时的最大增加量。,3.2图解法灵敏度分析,对于双变量的线性规划问题，当目标函数的系数或约束条件的右端值变化时，用图解法可以对其进行灵敏度分析。3.2.1 目标函数系数 让我们思考一下目标函数的系数变化会对Par公司的最优产量产生什么样的影响。选择每个标准袋的利润是10美元，每个高级袋的利润是9美元。很明显，如果其中一种袋子的利润下
5、降，公司就会削减其产量；如果利润上升，公司就会增加其产量。但问题是，究竟利润变化多少时，管理者才应该改变产量呢？,现在，模型的最优解是540个标准袋和252个高级袋。每个目标函数系数都有一个最优范围，即目标函数系数在什么范围内变化时，模型的最优解保持不变。我们应该注意那些系数的最优范围比较小，或者系数刚好靠近最优范围边界的情况。在这种情况下，这些系数的微小变动就有可能使最优解发生改变。下面，我们用图解法来求解Par公司的最有范围。,200,400,600,800,200,400,600,o,S,D,可行域,10S+9D=7668,图3-1,直线A(7/10)S+D=630,直线BS+(2/3)
6、D=708,在图3-1中，我们可以看到只要 直线B的斜率目标函数直线的斜率直线A的斜率 则最优解不变.,容易计算直线A和直线B的斜率，我们来看一看若想保持极点仍然为最优解点，应满足的条件：,（3-1）,因此，我们得到目标函数的斜率为CSCD。把CSCD代入式（3-1），我们看到只要满足下列条件，极点就仍然是最优解点：,现在让我们考虑目标函数直线斜率的一般形式。用CS表示标准袋的利润，CD表示高级袋的利润，P表示目标函数值。使用这些标识，目标函数直线可以写成：PCSSCDD把上面方程写成斜截式，得到：CDDCSSP以及,从左边的不等式，我们得到,（3-2）,为了计算标准袋利润最优的范围，我们假设
7、高级袋的利润CD9，代入式（3-2），我们得到：,因此,综合标准袋利润CS的极限，标准袋利润最优范围为：6.3CS13.5,从右边的不等式，我们得到,因此，,在最初Par公司的问题中，标准袋的利润是10美元。最优解是540个标准袋和252个高级袋。标准袋利润CS的最优范围告诉Par公司的管理者：在其他系数不变的情况下，只要标准袋的利润在6.3美元与13.5美元之间，540个标准袋和252个高级袋总是最优产量。然而值得注意的是，即使产量不变，总的利润也可能由于每一个标准袋利润的变化而变化。这些计算可以重复进行，假设标准袋的利润为常数CS10。如此一来，高级袋利润的最优范围就能够被确定出来。验证可
8、得，这个范围为6.67CD14.29。,多系数同时改变 目标函数系数的最优范围只能够应用于一次只有一个系数发生改变的情况，其他系数都假定保持初值而不发生变化。如果两个或两个以上目标函数的系数被同时改变，就有必要进一步判断最优解会不会也发生变化。然而对于解决只有两个变量的问题时，式（3-2）给出了一个简单的方法，以判断两个目标函数系数同时发生改变时，最优解是否也发生改变。简单地计算出在新的系数值下目标函数的斜率（-CS/CD）,如果这个比值大于等于目标函数斜率的下限，同时小于等于目标函数斜率的上限，那么系数值的变化就不会使最优解发生变化。,在式（3-2）中，我们计算出只要满足下列条件，极点仍然是
9、最优点,如果CS升高到13美元，同时使CD降低到8美元，新的目标函数斜率将变成,由于这个值要小于下限，因此当前的解S=540,D=252不再是最优的。把CS=13，CD=8代入，可得出极点是新的最优解。,观察最优范围，我们得出结论，无论是CS升高到13美元还是使CD降低到8美元（当不是同时变化），都不会带来最优解的变化。但当CS与CD同时改变时，目标函数斜率的变化导致了最优解的变化。这个结论强调了这样一个事实：仅仅是通过最优范围，只能用于判断在一次改变一个目标函数系数的情况下最优解的变化。,3.2.2 约束条件右端值的变化,现在让我们来考虑约束条件右端值的变化对可行域带来的影响，及可能对最优解
10、带来的变化。为了阐明敏感度分析的这方面内容，我们假设Par公司的切割与印染部门增加了10小时的生产时间，然后来考虑将会有什么发生。切割与印染约束条件的右端值由630变为640，约束条件可写作,又获得了10个小时的切割与印染时间，我们可以扩展问题的可行域，如图3-3所示。可行域变大了，现在我们考虑是否有新的解会使目标函数值更大。运用图解法可以看出，极点S=527.5，D=270.5是最优解点。新的目标函数值为10527.5+9270.5=7711.75美元，比原来利润增加了7711.75 7688.00=43.75美元。因此，利润的增加率为43.75/10=4.375美元/小时。,200,400
11、,600,800,200,400,600,o,S,D,可行域,10S+9D=7711.75,图3-3,直线A(7/10)S+D=640,S=527.50D=270.75,约束条件右端值每增加一个单位引起的最优值的改进量称为对偶价格。在这个例子里，切割与印约束条件的对偶价格为4.375美元换言之，如果我们使得右边切割与印染约束条件增加1小时，目标函数的值会相应的增加4.375美元。相反，如果我们使得右边切割与印染约束条件减少1小时，目标函数的值会相应的减少4.375美元。对偶价格可以用来求出当某个约束条件右端值改变1个单位，目标函数值将会有什么变化。,在这里，我们要注意的是，对偶价格可能只适用于
12、在右端值仅发生了很小的变动时的情况。随着所获得的资源越来越多，从而右端值越来越大，其他的约束条件也可能会约束和限制目标函数值的变化。拿Par公司的例子来说，我们最终会找到某一点，从那一点之后，再增加切割与印染的时间也不会使利润增加在切割与印染约束条件不再是束缚性约束条件是，这就有可能发生。在这一点，对偶价格等于0。,下一节中，我们会讨论如何确定右端值变动的有效范围，在这个范围内，通过对偶价格可以精确地预测出目标函数值的变动。最后要指出的是，任何非束缚性约束条件的对偶价格都是0，因为增加这样的约束条件的右端值，只会得到约束条件的剩余或松弛变量。,为了在解决最小化问题中正确解释对偶价格，假设我们刚
13、刚解出了一个关于总成本最小化的问题，最优解的值为100美元。此外，假设某个约束条件的对偶价格是-10美元。负的对偶价格告诉我们，如果使右端值增加1，目标函数值不会增加，反而会减少10美元。在最小化问题中，目标函数结果变得更坏意味着总成本的增加。那样的话，如果右端值增加1个单位，目标函数变成110美元。反过来，右端值减少了=1单位，总成本减少10美元。,3.3 灵敏度分析：计算机求解,在第2.4节，我们说明了如何使用管理科学家软件来解决Par公司的线性规划问题。回忆一下，为了使用管理科学家软件，我们必须使用小数来代替分数。Par公司的问题小数形式的系数表示如下：Max 10S+9D S.t.0.
14、7S+1D630 切割与印染 0.5S+0.833 33D600 缝合 1.0S+0.666 67D708 成型 0.1S+0.25D135 检查与包装 S,D0,我们现在示范如何利用管理科学家软件来进行灵敏度分析，如图3-4所示。,Objective Function Value=7667.99463 Variable Value Reduced Costs-S 539.99841 0.00000 D 252.00113 0.00000Constraint Slack/Surplus Dual Prices-1 0.00000 4.37496 2 120.00000 0.00000 3 0.
15、00000 6.93753 4 17.00000 0.00000,OBJECTIVE COEFFICIENT RANGES Varible Lower Limit Current Value Upper Limit-S 6.30000 10.00000 13.49993 D 6.66670 9.00000 14.28572RIGHT HAND SIDE RANGES Constraint Lower Limit Current Value Upper Limit-1 495.59998 630.00000 682.36316 2 479.99930 600.00000 No Upper Lim
16、it 3 580.00146 708.00000 900.00000 4 117.00012 135.00000 No Upper Limit,3.3.1 计算机输出的解释第一个例子 在第2.4节，我们对图3-4顶部的输出结果进行了讨论。在取近似值之后，我们得到最优解是S=540个标准袋和D=252个高级袋，目标函数最优解是7668美元。如我们在第2.4节讨论的一样，递减成本（Reduced Costs）一栏的信息告诉我们目标函数的每个系数应提高多少，目标函数的变量值才能是正数。对于Par公司的例子，两个变量都已经是正值，所以它们相应的递减成本就是0。在第3.4节，我们将会介绍递减成本，这时决
17、策变量在最优位置上并不是正值。,在最优解S,D以及递减成本信息下面，计算机输出了有关约束条件的信息。回忆Par公司的例子，其中有4个小于或等于约束条件的，都是关于各个生产部门的生产时间。在松弛/剩余变量一栏中，可以看到每个部门的松弛变量值。上述信息归总如下：,从上述数据中，我们可以看到束缚性约束条件（切割与印染和成型）在目标函数的最优下，松弛为0。缝合部门有120小时的松弛或未使用的缝合能力：检查与包装部门有18小时的松弛。对偶价格栏的信息是关于目标函数取得最优解时，这4种资源的边际价值。在第3.2节，我们对对偶价格进行了如下的定义：对偶价格就是约束条件右端值每增加一个单位引起的，最优解的增加
18、量。,这里，约束条件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（美元）。由于缝合和检查与包装约束条
19、件有松弛或未使用的工作能力，它们的零对偶价格表明，对这两个部门增加额外的工作时间也不会对目标函数的值产生影响。再次看看图3-4的结果，我们看到管理科学家软件除了提供松弛/剩余变量和对偶价格的约束条件信息之外，还给出了目标函数系数和约束条件右端值的变化范围。,考虑在输出结果的标题“目标系数范围”（OBJECTIVE COEFFICIENT RANGES）下面给出的信息，我们观察变量S（此时的值是10）有如下的最优化范围：6.30CS13.50因此，只要标准袋的利润在6.30到13.50之间，生产540个标准袋和252个高级袋都是最优解。仔细观察会发现，这个最优化范围与第3.2节用图解法得出的结论
20、是一致的。再观察一下高级袋的使目标函数值变化的信息，我们看到管理科学家软件计算出如下的最优化范围：6.67CS14.29,这个结果告诉我们，只要高级袋的利润在6.67到14.29之间，生产540个标准袋和252个高级袋都是最优的。计算机输出的结果的最后一部分右端值范围（RIGHT HAND SIDE RANGES）给出了对对偶价格适合范围的限制条件。只要约束条件右端值处于系统所给出的上限和下限之间，对偶价格就会给出当右端值增加1时，最优解的增加量。举例来说，我们说每额外增加一小时工作量，目标函数会增加4.37美元。没减少1小时工作量，当然也同样会使目标函数值减少4.37美元。,在右端值范围栏的
21、信息中可见，4.37美元的对偶价格在右端值增加到682.36316或减少到495.59998之间的范围内都是有效的。成型约束条件也是一样，在右端值增加到900小时或是减少到580.00146小时之间的范围内，对偶价格6.94美元都是有效地。如前所述，右端值范围给出了一个对偶价格的适用范围。如果右端值的变化超出了这个范围，就需要重解原问题并找出新的对偶价格。我们把这个对偶价格适用的范围叫做可行域。Par公司问题的可行域汇总如下：,只要右端值在这些范围之内，系统分析结果中的那些对偶价格就不会改变。右端值如果超出了这些范围，对偶价格的信息就会随之改变。,3.3.2多系数同时变化 系统灵敏度分析的输出
22、是基于单函数系数变化的。它假设所有其他的系数都保持不变。因此目标函数系数和约束条件右端值的变化范围只能适用于单个系数发生变化的情况。然而在很多情况下，我们可能更加关注当两个或两个以上系数同时变化时，目标函数将怎样变化。有些多系数同时变化的分析可能会用到100%法则（100 percent rule）。我们下面分析100%法则是如何应用于多系数同时变化的情形中的。,假设Par公司的会计部门指出，原先对标准袋和高级袋的利润的计算分别为10美元和9美元有错误，正确的利润是11.50美元和8.25美元。为了确定这样的变化是否会对最优解产生影响，我们先要定义两个术语“允许增加量”（allowable i
23、ncrease）和“允许减少量”（allowable decrease）。对于目标函数的系数，允许增加量是在不超过最优范围的情况下，系数可能增加的最大量；而允许减少量是在不低于最优范围下限的情况下，系数可能减少的最大量。,从图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），,允许
24、增加量（42.86%）和允许减少量（32.14%）变化之和为75%。现在我们对将要应用于多个变量同时改变情况中的100%法则进行定义。,目标函数系数的100%法则 对所有变化的目标函数系数，计算其占允许增加量和允许减少量的百分比之和。如果和没有达到100%，最优解就不会改变。,在Par公司的例子中，由于目标函数系数的两项改变的百分率之和为75%，因此最优解不会改变。然而值得注意的是，尽管最优解仍然是S=539.99841，D=252.00113，但最优值可能会因为标准袋的利润增加到11.50美元，高级袋的利润减少到8.25美元而变化。但是，100%法则并没有规定如果各百分比之和达到100%，最
25、优解就一定会发生变化。有可能个百分比之和超过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%，因此我们可以得到下面的结论：对偶价格在这里是适用的，并且目标函数值将会由此增加204.37+1006.94=781.40。,
26、3.3.3 计算机输出的解释第二个例子 我们重新考虑第2.5节中讨论的M&D化工公司的问题，以此作为解释计算机输出的第二个例子。M&D公司的目标是为产品A和产品B找出一个成本最低的生产计划。下面是解决这个问题的线性规划模型，其中，A表示产品A的产量，B表示产品B的产量。Min 2A+3B s.t.1A 125 产品A的需求 1A+1B350 总产量 2A+1B600 生产时间 A,B0,利用管理科学家软件对其进行求解，结果展示在图3-5中。计算机输出结果显示，最优解服从于800美元的目标函数。决策变量的值告诉我们，成本最低的生产计划是生产250加仑的产品A和100加仑的产品B。,Objecti
27、ve Function Value=800.000 Variable Value Reduced Costs-A 250.000 0.000 B 100.000 0.000,Constraint Slack/Surplus Dual Prices-1 125.000 0.000 2 0.000 4.000 3 0.000 1.000OBJECTIVE COEFFICIENT RANGES Variable Lower Limit Current Value Upper Limit-A No Lower Limit 2.000 3.000 B 2.000 3.000 No Upper Limit
28、RIGHT HAND SIDE RANGES Constraint Lower Limit Current Value Upper Limit-1 No Lower Limit 125.000 250.000 2 300.000 350.000 475.000 3 475.000 600.000 700.000,松弛/剩余变量栏显示，其中大于等于的约束条件意味着产品A的需求有125单位的剩余（见约束条件1）。这就是说，当处于最优解时，产品A的产量比需求多125加仑。对于总的生产要求（约束条件2）和生产时间限制（约束条件3），松弛/剩余变量值为0，这意味着这两个约束条件是最优解的束缚性约束条件。
29、,对偶价格栏再一次告诉我们，每增加一单位的约束条件右端值时最优解的改进。首先观察生产时间的限制（约束条件3），其对偶价格为1.00。如果我们增加生产时间，,使之从600小时变成601小时，目标函数的值就会改进1美元。由于目标的使成本最小，这里的“改进”意味着成本的降低。因此，如果生产时间变成601小时，最优解的值将会减少到8001=799美元。输出结果的右端值范围（right hand side range）部分给出了生产时间限制（约束条件3）的上限。因此，在总的生产时间低于700小时时，1美元的对偶价格都是有效的。再回到输出结果的对偶价格部分，考虑总产量约束（约束条件2）的对偶价格。负的对偶
30、价格表明，如果总产量约束的右端值增加一个单位，最优解不会改进。,事实上，-4.00的对偶价格告诉我们，如果总产量约束的右端值从350单位增加到351单位，最优解将会变坏4美元。“变坏”意味着成本的增加，即最优解将变为8004=804（美元）。由于对偶价格是关于当右端值增加一个单位时最优解的改进量，有负对偶价格的约束条件就不能再增加其右端值了，而应该努力减少其右端值。如果总产量约束条件的右端值从350单位减少到349单位，总成本就会减少4美元而变成8004=796（美元）,尽管对偶价格表示了右端值每增加一个单位对最优解的改进，然而对目标函数值“改进”的解释取决于所解决的问题是最大化问题还是最小化
31、问题。小于等于型约束条件的对偶价格总是大于或等于0的，因为增加其右端值不会使目标函数值变得更坏。类似地，大于等于型约束条件的对偶价格总是小于或等于0的，因为增加其右端值不会对最优解有所改进。最后，考虑图3-5中的右端值范围部分。M&D化工公司问题的可行域归纳如下：,只要右端值在上述范围，计算机输出的结果中的对偶价格就是适用的。,3.3.4 关于对偶价格解释的注释 如前所述，对偶价格是右端值每增加一个单位时对最优值的改进。当约束条件的右端值表示某中资源的可利用量时，对偶价格通常可以解释为公司对额外支付一单位这种资源所愿意提供的金额。然而这种解释也并非总是正确的。要理解这个问题，问你先要理解沉没成
32、本和相关成本的区别。沉没成本不会受决策影响，无论决策变量为何值，这种成本都会发生。相关成本则取决于决策的制定，这种成本依赖于决策变量值的变化而变化。,让我们重新考虑Par公司的例子。切割与印刷的总时间的630小时。如果说无论生产标准袋或是高级袋，都是按照时间来付出工资的，那么时间成本就是一种沉没成本。如果Par公司只需要为那些切割和印染高尔夫球袋的时间补偿工资，那么时间成本就是一种相关成本。所有的相关成本都要在线性规划的目标函数中有所反映。对Par公司而言，我们一直假设公司必须按照工作时间来向工人发工资，不管他们的工作时间是否有效率地被利用。因此，Par公司的劳动时间资源的成本就属于沉没成本而
33、不在目标函数中反映出来。,当某种资源的成本属于沉没成本，对偶价格就可以被解释为公司愿意为得到额外一个单位这种资源而付出的金额。当某种资源的成本属于相关成本，对偶价格则可以被解释为这种资源的价值超过其成本的数额，也就是增加一个单位这种资源时，公司能付出的最大成本量。,3.4 多于两个决策变量的情况,图解法只能应用于解决双决策变量的线性规划问题，而计算机软件是用来处理多变量和约束条件的线性规划问题的。在现实生活中，用线性规划解决的问题经常包含大量的变量和约束条件。在本节中，我们讨论在两个线性规划问题中，三决策变量问题的方程和计算机求解。在讨论过程中，我们会解释计算机输出结果中的递减成本部分的含义，
34、同时阐述如何解释带有百分数的约束条件的对偶价格。,3.4.1修正的Par公司问题 Par公司原来问题的模型如下：Max 10S 9D s.t.0.7S 1D630 切割与印染 0.7S0.833 33D600 缝合 1S0.666 67D708 成型 0.1S 0.25D135 检查与包装 S,D0回忆一下，S是标准袋的产量，D是高级袋的产量。假设管理者希望生产一种轻便的、可以被球手随身携带的球袋模型。,设计部门估计每个新型球袋将需要0.8小时的切割与印染的时间，1小时的缝合时间，1小时的成型时间和0.25小时的检查与包装时间。由于这种设计是独一无二的，管理者认为在当前销售期内每个轻便袋可以获
35、利12.58美元。我们来考虑对原来线性规划模型进行修改，修改后的模型需要加入新的决策变量的影响。令L为轻便袋的产量，将其加入目标函数以及4个约束条件，可以得到如下修改后的模型：,max 10S 9D12.58L s.t.0.7S 1D 0.8L630 切割与印染 0.5S0.833 33D 1L630 缝合 1S0.666 67D 1L708 成型 0.25D0.25L135 检查与包装 S,D,L0 图3-6是使用管理科学家软件对新问题进行求解的结果。最优解为280个标准袋，0个高级袋和428个轻便袋，最优值近似为8299.80美元。,Objective Function Value=829
36、9.80078 Variable Value Reduced Costs-S 280.00000 0.00000 D 0.00000 1.15003 L 428.00000 0.00000 Constraint Slack/Surplus Dual Prices-1 91.00000 0.00000 2 32.00000 0.00000 3 0.00000 8.10000 4 0.00000 19.00000,OBJECTIVE COEFFICIENT RANGES Variable Lower Limit Current Value Upper Limit-S 5.14000 10.0000
37、0 12.07007 D No Lower Limit 9.00000 10.15003 L 11.90907 12.85000 25.00000RIGHT HAND SIDE RANGES Constraint Lower Limit Current Value Upper Limit-1 538.40002 630.00000 No Upper Limit 2 568.00000 600.00000 No Upper Limit 3 540.00000 708.00000 852.63159 4 70.80000 135.00000 144.60001,图3-6 使用管理科学家软件对修改后
38、的Par公司问题的求解,现在来看递减成本栏的信息。回忆前面对递减成本的解释，表示使得变量为正数时相应目标函数的增加量。计算机输出结果表明，S和L的递减成本都是0，这是因为相应的决策变量值在最优解处已经是正值。变量D的递减成本为1.150 03，表明高级袋的利润至少增加到91.150 0310.150 03美元时，D才能变为一个正值。假设我们使D的系数正好增加1.150 03美元，再用科学家管理软件来重解原问题。如图3-7所示，注意到尽管D的值已经是正数，最优解的值仍然没有变。换言之，当D利润的增量正好等于其递减成本时，能得到多重最优解。但是，如果D的利润增加超过1.150 03美元，它在最优解
39、处就不再是0。,Objective Function Value=8299.80078 Variable Value Reduced Costs-S 403.78317 0.00000 D 222.81198 0.00000 L 155.67476 0.00000 Constraint Slack/Surplus Dual Prices-1 0.00000 0.00000 2 56.75776 0.00000 3 0.00000 8.10000 4 0.00000 19.00000,OBJECTIVE COEFFICIENT RANGES Variable Lower Limit Curren
40、t Value Upper Limit-S 10.00000 10.00000 12.51072 D 10.15003 10.15003 15.40790 L 10.65313 12.85000 12.85000 RIGHT HAND SIDE RANGES Constraint Lower Limit Current Value Upper Limit-1 538.40002 630.00000 628.36316 2 543.24225 600.00000 No Upper Limit 3 580.00140 708.00000 852.63159 4 117.00012 135.0000
41、0 151.15410,图3-7 Par公司问题中的系数D的值增加了1.150 03美元后的解,3.4.2牧草农场问题 为了提高我们对多变量问题的求解能力，我们来考虑一种三决策变量的最小化问题。牧草农场公司位于肯塔基州列克星敦市，一直在试验一种特殊的赛马食品。该食品的成分包括标准的马饲料产品，一种富含维生素的燕麦，以及一种新型维生素和矿物质饲料添加剂。表3-1中归纳了每磅食品的营养价值以及各种成分的成本。比如，每磅标准饲料包含0.8单位的成分A，1单位的成分B和0.1单位的成分C。每匹马每天的营养价值最低为3单位成分A，6单位成分B和4单成C。此外，为了控制马匹的体重，每匹马每天进食不得超过6
42、磅。,牧场农场要在满足每天的食品需求的情况下确定出成本最低的配料方案。,表3-1 牧草农场饲料的营养价值和成本,3.4.3建立牧草农场问题的模型 建立牧草农场的线性规划模型之前，我们需要引进如下3个变量：S标准马饲料的量；E高营养燕麦的量；A维生素和矿物质饲料添加剂的量；运用表3-1中的数据，总成本最小的目标函数可以表示如下：min 0.25S+0.50E+3A对每天3磅需求的成分A，有如下约束：0.8S+0.2E3成分B的约束：1.0S+1.5E+3.0A6,成分C的约束：0.1S+0.6E+2.0A4最后是最多6磅的混合重量约束：S+E+A 6合并所有的约束条件，再加上非负约束，完整的牧草
43、农场问题的线性规划模型表述如下：min 0.25S+0.50E+3A s.t.0.8S+0.2E 3 成分A 1.0S+1.5E+3.0A 6 成分B 0.1S+0.6E+2.0A4 成分C S+E+A6 加权 S,E,A0,3.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.
44、54*3.00=4.62（美元）总成本=5.97(美元)取近似后，该结果与计算机输出（见图3-10结果一致）,Objective Function Value=8299.80078 Variable Value Reduced Costs-S 3.514 0.000 E 0.946 0.000 A 1.541 0.000 Constraint Slack/Surplus Dual Prices-1 0.000-1.216 2 3.554 0.000 3 0.000-1.959 4 0.000 0.919,OBJECTIVE COEFFICIENT RANGES Variable Lower L
45、imit Current Value Upper Limit-S-0.393 0.250 No Upper Limit E No Lower Limit 0.500 0.925 A 1.522 3.000 No Upper Limit RIGHT HAND SIDE RANGES Constraint Lower Limit Current Value Upper Limit-1 1.143 3.000 3.368 2 No Lower Limit 6.000 9.554 3 2.100 4.000 4.875 4 5.562 6.000 8.478,图3-10 使用管理科学家软件对牧草农场问
46、题求解,观察计算机输出地松弛/剩余部分，约束条件2的值为3.554。由于约束2是大于等于型的，因此，3.554是剩余值。由于约束1和约束3的剩余值都是0，因而我们看到最优混合中，成分A和成分C刚好满足最低要求。此外，约束4的剩余值也是0，说明最优解中每天的饲料重量正好为6磅。,成分A的约束条件（约束条件1）的对偶价格为-1.22.合理解释这个值，首先我们看它的符号为负，因此我们知道如果增加其右端值，将使得最优解变得更坏。在最小化问题中，“更坏”意味着总成本的增加，因此，右端值一单位的增加会使总成本上升1.22美元。反过来，也可以说右端值每减少一个单位，总成本下降1.22美元。观察右端值范围部分
47、，我们看到只要右端值在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的下限
48、为0.我们有此可以得到，无论标准饲料的价格下降多少，最优解都不会改变。即使牧草农场可以免费获得标准饲料，最优解仍然是3.51磅的标准饲料，0.95磅的高营养燕麦和1.54磅维生素和矿物质饲料添加剂。然而，标准饲料单位成本的减少，都会引起总成本的减少。,注意目标函数系数S和A是没有上限限制的。如果增加A的值，比如，从每磅3美元增加到每磅13美元，最优解释不会变化的，而总成本则会增加10倍，即从1.54 1美元变为15.41美元。切记，我们对计算机输出结果所做的灵敏度分析的解释，只有在问题中其他的系数不变的情况下才是有效的。为了解决多系数变化的情况，我们必须用100%规则或是重新求解问题。,3.5
49、电子通信公司问题,本节讨论的电子通信公司是一个最大化问题，这个问题包括4个决策变量，2个小于等于形式的约束条件，1个等于形式的约束条件和1个大于等于形式的约束条件。我们的目标是建立一个简单的数学模型，使用管理科学家软件求出模型的最优解，对求出的解进行解释，并进行灵敏度分析。在下一章。我们会向读者介绍线性规划在营销、金融、生产管理等方面的应用。一旦你能够对电子通信公司这样的问题进行建模、求解和分析，你就会明白线性规划能够解决多么复杂的问题。,让我们来看这个例子，电子通信公司主要生产双向便携式无线双向便携式无线电报话机。该公司最近开发了一种新产品，这种产品的通信范围可以覆盖25英里，适合企业和个人
50、使用。该新产品的分销渠道是：航海器材经销商。商用器材经销商。全国范围的连锁零售店。直接邮购。,由于分销和促销成本的差异，产品的利润也因销售渠道的不同而不同。此外，广告费用和人力成本也与销售渠道有关，表3-2简要地将电子通信公司不同销售渠道的销售利润、广告费用、人工成本列了出来。公司的广告费用预算是5000美元，每个销售渠道的最大个人销售时间是1800个小时。公司现阶段决定制造的产品数为600件，此外，全国连锁零售店要求最少销售150件产品。,表3-2 电子通信公司的利润、广告费用和个人销售时间,电子通信面临的问题是如何制定一个分销策略，使其总的销售利润最大。公司必须决定如何分配各渠道的销售量、
