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

§5.2单纯形法的灵敏度分析

目标函数系数Cj的改变对原问题的影响约束条件右侧常数bi改变对原问题的影响

约束条件系数矩阵A发生变动对原问题的影响

1a例：某工厂方案生产甲、乙、丙三种产品，这三种产品的单位利润分别为2元、3元、1元，生产单位产品所需要的劳动力和材料如下表所列，现工厂方案部门列出线性规划的模型，以确定最优的生产方案。甲乙丙可使用资源劳动力材料1/31/31/34/31/37/313利润2312a设方案生产三种产品产量分别为x1，x2，x3引入松弛变量x4，x5，得如下单纯形表3a解到第三段得到最优解：x1=1〔甲产品生产1单位〕，x2=2〔乙产品生产2单位〕，x3=0〔丙产品不生产〕，maxZ=8〔最大利润到达8元〕段Cj↓→基0b2x13x21x30x40x5Qi100x4x5131/31/31/3（4/3）1/37/3100139/4→Cj-Zj→23100203x4x21/49/4（1/4）1/401-1/47/410-1/43/419→Cj-Zj→5/40-17/40-9/4323x1x2121001-124-1-11Cj-Zj→-800-3-5-14a一、目标函数系数Cj的改变对原问题的影响讨论：上例中甲、乙、丙三种产品单位利润发生变化时对原问题的影响。思考：数学模型中，cj变化将影响数学模型中哪些因素？如：丙产品单位利润的变化将影响到模型中哪些因素？c3=1c3=2或c3=1c3=6再如：甲、乙产品单位利润发生变化时，将影响到哪些因素？c1=2c1=4或c2=3c2=25a结论在单纯形法中，cj的变化→cj-zj变化→基变量的调出、入。分两种情况：非基变量的cj发生变化只影响其本身对应的检验数cj-zj；如上例中x3为非基变量，那么丙产品单位利润发生变化只影响本身的检验数。基变量的cj发生变化，由于影响到cB，从而所有非基变量的检验数均受到影响〔基变量的检验数仍保持为0〕。如上例中x1、x2为基变量，那么甲、乙产品单位利润变化，将影响除甲、乙外其他变量的检验数。6a〔一〕非基变量目标函数系数的改变上例中，x1、x2为基变量，x3为非基变量，它的最优解为x3=0，既不安排生产。为什么不生产丙产品呢？因为x3所对应的检验数Cj-Zj不是绝对值最大者，无法调入成为基变量。如果要生产丙产品，意味着x3>0，那么必须将x3调入成为基变量，考察单纯形表最后一段，此时检验数Cj-Zj均为非正，如果此时改变c3，那么C3-Z3会发生变化，当它变成＞0时，就可以调入。所以，分析c3-z3的变动：7aC3变动范围∴当C3-Z3＞0即C3＞4时，调入成为基变量，那么x3>0。也就是说，此时当改变丙产品的单位利润c3到大于4元时，它的产量就大于零，即需考虑生产丙产品了。8a所以，丙产品单位利润的变动范围是c3<4；讨论：假设此时c3增加到6元，产量应为多少？9aC3已超出变动范围代入单纯形表最后一段继续计算。即当丙产品利润增加到6元时，最优解为x1=2，x3=1，x2=0，最优值为maxZ=10。段Cj↓→基0b2x13x26x30x40x5Qi123x1x2121001（-1）24-1-11→Cj-Zj→-8002-5-1226x1x321101/21/2017/2-1/2-1/21/2Cj-Zj→-100-10-4-210a〔二〕基变量目标函数系数的改变讨论：甲产品单位利润的变化对原问题的影响。单纯形法最后一段如下：段Cj↓→基0b2x13x21x30x40x5Qi323x1x2121001-124-1-11Cj-Zj→-800-3-5-111a分析结果从单纯表最后一段可知：x1为基变量，x1>0，意味着生产甲产品。再进一步分析，如果C1降到某一程度之后，即利润非常小，从实际意义上讲，是不应该安排甲产品生产的。另一方面，当甲产品利润增加到很高一个水平时，就可以考虑只生产甲产品而不生产其他产品，那么究竟甲产品利润必须变动到什么程度才可能发生以上变化呢？12a〔二〕基变量目标函数系数的改变∵x1是基变量，基变量的检验数C1-Z1=0，而C1变化会影响到非基变量的检验数。∴我们可以分析所有非基变量的检验数13aC1的变动范围∴C1的变动范围为〔3/4，3〕也就是说，当甲产品利润在3/4到3之间变动时，它不会影响到基变量，即仍安排生产甲产品和乙产品，不生产丙产品，只是随着C1的变化，最优解即甲、乙产品的产量不会改变，而总利润会发生变动，如当C1=1时，最优解为x1=1，x2=2，而最优值Z=7，假设C1变动超过以上界限，那么需重新计算。14a〔三〕基变量和非基变量的目标函数系数同时发生变化时思路：参考以上两种情况，在单纯形表最后一段中，用变化后的新Cj代入计算检验数Cj-Zj，假设满足符号条件，那么最优解不变，最优值变动；假设不满足符号条件，那么用变化后的Cj代入最后一段，继续进行迭代计算。15a如上例，当Cj变为：C2=4，C3=4代入最后一段，得∵Cj-Zj≤0，均满足符号条件∴最优解不变，x1=1，x2=2最优值Z=10段Cj↓→基0b2x14x24x30x40x5Qi124x1x2121001-124-1-11Cj-Zj→-1000-2-4-216a当Cj变为C2=4，C3=8代入最后一段，得∵Cj-Zj≤0，均满足符号条件∴经过两段计算，得到最优解，x1=2，x2=1最优值Z=12段Cj↓→基0b2x14x28x30x40x5Qi124x1x2121001-1（2）4-1-11Cj-Zj→-10002-4-2228x1x321101/21/2017/2-1/2-1/21/2→Cj-Zj→-120-10-3-317a二、约束条件右侧常数bi改变对原问题的影响

讨论：例中资源最高限制量改变时将影响数学模型中的哪些因素？段Cj↓→基0b2x13x21x30x40x5Qi100x4x5131/31/31/3（4/3）1/37/3100139/4→Cj-Zj→023100203x4x21/49/4（1/4）1/401-1/47/410-1/43/419→Cj-Zj→-27/45/40-17/40-9/4323x1x2121001-124-1-11Cj-Zj→-800-3-5-118aBi变化影响哪些因素？当bi变化时，从单纯形法计算过程可知，它不影响检验数，只影响b列本身，也就是说，它不影响基变量但会改变最优解的具体数值，如上例中，假设b1发生变化，劳动力使用从一个劳动力增加到2个劳动力，即b1=2，那么∵b变化不影响检验数∴单纯形表最后一段基变量结构不变，仍是x1，x2，改变的是x1，x2的数值用公式表示如下：19a20a分析从以上计算结果说明，增加一个单位b1〔劳动力数量〕会使总利润增加，但在实际经济工作中，b1增加不可能是无限的，因为劳动力增加太多，而其他条件不变时，势必造成劳动力过剩，影响生产率，进而影响利润率，即Cj会变化，因此，b1的变化也是有范围的。从数学模型上思考：b取值的制约条件？21abi变动的制约条件当我们用单纯形法解线性规划问题时，要求b≥0∴b的变化必须首先满足这个条件用公式表示如下：22a设基变量不变〔意味着生产产品结构不变〕，即B=(P1P2)保持不变，那么∴b1变动的范围是〔3/4，3〕也就是说，b1在3/4∽3之间变动时，基变量结构不变〔仍是生产甲、乙两种产品，不生产丙产品〕，但变量值发生变动〔产量变化〕，最优值也会变动〔总利润变化〕，即23a24a分析例中第二个资源——材料的最高限制变化时对原问题的影响。即讨论：b2变动的范围。25aB2变动的范围B2的变动范围是[14]26a影子价格的概念“影子价格〞是经济领域的概念。“影子价格〞是指当其他原料数量都保持不变时，第k种原料由bk增加一个单位时，由此而产生的目标函数值的增加，它对应于单纯形表最后一段松弛变量所对应的检验数〔取正值〕。27a如例中，b1表示劳动力资源①当b1变动时28a从以上计算结果说明b1的影子价格即松弛变量x4的检验数的相反数Z4-C4=5，说明每增加一个单位的劳动力会使得目标函数值Z增加5个单位。29ab2表示材料资源②当b2变动时30a计算结果说明b2的影子价格即松弛变量x5的检验数的相反数Z5-C5=1，说明每增加一个单位的材料会使得目标函数值Z增加1个单位。31a影子价格的经济意义当影子价格Zj-Cj=0时，说明当各种产品的数量按照最优决策，分别生产数量x1，x2，…，xn并到达最大收益时，第j种原料尚有剩余，如果单独增加第j种原料的数量不会使总收益增加，故影子价格Zj-Cj=0。当影子价格Zj-Cj>0时，说明第j种原料已经在到达最大收益时全部耗尽，生产组织者如果要扩大生产增加收益，必须增加第j种原料的购置量，如果市场上该种原料的市场价格小于或等于Zj-Cj时，那么用增加第j种原料来增加收益是合算的；反之，假设市场价格大于影子价格时，那么用增加第j种原料来增加收益的方法是不利的.所以影子价格能为企业或部门提供今后“活动〞的一种经济信息。32a三、约束条件系数矩阵A发生变动对原问题的影响增加新的产品生产，使A矩阵多一列aj现行的产品生产资源消耗量发生改变，即aij变化时增加新的约束条件，即增加新的一行ai33a〔一〕增加新的产品生产，使A矩阵多一列aj设该厂研究出新的产品丁，每生产一单位产品丁，需要一个劳动力和一单位原料，单位利润为3单位，丁产品销路良好，现在想知道，在原有资源不变的情况下，安排丁生产是否有利。结合数学模型分析：34a分析要判断是否安排丁生产，就看丁所对应的检验数Cj-Zj是否满足符号条件，假设满足符号条件，说明原问题最优解不变，丁变量不会成为基变量，解仍为零，即不应安排丁产品的生产；相反的，假设Cj-Zj不满足符号条件，那么丁变量就有可能被调入成为基变量，即应考虑生产丁。如例中，原问题变为：〔多一个变量x6〕35a多一个变量x6，使A矩阵多了一列假设参加最后一段计算，不能直接用p6，而应将p6线性变化后带入36a根据单纯形表最后一段有关数据，得

段Cj↓→基0b2x13x21x30x40x5Qi323x1x2121001-124-1-11Cj-Zj→-800-3-5-137a分析检验数符号∵C6-Z6满足符号条件∴原问题最优解不变，仍是x1=1，x2=2，x3=x6=0即不安排丁产品生产。注意区别和的不同38a假设将以上丁产品利润改为

C6=7，

其他条件不变，

情况会有什么变化？39a分析检验数符号∵C6-Z6不满足符号条件∴原问题最优解将变动，将C6代入单纯形表最后一段重新计算。注意：40a对p6进行线性变化段Cj↓→基0b2x13x21x30x40x57x6123x1x2121001-124-1-11(3)0Cj-Zj→-800-3-5-11273x6x31/321/3001-1/324/3-1-1/3110Cj-Zj→-25/3-1/30-8/3-19/3-2/3041a此时得到最优解，x1=0，x2=2，x3=x4=x5=0x6=1/3，最优值Z=25/3。说明由于丁产品利润的增加，应考虑生产丁产品。42a〔二〕现行的产品生产资源消耗量发生改变，即aij变化时1、当非基变量的aij变化时，如上例，丙产品的技术条件发生变化，单位丙产品所需的劳动力数量不变：a13=1/3，所需的材料数量减少为a23=5/3即：43a分析方法非基变量的aij的变化只影响本列的数值，只影响本列的检验数。所以与增添新产品的情况相同，只要重新计算发生变化的aij对应的Cj-Zj，根据Cj-Zj的符号判断最优解有否改变。如例中，丙产品的技术条件发生变化，单位丙产品所需的劳动力数量不变：a13=1/3，所需的材料数量减少为a23=5/344a计算检验数∵C3-Z3满足符号条件∴原问题最优解不变，最优值也不变。45a2、当基变量对应的aij变化时当基变量对应的aij变化时，由于此时基矩阵CB受到影响，进而影响所有检验数，即：所以，应对规划问题重新计算。46a如上例，甲产品、乙产品的技术条件发生变化时，即a11、a21、a12、a22变化时将影响到那么应重新计算。47a〔三〕增加新的约束条件，

即增加新的一行ai如上例，假设增加一个约束条件分析：最优解是否要改变？48a比照数学模型49a分析将最优解带入新参加的约束条件中，看看是否满足假设满足新的约束条件，最优解不变；假设不满足新的约束条件，那么应参加新的约束条件于单纯形表最后一段，标准化后，继续进行迭代计算直至求出最优解或判断无解。50a将最优解x1=1，x2=2代入上式，得

左边=1+2*2+0=5，右边=4显然不满足约束条件，那么应重新计算最优解。51a分析参加松弛变量x6，得将标准化后的式子代入单纯形表最后一段52a分析思考：以上单纯形表可否直接计算？段Cj↓→基0b2x13x21x30x40x50x6Qi3230x1x2x6124101012-1214-10-110001Cj-Zj→-800-3-5-153a应进行线性变换段Cj↓→基0b2x13x21x30x40x50x6Qi3230x1x2x61