灵敏度分析(运筹学)

《灵敏度分析(运筹学)》由会员分享，可在线阅读，更多相关《灵敏度分析(运筹学)（60页珍藏版）》请在金锄头文库上搜索。

1、灵敏度分析灵敏度分析 2.5.1 单纯形法的矩阵描述 2.5.2 图解法灵敏度分析 2.5.3 单纯形法灵敏度分析 第五节第五节灵敏度分析灵敏度分析 在单纯形法的迭代中，我们注意到，迭代过程中主 要应用了矩阵的行变换，如在某一行上乘以一个不 等于0的乘数k,或在某一行上乘以常数k加到另一行 上。这种迭代过程相当于左乘一个相应的初等阵， 而初等阵及其乘积为可逆矩阵。 因此，约束方程系数矩阵的迭代实际上相当于左乘 相应的可逆矩阵。 2.5.1 2.5.1 单纯形法的矩阵描述单纯形法的矩阵描述 Cj x1x2x3x4 XBbCB 1 1 1 0 1 2 0 1 2 3 0 0 3 4 x3 x4 0

2、 0 cj - zj 2300 1/2 0 1 -1/2 1/2 1 0 1/2 x3 x2 1 2 cj - zj 1/2 0 0 -3/2 0 3 1 0 2 -1 0 1 -1 1 x1 x2 2 1 cj - zj 0 0 -1 -1 2 3 2.5.1 2.5.1 单纯形法的矩阵描述单纯形法的矩阵描述 1. 约束方程系数矩阵的变化 约束方程系数矩阵 ，进行初等行变换， 相当于左乘一个相应的初等阵。 即 ，在A中所包含的矩阵B，左乘 后， 则得到 。 2. 约束方程右端项的变化 3. 目标函数系数的变化 由 ，得 ，两边左乘基变量的目 标函数系数 ，得到 与 得到 2.5.1 2.5.

3、1 单纯形法的矩阵描述单纯形法的矩阵描述 用单纯形表表示如下： XS = b B N E XB = b E N B-1 初始表 XB XN XS cj - zj 0,0 N S 最终表 XB XN XS cj - zj B N 0,0 表中， b =B-1 b N =B -1 N 或者 Pj =B -1 Pj N = CN-CB B-1 N 或者j =Cj-CBB-1 Pj S = -CB B-1 -第2章 对偶问题-7- 练习： 用单纯形法解目标规划问题时，有如下二个单纯形表，试求括 弧中未知数al的值。 x1x2x3x4 XBb (b) (c) (d) 1 0 -1 3 (e) 0 1 (

4、a) 1 - 2 0 0 6 1 x4 x5 cj - zj XB b x1 x2 x3 x4 x5 x1 x5 cj - zj x5 (g) 2 -1 1/2 0 (h) (i) 1 1/2 1 0 7 (j) (k) (l) (f) 4 以前讨论线性规划问题时，假定ij，bi,cj都是常数。 但实际上这些系数往往是估计值和预测值。如市场 条件一变，cj值就会变化；ij往往是因工艺条件的 改变而改变；bi是根据资源投入后的经济效果决定 的一种决策选择。显然，当线性规划问题中某一个 或几个系数发生变化后，原来已得结果一般会发生 变化。 因此，所谓灵敏度分析灵敏度分析，是指当线性规划问题中的 参

5、数发生变化后，引起最优解如何改变的分析。 2.5.2 2.5.2 图解法灵敏度分析图解法灵敏度分析 例子例子 用图解法求得的最优解 为Q（4，2）点。即生 产甲产品4件，乙产品2件。 考虑目标函数系数变化对例题中最优产量解有什么 影响。甲产品的利润为2元，乙产品的利润为3元， 如果其中一种产品的利润增加，公司就会增加该产 品的产量，如果其中一种产品的利润减少，公司就 会减少该产品的产量。但问题是，利润变化多少时， 管理者才应该决定改变产量呢？ 每个目标函数都有一个最优范围，目标函数系数在 此范围内变化，模型最优解保持不变。 下面用图解法求解这个最优范围。 1.1.目标函数系数的变化目标函数系数

6、的变化 只要目标函数直线的斜率处于直线 x1+2x2=8与直线4x1=16的斜率之 间，Q2点就仍然是最优解的点。 目标函数直线的斜率z=c1x1+c2x2 的斜率-c1 /c2 小于等于-0.5 如果甲产品的单位利润不变，乙产 品的单位利润改变，可得甲产品的 利润范围c11.5.同理，乙产品的利 润最优范围0C24。 当两个系数C1、C2都改变时，我们 仍然可以用目标函数斜率的变化范 围来确定最优解是否改变。 由于系数的改变，最优值z可能发生 变化而不再是原值了。 2 2、约束条件右端值的变化约束条件右端值的变化 约束条件右端值每增加一个单位 引起的最优值的改进量称为对偶对偶 价格价格。 对

7、偶价格只适用于在右端值仅发 生了很小变动的情况 在其他系数不变的情况下，一些参数在一定范围内 变化最优解不变。但是如果一些参数的变化较大， 最优解就可能发生变化。 这样就要问：这些参数在什么范围内变化时，问题 的最优基（或最优解）不变，或者当这些参数中的 一个或几个发生变化时，问题的最优解会有何变化。 这就是灵敏度分析要研究解决的问题。 2.5.3 2.5.3 单纯形法灵敏度分析单纯形法灵敏度分析 当某一个参数发生变化后，引起最优解如何改变的 分析。 可以改变的参数有： bi约束右端项的变化，通常称资源的改变； cj 目标函数系数的变化，通常称市场条件的变 化； pj 约束条件系数的变化，通常

8、称工艺系数的变 化； 其他的变化有：增加一种新产品、增加一道新的工 序等。 1. 1. 灵敏度分析的概念：灵敏度分析的概念： （1）借助最终单纯形表将变化后的结果按下述基 本原则反映到最终表里去。 bi变化： （b+b）=B-1 （b+b）= B-1 b+ B-1 b = b+B-1 b pj变化：（pj+ pj ）= B-1 （pj+ pj ）= B -1 pj+ B-1 pj = pj + B-1 pj cj变化：直接反映到最终表中，计算检验数。 增加一个约束方程：直接反映到最终表中。 增加新产品：仿照pj变化。 2 2分析原理及步骤：分析原理及步骤： （2）检查改变后的最终表是否符合单纯

9、形表的结 构要求（基变量的值中无负数，基变量的系数向量 构成单位矩阵，基变量的检验数全为0），或是否 符合对偶单纯形表的结构要求 （检验数中无正数， 基变量的检验数全为0，基变量的系数向量构成单 位矩阵）; （3）检查原问题是否仍为可行解; （4）检查对偶问题是否仍为可行解; 2 2分析原理及步骤：分析原理及步骤： （5）按照下表所列情况得出结论或继续计算的步 骤。 2 2分析原理及步骤：分析原理及步骤： 原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤 可行解可行解原最优基不变 可行解非可行解用单纯形法继续迭代 非可行解可行解用对偶单纯形法继续迭 代 非可行解非可行解引入

10、人工变量，扩大原 单纯形表继续计算 2.12.1资源数量变化的分析资源数量变化的分析 资源数量变化是指资源中某系数br发生变化，即 br=br+br。并假设规划问题的其他系数都不变。 这样使最终表中原问题的解相应地变化为 XB=B-1(b+b) 这里b=(0,，br,0,，0)T。只要XB0， 因最终表中检验数不变，故最优基不变，但最优 解的值发生了变化，所以XB为新的最优解。新 的最优解的值可允许变化范围用以下方法确定。 B B B B -1-1-1-1 是最终计算表中的最优基的逆 是最终计算表中的最优基的逆是最终计算表中的最优基的逆是最终计算表中的最优基的逆 最优基不变，即最优基不变，即最

11、优基不变，即最优基不变，即在最终表中求得的经过变化后在最终表中求得的经过变化后在最终表中求得的经过变化后在最终表中求得的经过变化后 的的的的b b b b列的所有元素列的所有元素列的所有元素列的所有元素要求不小于要求不小于要求不小于要求不小于0 0 0 0 例如求例题中第二个约束条件例如求例题中第二个约束条件例如求例题中第二个约束条件例如求例题中第二个约束条件b b b b 2 2 2 2 的变化范围。的变化范围。的变化范围。的变化范围。 解：利用题中最终计算表中的数据： -第2章 对偶问题-21- 可计算可计算可计算可计算bbbb2 2 2 2： ： 由上式，可得 b2-4/0.25=-16

12、，b2-4/0.5=-8，b22/0.125=16。 所以b2的变化范围是-8，16；显然原b2 =16，加它 的变化范围后， b2的变化范围是8，32。 例例例例 从表得知，第一种资源的影子价格为从表得知，第一种资源的影子价格为从表得知，第一种资源的影子价格为从表得知，第一种资源的影子价格为1.51.51.51.5元，若该厂又从其元，若该厂又从其元，若该厂又从其元，若该厂又从其 他处抽调他处抽调他处抽调他处抽调4 4 4 4单位资源用于生产产品单位资源用于生产产品单位资源用于生产产品单位资源用于生产产品，。求这时该厂生产产品。求这时该厂生产产品。求这时该厂生产产品。求这时该厂生产产品 ，的最

13、优方案。的最优方案。的最优方案。的最优方案。 解解解解 先计算先计算先计算先计算B B B B-1 -1-1-1b, b,b,b,将结果反映到最终表将结果反映到最终表将结果反映到最终表将结果反映到最终表1-51-51-51-5中，得中，得中，得中，得 表表表表2-102-102-102-10。 -第2章 对偶问题-24- 由于表由于表由于表由于表2-102-102-102-10中中中中b b b b列有负数，故用对偶单纯形法求新的最优解。计算结果见表列有负数，故用对偶单纯形法求新的最优解。计算结果见表列有负数，故用对偶单纯形法求新的最优解。计算结果见表列有负数，故用对偶单纯形法求新的最优解。计

14、算结果见表2-2-2-2- 11111111。 表2-11 -第2章 对偶问题-25- 即该厂最优生产方案应改为生产4件产品，生产3 件产品，获利 z*=42+33=17(元) 从表2.11 看出x3=2，即设备还有2小时未被利用 目标函数中价值系数目标函数中价值系数c cj j的变化分析的变化分析 分为cj是对应的非基变量和基变量两种情况。 (1) 若cj是最终单纯形表中，非基变量xj的系数，要 保证最终表中这个检验数仍小于或等于零。 (2) 若cj是最终单纯形表中，基变量xj的系数，要 保证最终表中所以的非基变量的检验数仍小于或等 于零。 例：例：例：例：设基变量设基变量设基变量设基变量x x x x 2 2 2 2 的系数的系数的系数的系数c c c c 2 2 2 2 变化变化变化变化cccc 2 2 2 2 ，在原最优解不在原最优解不在原最优解不在原最优解不 变条件下，确定变条件下，确定变条件下，确定变条件下，确定cccc 2 2 2 2 的变的变的变的变 化范围。化范围。化范围。化范围。 解解 这时表1-5最终计算表便成为下表所示。 若保持原最优解，从表2-12的检验数行可见应有 由此可得c2-3 和c21。 c2的变化范围为 -3c21 即x2的价值系数c2可以在0，4之间变化，而不 影响原最优解。 3 3 技术系数