数据模型与决策 第三章ppt课件.ppt

《数据模型与决策 第三章ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据模型与决策 第三章ppt课件.ppt（66页珍藏版）》请在三一办公上搜索。

1、第三章,线性规划的灵敏度分析与最优解的解释,2,灵敏度分析简介,图解法灵敏度分析,灵敏度分析：计算机求解,传统灵敏度分析的不足,电子通信公司问题,3,1,4,5,主要内容,灵敏度分析（sensitivity analysis） 研究线性规划问题中系数的变化对函数最优解的影响程度，有时也被称为后优化分析（postoptimality analysis）。 运用灵敏度分析，我们可以回答以下问题： （1）如果目标函数的系数发生变化，对最优解会产生什么影响？（2）如果改变约束条件的右端值，对最优解会产生什么影响？,3.1 灵敏度分析简介,3.1 灵敏度分析简介,分析目标函数系数的变化对最优解的影响；

2、分析模型中的系数哪个更能左右最优解； 分析约束条件右端值的变化对最优解的影响。,3.1 灵敏度分析简介,以Par公司问题为例：,原问题模型：max 10 S + 9 D s.t. 7/10 S+ 1 D 630 切割与印染 1/2 S+ 5/6 D 600 缝合 1 S+ 2/3 D 708 成型 1/10 S+ 1/4 D 135 检查与包装 S, D 0模型最优解：S=540，D=252,分析目标函数系数的变化对最优解的影响,3.1 灵敏度分析简介,我们已经知道这个问题的最优解是标准袋生产540个，高级袋生产252个。这个最优解的前提是每个标准袋的利润是10美元，每个高级袋的利润是9美元。

3、 假设，由于价格下降，标准袋的利润由10美元降到8.5美元。这时我们可以用灵敏度分析来确定标准袋生产540个，高级袋生产252个是否还是最优解。如果还是，则不必建立新的模型求解了。,3.1 灵敏度分析简介,比如，管理层认为高级袋的利润9美元只是一个估计量。 如果通过灵敏度分析得到，高级袋的利润在6.67-14.29美元之间变化时，最优解不变，那么管理层对9美元这个估计量和最优产量比较满意。但是，如果灵敏度分析告诉我们，只有当高级袋的利润在8.9-9.25美元之间变化时，最优解才不变。那么管理层就必须思考每个高级袋获利9美元这个估计量的可信程度有多大了。管理层希望知道如果高级袋的利润下降，最优产

4、量会怎样变化。,分析模型中的系数哪个更能左右最优解,3.1 灵敏度分析简介,以Par公司问题为例： 在最优产量的情况下，切割与印染部和成型部的工作时间已经全被占用了。如果现在公司增加了这两个部门的生产能力，那么最优解以及总利润的值会发生什么样的变化呢？灵敏度分析可以帮助确定每一个工时的边际价值，以及在利润下降之前部门工时的最大增加量。,分析约束条件右端值的变化对最优解的影响,3.2 图解法灵敏度分析,目标函数的系数变化会对Par公司的最优产量产生什么样的影响？选择每个标准袋的利润是10美元，每个高级袋的利润是9美元。很明显，如果其中一种袋子的利润下降，公司就会消减其产量；如果利润上升，公司就会

5、增加其产量。但问题是，究竟利润变化多少时，管理者才应该改变产量呢？,图解法灵敏度分析仅适用于双变量的线性规划问题。,3.2.1 目标函数系数,3.2.1 目标函数系数,每个目标函数系数都有一个最优范围（range of optimality），即目标函数系数在什么范围内变化时，模型的最优解保持不变。我们应该注意那些系数的最优范围比较小，或者系数刚好靠近最优范围边界的情况。在这种情况下，这些系数的微小变动就有可能使最优解发生改变。,3.2.1 目标函数系数,如图3-1所示：只要目标函数线的斜率处于直线A（和切割与印染约束线重合）的斜率与直线B（与成型约束线重合）的斜率之间，极点 （S=540，D

6、=252）就是最优解点。,图3-1 图解法求Par公司问题,3.2.1 目标函数系数,改变目标函数中标准袋产量S和高级袋产量D的系数，将引起目标函数斜率的变化。这种变化导致目标函数线饶着极点旋转。然而，只要目标函数线仍然在阴影区域内，极点就仍然是最优解点。 逆时针选择目标函数线，使其斜率变成一个绝对值更小的负数，从而斜率变大了。当目标函数线逆时针旋转到足够的角度，与直线A重合，我们就获得了多重最优解-在极点和极点之间的点都是最优点。任何对目标函数线的进一步逆时针转动，都会使得极点不再是最优解点。因此，直线A的斜率就是目标函数线的上限。,3.2.1 目标函数系数,顺时针转动目标函数线，使其斜率变

7、成一个绝对值更大的负数，从而斜率变小了。当目标函数线顺时针旋转到足够的角度，直至与直线B重合，我们就会获得了多重最优解-在极点与极点之间的点都是最优点。任何对目标函数线的进一步顺时针转动，也都会使得极点不再是最优解点。因此，直线B的斜率就是目标函数线斜率的下限。,3.2.1 目标函数系数,因此，极点总是最优解点，只要 直线B 的斜率目标函数线的斜率直线A的斜率 即， -3/2目标函数的斜率-7/10 (3-1) 现在让我们考虑目标函数线斜率的一般形式。用 CS 表示标准袋的利润，CD 表示高级袋的利润，P表示目标函数值。使用这些符号，目标函数直线可以写成： P = CS S + CD D,3.

8、2.1 目标函数系数,把上面方程写成斜截式，得到： CD D = - CS S + P以及 D = S +因此，我们得到目标函数的斜率为 。把 代入式（3-1），我们看到只要满足下列条件，极点就仍然是最优解点： -3/2 -7/10 (3-2),3.2.1 目标函数系数,标准袋利润最优的范围 我们假设高级袋的利润CD=9，代入式（3-2），我们得到： -3/2 -7/10 解得， 6.3 CS 13.5 即标准袋利润最优范围为： 6.3 CS 13.5 高档袋利润最优的范围 同上求解过程，假设标准袋的利润为常数CS=10，可得高档袋利润最优范围为： 6.67 CD 14.29,3.2.1 目标

9、函数系数,当目标函数绕最优点旋转，使之与坐标轴垂直时，像式（3-2）中出现的那种斜率的上限或下限就不再存在了。 为了说明这种特殊的情况，我们设Par公司的目标函数为 18 CS + 9 CD ；这样，在图3-2中，极点就是最优解点。,图3-2 图解法求Par公司问题 目标函数为18S+9D,3.2.1 目标函数系数,3.2.1 目标函数系数,3.2.1 目标函数系数,目标函数系数的最优范围只能够应用于一次只有一个系数发生改变的情况。如果两个或两个以上目标函数的系数同时改变，就有必要进一步判断最优解会不会也发生变化。 对于解决只有两个变量的问题，式（3-2）给出了一个简单的方法。简单地计算出在新

10、的系数值下目标函数的斜率（- CS/CD）,如果这个新目标函数的斜率在原目标函数斜率的上下限范围内，那么系数值的变化不会使最优解发生变化。,多系数同时改变,3.2.1 目标函数系数,考虑Par公司问题中目标函数两个系数的变化。假设每个标准袋利润增加到13美元，同时每个高级袋利润减少到8美元。回忆标准袋利润CS与高级袋利润CD的最优范围为： 6.3 CS 13.5 （3-3） 6.67 CD 14.29 （3-4） 对于上述最优范围，我们可以推断，无论是使CS升高到13美元还是使CD降低到8美元（不是同时），都不会使最优解（S=540，D=252）发生变化。 但是我们无法从上述最优范围中推断出如

11、果两个系数同时发生改变，最优解是否会发生改变。,3.2.1 目标函数系数,在式（3-2）中，我们计算出只要满足下列条件，极点仍然是最优点： -3/2 -7/10 如果CS 升高到13美元，同时使CD降低到8美元，新的目标函数斜率将变成： = -13/8 = -1.625 由于这个值要小于下限-3/2，因此当前的解S=540，D=252不再是最优的。把 CS =13，CD =8代入，可以得出极点是新的最优解。,3.2.2 约束条件右端值的变化,我们仍以Par公司问题为例来考虑约束条件右端值的变化对可行域及最优解带来的影响。 我们假设Par公司的切割与印染部增加了10个小时的生产时间，然后考虑将会

12、发生什么。 新切割与印染约束条件可写作： 7/10 S + 1 D 640,3.2.2 约束条件右端值的变化,新约束条件： 7/10 S +1D640扩展可行域，如右图。图解法新解： S=527.5，D=270.5新目标函数值： 7711.75（美元）利润增加率： 4.375（美元每小时）,图3-3 切割与印染约束条件的右端值增加10小时的影响,3.2.2 约束条件右端值的变化,约束条件右端值每增加一个单位引起的最优值变化量称为对偶值（dual value）。在新Par公司问题里，利润增加率4.375即为切割与印染约束条件的对偶值。换言之，切割与印染约束条件右端值增加/减少1小时，目标函数的值

13、会增加/减少4.375美元。对偶值可以用来求出当某个约束条件右端值改变一个单位时，目标函数值将会有什么变化。,3.2.2 约束条件右端值的变化,注意：,对偶值可能只适用于右端值仅发生了很小变动时的情况。 右端值大到一定程度时，其约束可能不再是束缚性约束，其他的约束条件也可能会约束和限制目标函数值的变化。例：Par公司问题，我们最终会找到某一点，从那一点之后，再增加切割与印染的时间也不会使利润增加。在这一点，对偶值等于0。,3.3 灵敏度分析：计算机求解,仍以Par公司问题为例：Par公司问题模型：,max 10 S + 9 D s.t. 7/10 S+ 1 D 630 切割与印染 1/2 S+

14、 5/6 D 600 缝合 1 S+ 2/3 D 708 成型 1/10 S+ 1/4 D 135 检查与包装 S, D 0,我们现在示范如何通过考虑Par公司的线性规划求解来理解灵敏度分析，如图3-4所示。,Optimal Objective Value = 7668.00000 Variable Value Reduced Cost S 540.00000 0.00000 D 252.00000 0.00000Constraint Slack/Surplus Dual Value 1 0.00000 4.37500 2 120.00000 0.00000 3 0.00000 6.93750

15、 4 18.00000 0.00000 Objective Allowable Allowable Variable Coefficient Increase Decrease S 10.00000 3.50000 3.70000 D 9.00000 5.28571 2.33333 Allowable Allovable Constraint RHS value Increase Decrease 1 630.00000 52.36364 134.40000 2 600.00000 Infinite 120.00000 3 708.00000 192.00000 128.00000 4 135

16、.00000 Infinite 18.00000,图3-4 Par 公司问题的求解,3.3.1 计算机输出结果的解释,最优解信息,Optimal Objective Value=7668.0000 Variable Value S 540.00000 D 252.00000,Par公司问题模型最优解，S=540，D=252，目标函数最优解是7668美元。,约束条件信息,Constraint Slack/Surplus 1 0.00000 2 120.00000 3 0.00000 4 18.00000,松弛/剩余信息,3.3.1 计算机输出结果的解释,对偶值信息（资源边际价值）,Constra

17、int Slack/Surplus Dual Value 1 0.00000 4.37500 2 120.00000 0.00000 3 0.00000 6.93750 4 18.00000 0.00000,在第3.2节中，我们对对偶值进行了如下定义： 对偶值就是约束条件右端值每增加一个单位引起的最优值变化量。 这里，图3-4中的对偶值可做如下解释：,3.3.1 计算机输出结果的解释,约束条件1（切割与印染）和约束条件3（成型时间）的非零对偶值分别为4.375和6.9375。这告诉我们，每额外增加1小时的切割与印染时间会使最优值增加4.37美元；每增加1小时的成型时间将会使最优值增加6.94美

18、元。因此，在其他系数不变的情况下，如果切割与印染时间从630小时增加到631小时，Par公司的利润会增加4.37美元，即由7668美元增加到7668+4.37=7672.37（美元）。在其他系数保持不变的情况下，如果有效成型时间从708小时增加到709小时，Par公司的利润将会增加到7668+6.94=7674.94（美元）。由于缝合和检查时间与包装约束条件有松弛或未使用的工作能力，它们的零对偶值表明，对这两个部门增加额外工作时间也不会对目标函数的值产生影响。,3.3.1 计算机输出结果的解释,递减成本（reduced cost）：一个变量的递减成本等于这个变量非负约束的对偶值。,Optima

19、l Objective Value= 7668.00000 Variable Value Reduced Cost S 540.00000 0.00000 D 252.00000 0.00000,图3-4中显示，变量S和D的递减成本均为0。 非负约束是S0，S的当前值是540，因此改变非负约束使S1 对最优值没有影响。因为增加一个单位的右端值对最优目标函数值没有影响，因此这个非负约束的对偶值（即递减成本）是0。同样这也可以应用于变量D。通常来说，如果一个变量在最优解中有一个非零值，那么它的递减成本将是0.,3.3.1 计算机输出结果的解释,变量S：变量S当前的利润系数是10，允许增加的值是3.

20、5，允许减小的值是3.7。因此，只要标准袋的利润贡献在10-3.7=6.3（美元），10+3.5=13.5（美元）之间时，最优解不变。 变量D：同理，由图3-4可得变量D的目标函数系数在6.6714.29之间变动时，最优解不变。,目标函数系数范围,Objective Allowable Allowable Variable Coefficient Increase Decrease S 10.00000 3.50000 3.70000 D 9.00000 5.28571 2.33333,3.3.1 计算机输出结果的解释,在范围栏的信息中可见：约束条件1的右端值为630，允许增加的值为52.36

21、364，允许减少的值为134.4，因此切割与印染约束右端值在495.6682.4范围内变化时，对偶值都是有效的。 同理，成型约束条件的右端值在580900范围内变化时，对偶值都是有效的。,约束条件右端值的变化范围,Allowable Allowable Constraint RHS value Increase Decrease 1 630.00000 52.36364 134.40000 2 600.00000 Infinite 120.00000 3 708.00000 192.00000 128.00000 4 135.00000 Infinite 18.00000,3.3.1 计算机输

22、出结果的解释,可行域（range of feasibility）：对偶值适用的范围称做可行 域。Par公司问题的可行域汇总如下：,只要右端值在这些范围内，系统分析结果中的那些对偶值就不会改变。右端值如果超出了这些范围，对偶值的信息就会随之改变.,3.3.2 深入理解对偶值,对偶值是右端值每增加一个单位时最优值的变化。然而这种解释也并非总是正确的。要理解这个问题，我们先要理解沉没成本（sunk cost）和相关成本（relevant cost）的区别。沉没成本不会受决策影响，无论决策变量为何值，这种成本都会发生。相关成本则取决于决策的制定，这种成本随决策变量值的变化而变化。 让我们重新考虑Par

23、公司的例子。切割与印染的总时间是630小时。如果说无论生产标准袋或者高级袋，都是按照时间来支付工资的，那么时间成本就是一种沉没成本。所有的相关成本都要在线性规划的目标函数中有所反映。假设Par公司必须按照工作时间来发放工人工资，不管他们的工作时间是否被有效地利用。因此，Par公司劳动时间资源的成本就属于沉没成本，而不在目标函数中反映出来。,3.3.3 修改的Par公司问题,图解法只能应用于解决双决策变量的线性规划问题。在现实生活中，用线性规划解决的问题经常包含大量的变量和约束条件。在本节中，我们讨论在两个线性规划问题中，三决策变量问题的方程和计算机求解。在讨论过程中，我们会解释计算机输出结果中

24、递减成本部门的含义。 Par公司原来问题的模型如下：,max 10 S + 9 D s.t. 7/10 S+ 1 D 630 切割与印染 1/2 S+ 5/6 D 600 缝合 1 S+ 2/3 D 708 成型 1/10 S+ 1/4 D 135 检查与包装 S, D 0,3.3.3 修改的Par公司问题,设S是标准袋的产量，D是高级袋的产量。假设管理者希望生产一种轻便、球手可以随身携带的高尔夫袋模型。设计部门估计每个新型袋将需要0.8小时的切割与印染时间，1小时的缝合时间，1小时的成型时间和0.25小时的检查与包装时间。管理者认为在当前销售期内每个轻便袋可以获利12.85美元。 我们对原模

25、型进行修改，修改后的模型需要加入新的决策变量的影响。令L为轻便袋的产量，将其加入目标函数及4个约束条件，可得到如下模型：图3-5给出了修改后模型的求解结果。,max 10 S + 9 D +12.85 L s.t. 7/10 S+ 1 D + 0.8 L630 切割与印染 1/2 S+ 5/6 D + 1 L600 缝合 1 S+ 2/3 D + 1 L708 成型 1/10 S+ 1/4 D + 1/4 L135 检查与包装 S, D0,图3-5 修改后的Par公司问题的求解,Optimal Objective Value = 8299.80000 Variable Value Reduce

26、d Cost S 280.00000 0.00000 D 0.00000 -1.15000 L 428.00000 0.00000Constraint Slack/Surplus Dual Value 1 91.60000 0.00000 2 32.00000 0.00000 3 0.00000 8.10000 4 0.00000 19.00000 Objective Allowable Allowable Variable Coefficient Increase Decrease S 10.00000 2.07000 4.86000 D 9.00000 1.15000 Infinite L

27、 12.85000 12.15000 0.94091 Allowable Allovable Constraint RHS value Increase Decrease 1 630.00000 Infinite 91.60000 2 600.00000 Infinite 32.00000 3 708.00000 144.63158 168.00000 4 135.00000 9.60000 64.20000,3.3.3 修改的Par公司问题,根据图3-5给出的结果。最优解为280个标准袋，0个高级袋和428个轻便袋，最优值为8299.80美元。 根据递减成本的解释，计算机输出结果表明，S和L

28、的递减成本都为0。变量D的递减成本为 -1.15，表明如果高档袋的产量从0增加到1，那么最优目标函数值将减少1.15。另外一种解释是，如果我们将高档袋的成本降低1.15（也就是将边际收益增加1.5），那么将会出现一个生产非零个高档袋的最优方案。 假设使D的系数正好增加1.15美元，这样新的值就是9+1.15=10.15（美元），然后重解原问题。新的求解如图3-6所示，注意到尽管D的值已经是正数，最优解的值仍然没有变。,图3-6 Par公司问题中系数D的值增加 1.15美元后的求解,Optimal Objective Value= 8299.80000 Variable Value Reduce

29、d Cost S 403.78378 0.00000 D 222.81081 0.00000 L 155.67568 0.00000Constraint Slack/Surplus Dual Value 1 0.00000 0.00000 2 56.75676 0.00000 3 0.00000 8.10000 4 0.00000 19.00000 Objective Allowable Allowable Variable Coefficient Increase Decrease S 10.00000 2.51071 0.00000 D 10.15000 5.25790 0.00000 L

30、 12.85000 0.00000 2.19688 Allowable Allovable Constraint RHS Value Increase Decrease 1 630.00000 52.36364 91.60000 2 600.00000 Infinite 56.75676 3 708.00000 144.63158 128.00000 4 135.00000 16.15385 18.00000,3.3.3 修改的Par公司问题,换言之，当D利润的增量正好等于其递减成本时，能得到多重最优解。如果D的利润增加量超过1.15美元，它在最优解处就不再是0。 注意图3-6中，约束条件3和

31、4的对偶值分别为8.1和19，表明这两个约束条件是束缚性约束条件。因此，成型部每增加1小时工作时间就会使最优值增加8.10美元，检验与包装部每增加1小时工作时间就会使最优值增加19美元。由于切割与印染部有91.6小时的松弛时间，而缝合部门有32小时的松弛时间（见图3-6），管理者可能打算利用这两个部门的未使用劳动时间。Par公司可能会尝试对工人进行交叉训练，使得某部门未使用的生产能力可以转而分配到其他部门中去。下一章我们将考虑类似的情形。,3.4 传统灵敏度分析的不足,计算机软件提供的传统灵敏度分析还存在一些不足。在这一部分，我们讨论3类这样的限制：输入数据同时变化约束条件系数的变化非直觉对偶

32、值 我们对这3种情况分别给出了例子，同时讨论了当模型发生变化时怎样通过重解模型来高效地处理这些问题。,3.4.1 多系数同时变化,针对两个或两个以上系数同时变化时，目标函数将怎样变化的问题。 这里，再次分析修改后的Par公司问题。假设Par公司找到了一个新的供应商，并且可以以更低的价格购买那些高尔夫袋所需要的皮革。皮革是3种高尔夫袋重要的组成成分，只是每种袋所含的量不同。在使用这种新的皮革生产以后，每个标准袋的边际利润是10.3美元，每个高档袋的边际利润是11.4美元，每个轻型的边际利润是12.97美元。那么图3-5给出的方案仍是最优的吗？我们可用新的边际利润作为目标函数系数来简单重解这个模型

33、从而回答这个问题。,3.4.1 多系数同时变化,我们使用新的目标函数：max 10.3S+11.4D+12.97L，其他约束条件不变。图3-7给出了对这个问题的求解，新的最优利润是8718.13美元，3种包装袋都要生产。 假设我们没有用新的目标函数系数重解这个模型，我们还是使用原模型的方案，该方案如图3-5所示。因此我们的利润将是10.3280+11.40+12.97428=8435.16（美元）。通过新的信息和图3-7中修改过的计划重解这个模型，可看到，总利润增长了8718.13-8435.16=282.97（美元）。,图3-7 修改目标函数系数后的Par公司问题的求解,Optimal Ob

34、jective Value= 8718.12973 Variable Value Reduced Cost S 403.78378 0.00000 D 222.81081 0.00000 L 155.67568 0.00000 Constraint Slack/Surplus Dual Value 1 0.00000 3.08919 2 56.75676 0.00000 3 0.00000 6.56351 4 0.00000 15.74054 Objective Allowable Allowable Variable Coefficient Increase Decrease S 10.30

35、000 2.08000 2.28600 D 11.40000 4.26053 1.27000 L 12.97000 1.03909 1.82000 Allowable Allovable Constraint RHA value Increase Decrease 1 630.00000 52.36364 91.60000 2 600.00000 Infinite 56.75676 3 708.00000 144.63158 128.00000 4 135.00000 16.15385 18.00000,3.4.2 约束条件系数的变化,当采用某种新技术时，生产效率也会相应的有所提高。本小节针对

36、这种情况进行讨论。 假设采用一种新技术，此技术能够高效地生产标准袋，能将加工时间从当前的1小时减少到0.5小时，而不影响高级袋和轻便袋的加工时间。这种情况下的约束条件为： 1/2 S + 2/3 D + 1L708 使用新技术 我们改变系数，重新求解，如图3-8所示，标准袋的最优数量从280增加到了521.1，轻质袋的最优数量从428降低到了331.6，仍旧不生产高档袋。重要的是，通过使用新技术，最优利润从8299.80美元增加到9471.32美元，增加了1171.52美元。结合新技术的成本信息，管理者将会根据当前的利润增加估计算出偿还新技术成本的时间。,图3-8 应用生产标准袋新技术后的Pa

37、r公司问题的求解,Optimal Objective Value = 9471.31579 Variable Value Reduced Cost S 521.05263 0.00000 D 0.00000 -6.40789 L 331.57895 0.00000 Constraint Slack/Surplus Dual Value 1 0.00000 12.78947 2 7.89474 0.00000 3 115.89474 0.00000 4 0.00000 10.47368 Objective Allowable Allowable Variable Coefficient Incr

38、ease Decrease S 10.00000 1.24375 4.86000 D 9.00000 6.40789 Infinite L 12.85000 12.15000 1.42143 Allowable Allovable Constraint RHS Value Increase Decrease 1 630.00000 30.00000 198.00000 2 600.00000 Infinite 7.89474 3 708.00000 Infinite 115.89474 4 135.00000 2.50000 45.00000,3.4.3 非直觉对偶值,两边都有变量的约束条件往

39、往会使对偶值产生非直觉的解释。为说明这种情况，本小节将重新思考第3.3节中讨论过的修改后的Par公司问题。 问题：管理者在审核图3-5中的问题求解后发现，他们会放弃所有不生产高级袋的方案，并要求高级袋的产量至少要达到标准袋产量的30%。用变量表示如下： D0.3S将此新的约束条件设为修改的Par公司模型的约束条件5。重解这个模型，得到如图3-9所示的最优解。,图3-9 约束高档袋产量后的Par公司问题的求解,Optimal Objective Value = 8183.88000 Variable Value Reduced Cost S 336.00000 0.00000 D 100.800

40、00 0.00000 L 304.80000 0.00000Constraint Slack/Surplus Dual Value 1 50.16000 0.00000 2 43.20000 0.00000 3 0.00000 7.41000 4 0.00000 21.76000 5 0.00000 -1.38000 Objective Allowable Allowable Variable Coefficient Increase Decrease S 10.00000 2.07000 3.70500 D 9.00000 1.15000 12.35000 L 12.85000 5.2928

41、6 0.94091 Allowable Allovable Constraint RHS Value Increase Decrease 1 630.00000 Infinite 50.16000 2 600.00000 Infinite 43.20000 3 708.00000 57.00000 168.00000 4 135.00000 12.00000 31.75000 5 0.00000 101.67568 84.00000,3.4.3 非直觉对偶值,在此，解释一下约束条件5的对偶值。根据图3-9结果可知，其对偶值为-1.38，表明若右端值增加一个单位，将使利润减少1.38美元。 当约

42、束条件变为：D 0.3 S+1 ，则对-1.38的对偶值比较正确的解释如下：如果高级袋的产量由30%的标准袋产量提高一个单位，总利润会减少1.38美元。相反，若减少一个单位，总利润会增加1.38美元。 人们可能会对约束条件中变量的系数，如0.3更感兴趣 ，对此我们以5%为间隔，分别实验了比例从5%增长到100%的利润变化，这个比例改变对利润的影响如图3-10所示，最后的结果如表3-1所示。,图3-10 不同高档袋占标准袋产量的比例下的总利润,3.4.3 非直觉对偶值,从图3-10可以看到，当比例大于55%时曲线的斜率变得更陡了，这说明从55%开始利润下降的速度发生了变化。因此，可看到，比例小于

43、或等于55%时，损失的利润较小；大于55%时，将会有较大的利润损失。 另外，从表3-1中看出，当增加生产高档袋的比例时，生产轻便袋的数量会减少。,3.5 电子通信公司问题,在分销渠道的销售量、销售时间以及广告预算中应用线性规划的目的在于帮助管理者如何制定一个分销策略目的：销售利润最大化在接下来所介绍的应用中，我们将介绍如何利用线性规划建立模型以帮助管理者如何制定一个分销策略,3.5.1 建模,约束条件：公司的广告费用预算是5000美元；每个销售渠道的最大个人销售时间是1800小时；公司现阶段决定制造的产品数为600件；全国连锁零售店要求最少销售150件产品.定义如下决策变量：M-航海器材经销店

44、销售的产品数量；B-商用器材经销店销售的产品数量；R-全国连锁零售店销售的产品数量；D-直接邮购的产品数量。相关数据见表3-2,建立模型如下：Max 90M+84B+70R+60Ds.t. 10M+8B+9R+15D 5000 广告预算 2M+3B+3R 1800 可用销售时间 M+ B+ R+ D = 600 产量 R 150 全国连锁零售店合同约束 M, B, R, D 0,3.5.2 计算机求解及其解释,Optimal Objective Value = 48450.00000 Variable Value Reduced Cost M 25.00000 0.00000 B 425.00

45、000 0.00000 R 150.00000 0.00000 D 0.00000 - 45.00000Constraint Slack/Surplus Dual Value 1 0.00000 3.00000 2 25.00000 0.00000 3 0.00000 60.00000 4 0.00000 - 17.00000,图3-11 对电子通信公司问题的求解,对该公司的问题模型利用计算机求解，得出部分结果如图3-11所示：,根据图3-11可知，最优解为 M=25，B=425，R=150，D=0。计算机输出的松弛/剩余变量以及对偶值如图3-12。,图3-12 电子通信公司问题的目标系数和右

46、端值范围,Optimal Objective Value = 48450.00000 Variable Value Reduced Cost M 25.00000 0.00000 B 425.00000 0.00000 R 150.00000 0.00000 D 0.00000 - 45.00000Constraint Slack/Surplus Dual Value 1 0.00000 3.00000 2 25.00000 0.00000 3 0.00000 60.00000 4 0.00000 - 17.00000 Objective Allowable Allowable Variabl

47、e Coefficient Increase Decrease M 90.00000 Infinite 6.00000 B 84.00000 6.00000 34.00000 R 70.00000 17.00000 Infinite D 60.00000 45.00000 Infinite Allowable Allovable Constraint RHS Value Increase Decrease 1 5000.00000 850.00000 50.00000 2 1800.00000 Infinite 25.00000 3 600.00000 3.57143 85.00000 4 1

48、50.00000 50.00000 150.00000,我们通过对图3-12中，有关灵敏度方面的信息进行分析，得出目标函数系数的最优范围如下：,只要系数的变化在此范围内，当前的解或者策略仍然是最优的。注意到直接邮购渠道系数允许变化的范围，这个之前讨论的递减成本是一致的。,3.5.2 计算机求解及其解释,61,根据图3-12所示，关于约束条件右端值的灵敏度分析，它表明了约束条件右端值的变化范围，如下：,这里由计算机提供的灵敏度分析和最优化分析只适用于单一参数变化，其他参数保持不变的情况。如遇到参数同时改变的情况，最好的方法就是对其进行重解。,最后，我们给出电子通信公司最优策略下各种资源的分配情况

49、，见表3-3。,本章小结,针对灵敏度分析问题，本章详细研究了线性规划问题系数的变化对最优解所产生的影响，分别介绍了图解法分析目标函数系数和约束条件右端值的变化对最优解的影响。针对灵敏度分析的相关内容，本章以修改的Par公司问题为例，讨论了建模、灵敏度分析及其不足，并对模型进行了解释。同时，为加强对多于双变量的线性规划问题的掌握，又以电子通信公司为例，对其进行了研究分析。,63,专业术语,sensitivity analysis 灵敏度分析 研究线性规划问题中系数的变化对最优解的影响。range of optimality 最优范围 在最优解的值不变的前提条件下，目标函数系数的变化范围。obje

50、ctive function allowable increase/decrease 目标函数允许增加的值/减少的值 目标函数系数允许增加或减少的值是指不引起最优解中决策变量的值发生改变的系数增加或减少的量。这个范围可以用来计算最优解的范围。dual price 对偶值 约束条件右端值每增加一单位，目标函数值的变化量。reduced cost 递减成本 一个变量的递减成本等于这个变量的非负约束的对偶值。,64,专业术语,range of feasibility 可行域 使对偶值不变的约束条件右端值的变化范围。right-hand-side allowable increase/decrease