线性规划灵敏度分析.pptx

《线性规划灵敏度分析.pptx》由会员分享，可在线阅读，更多相关《线性规划灵敏度分析.pptx（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1线性规划灵敏度分析线性规划灵敏度分析3.1灵敏度分析简介 灵敏度分析对于决策者的重要性不言而喻，在真实世界里，周围的环境、条件是在不断变化的。原材料的成本在变，产品的需求在变，公司购买新设备、股票价格波动、员工流动等等这些都在不断发生。如果我们要用线性规划模型去解决实际问题，那模型中的系数就不可能是一成不变的。这些系数的变化会对模型的最优解产生什么样的影响呢？运用灵敏度分析，我们只需改变相应的系数就可以得到答案，而不需建立新的模型。第2页/共93页第1页/共93页回忆回忆Par公司的问题：公司的问题：第3页/共93页第2页/共93页 我们已经知道这个问题的最优解是标准袋生产我们已经知道

2、这个问题的最优解是标准袋生产540个，高级袋生产个，高级袋生产252个，这个最优解的前提是每个标准袋的利润是个，这个最优解的前提是每个标准袋的利润是10美元，每个高级袋的利润是美元，每个高级袋的利润是9美元。假设，我们得知由于价格的下降，标准袋的利润由美元。假设，我们得知由于价格的下降，标准袋的利润由10美元降到美元降到8.5美元。这时我们可以用灵敏度分析来确定标准袋生产美元。这时我们可以用灵敏度分析来确定标准袋生产540个，高级袋生产个，高级袋生产252个是否还是最优解。如果还是，则不必建立新的模型求解了。个是否还是最优解。如果还是，则不必建立新的模型求解了。第4页/共93页第3页/共93页

3、 灵敏度分析还可以用来分析模型中的系数哪个更能左右最优解。比如，管理层认为高级袋的利润灵敏度分析还可以用来分析模型中的系数哪个更能左右最优解。比如，管理层认为高级袋的利润9美元只是一个估计量。如果通过灵敏度分析得到，当高级袋的利润在美元只是一个估计量。如果通过灵敏度分析得到，当高级袋的利润在6.67美元与美元与14.29 美元之间变化时，模型的最优解都是美元之间变化时，模型的最优解都是540个标准袋和个标准袋和252个高级袋，那么管理层就必须思考每个高级袋获利个高级袋，那么管理层就必须思考每个高级袋获利9美元这个估计量的可信程度有多大了。管理层希望知道如果高级袋的利润下降，最优产量会怎样变化。

4、美元这个估计量的可信程度有多大了。管理层希望知道如果高级袋的利润下降，最优产量会怎样变化。第5页/共93页第4页/共93页 灵敏度分析的另一个用途是分析约束条件的右端值变化对最优解的影响。还是以灵敏度分析的另一个用途是分析约束条件的右端值变化对最优解的影响。还是以Par公司为例，在最优产量的情况下，切割与印染部和成型部的工作时间已经被占用了。如果现在公司增加了这两个部门的生产能力，那么最优解以及总利润的值会发生什么样的变化呢？灵敏度分析可以帮助确定每一个工时的边际价值，以及在利润下降之前部门工时的最大增加量。公司为例，在最优产量的情况下，切割与印染部和成型部的工作时间已经被占用了。如果现在公司

5、增加了这两个部门的生产能力，那么最优解以及总利润的值会发生什么样的变化呢？灵敏度分析可以帮助确定每一个工时的边际价值，以及在利润下降之前部门工时的最大增加量。第6页/共93页第5页/共93页3.2图解法灵敏度分析图解法灵敏度分析 对于双变量的线性规划问题，当目标函数的系数或约束条件的右端值变化时，用图解法可以对其进行灵敏度分析。对于双变量的线性规划问题，当目标函数的系数或约束条件的右端值变化时，用图解法可以对其进行灵敏度分析。3.2.1 目标函数系数目标函数系数 让我们思考一下目标函数的系数变化会对让我们思考一下目标函数的系数变化会对Par公司的最优产量产生什么样的影响。选择每个标准袋的利润是

6、公司的最优产量产生什么样的影响。选择每个标准袋的利润是10美元，每个高级袋的利润是美元，每个高级袋的利润是9美元。很明显，如果其中一种袋子的利润下降，公司就会削减其产量；如果利润上升，公司就会增加其产量。但问题是，究竟利润变化多少时，管理者才应该改变产量呢？美元。很明显，如果其中一种袋子的利润下降，公司就会削减其产量；如果利润上升，公司就会增加其产量。但问题是，究竟利润变化多少时，管理者才应该改变产量呢？第7页/共93页第6页/共93页 现在，模型的最优解是现在，模型的最优解是540个标准袋和个标准袋和252个高级袋。每个目标函数系数都有一个最优范围，即目标函数系数在什么范围内变化时，模型的最

7、优解保持不变。我们应该注意那些系数的最优范围比较小，或者系数刚好靠近最优范围边界的情况。在这种情况下，这些系数的微小变动就有可能使最优解发生改变。下面，我们用图解法来求解个高级袋。每个目标函数系数都有一个最优范围，即目标函数系数在什么范围内变化时，模型的最优解保持不变。我们应该注意那些系数的最优范围比较小，或者系数刚好靠近最优范围边界的情况。在这种情况下，这些系数的微小变动就有可能使最优解发生改变。下面，我们用图解法来求解Par公司的最有范围。公司的最有范围。第8页/共93页第7页/共93页200400600800200400600oSD可行域可行域10S+9D=7668图3-1直线直线A(7

8、/10)S+D=630直线直线BS+(2/3)D=708 第9页/共93页第8页/共93页在图在图3-1中，我们可以看到只要中，我们可以看到只要 直线直线B的斜率的斜率目标函数直线的斜率目标函数直线的斜率直线直线A的斜率的斜率 则最优解不变则最优解不变.容易计算直线容易计算直线A和直线和直线B的斜率，我们来看一看若想保持极点的斜率，我们来看一看若想保持极点仍然为最优解点，应满足的条件：仍然为最优解点，应满足的条件：（3-1）第10页/共93页第9页/共93页因此，我们得到目标函数的斜率为因此，我们得到目标函数的斜率为CSCD。把。把CSCD代入式（代入式（3-1），我们看到只要满足下列条件，极

9、点），我们看到只要满足下列条件，极点就仍然是最优解点：就仍然是最优解点：现在让我们考虑目标函数直线斜率的一般形式。用现在让我们考虑目标函数直线斜率的一般形式。用CS表示标准袋的利润，表示标准袋的利润，CD表示高级袋的利润，表示高级袋的利润，P表示目标函数值。使用这些标识，目标函数直线可以写成：表示目标函数值。使用这些标识，目标函数直线可以写成：PCSSCDD把上面方程写成斜截式，得到：把上面方程写成斜截式，得到：CDDCSSP以及以及第11页/共93页第10页/共93页从左边的不等式，我们得到从左边的不等式，我们得到（3-2）为了计算标准袋利润最优的范围，我们假设高级袋的利润为了计算标准袋利润

10、最优的范围，我们假设高级袋的利润CD9，代入式（，代入式（3-2），我们得到：），我们得到：因此因此第12页/共93页第11页/共93页综合标准袋利润综合标准袋利润CS的极限，标准袋利润最优范围为：的极限，标准袋利润最优范围为：6.3CS13.5从右边的不等式，我们得到从右边的不等式，我们得到因此，因此，第13页/共93页第12页/共93页 在最初在最初Par公司的问题中，标准袋的利润是公司的问题中，标准袋的利润是10美元。最优解是美元。最优解是540个标准袋和个标准袋和252个高级袋。标准袋利润个高级袋。标准袋利润CS的最优范围告诉的最优范围告诉Par公司的管理者：在其他系数不变的情况下，只

11、要标准袋的利润在公司的管理者：在其他系数不变的情况下，只要标准袋的利润在6.3美元与美元与13.5美元之间，美元之间，540个标准袋和个标准袋和252个高级袋总是最优产量。然而值得注意的是，即使产量不变，总的利润也可能由于每一个标准袋利润的变化而变化。个高级袋总是最优产量。然而值得注意的是，即使产量不变，总的利润也可能由于每一个标准袋利润的变化而变化。这些计算可以重复进行，假设标准袋的利润为常数这些计算可以重复进行，假设标准袋的利润为常数CS10。如此一来，高级袋利润的最优范围就能够被确定出来。验证可得，这个范围为。如此一来，高级袋利润的最优范围就能够被确定出来。验证可得，这个范围为6.67C

12、D14.29。第14页/共93页第13页/共93页 多系数同时改变多系数同时改变 目标函数系数的最优范围只能够应用于一次只有一个系数发生改变的情况，其他系数都假定保持初值而不发生变化。如果两个或两个以上目标函数的系数被同时改变，就有必要进一步判断最优解会不会也发生变化。然而对于解决只有两个变量的问题时，式（目标函数系数的最优范围只能够应用于一次只有一个系数发生改变的情况，其他系数都假定保持初值而不发生变化。如果两个或两个以上目标函数的系数被同时改变，就有必要进一步判断最优解会不会也发生变化。然而对于解决只有两个变量的问题时，式（3-2）给出了一个简单的方法，以判断两个目标函数系数同时发生改变时

13、，最优解是否也发生改变。简单地计算出在新的系数值下目标函数的斜率（）给出了一个简单的方法，以判断两个目标函数系数同时发生改变时，最优解是否也发生改变。简单地计算出在新的系数值下目标函数的斜率（-CS/CD）,如果这个比值大于等于目标函数斜率的下限，同时小于等于目标函数斜率的上限，那么系数值的变化就不会使最优解发生变化。如果这个比值大于等于目标函数斜率的下限，同时小于等于目标函数斜率的上限，那么系数值的变化就不会使最优解发生变化。第15页/共93页第14页/共93页 在式（在式（3-23-2）中，我们计算出只要满足下列条件，极点）中，我们计算出只要满足下列条件，极点仍然是最优点仍然是最优点 如果

14、如果C CS S升高到升高到1313美元，同时使美元，同时使CD降低到降低到8 8美元，新的目标函数斜率将变成美元，新的目标函数斜率将变成由于这个值要小于下限，因此当前的解S=540,D=252 不再是最优的。把CS=13，CD=8代入，可得出极点是新的最优解。第16页/共93页第15页/共93页 观察最优范围，我们得出结论，无论是观察最优范围，我们得出结论，无论是CS升高到升高到13美元还是使美元还是使CD降低到降低到8美元（当不是同时变化），都不会带来最优解的变化。但当美元（当不是同时变化），都不会带来最优解的变化。但当CS与与CD同时改变时，目标函数斜率的变化导致了最优解的变化。这个结论

15、强调了这样一个事实：仅仅是通过最优范围，只能用于判断在一次改变一个目标函数系数的情况下最优解的变化。同时改变时，目标函数斜率的变化导致了最优解的变化。这个结论强调了这样一个事实：仅仅是通过最优范围，只能用于判断在一次改变一个目标函数系数的情况下最优解的变化。第17页/共93页第16页/共93页3.2.2 约束条件右端值的变化约束条件右端值的变化 现在让我们来考虑约束条件右端值的变化对可行域带来的影响，及可能对最优解带来的变化。为了阐明敏感度分析的这方面内容，我们假设现在让我们来考虑约束条件右端值的变化对可行域带来的影响，及可能对最优解带来的变化。为了阐明敏感度分析的这方面内容，我们假设Par公

16、司的切割与印染部门增加了公司的切割与印染部门增加了10小时的生产时间，然后来考虑将会有什么发生。切割与印染约束条件的右端值由小时的生产时间，然后来考虑将会有什么发生。切割与印染约束条件的右端值由630变为变为640，约束条件可写作，约束条件可写作第18页/共93页第17页/共93页 又获得了又获得了1010个小时的切割与印染时间，我们个小时的切割与印染时间，我们可以扩展问题的可行域，如图可以扩展问题的可行域，如图3-3所示。可行域变大了，现在我们考虑是否有新的解会使目标函数值更大。运用图解法可以看出，极点所示。可行域变大了，现在我们考虑是否有新的解会使目标函数值更大。运用图解法可以看出，极点S

17、=527.5，D=270.5是最优解点。新的目标函数值为是最优解点。新的目标函数值为10527.5+9270.5=7711.75美元，比原来利润增加了美元，比原来利润增加了7711.75 7688.00=43.75美元。因此，利润的增加率为美元。因此，利润的增加率为43.75/10=4.375 美元美元/小时。小时。第19页/共93页第18页/共93页200400600800200400600oSD可行域可行域10S+9D=7711.75图3-3直线直线A(7/10)S+D=640S=527.50D=270.75 第20页/共93页第19页/共93页 约束条件右端值每增加一个单位引起的最优值的

18、改进量称为约束条件右端值每增加一个单位引起的最优值的改进量称为对偶价格对偶价格。在这个例子里，切割与印约束条件的对偶价格为。在这个例子里，切割与印约束条件的对偶价格为4.375 美元美元换言之，如果我们使得右边切割与印染约束条件增加换言之，如果我们使得右边切割与印染约束条件增加1小时，目标函数的值会相应小时，目标函数的值会相应的增加的增加4.375 美元。相反，如果我们使得右边切割与印染约束条件减少美元。相反，如果我们使得右边切割与印染约束条件减少1小时，目标函数的值会相应的减少小时，目标函数的值会相应的减少4.375 美元。对偶价格可以用来求出当某个约束条件右端值改变美元。对偶价格可以用来求

19、出当某个约束条件右端值改变1个单位，目标函数值将会有什么变化。个单位，目标函数值将会有什么变化。第21页/共93页第20页/共93页 在这里，我们要注意的是，对偶价格可能只适用于在右端值仅发生了很小的变动时的情况。随着所获得的资源越来越多，从而右端值越来越大，其他的约束条件也可能会约束和限制目标函数值的变化。拿在这里，我们要注意的是，对偶价格可能只适用于在右端值仅发生了很小的变动时的情况。随着所获得的资源越来越多，从而右端值越来越大，其他的约束条件也可能会约束和限制目标函数值的变化。拿Par公司的例子来说，我们最终会找到某一点，从那一点之后，再增加切割与印染的时间也不会使利润增加公司的例子来说

20、，我们最终会找到某一点，从那一点之后，再增加切割与印染的时间也不会使利润增加在切割与印染约束条件不再是束缚性约束条件是，这就有可能发生。在这一点，对偶价格等于在切割与印染约束条件不再是束缚性约束条件是，这就有可能发生。在这一点，对偶价格等于0。第22页/共93页第21页/共93页 下一节中，我们会讨论如何确定右端值变动的有效范围，在这个范围内，通过对偶价格可以精确地预测出目标函数值的变动。最后要指出的是，任何非束缚性约束条件的对偶价格都是下一节中，我们会讨论如何确定右端值变动的有效范围，在这个范围内，通过对偶价格可以精确地预测出目标函数值的变动。最后要指出的是，任何非束缚性约束条件的对偶价格都

21、是0，因为增加这样的约束条件的右端值，只会得到约束条件的剩余或松弛变量。，因为增加这样的约束条件的右端值，只会得到约束条件的剩余或松弛变量。第23页/共93页第22页/共93页 为了在解决最小化问题中正确解释对偶价格，假设我们刚刚解出了一个关于总成本最小化的问题，最优解的值为为了在解决最小化问题中正确解释对偶价格，假设我们刚刚解出了一个关于总成本最小化的问题，最优解的值为100美元。此外，假设某个约束条件的对偶价格是美元。此外，假设某个约束条件的对偶价格是-10美元。负的对偶价格告诉我们，如果使右端值增加美元。负的对偶价格告诉我们，如果使右端值增加1，目标函数值不会增加，反而会减少，目标函数值

22、不会增加，反而会减少10美元。在最小化问题中，目标函数结果变得更坏意味着总成本的增加。那样的话，如果右端值增加美元。在最小化问题中，目标函数结果变得更坏意味着总成本的增加。那样的话，如果右端值增加1个单位，目标函数变成个单位，目标函数变成110美元。反过来，右端值减少了美元。反过来，右端值减少了=1单位，总成本减少单位，总成本减少10美元。美元。第24页/共93页第23页/共93页3.3 灵敏度分析：计算机求解灵敏度分析：计算机求解 在第在第2.4节，我们说明了如何使用管理科学家软件来解决节，我们说明了如何使用管理科学家软件来解决Par公司的线性规划问题。回忆一下，为了使用管理科学家软件，我们

23、必须使用小数来代替分数。公司的线性规划问题。回忆一下，为了使用管理科学家软件，我们必须使用小数来代替分数。Par公司的问题小数形式的系数表示如下：公司的问题小数形式的系数表示如下：Max 10S+9D S.t.0.7S+1D630 切割与印染切割与印染 0.5S+0.833 33D600 缝合缝合 1.0S+0.666 67D708 成型成型 0.1S+0.25D135 检查与包装检查与包装 S,D0第25页/共93页第24页/共93页我们现在示范如何利用管理科学家软件来进行灵敏度分析，如图我们现在示范如何利用管理科学家软件来进行灵敏度分析，如图3-4所示。所示。Objective Funct

24、ion 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.00000 6.93753 4 17.00000 0.00000第26页/共93页第25页/共93页OBJECTIVE COEFFICIENT RANGES Varible Lower Limit Current Value Upper Limit-S 6.30

25、000 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 Limit 3 580.00146 708.00000 900.00000 4 117.00012 135.00000 No Upper Limit 第27页/共93页第26页/共93页3.3.1 计算机输出的解释计算机输出的解释第一

26、个例子第一个例子 在第在第2.4节，我们对图节，我们对图3-4顶部的输出结果进行了讨论。在取近似值之后，我们得到最优解是顶部的输出结果进行了讨论。在取近似值之后，我们得到最优解是S=540个标准袋和个标准袋和D=252个高级袋，目标函数最优解是个高级袋，目标函数最优解是7668 美元。如我们在第美元。如我们在第2.4节讨论的一样，递减成本（节讨论的一样，递减成本（Reduced Costs）一栏的信息告诉我们目标函数的每个系数应提高多少，目标函数的变量值才能是正数。对于）一栏的信息告诉我们目标函数的每个系数应提高多少，目标函数的变量值才能是正数。对于Par公司的例子，两个变量都已经是正值，所以

27、它们相应的递减成本就是公司的例子，两个变量都已经是正值，所以它们相应的递减成本就是0。在第。在第3.4节，我们将会介绍递减成本，这时决策变量在最优位置上并不是正值。节，我们将会介绍递减成本，这时决策变量在最优位置上并不是正值。第28页/共93页第27页/共93页 在最优解在最优解S,D以及递减成本信息下面，计算机输出了有关约束条件的信息。回忆以及递减成本信息下面，计算机输出了有关约束条件的信息。回忆Par公司的例子，其中有公司的例子，其中有4个小于或等于约束条件的，都是关于各个生产部门的生产时间。在松弛个小于或等于约束条件的，都是关于各个生产部门的生产时间。在松弛/剩余变量一栏中，可以看到每个

28、部门的松弛变量值。上述信息归总如下：剩余变量一栏中，可以看到每个部门的松弛变量值。上述信息归总如下：约束条件序号约束条件序号 约束条件名约束条件名 松弛松弛 1 切割与印染 0 2 缝合 120 3 成型 0 4 检查与包装 18 第29页/共93页第28页/共93页 从上述数据中，我们可以看到束缚性约束条件（切割与印染和成型）在目标函数的最优下，松弛为从上述数据中，我们可以看到束缚性约束条件（切割与印染和成型）在目标函数的最优下，松弛为0。缝合部门有。缝合部门有120小时的松弛或未使用的缝合能力：检查与包装部门有小时的松弛或未使用的缝合能力：检查与包装部门有18小时的松弛。小时的松弛。对偶价

29、格栏的信息是关于目标函数取得最优解时，这对偶价格栏的信息是关于目标函数取得最优解时，这4种资源的边际价值。在第种资源的边际价值。在第3.2节，我们对对偶价格进行了如下的定义：节，我们对对偶价格进行了如下的定义：对偶价格就是约束条件右端值每增加一个单位引起的，最优解的增加量。对偶价格就是约束条件右端值每增加一个单位引起的，最优解的增加量。第30页/共93页第29页/共93页 这里，约束条件这里，约束条件1（切割与印染）和约束条件（切割与印染）和约束条件3（成型）的非零对偶价格分别为（成型）的非零对偶价格分别为4.37496 和和6.93753。这告诉我们，每额外增加。这告诉我们，每额外增加1小时

30、的切割与印染时间会使最优解增加小时的切割与印染时间会使最优解增加4.37美元；每增加美元；每增加1小时成型时间将会使最优解增加小时成型时间将会使最优解增加6.94美元。因此，在其他系数保持不变的情况下，如果有效成型时间从美元。因此，在其他系数保持不变的情况下，如果有效成型时间从708小时增加到小时增加到709小时，小时，Par公司的利润会增加公司的利润会增加4.37，即有，即有7.668 美元增加到美元增加到7668+4.37=7672.37（美元）。（美元）。第31页/共93页第30页/共93页成型约束条件与之类似成型约束条件与之类似在其他系数保持不变的情况下，如果有效成型时间从在其他系数保

31、持不变的情况下，如果有效成型时间从708小时增加到小时增加到709小时，小时，Par公司的利润将增加到公司的利润将增加到7668+6.94=7674.94（美元）。由于缝合和检查与包装约束条件有松弛或未使用的工作能力，它们的零对偶价格表明，对这两个部门增加额外的工作时间也不会对目标函数的值产生影响。（美元）。由于缝合和检查与包装约束条件有松弛或未使用的工作能力，它们的零对偶价格表明，对这两个部门增加额外的工作时间也不会对目标函数的值产生影响。再次看看图再次看看图3-4的结果，我们看到管理科学家软件除了提供松弛的结果，我们看到管理科学家软件除了提供松弛/剩余变量和对偶价格的约束条件信息之外，还给

32、出了目标函数系数和约束条件右端值的变化范围。剩余变量和对偶价格的约束条件信息之外，还给出了目标函数系数和约束条件右端值的变化范围。第32页/共93页第31页/共93页 考虑在输出结果的标题考虑在输出结果的标题“目标系数范围目标系数范围”（OBJECTIVE COEFFICIENT RANGES）下面给出的信息，我们观察变量）下面给出的信息，我们观察变量S（此时的值是（此时的值是10）有如下的最优化范围：）有如下的最优化范围：6.30CS13.50因此，只要标准袋的利润在因此，只要标准袋的利润在6.30到到13.50 之间，生产之间，生产540个标准袋和个标准袋和252个高级袋都是最优解。仔细观

33、察会发现，这个最优化范围与第个高级袋都是最优解。仔细观察会发现，这个最优化范围与第3.2节用图解法得出的结论是一致的。节用图解法得出的结论是一致的。再观察一下高级袋的使目标函数值变化的信息，我们看到管理科学家软件计算出如下的最优化范围：再观察一下高级袋的使目标函数值变化的信息，我们看到管理科学家软件计算出如下的最优化范围：6.67CS14.29第33页/共93页第32页/共93页这个结果告诉我们，只要高级袋的利润在这个结果告诉我们，只要高级袋的利润在6.67到到14.29 之间，生产之间，生产540个标准袋和个标准袋和252个高级袋都是最优的。个高级袋都是最优的。计算机输出的结果的最后一部分右

34、端值范围（计算机输出的结果的最后一部分右端值范围（RIGHT HAND SIDE RANGES）给出了对对偶价格适合范围的限制条件。只要约束条件右端值处于系统所给出的上限和下限之间，对偶价格就会给出当右端值增加）给出了对对偶价格适合范围的限制条件。只要约束条件右端值处于系统所给出的上限和下限之间，对偶价格就会给出当右端值增加1时，最优解的增加量。举例来说，我们说每额外增加一小时工作量，目标函数会增加时，最优解的增加量。举例来说，我们说每额外增加一小时工作量，目标函数会增加4.37美元。没减少美元。没减少1小时工作量，当然也同样会使目标函数值减少小时工作量，当然也同样会使目标函数值减少4.37美

35、元。美元。第34页/共93页第33页/共93页在右端值范围栏的信息中可见，在右端值范围栏的信息中可见，4.37美元的对偶价格在右端值增加到美元的对偶价格在右端值增加到682.36316 或减少到或减少到495.59998 之间的范围内都是有效的。成型约束条件也是一样，在右端值增加到之间的范围内都是有效的。成型约束条件也是一样，在右端值增加到900小时或是减少到小时或是减少到580.00146 小时之间的范围内，对偶价格小时之间的范围内，对偶价格6.94美元都是有效地。美元都是有效地。如前所述，右端值范围给出了一个对偶价格的适用范围。如果右端值的变化超出了这个范围，就需要重解原问题并找出新的对偶

36、价格。我们把这个对偶价格适用的范围叫做可行域。如前所述，右端值范围给出了一个对偶价格的适用范围。如果右端值的变化超出了这个范围，就需要重解原问题并找出新的对偶价格。我们把这个对偶价格适用的范围叫做可行域。Par公司问题的可行域汇总如下：公司问题的可行域汇总如下：第35页/共93页第34页/共93页约束条件约束条件 最小右端值最小右端值 最大右端值最大右端值切割与印染切割与印染 495.6 682.4495.6 682.4缝合缝合 480.0 480.0 无上限无上限成型成型 580.0 900.0检查与包装检查与包装 117.0 无上限无上限 只要右端值在这些范围之内，系统分析结果中的那些对偶

37、价格就不会改变。右端值如果超出了这些范围，对偶价格的信息就会随之改变。只要右端值在这些范围之内，系统分析结果中的那些对偶价格就不会改变。右端值如果超出了这些范围，对偶价格的信息就会随之改变。第36页/共93页第35页/共93页3.3.2 多系数同时变化多系数同时变化 系统灵敏度分析的输出是基于单函数系数变化的。它假设所有其他的系数都保持不变。因此目标函数系数和约束条件右端值的变化范围只能适用于单个系数发生变化的情况。然而在很多情况下，我们可能更加关注当两个或两个以上系数同时变化时，目标函数将怎样变化。有些多系数同时变化的分析可能会用到系统灵敏度分析的输出是基于单函数系数变化的。它假设所有其他的

38、系数都保持不变。因此目标函数系数和约束条件右端值的变化范围只能适用于单个系数发生变化的情况。然而在很多情况下，我们可能更加关注当两个或两个以上系数同时变化时，目标函数将怎样变化。有些多系数同时变化的分析可能会用到100%法则（法则（100 percent rule）。我们下面分析）。我们下面分析100%法则是如何应用于多系数同时变化的情形中的。法则是如何应用于多系数同时变化的情形中的。第37页/共93页第36页/共93页 假设假设Par公司的会计部门指出，原先对标准袋和高级袋的利润的计算公司的会计部门指出，原先对标准袋和高级袋的利润的计算分别为分别为10美元和美元和9美元有错误，正确的利润是美

39、元有错误，正确的利润是11.50美元和美元和8.25美元。为了确定这样的变化是否会对最优解产生影响，我们先要定义两个术语美元。为了确定这样的变化是否会对最优解产生影响，我们先要定义两个术语“允许增加量允许增加量”（allowable increase）和）和“允许减少量允许减少量”（allowable decrease）。对于目标函数的系数，允许增加量是在不超过最优范围的情况下，系数可能增加的最大量；而允许减少量是在不低于最优范围下限的情况下，系数可能减少的最大量。）。对于目标函数的系数，允许增加量是在不超过最优范围的情况下，系数可能增加的最大量；而允许减少量是在不低于最优范围下限的情况下，系

40、数可能减少的最大量。第38页/共93页第37页/共93页 从图从图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

41、.75美元（从美元（从9到到8.25），），第39页/共93页第38页/共93页 允许增加量（允许增加量（42.86%）和允许减少量（）和允许减少量（32.14%）变化之和为）变化之和为75%。现在我们对将要应用于多个变量同时改变情况中的现在我们对将要应用于多个变量同时改变情况中的100%法则进行定义。法则进行定义。目标函数系数的目标函数系数的100%100%法则法则 对所有变化的目标函数系数，计算其占允许增加量和允许减少量的百分比之和。如果和没有达到对所有变化的目标函数系数，计算其占允许增加量和允许减少量的百分比之和。如果和没有达到100%，最优解就不会改变。，最优解就不会改变。第40页/共

42、93页第39页/共93页 在在Par公司的例子中，由于目标函数系数的两项改变的百分率之和为公司的例子中，由于目标函数系数的两项改变的百分率之和为75%，因此最优解不会改变。然而值得注意的是，尽管最优解仍然是，因此最优解不会改变。然而值得注意的是，尽管最优解仍然是S=539.99841，D=252.00113，但最优值可能会因为标准袋的利润增加到，但最优值可能会因为标准袋的利润增加到11.50美元，高级袋的利润减少到美元，高级袋的利润减少到8.25美元而变化。美元而变化。但是，但是，100%法则并没有规定如果各百分比之和达到法则并没有规定如果各百分比之和达到100%，最优解就一定会发生变化。有可

43、能个百分比之和超过，最优解就一定会发生变化。有可能个百分比之和超过100%，最优解也不变。如果，最优解也不变。如果100%法则的条件不能被满足，就必须对问题重新求解，以确定最优解是否发生变化。法则的条件不能被满足，就必须对问题重新求解，以确定最优解是否发生变化。第41页/共93页第40页/共93页切割与印染时间的允许增加量为切割与印染时间的允许增加量为682.36316-630.0=52.36316，成型时间的允许增加量为，成型时间的允许增加量为900.0-708.0=192.0（见图（见图3-4）。新增的）。新增的20小时切割与印染时间占了约束条件右端值允许增加量的小时切割与印染时间占了约束

44、条件右端值允许增加量的额外的额外的100小时成型占了总允许增加的小时成型占了总允许增加的第42页/共93页第41页/共93页二者百分比之和为二者百分比之和为38.19%+52.08%=90.27%，没有超过，没有超过100%，因此我们可以得到下面的结论：对偶价格在这里是适用的，并且目标函数值将会由此增加，因此我们可以得到下面的结论：对偶价格在这里是适用的，并且目标函数值将会由此增加204.37+1006.94=781.40。第43页/共93页第42页/共93页3.3.3 计算机输出的解释计算机输出的解释第二个例子第二个例子 我们重新考虑第我们重新考虑第2.5节中讨论的节中讨论的M&D化工公司的

45、问题，以此作为解释计算机输出的第二个例子。化工公司的问题，以此作为解释计算机输出的第二个例子。M&D公司的目标是为产品公司的目标是为产品A和产品和产品B找出一个成本最低的生产计划。下面是解决这个问题的线性规划模型，其中，找出一个成本最低的生产计划。下面是解决这个问题的线性规划模型，其中，A表示产品表示产品A的产量，的产量，B表示产品表示产品B的产量。的产量。Min 2A+3B s.t.1A 125 产品产品A的需求的需求 1A+1B350 总产量总产量 2A+1B600 生产时间生产时间 A,B0第44页/共93页第43页/共93页 利用管理科学家软件对其进行求解，结果展示在图利用管理科学家软

46、件对其进行求解，结果展示在图3-5中。计算机输出结果显示，最优解服从于中。计算机输出结果显示，最优解服从于800美元的目标函数。决策变量的值告诉我们，成本最低的生产计划是生产美元的目标函数。决策变量的值告诉我们，成本最低的生产计划是生产250加仑的产品加仑的产品A和和100加仑的产品加仑的产品B。Objective Function Value=800.000 Variable Value Reduced Costs -A 250.000 0.000 B 100.000 0.000第45页/共93页第44页/共93页 Constraint Slack/Surplus Dual Prices -

47、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 LimitRIGHT HAND SIDE RANGES Constraint Lower Limit Current Value Upper Limit -1 No Lower Limit 125.000 250.000 2 300.000 350.000

48、 475.000 3 475.000 600.000 700.000第46页/共93页第45页/共93页 松弛松弛/剩余变量栏显示，其中大于等于的约束条件意味着产品剩余变量栏显示，其中大于等于的约束条件意味着产品A的需求有的需求有125单位的剩余（见约束条件单位的剩余（见约束条件1）。这就是说，当处于最优解时，产品）。这就是说，当处于最优解时，产品A的产量比需求多的产量比需求多125加仑。对于总的生产要求（约束条件加仑。对于总的生产要求（约束条件2）和生产时间限制（约束条件）和生产时间限制（约束条件3），松弛），松弛/剩余变量值为剩余变量值为0，这意味着这两个约束条件是最优解的束缚性约束条件。

49、，这意味着这两个约束条件是最优解的束缚性约束条件。对偶价格栏再一次告诉我们，每增加一单位的约束条件右端值时最优解的改进。首先观察生产时间的限制（约束条件对偶价格栏再一次告诉我们，每增加一单位的约束条件右端值时最优解的改进。首先观察生产时间的限制（约束条件3），其对偶价格为），其对偶价格为1.00。如果我们增加生产时间，。如果我们增加生产时间，第47页/共93页第46页/共93页使之从使之从600小时变成小时变成601小时，目标函数的值就会改进小时，目标函数的值就会改进1美元。由于目标的使成本最小，这里的美元。由于目标的使成本最小，这里的“改进改进”意味着成本的降低。因此，如果生产时间变成意味着

50、成本的降低。因此，如果生产时间变成601小时，最优解的值将会减少到小时，最优解的值将会减少到8001=799美元。输出结果的右端值范围（美元。输出结果的右端值范围（right hand side range）部分给出了生产时间限制（约束条件）部分给出了生产时间限制（约束条件3）的上限。因此，在总的生产时间低于）的上限。因此，在总的生产时间低于700小时时，小时时，1美元的对偶价格都是有效的。美元的对偶价格都是有效的。再回到输出结果的对偶价格部分，考虑总产量约束（约束条件再回到输出结果的对偶价格部分，考虑总产量约束（约束条件2）的对偶价格。负的对偶价格表明，如果总产量约束的右端值增加一个单位，最