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

《数据模型与决策-第三章ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据模型与决策-第三章ppt课件.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章线性规划的灵敏度分析与最优解的线性规划的灵敏度分析与最优解的解释解释2灵敏度分析简介灵敏度分析简介图解法灵敏度分析图解法灵敏度分析灵敏度分析：计算机求解灵敏度分析：计算机求解传统灵敏度分析的不足传统灵敏度分析的不足电子通信公司问题电子通信公司问题3145主要内容主要内容 灵敏度分析（灵敏度分析（sensitivity analysis） 研究线性规划问题中研究线性规划问题中系数的变化对函数最优解的影响程度，有时也被称为系数的变化对函数最优解的影响程度，有时也被称为后优化后优化分析（分析（postoptimality analysis）。 运用灵敏度分析，我们可以回答以下问题：运用灵

2、敏度分析，我们可以回答以下问题： （1）如果目标函数的系数发生变化，对最优解会产生什）如果目标函数的系数发生变化，对最优解会产生什么影响？（么影响？（2）如果改变约束条件的右端值，对最优解会产）如果改变约束条件的右端值，对最优解会产生什么影响？生什么影响？ 3.1 灵敏度分析简介灵敏度分析简介 3.1 灵敏度分析简介灵敏度分析简介 分析目标函数系数的变化对最优解的影响；分析目标函数系数的变化对最优解的影响； 分析模型中的系数哪个更能左右最优解；分析模型中的系数哪个更能左右最优解； 分析约束条件右端值的变化对最优解的影响。分析约束条件右端值的变化对最优解的影响。灵敏度分析的用途灵敏度分析的用途

3、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 灵敏度分析简介灵敏度分析简介p 我们已经知道这个问题的最优解是标准袋生产我们已经知道这个问题的最优解是标准袋生产540个，

4、高个，高级袋生产级袋生产252个。这个最优解的前提是每个标准袋的利润是个。这个最优解的前提是每个标准袋的利润是10美元，每个高级袋的利润是美元，每个高级袋的利润是9美元。美元。p 假设，由于价格下降，标准袋的利润由假设，由于价格下降，标准袋的利润由10美元降到美元降到8.5美美元。这时我们可以用灵敏度分析来确定标准袋生产元。这时我们可以用灵敏度分析来确定标准袋生产540个，个，高级袋生产高级袋生产252个是否还是最优解。如果还是，则不必建立个是否还是最优解。如果还是，则不必建立新的模型求解了。新的模型求解了。 3.1 灵敏度分析简介灵敏度分析简介 比如，管理层认为高级袋的利润比如，管理层认为高

5、级袋的利润9美元只是一个估计量。美元只是一个估计量。 如果通过灵敏度分析得到，高级袋的利润在如果通过灵敏度分析得到，高级袋的利润在6.67-14.29美美元之间变化时，最优解不变，那么管理层对元之间变化时，最优解不变，那么管理层对9美元这个估计美元这个估计量和最优产量比较满意。但是，如果灵敏度分析告诉我们，量和最优产量比较满意。但是，如果灵敏度分析告诉我们，只有当高级袋的利润在只有当高级袋的利润在8.9-9.25美元之间变化时，最优解才美元之间变化时，最优解才不变。那么管理层就必须思考每个高级袋获利不变。那么管理层就必须思考每个高级袋获利9美元这个估美元这个估计量的可信程度有多大了。管理层希望

6、知道如果高级袋的利计量的可信程度有多大了。管理层希望知道如果高级袋的利润下降，最优产量会怎样变化。润下降，最优产量会怎样变化。 分析模型中的系数哪个更能左右最优解分析模型中的系数哪个更能左右最优解 3.1 3.1 灵敏度分析简介灵敏度分析简介以以Par公司问题为例：公司问题为例： 在最优产量的情况下，切割与印染部和成型部的工作在最优产量的情况下，切割与印染部和成型部的工作时间已经全被占用了。如果现在公司增加了这两个部门的时间已经全被占用了。如果现在公司增加了这两个部门的生产能力，那么最优解以及总利润的值会发生什么样的变生产能力，那么最优解以及总利润的值会发生什么样的变化呢？灵敏度分析可以帮助确

7、定每一个工时的边际价值，化呢？灵敏度分析可以帮助确定每一个工时的边际价值，以及在利润下降之前部门工时的最大增加量。以及在利润下降之前部门工时的最大增加量。 分析约束条件右端值的变化对最优解的影响分析约束条件右端值的变化对最优解的影响 3.2 图解法灵敏度分析图解法灵敏度分析目标函数的系数变化会对目标函数的系数变化会对Par公司的最优产量产生什么样公司的最优产量产生什么样的影响？选择每个标准袋的利润是的影响？选择每个标准袋的利润是10美元，每个高级袋美元，每个高级袋的利润是的利润是9美元。很明显，如果其中一种袋子的利润下降，美元。很明显，如果其中一种袋子的利润下降，公司就会消减其产量；如果利润上

8、升，公司就会增加其公司就会消减其产量；如果利润上升，公司就会增加其产量。但问题是，究竟利润变化多少时，管理者才应该产量。但问题是，究竟利润变化多少时，管理者才应该改变产量呢？改变产量呢？图解法灵敏度分析仅适用于双变量的线性规划问题。图解法灵敏度分析仅适用于双变量的线性规划问题。3.2.1 目标函数系数目标函数系数 3.2.1 目标函数系数目标函数系数 每个目标函数系数都有一个每个目标函数系数都有一个最优范围（最优范围（range of optimality），即目标函数系数在什么范围内变化时，模型，即目标函数系数在什么范围内变化时，模型的最优解保持不变。我们应该注意那些系数的最优范围比的最优解

9、保持不变。我们应该注意那些系数的最优范围比较小，或者系数刚好靠近最优范围边界的情况。在这种情较小，或者系数刚好靠近最优范围边界的情况。在这种情况下，这些系数的微小变动就有可能使最优解发生改变。况下，这些系数的微小变动就有可能使最优解发生改变。 3.2.1 目标函数系数目标函数系数如图如图3-1所示：只所示：只要目标函数线的要目标函数线的斜率处于直线斜率处于直线A（和切割与印染（和切割与印染约束线重合）的约束线重合）的斜 率 与 直 线斜 率 与 直 线 B（与成型约束线（与成型约束线重合）的斜率之重合）的斜率之间 ， 极 点 间 ， 极 点 （S=540，D=252）就是最优解点。就是最优解点

10、。 图图3-1 图解法求图解法求Par公司问题公司问题 3.2.1 目标函数系数目标函数系数 改变目标函数中标准袋产量改变目标函数中标准袋产量S和高级袋产量和高级袋产量D的系数，将的系数，将引起目标函数斜率的变化。这种变化导致目标函数线饶着极引起目标函数斜率的变化。这种变化导致目标函数线饶着极点旋转。然而，只要目标函数线仍然在阴影区域内，极点点旋转。然而，只要目标函数线仍然在阴影区域内，极点就仍然是最优解点。就仍然是最优解点。 逆时针选择目标函数线，使其斜率变成一个绝对值更小逆时针选择目标函数线，使其斜率变成一个绝对值更小的负数，从而斜率变大了。当目标函数线逆时针旋转到足够的负数，从而斜率变大

11、了。当目标函数线逆时针旋转到足够的角度，与直线的角度，与直线A重合，我们就获得了多重最优解重合，我们就获得了多重最优解-在极点在极点和极点之间的点都是最优点。任何对目标函数线的进一和极点之间的点都是最优点。任何对目标函数线的进一步逆时针转动，都会使得极点不再是最优解点。因此，直步逆时针转动，都会使得极点不再是最优解点。因此，直线线A的斜率就是目标函数线的上限。的斜率就是目标函数线的上限。 3.2.1 目标函数系数目标函数系数 顺时针转动目标函数线，使其斜率变成一个绝对值更顺时针转动目标函数线，使其斜率变成一个绝对值更大的负数，从而斜率变小了。当目标函数线顺时针旋转到大的负数，从而斜率变小了。当

12、目标函数线顺时针旋转到足够的角度，直至与直线足够的角度，直至与直线B重合，我们就会获得了多重最重合，我们就会获得了多重最优解优解-在极点与极点之间的点都是最优点。任何对在极点与极点之间的点都是最优点。任何对目标函数线的进一步顺时针转动，也都会使得极点不再目标函数线的进一步顺时针转动，也都会使得极点不再是最优解点。因此，直线是最优解点。因此，直线B的斜率就是目标函数线斜率的的斜率就是目标函数线斜率的下限。下限。 3.2.1 目标函数系数目标函数系数 因此，极点总是最优解点，只要因此，极点总是最优解点，只要 直线直线B 的斜率的斜率目标函数线的斜率目标函数线的斜率直线直线A的斜率的斜率 即，即，

13、-3/2目标函数的斜率目标函数的斜率-7/10 (3-1) 现在让我们考虑目标函数线斜率的一般形式。用现在让我们考虑目标函数线斜率的一般形式。用 CS 表示标准袋的利润，表示标准袋的利润，CD 表示高级袋的利润，表示高级袋的利润，P表示目标表示目标函数值。使用这些符号，目标函数直线可以写成：函数值。使用这些符号，目标函数直线可以写成： P = CS S + CD D 3.2.1 目标函数系数目标函数系数把上面方程写成斜截式，得到：把上面方程写成斜截式，得到： CD D = - CS S + P以及以及 D = S +因此，我们得到目标函数的斜率为因此，我们得到目标函数的斜率为 。把。把 代代入

14、式（入式（3-1），我们看到只要满足下列条件，极点就仍然），我们看到只要满足下列条件，极点就仍然是最优解点：是最优解点： -3/2 -7/10 (3-2)SDCCDPCSDC CSDC CSDCC 3.2.1 目标函数系数目标函数系数 标准袋利润最优的范围标准袋利润最优的范围 我们假设高级袋的利润我们假设高级袋的利润CD=9，代入式（，代入式（3-2），我们得到：），我们得到： -3/2 -7/10 解得，解得， 6.3 CS 13.5 即标准袋利润最优范围为：即标准袋利润最优范围为： 6.3 CS 13.5 高档高档袋利润最优的范围袋利润最优的范围 同上求解过程，假设标准袋的利润为常数同上求

15、解过程，假设标准袋的利润为常数CS=10，可得高档袋，可得高档袋利润最优范围为：利润最优范围为： 6.67 CD 14.299SC 3.2.1 目标函数系数目标函数系数 当目标函数绕最优当目标函数绕最优点旋转，使之与坐标点旋转，使之与坐标轴垂直时，像式（轴垂直时，像式（3-2）中出现的那种斜率的中出现的那种斜率的上限或下限就不再存上限或下限就不再存在了。在了。 为了说明这种特殊为了说明这种特殊的情况，我们设的情况，我们设Par公公司的目标函数为司的目标函数为 18 CS + 9 CD ；这样，在图；这样，在图3-2中，极点中，极点就是最优就是最优解点。解点。图图3-2 图解法求图解法求Par公

16、司问题公司问题 目标函数为目标函数为18S+9D 3.2.1 目标函数系数目标函数系数 绕着极点逆时针旋转目标函数，当目标函数与直线绕着极点逆时针旋转目标函数，当目标函数与直线B重重合时，就得到了斜率的上限。我们前面已经计算出，直线合时，就得到了斜率的上限。我们前面已经计算出，直线B 的斜率为的斜率为- 3/2，所以目标函数斜率的上限就一定是，所以目标函数斜率的上限就一定是-3/2。 然而，顺时针旋旋转目标函数直至垂直于坐标轴时，其然而，顺时针旋旋转目标函数直至垂直于坐标轴时，其斜率接近负无穷大。此时，目标函数的斜率没有下限，只有斜率接近负无穷大。此时，目标函数的斜率没有下限，只有上限，即上限

17、，即 SDCC-3/2-3/2 3.2.1 目标函数系数目标函数系数按照前面假定的按照前面假定的CD 的值，仍为常数的值，仍为常数9，我们得到：，我们得到：9SC-3/2或或 3/29SC解出解出CS ,得：得： CS 27/2=13.5 观察图观察图3-2，我们注意到，只要，我们注意到，只要CS 的值大于等于的值大于等于13.5，极点，极点仍然是最优解点。因此我们得到以下极点仍然是最优解点。因此我们得到以下极点为最优解点的为最优解点的CS的范的范围：围：13.5 CS 3.2.1 目标函数系数目标函数系数 目标函数系数的最优范围只能够应用于一次只有一个系数目标函数系数的最优范围只能够应用于一

18、次只有一个系数发生改变的情况。如果两个或两个以上目标函数的系数同时发生改变的情况。如果两个或两个以上目标函数的系数同时改变，就有必要进一步判断最优解会不会也发生变化。改变，就有必要进一步判断最优解会不会也发生变化。 对于解决只有两个变量的问题，式（对于解决只有两个变量的问题，式（3-2）给出了一个简）给出了一个简单的方法。简单地计算出在新的系数值下目标函数的斜率（单的方法。简单地计算出在新的系数值下目标函数的斜率（- CS/CD）,如果这个新目标函数的斜率在原目标函数斜率的上下如果这个新目标函数的斜率在原目标函数斜率的上下限范围内，那么系数值的变化不会使最优解发生变化。限范围内，那么系数值的变

19、化不会使最优解发生变化。 多系数同时改变多系数同时改变 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降低到降

20、低到8美元（不是同时），都不会使最美元（不是同时），都不会使最优解（优解（S=540，D=252）发生变化。）发生变化。 但是我们无法从上述最优范围中推断出如果两个系数同但是我们无法从上述最优范围中推断出如果两个系数同时发生改变，最优解是否会发生改变。时发生改变，最优解是否会发生改变。 3.2.1 目标函数系数目标函数系数 在式（在式（3-2）中，我们计算出只要满足下列条件，极点）中，我们计算出只要满足下列条件，极点仍然是最优点：仍然是最优点： -3/2 -7/10 如果如果CS 升高到升高到13美元，同时使美元，同时使CD降低到降低到8美元，新的目美元，新的目标函数斜率将变成：标函数斜率将变

21、成： = -13/8 = -1.625 由于这个值要小于下限由于这个值要小于下限-3/2，因此当前的解，因此当前的解S=540，D=252不再是最优的。把不再是最优的。把 CS =13，CD =8代入，可以得出极点是新的代入，可以得出极点是新的最优解。最优解。 SDCC SDCC 3.2.2 约束条件右端值的变化约束条件右端值的变化 我们仍以我们仍以Par公司问题为例来考虑约束条件右端值的变化公司问题为例来考虑约束条件右端值的变化对可行域及最优解带来的影响。对可行域及最优解带来的影响。 我们假设我们假设Par公司的切割与印染部增加了公司的切割与印染部增加了10个小时的生产个小时的生产时间，然后

22、考虑将会发生什么。时间，然后考虑将会发生什么。 新切割与印染约束条件可写作：新切割与印染约束条件可写作： 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 3-3 切割与印染约束条件的右端值增加切割与印染约束条件的右端值增加1010小时的影响小时的影响 3.2.2 约束条件右端值

23、的变化约束条件右端值的变化 约束条件右端值每增加一个单位引起的最优值变化量称为约束条件右端值每增加一个单位引起的最优值变化量称为对偶值（对偶值（dual value）。在新在新Par公司问题里，利润增加率公司问题里，利润增加率4.375即为即为切割与印染约切割与印染约束条件的对偶值束条件的对偶值。换言之，切割与印染约束条件右端值增加换言之，切割与印染约束条件右端值增加/减少减少1小时，目标函数的值会增加小时，目标函数的值会增加/减少减少4.375美元。美元。对偶值可以用来求出当某个约束条件右端值改变一个单位对偶值可以用来求出当某个约束条件右端值改变一个单位时，目标函数值将会有什么变化。时，目标

24、函数值将会有什么变化。 3.2.2 约束条件右端值的变化约束条件右端值的变化注意：注意： 对偶值可能只适用于右端值仅发生了很小变动时的情况。对偶值可能只适用于右端值仅发生了很小变动时的情况。 右端值大到一定程度时，其约束可能不再是束缚性约束，其右端值大到一定程度时，其约束可能不再是束缚性约束，其他的约束条件也可能会约束和限制目标函数值的变化。他的约束条件也可能会约束和限制目标函数值的变化。例：例：ParPar公司问题，我们最终会找到某一点，从那一点之后，公司问题，我们最终会找到某一点，从那一点之后，再增加切割与印染的时间也不会使利润增加。在这一点，对偶再增加切割与印染的时间也不会使利润增加。在

25、这一点，对偶值等于值等于0 0。 3.3 灵敏度分析：计算机求解灵敏度分析：计算机求解仍以仍以Par公司问题为例：公司问题为例：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我们现在示范如何通过考虑我们现在示范如何通过考虑Par公司的线性规划求解来理解公司的线性规划求解来理解灵敏度分析，如图灵敏度分析，如图3-4所示。所示。Optimal Objective V

26、alue = 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 4 18.00000 0.00000 Objective Allowable Allowable Variable Coefficient Increase Decrease S 10.00000 3.50000 3.70000 D 9.0000

27、0 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.00000 Infinite 18.00000图图3-4 Par 公司问题的求解公司问题的求解 3.3.1 计算机输出结果的解释计算机输出结果的解释 最优解信息最优解信息Optimal Objective Value=7668.0000 Va

28、riable 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 约束约束条件条件序号序号约束约束条件条件名名松松弛弛约束约束条件条件序号序号约束约束条件条件名名松松弛弛1切割切割与印与印染染03成型成型02缝合缝合1204检查检查与包与包装装18松弛松弛/剩余信息剩余信息 3.3.1 计算机输出结果的解

29、释计算机输出结果的解释 对偶值信息（资源边际价值）对偶值信息（资源边际价值） Constraint 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-43-4中的对偶值可做如下解释：中的对偶值可做如下解释： 3.3.1 计算机输

30、出结果的解释计算机输出结果的解释 约束条件约束条件1（切割与印染）和约束条件（切割与印染）和约束条件3（成型时间）的非（成型时间）的非零对偶值分别为零对偶值分别为4.375和和6.9375。这告诉我们，。这告诉我们，每额外增加每额外增加1小时小时的切割与印染时间会使最优值增加的切割与印染时间会使最优值增加4.37美元；美元；每增加每增加1小时的成小时的成型时间将会使最优值增加型时间将会使最优值增加6.94美元。因此，在其他系数不变的情美元。因此，在其他系数不变的情况下，如果切割与印染时间从况下，如果切割与印染时间从630小时增加到小时增加到631小时，小时，Par公司公司的的 利 润 会 增

31、加利 润 会 增 加 4 . 3 7 美 元 ， 即 由美 元 ， 即 由 7 6 6 8 美 元 增 加 到美 元 增 加 到7668+4.37=7672.37（美元）。（美元）。在其他系数保持不变的情况下，在其他系数保持不变的情况下，如果有效成型时间从如果有效成型时间从708小时增加到小时增加到709小时，小时，Par公司的利润将公司的利润将会增加到会增加到7668+6.94=7674.94（美元）。（美元）。由于缝合和检查时间与由于缝合和检查时间与包装约束条件有松弛或未使用的工作能力，它们的零对偶值表包装约束条件有松弛或未使用的工作能力，它们的零对偶值表明，对这两个部门增加额外工作时间也

32、不会对目标函数的值产明，对这两个部门增加额外工作时间也不会对目标函数的值产生影响。生影响。 3.3.1 计算机输出结果的解释计算机输出结果的解释 递减成本（递减成本（reduced cost）：）：一个变量的一个变量的递减成本等于这个递减成本等于这个变量非负约束的对偶值变量非负约束的对偶值。Optimal Objective Value= 7668.00000 Variable Value Reduced Cost S 540.00000 0.00000 D 252.00000 0.00000图图3-4中显示，变量中显示，变量S和和D的递减成本均为的递减成本均为0。 非负约束是非负约束是S0，

33、S的当前值是的当前值是540，因此改变非负约束使，因此改变非负约束使S1 对最优值没有影响。因为增加一个单位的右端值对最优目对最优值没有影响。因为增加一个单位的右端值对最优目标函数值没有影响，因此这个非负约束的对偶值（即递减成本）标函数值没有影响，因此这个非负约束的对偶值（即递减成本）是是0。同样这也可以应用于变量。同样这也可以应用于变量D。通常来说，。通常来说，如果一个变量如果一个变量在最优解中有一个非零值，那么它的递减成本将是在最优解中有一个非零值，那么它的递减成本将是0. 3.3.1 计算机输出结果的解释计算机输出结果的解释l 变量变量S：变量：变量S当前的利润系数是当前的利润系数是10

34、，允许增加的值是，允许增加的值是3.5，允许减小的值是允许减小的值是3.7。因此，只要标准袋的利润贡献在。因此，只要标准袋的利润贡献在10-3.7=6.3（美元），（美元），10+3.5=13.5（美元）之间时，最优解不变。（美元）之间时，最优解不变。l 变量变量D：同理，由图：同理，由图3-4可得变量可得变量D的目标函数系数在的目标函数系数在6.6714.29之间变动时，最优解不变。之间变动时，最优解不变。 目标函数系数范围目标函数系数范围 Objective Allowable Allowable Variable Coefficient Increase Decrease S 10.00

35、000 3.50000 3.70000 D 9.00000 5.28571 2.33333 3.3.1 计算机输出结果的解释计算机输出结果的解释在范围栏的信息中可见：在范围栏的信息中可见：l约束条件约束条件1的右端值为的右端值为630，允许增加的值为，允许增加的值为52.36364，允，允许减少的值为许减少的值为134.4，因此切割与印染约束右端值在，因此切割与印染约束右端值在495.6682.4范围内变化时，范围内变化时，对偶值都是有效的。对偶值都是有效的。l 同理，成型约束条件的右端值在同理，成型约束条件的右端值在580900范围内变化时，范围内变化时，对偶值都是有效的。对偶值都是有效的。

36、 约束条件右端值的变化范围约束条件右端值的变化范围 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 计算机输出结果的解释计算机输出结果的解释可行域（可行域（range of feasibility）：对偶值适用的范围称做可行：对偶值适用的范围称做可行 域。域。Par公司

37、问题的可行域汇总如下：公司问题的可行域汇总如下：约束条件约束条件最小右最小右端值端值最大右最大右端值端值约束条件约束条件最小右最小右端值端值最大右最大右端值端值切割与印染切割与印染495.6682.4成型成型580.0900.0缝合缝合480.0无上限无上限检查与包装检查与包装117.0无上限无上限只要右端值在这些范围内，系统分析结果中的那些对偶值就不只要右端值在这些范围内，系统分析结果中的那些对偶值就不会改变。右端值如果超出了这些范围，对偶值的信息就会随之会改变。右端值如果超出了这些范围，对偶值的信息就会随之改变改变. 3.3.2 深入理解对偶值深入理解对偶值 对偶值是右端值每增加一个单位时

38、最优值的变化。然而这种对偶值是右端值每增加一个单位时最优值的变化。然而这种解释也并非总是正确的。要理解这个问题，我们先要理解解释也并非总是正确的。要理解这个问题，我们先要理解沉没成沉没成本（本（sunk cost）和和相关成本（相关成本（relevant cost）的区别。的区别。沉没成本沉没成本不不会受决策影响，无论决策变量为何值，这种成本都会发生。会受决策影响，无论决策变量为何值，这种成本都会发生。相关相关成本成本则取决于决策的制定，这种成本随决策变量值的变化而变化。则取决于决策的制定，这种成本随决策变量值的变化而变化。 让我们重新考虑让我们重新考虑Par公司的例子。切割与印染的总时间是公

39、司的例子。切割与印染的总时间是630小时。如果说无论生产标准袋或者高级袋，都是按照时间来支付小时。如果说无论生产标准袋或者高级袋，都是按照时间来支付工资的，那么时间成本就是一种沉没成本。所有的相关成本都要工资的，那么时间成本就是一种沉没成本。所有的相关成本都要在线性规划的目标函数中有所反映。假设在线性规划的目标函数中有所反映。假设Par公司必须按照工作时公司必须按照工作时间来发放工人工资，不管他们的工作时间是否被有效地利用。因间来发放工人工资，不管他们的工作时间是否被有效地利用。因此，此，Par公司劳动时间资源的成本就属于沉没成本，而不在目标函公司劳动时间资源的成本就属于沉没成本，而不在目标函

40、数中反映出来。数中反映出来。 3.3.3 修改的修改的Par公司问题公司问题 图解法只能应用于解决双决策变量的线性规划问题。在图解法只能应用于解决双决策变量的线性规划问题。在现实生活中，用线性规划解决的问题经常包含大量的变量和约现实生活中，用线性规划解决的问题经常包含大量的变量和约束条件。在本节中，我们讨论在两个线性规划问题中，三决策束条件。在本节中，我们讨论在两个线性规划问题中，三决策变量问题的方程和计算机求解。在讨论过程中，我们会解释计变量问题的方程和计算机求解。在讨论过程中，我们会解释计算机输出结果中递减成本部门的含义。算机输出结果中递减成本部门的含义。 Par公司原来问题的模型如下：公

41、司原来问题的模型如下： 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小时的切割与印染时间，小

42、时的切割与印染时间，1小时的缝合时小时的缝合时间，间，1小时的成型时间和小时的成型时间和0.25小时的检查与包装时间。管理者认小时的检查与包装时间。管理者认为在当前销售期内每个轻便袋可以获利为在当前销售期内每个轻便袋可以获利12.85美元。美元。 我们对原模型进行修改，修改后的模型需要加入新的决策我们对原模型进行修改，修改后的模型需要加入新的决策变量的影响。令变量的影响。令L为轻便袋的产量，将其加入目标函数及为轻便袋的产量，将其加入目标函数及4个约个约束条件，可得到如下模型：图束条件，可得到如下模型：图3-5给出了修改后模型的求解结果。给出了修改后模型的求解结果。max 10 S + 9 D

43、+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 Reduced Cost S 280.00000 0.00000 D 0.00000 -1.15000 L 428.00000 0.00000Const

44、raint 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 12.85000 12.15000 0.94091 Allowable Allovable Constraint RHS value In

45、crease 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的递减的递减成

46、本都为成本都为0。变量。变量D的递减成本为的递减成本为 -1.15，表明如果高档袋的产量，表明如果高档袋的产量从从0增加到增加到1，那么最优目标函数值将减少，那么最优目标函数值将减少1.15。另外一种解释。另外一种解释是，如果我们将高档袋的成本降低是，如果我们将高档袋的成本降低1.15（也就是将边际收益增（也就是将边际收益增加加1.5），那么将会出现一个生产非零个高档袋的最优方案。），那么将会出现一个生产非零个高档袋的最优方案。 假设使假设使D的系数正好增加的系数正好增加1.15美元，这样新的值就是美元，这样新的值就是9+1.15=10.15（美元），然后重解原问题。新的求解如图（美元），然后

47、重解原问题。新的求解如图3-6所所示，注意到尽管示，注意到尽管D的值已经是正数，最优解的值仍然没有变。的值已经是正数，最优解的值仍然没有变。图图3-6 Par公司问题中公司问题中系数系数D的值增加的值增加 1.15美元后的求解美元后的求解Optimal Objective Value= 8299.80000 Variable Value Reduced 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

48、.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 12.85000 0.00000 2.19688 Allowable Allovable Constraint RHS Value Increase Decrease 1 630.00000 52.36364 91.60000 2 600.000

49、00 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和和4的对偶值分别为的对偶值分别为8.1和和19，表明，表明这两个约束条件是束缚性约束条件。因此，成型部每增加这

50、两个约束条件是束缚性约束条件。因此，成型部每增加1小时小时工作时间就会使最优值增加工作时间就会使最优值增加8.10美元，检验与包装部每增加美元，检验与包装部每增加1小小时工作时间就会使最优值增加时工作时间就会使最优值增加19美元。由于切割与印染部有美元。由于切割与印染部有91.6小时的松弛时间，而缝合部门有小时的松弛时间，而缝合部门有32小时的松弛时间（见图小时的松弛时间（见图3-6），管理者可能打算利用这两个部门的未使用劳动时间。），管理者可能打算利用这两个部门的未使用劳动时间。Par公司可能会尝试对工人进行交叉训练，使得某部门未使用的生公司可能会尝试对工人进行交叉训练，使得某部门未使用的生