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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,5.2,单纯形法的灵敏度分析,目标函数系数,Cj,的改变对原问题的影响,约束条件右侧常数,bi,改变对原问题的影响,约束条件系数矩阵,A,发生变动对原问题的影响,例：,某工厂计划生产甲、乙、丙三种产品，这三种产品的单位利润分别为,2,元、,3,元、,1,元，生产单位产品所需要的劳动力和材料如下表所列，现工厂计划部门列出线性规划的模型，以确定最优的生产方案。,甲,乙,丙,可使用资源,劳动力,材料,1/3,1/3,1/3,4/3,1/3,7/3,1,3,利润,2,3,1,设计划生产三种产品产量分别为,x,1,，,x,2,，,x,3,引入松弛变量,x,4,，,x,5,，得如下单纯形表,解到第三段得到最优解：,x,1,=1,（甲产品生产,1,单位），,x,2,=2,（乙产品生产,2,单位），,x,3,=0,（丙产品不生产），,maxZ,=8,（最大利润达到,8,元）,段,Cj,基,0,b,2,x,1,3,x,2,1,x,3,0,x,4,0,x,5,Qi,1,0,0,x,4,x,5,1,3,1/3,1/3,1/3,（,4/3,）,1/3,7/3,1,0,0,1,3,9/4,Cj-Zj,2,3,1,0,0,2,0,3,x,4,x,2,1/4,9/4,（,1/4,）,1/4,0,1,-1/4,7/4,1,0,-1/4,3/4,1,9,Cj-Zj,5/4,0,-17/4,0,-9/4,3,2,3,x,1,x,2,1,2,1,0,0,1,-1,2,4,-1,-1,1,Cj-Zj,-8,0,0,-3,-5,-1,一、目标函数系数,Cj,的改变对原问题的影响,讨论：上例中甲、乙、丙三种产品单位利润发生变化时对原问题的影响。,思考：数学模型中，,c,j,变化将影响数学模型中哪些因素？,如：丙产品单位利润的变化将影响到模型中哪些因素？,c,3,=1 c,3,=2,或,c,3,=1 c,3,=6,再如：甲、乙产品单位利润发生变化时，将影响到哪些因素？,c,1,=2 c,1,=4,或,c,2,=3 c,2,=2,结论,在单纯形法中，,c,j,的变化,c,j,-z,j,变化,基变量的调出、入。,分两种情况：,非基变量的,c,j,发生变化只影响其本身对应的检验数,c,j,-z,j,；,如上例中,x,3,为非基变量，则丙产品单位利润发生变化只影响本身的检验数。,基变量的,c,j,发生变化，由于影响到,c,B,，从而所有非基变量的检验数均受到影响（基变量的检验数仍保持为,0,）。,如上例中,x,1,、,x,2,为基变量，则甲、乙产品单位利润变化，将影响除甲、乙外其他变量的检验数。,（一）非基变量目标函数系数的改变,上例中，,x,1,、,x,2,为基变量，,x,3,为非基变量，它的最优解为,x,3,=0,，既不安排生产。为什么不生产丙产品呢？因为,x,3,所对应的检验数,C,j,-Z,j,不是绝对值最大者，无法调入成为基变量。,如果要生产丙产品，意味着,x,3,0,，则必须将,x,3,调入成为基变量，考察单纯形表最后一段，此时检验数,C,j,-Z,j,均为非正，如果此时改变,c,3,，则,C,3,-Z,3,会发生变化，当它变成,0,时，就可以调入。,所以，分析,c,3,-z,3,的变动：,C,3,变动范围,当,C,3,-Z,3,0,即,C,3,4,时，调入成为基变量，则,x,3,0,。,也就是说，此时当改变丙产品的单位利润,c,3,到大于,4,元时，它的产量就大于零，即需考虑生产丙产品了。,所以，丙产品单位利润的变动范围是,c,3,0,，意味着生产甲产品。,再进一步分析，如果,C,1,降到某一程度之后，即利润非常小，从实际意义上讲，是不应该安排甲产品生产的。另一方面，当甲产品利润增加到很高一个水平时，就可以考虑只生产甲产品而不生产其他产品，那么究竟甲产品利润必须变动到什么程度才可能发生以上变化呢？,（二）基变量目标函数系数的改变,x,1,是基变量，基变量的检验数,C,1,-Z,1,=0,，而,C,1,变化会影响到非基变量的检验数。,我们可以分析所有非基变量的检验数,C,1,的变动范围,C,1,的变动范围为,3/4,，,3,也就是说，当甲产品利润在,3/4,到,3,之间变动时，它不会影响到基变量，即仍安排生产甲产品和乙产品，不生产丙产品，只是随着,C,1,的变化，最优解即甲、乙产品的产量不会改变，而总利润会发生变动，如当,C,1,=1,时，最优解为,x,1,=1,，,x,2,=2,，而最优值,Z=7,，若,C,1,变动超过以上界限，则需重新计算。,（三）基变量和非基变量的目标函数系数同时发生变化时,思路：参考以上两种情况，在单纯形表最后一段中，用变化后的新,Cj,代入计算检验数,Cj-Zj,，若满足符号条件，则最优解不变，最优值变动；若不满足符号条件，则用变化后的,Cj,代入最后一段，继续进行迭代计算。,如上例，当,Cj,变为：,C,2,=4,，,C,3,=4,代入最后一段，得,Cj-Zj,0,，均满足符号条件,最优解不变，,x,1,=1,，,x,2,=2,最优值,Z=10,段,Cj,基,0,b,2,x,1,4,x,2,4,x,3,0,x,4,0,x,5,Qi,1,2,4,x,1,x,2,1,2,1,0,0,1,-1,2,4,-1,-1,1,Cj-Zj,-10,0,0,-2,-4,-2,当,Cj,变为,C,2,=4,，,C,3,=8,代入最后一段，得,Cj-Zj,0,，均满足符号条件,经过两段计算，得到最优解，,x,1,=2,，,x,2,=1,最优值,Z=12,段,Cj,基,0,b,2,x,1,4,x,2,8,x,3,0,x,4,0,x,5,Qi,1,2,4,x,1,x,2,1,2,1,0,0,1,-1,（,2,）,4,-1,-1,1,Cj-Zj,-10,0,0,2,-4,-2,2,2,8,x,1,x,3,2,1,1,0,1/2,1/2,0,1,7/2,-1/2,-1/2,1/2,Cj-Zj,-12,0,-1,0,-3,-3,二、约束条件右侧常数,bi,改变对原问题的影响,讨论：例中资源最高限制量改变时将影响数学模型中的哪些因素？,段,Cj,基,0,b,2,x,1,3,x,2,1,x,3,0,x,4,0,x,5,Qi,1,0,0,x,4,x,5,1,3,1/3,1/3,1/3,（,4/3,）,1/3,7/3,1,0,0,1,3,9/4,Cj-Zj,0,2,3,1,0,0,2,0,3,x,4,x,2,1/4,9/4,（,1/4,）,1/4,0,1,-1/4,7/4,1,0,-1/4,3/4,1,9,Cj-Zj,-27/4,5/4,0,-17/4,0,-9/4,3,2,3,x,1,x,2,1,2,1,0,0,1,-1,2,4,-1,-1,1,Cj-Zj,-8,0,0,-3,-5,-1,Bi,变化影响哪些因素？,当,bi,变化时，从单纯形法计算过程可知，它不影响检验数，只影响,b,列本身，也就是说，它不影响基变量但会改变最优解的具体数值，如上例中，假设,b,1,发生变化，劳动力使用从一个劳动力增加到,2,个劳动力，即,b,1,=2,，则,b,变化不影响检验数,单纯形表最后一段基变量结构不变，仍是,x,1,，,x,2,，改变的是,x,1,，,x,2,的数值,用公式表示如下：,分析,从以上计算结果表明，增加一个单位,b,1,（劳动力数量）会使总利润增加，但在实际经济工作中，,b,1,增加不可能是无限的，因为劳动力增加太多，而其他条件不变时，势必造成劳动力过剩，影响生产率，进而影响利润率，即,Cj,会变化，因此，,b,1,的变化也是有范围的。,从数学模型上思考：,b,取值的制约条件？,bi,变动的制约条件,当我们用单纯形法解线性规划问题时，要求,b0,b,的变化必须首先满足这个条件,用公式表示如下：,设基变量不变（意味着生产产品结构不变），即,B=(P,1,P,2,),保持不变，则,b,1,变动的范围是,3/4,，,3,也就是说，,b,1,在,3/43,之间变动时，基变量结构不变（仍是生产甲、乙两种产品，不生产丙产品），但变量值发生变动（产量变化），最优值也会变动（总利润变化），即,分析,例中第二个资源,材料的最高限制变化时对原问题的影响。,即讨论：,b,2,变动的范围。,B,2,变动的范围,B,2,的变动范围是,1 4,影子价格的概念,“,影子价格”是经济领域的概念。,“影子价格”是指当其他原料数量都保持不变时，第,k,种原料由,b,k,增加一个单位时，由此而产生的目标函数值的增加，它对应于单纯形表最后一段松弛变量所对应的检验数（取正值）。,如例中，,b,1,表示劳动力资源,当,b,1,变动时,从以上计算结果表明,b,1,的影子价格即松弛变量,x,4,的检验数的相反数,Z,4,-C,4,=5,，说明每增加一个单位的劳动力会使得目标函数值,Z,增加,5,个单位。,b,2,表示材料资源,当,b,2,变动时,计算结果表明,b,2,的影子价格即松弛变量,x,5,的检验数的相反数,Z,5,-C,5,=1,，说明每增加一个单位的材料会使得目标函数值,Z,增加,1,个单位。,影子价格的经济意义,当影子价格,Zj-Cj,=0,时，表明当各种产品的数量按照最优决策，分别生产数量,x,1,，,x,2,，,，,x,n,并达到最大收益时，第,j,种原料尚有剩余，如果单独增加第,j,种原料的数量不会使总收益增加，故影子价格,Zj-Cj,=0,。,当影子价格,Zj-Cj,0,时，表明第,j,种原料已经在达到最大收益时全部耗尽，生产组织者如果要扩大生产增加收益，必须增加第,j,种原料的购买量，如果市场上该种原料的市场价格小于或等于,Zj-Cj,时，则用增加第,j,种原料来增加收益是合算的；反之，若市场价格大于影子价格时，那么用增加第,j,种原料来增加收益的办法是不利的,.,所以影子价格能为企业或部门提供今后“活动”的一种经济信息。,三、约束条件系数矩阵,A,发生变动对原问题的影响,增加新的产品生产，使,A,矩阵多一列,a,j,现行的产品生产资源消耗量发生改变，,即,a,ij,变化时,增加新的约束条件，即增加新的一行,a,i,（一）增加新的产品生产，使,A,矩阵多一列,a,j,设该厂研究出新的产品丁，每生产一单位产品丁，需要一个劳动力和一单位原料，单位利润为,3,单位，丁产品销路良好，现在想知道，在原有资源不变的情况下，安排丁生产是否有利。,结合数学模型分析：,分析,要判断是否安排丁生产，就看丁所对应的检验数,Cj-Zj,是否满足符号条件，若满足符号条件，说明原问题最优解不变，丁变量不会成为基变量，解仍为零，即不应安排丁产品的生产；相反的，若,Cj-Zj,不满足符号条件，则丁变量就有可能被调入成为基变量，即应考虑生产丁。,如例中，原问题变为：（多一个变量,x,6,）,多一个变量,x,6,，使,A,矩阵多了一列,若加入最后一段计算，,不能直接用,p,6,，,而应将,p6,线性变化后带入,根据单纯形表最后一段有关数据，得,段,Cj,基,0,b,2,x,1,3,x,2,1,x,3,0,x,4,0,x,5,Qi,3,2,3,x,1,x,2,1,2,1,0,0,1,-1,2,4,-1,-1,1,Cj-Zj,-8,0,0,-3,-5,-1,分析检验数符号,C,6,-Z,6,满足符号条件,原问题最优解不变，仍是,x,1,=1,，,x,2,=2,，,x,3,=x,6,=0,即不安排丁产品生产。,注意区别 和的 不同,若将以上丁产品利润改为,C,6,=7,，其他条件不变，情况会有什么变化？,分析检验数符号,C,6,-Z,6,不满足符号条件,原问题最优解将变动，将,C,6,代入单纯形表最后一段重新计算。,注意：,对,p,6,进行线性变化,段,Cj,基,0,b,2,x,1,3,x,2,1,x,3,0,x,4,0,x,5,7,x,6,1,2,3,x,1,x,2,1,2,1,0,0,1,-1,2,4,-1,-1,1,(3),0,Cj-Zj,-8,0,0,-3,-5,-1,1,2,7,3,x,6,x,3,1/3,2,1/3,0,0,1,-1/3,2,4/3,-1,-1/3,1,1,0,Cj-Zj,-25/3,-1/3,0,-8/3,-19/3,-2/3,0,此时得到最优解，,x,1,=0,，,x,2,=2,，,x,3,=x,4,=x,5,=0 x,6,=1/3,，最优值,Z=25/3,。,说明由于丁产品利润的增加，应考虑生产丁产品。,（二）现行的产品生产资源消耗量发生改变，即,a,ij,变化时,1,、当非基变量的,a,ij,变化时，,如上例，丙产品的技术条件发生变化，单位丙产品所需的劳动力数量不变：,a,13,=1/3,，所需的材料数量减少为,a,23,=5/3,即：,分析方法,非基变量的,a,ij,的变化只影响本列的数值，只影响本列的检验数。,所以与增添新产品的情况相同，只要重新计算发生变化的,a,ij,对应的,Cj-Zj,，根据,Cj-Zj,的符号判断最优解有否改变。,如例中，丙产品的技术条件发生变化，单位丙产品所需的劳动力数量不变：,a,13,=1/3,，所需的材料数量减少为,a,23,=5/3,计算检验数,C,3,-Z,3,满足符号条件,原问题最优解不变，最优值也不变。,2,、当基变量对应的,a,ij,变化时,当基变量对应的,a,ij,变化时,，由于此时基矩阵,C,B,受到影响，进而影响所有检验数，,即：,所以，应对规划问题重新计算。,如上例，甲产品、乙产品的技术条件发生变化时，即,a,11,、,a,21,、,a,12,、,a,22,变化时将影响到,则应重新计算。,（三）增加新的约束条件，即增加新的一行,a,i,如上例，若增加一个约束条件,分析：最优解是否要改变？,对比数学模型,分析,将最优解带入新加入的约束条件中，看看是否满足,若满足新的约束条件，最优解不变；,若不满足新的约束条件，则应加入新的约束条件于单纯形表最后一段，,标准化后,，继续进行迭代计算直至求出最优解或判断无解。,将最优解,x,1,=1,，,x,2,=2,代入上式，得,左边,=1+2*2+0=5,， 右边,=4,显然不满足约束条件，则应重新计算最优解。,分析,加入松弛变量,x,6,，得,将标准化后的式子代入单纯形表最后一段,分析,思考：以上单纯形表可否直接计算？,段,Cj,基,0,b,2,x,1,3,x,2,1,x,3,0,x,4,0,x,5,0,x6,Qi,3,2,3,0,x,1,x,2,x,6,1,2,4,1,0,1,0,1,2,-1,2,1,4,-1,0,-1,1,0,0,0,1,Cj-Zj,-8,0,0,-3,-5,-1,应进行线性变换,段,Cj,基,0,b,2,x,1,3,x,2,1,x,3,0,x,4,0,x,5,0,x,6,Qi,3,2,3,0,x,1,x,2,x,6,1,2,1,0,0,0,1,0,-1,2,4,-1,-1,1,0,0,1,Cj-Zj,代入新的约束条件，得,段,Cj,基,0,b,2,x,1,3,x,2,1,x,3,0,x,4,0,x,5,Qi,3,2,3,x,1,x,2,1,2,1,0,0,1,-1,2,4,-1,-1,1,Zj-Cj,8,0,0,3,5,1,加入人工变量,x,7,代入单纯形法最后一段，得,段,Cj,基,0,b,2,x,1,3,x,2,1,x,3,0,x,4,0,x,5,7,x,6,-M,x,7,1,2,3,-M,x,1,x,2,x,7,1,2,1,1,0,0,0,1,0,-1,2,（,2,）,4,-1,2,-1,1,1,0,0,-1,0,0,1,Cj-Zj,-,0,0,2M-3,2M-5,M-1,-M,0,2,2,3,1,x,1,x,2,x,3,3/2,1,1/2,1,0,0,0,1,0,0,0,1,5,-3,1,-1/2,0,（,1/2,）,-1/2,1,-1/2,1/2,-1,1/2,Cj-Zj,0,0,0,-2,1/2,-3/2,-,3,2,3,0,x,1,x,2,x,5,2,1,1,1,0,0,0,1,0,1,0,2,6,-3,2,0,0,1,-1,1,-1,1,-1,1,Cj-Zj,-7,0,0,-1,-3,0,-1,-,所有检验数均满足符号条件,得到新的最优解，,x,1,=2,，,x,2,=1,，,x,3,=x,4,=x,6,=0 x,5,=1,，最优值,Z=7,。,以上说明了各种条件发生变化后，重新在求得最优解的方法，这种优化后的分析，所得到的信息，较之最优值本身具有更多价值，在实际工作中更有意义。,练习题,