运筹学单纯形法的灵敏度分析

1、5.2 单纯形法的灵敏度分析,目标函数系数cj的改变对原问题的影响 约束条件右侧常数bi改变对原问题的影响 约束条件系数矩阵a发生变动对原问题的影响,例：,某工厂计划生产甲、乙、丙三种产品，这三种产品的单位利润分别为2元、3元、1元，生产单位产品所需要的劳动力和材料如下表所列，现工厂计划部门列出线性规划的模型，以确定最优的生产方案。,设计划生产三种产品产量分别为x1，x2，x3 引入松弛变量x4，x5，得如下单纯形表,解到第三段得到最优解： x1=1（甲产品生产1单位），x2=2（乙产品生产2单位），x3=0（丙产品不生产）， maxz=8（最大利润达到8元）,一、目标函数系数cj的改变对原问

2、题的影响,讨论：上例中甲、乙、丙三种产品单位利润发生变化时对原问题的影响。 思考：数学模型中，cj变化将影响数学模型中哪些因素？ 如：丙产品单位利润的变化将影响到模型中哪些因素？ c3=1 c3=2 或 c3=1 c3=6 再如：甲、乙产品单位利润发生变化时，将影响到哪些因素？ c1=2 c1=4 或c2=3 c2=2,结论,在单纯形法中，cj的变化cj-zj变化基变量的调出、入。 分两种情况： 非基变量的cj发生变化只影响其本身对应的检验数cj-zj； 如上例中x3为非基变量，则丙产品单位利润发生变化只影响本身的检验数。 基变量的cj发生变化，由于影响到cb，从而所有非基变量的检验数均受到影

3、响（基变量的检验数仍保持为0）。 如上例中x1、x2为基变量，则甲、乙产品单位利润变化，将影响除甲、乙外其他变量的检验数。,（一）非基变量目标函数系数的改变,上例中，x1、x2为基变量，x3为非基变量，它的最优解为x3=0，既不安排生产。为什么不生产丙产品呢？因为x3所对应的检验数cj-zj不是绝对值最大者，无法调入成为基变量。 如果要生产丙产品，意味着x30，则必须将x3调入成为基变量，考察单纯形表最后一段，此时检验数cj-zj均为非正，如果此时改变c3，则c3-z3会发生变化，当它变成0时，就可以调入。 所以，分析c3-z3的变动：,c3变动范围,当c3-z30即c34时，调入成为基变量，

4、则x30。 也就是说，此时当改变丙产品的单位利润c3到大于4元时，它的产量就大于零，即需考虑生产丙产品了。,所以，丙产品单位利润的变动范围是c34； 讨论： 假设此时c3增加到6元，产量应为多少？,c3已超出变动范围,代入单纯形表 最后一段 继续计算。 即当丙产品利润增加到6元时，最优解为x1=2，x3=1，x2=0，最优值为maxz=10。,（二）基变量目标函数系数的改变,讨论：甲产品单位利润的变化对原问题的影响。 单纯形法最后一段如下：,分析结果,从单纯表最后一段可知：x1为基变量，x10，意味着生产甲产品。 再进一步分析，如果c1降到某一程度之后，即利润非常小，从实际意义上讲，是不应该安

5、排甲产品生产的。另一方面，当甲产品利润增加到很高一个水平时，就可以考虑只生产甲产品而不生产其他产品，那么究竟甲产品利润必须变动到什么程度才可能发生以上变化呢？,（二）基变量目标函数系数的改变,x1是基变量，基变量的检验数c1-z1=0，而c1变化会影响到非基变量的检验数。 我们可以分析所有非基变量的检验数,c1的变动范围,c1的变动范围为3/4，3 也就是说，当甲产品利润在3/4到3之间变动时，它不会影响到基变量，即仍安排生产甲产品和乙产品，不生产丙产品，只是随着c1的变化，最优解即甲、乙产品的产量不会改变，而总利润会发生变动，如当c1=1时，最优解为x1=1，x2=2，而最优值z=7，若c1

6、变动超过以上界限，则需重新计算。,（三）基变量和非基变量的目标函数系数同时发生变化时,思路：参考以上两种情况，在单纯形表最后一段中，用变化后的新cj代入计算检验数cj-zj，若满足符号条件，则最优解不变，最优值变动；若不满足符号条件，则用变化后的cj代入最后一段，继续进行迭代计算。,如上例，当cj变为：c2=4，c3=4,代入最后一段，得 cj-zj0，均满足符号条件 最优解不变，x1=1，x2=2 最优值z=10,当cj变为c2=4，c3=8,代入最后一段，得 cj-zj 0 ，均满足符号条件 经过两段计算，得到最优解，x1=2，x2=1 最优值z=12,二、约束条件右侧常数bi改变对原问题

7、的影响,讨论：例中资源最高限制量改变时将影响数学模型中的哪些因素？,bi变化影响哪些因素？,当bi变化时，从单纯形法计算过程可知，它不影响检验数，只影响b列本身，也就是说，它不影响基变量但会改变最优解的具体数值，如上例中，假设b1发生变化，劳动力使用从一个劳动力增加到2个劳动力，即b1=2，则 b变化不影响检验数 单纯形表最后一段基变量结构不变，仍是x1，x2，改变的是x1，x2的数值 用公式表示如下：,分析,从以上计算结果表明，增加一个单位b1（劳动力数量）会使总利润增加，但在实际经济工作中，b1增加不可能是无限的，因为劳动力增加太多，而其他条件不变时，势必造成劳动力过剩，影响生产率，进而影

8、响利润率，即cj会变化，因此，b1的变化也是有范围的。 从数学模型上思考：b取值的制约条件？,bi变动的制约条件,当我们用单纯形法解线性规划问题时，要求b0 b的变化必须首先满足这个条件 用公式表示如下：,设基变量不变（意味着生产产品结构不变），即b=(p1 p2)保持不变，则,b1变动的范围是3/4，3 也就是说，b1在3/43之间变动时，基变量结构不变（仍是生产甲、乙两种产品，不生产丙产品），但变量值发生变动（产量变化），最优值也会变动（总利润变化），即,分析,例中第二个资源材料的最高限制变化时对原问题的影响。 即讨论：b2变动的范围。,b2变动的范围,b2的变动范围是1 4,影子价格的概

9、念,“影子价格”是经济领域的概念。 “影子价格”是指当其他原料数量都保持不变时，第k种原料由bk增加一个单位时，由此而产生的目标函数值的增加，它对应于单纯形表最后一段松弛变量所对应的检验数（取正值）。,如例中，b1表示劳动力资源,当b1变动时,从以上计算结果表明,b1的影子价格即松弛变量x4的检验数的相反数 z4-c4=5，说明每增加一个单位的劳动力会使得目标函数值z增加5个单位。,b2表示材料资源,当b2变动时,计算结果表明,b2的影子价格即松弛变量x5的检验数的相反数 z5-c5=1，说明每增加一个单位的材料会使得目标函数值z增加1个单位。,影子价格的经济意义,当影子价格zj-cj=0时，

10、表明当各种产品的数量按照最优决策，分别生产数量x1，x2，xn并达到最大收益时，第j种原料尚有剩余，如果单独增加第j种原料的数量不会使总收益增加，故影子价格zj-cj=0。 当影子价格zj-cj0时，表明第j种原料已经在达到最大收益时全部耗尽，生产组织者如果要扩大生产增加收益，必须增加第j种原料的购买量，如果市场上该种原料的市场价格小于或等于zj-cj时，则用增加第j种原料来增加收益是合算的；反之，若市场价格大于影子价格时，那么用增加第j种原料来增加收益的办法是不利的. 所以影子价格能为企业或部门提供今后“活动”的一种经济信息。,三、约束条件系数矩阵a发生变动对原问题的影响,增加新的产品生产，

11、使a矩阵多一列aj 现行的产品生产资源消耗量发生改变， 即aij变化时 增加新的约束条件，即增加新的一行ai,（一）增加新的产品生产，使a矩阵多一列aj,设该厂研究出新的产品丁，每生产一单位产品丁，需要一个劳动力和一单位原料，单位利润为3单位，丁产品销路良好，现在想知道，在原有资源不变的情况下，安排丁生产是否有利。 结合数学模型分析：,分析,要判断是否安排丁生产，就看丁所对应的检验数cj-zj是否满足符号条件，若满足符号条件，说明原问题最优解不变，丁变量不会成为基变量，解仍为零，即不应安排丁产品的生产；相反的，若cj-zj不满足符号条件，则丁变量就有可能被调入成为基变量，即应考虑生产丁。 如例

12、中，原问题变为：（多一个变量x6）,多一个变量x6，使a矩阵多了一列,若加入最后一段计算， 不能直接用p6， 而应将p6线性变化后带入,根据单纯形表最后一段有关数据，得,分析检验数符号,c6-z6满足符号条件 原问题最优解不变，仍是x1=1，x2=2，x3=x6=0 即不安排丁产品生产。,注意区别 和的 不同,若将以上丁产品利润改为c6=7，其他条件不变，情况会有什么变化？,分析检验数符号,c6-z6不满足符号条件 原问题最优解将变动，将c6代入单纯形表最后一段重新计算。 注意：,对p6进行线性变化,此时得到最优解，x1=0，x2=2，x3=x4=x5=0 x6=1/3，最优值z=25/3。

13、说明由于丁产品利润的增加，应考虑生产丁产品。,（二）现行的产品生产资源消耗量发生改变，即aij变化时,1、当非基变量的aij变化时， 如上例，丙产品的技术条件发生变化，单位丙产品所需的劳动力数量不变：a13=1/3，所需的材料数量减少为a23=5/3 即：,分析方法,非基变量的aij的变化只影响本列的数值，只影响本列的检验数。 所以与增添新产品的情况相同，只要重新计算发生变化的aij对应的cj-zj，根据cj-zj的符号判断最优解有否改变。 如例中，丙产品的技术条件发生变化，单位丙产品所需的劳动力数量不变：a13=1/3，所需的材料数量减少为a23=5/3,计算检验数,c3-z3满足符号条件

14、原问题最优解不变，最优值也不变。,2、当基变量对应的aij变化时,当基变量对应的aij变化时，由于此时基矩阵cb受到影响，进而影响所有检验数， 即： 所以，应对规划问题重新计算。,如上例，甲产品、乙产品的技术条件发生变化时，即a11、a21、a12、a22变化时将影响到 则应重新计算。,（三）增加新的约束条件，即增加新的一行ai,如上例，若增加一个约束条件 分析：最优解是否要改变？,对比数学模型,分析,将最优解带入新加入的约束条件中，看看是否满足 若满足新的约束条件，最优解不变； 若不满足新的约束条件，则应加入新的约束条件于单纯形表最后一段，标准化后，继续进行迭代计算直至求出最优解或判断无解。,将最优解x1=1，x2=2代入上式，得 左边=1+2*2+0=5， 右边=4 显然不满足约束条件，则应重新计算最优解