资源描述
,2.4 灵敏度分析,Sensitivity Analysis,Ch2 Dual Problem,Page,*,of 34,*,线性规划的灵敏度分析也称为敏感性分析，它是研究和分析参数（,c,j,，,b,i,，,a,ij,）的波动对最优解的影响程度，主要研究下面两个方面：,（1）参数在什么范围内变化时，原最优解或最优基不变；,（2）当参数已经变化时，最优解或最优基有何变化。,当模型的参数发生变化后，可以不必对线性规划问题重新求解，而用灵敏度分析方法直接在原线性规划取得的最优结果的基础上进行分析或求解，既可减少计算量，又可事先知道参数的变化范围，及时对原决策作出调整和修正。,2.4.1价值系数,c,j,的变化分析,为使最优解不变，求,c,j,的变化范围。,11/18/2024,设线性规划,其中,A,m,n,，线性规划存在最优解，最优基的逆矩阵为,检验数为,要使最优解不变，即当,c,j,变化为 后，检验数仍然是小于等于零，即,这时分,c,j,是非基变量和基变量的系数两种情况讨论。,11/18/2024,一、,c,j,是非基变量,x,j,的系数,即,c,j,的增量 不超过,c,j,的检验数的相反数时，最优解不变，否则最优解就要改变。,所以,11/18/2024,二、,c,i,是基变量,x,i,的系数,因,c,i,C,B,，所以每个检验数,j,中含有,c,i,当,c,i,变化为,c,i,后,j,同时变化，这时令,令,11/18/2024,要使得所有 ，则有,【,例2.13,】线性规划,（1）求最优解；,（2）分别求,c,1,c,2,c,3,的变化范围，使得最优解不变。,11/18/2024,【,解,】（1）加入松弛变量,x,4,x,5,x,6,，用单纯形法求解，最优表如表26所示。,表26,C,j,1,1,3,0,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,0,2,0,1,1,1,5,1,x,1,1,1,0,0,1,1,5,3,x,3,0,1,1,0,0,1,15,j,0,3,0,0,1,2,最优解X=（5，0，15）;最优值,Z,=50。,11/18/2024,（2）,x,2,为非基变量，,x,1,、,x,3,为基变量，则,c,2,变化范围是：,对于,c,1,：表26是,x,1,对应行的系数只有一个负数 ,有两个正数,c,1,的变化范围是：,11/18/2024,对于,c,3,：表26中,x,3,对应行,c,3,无上界，即有c,3,2，c,3,的变化范围是。,11/18/2024,对,c,3,的变化范围，也可直接从表26推出，将,c,3,=3写成,分别计算非基变量的检验数并令其小于等于零。,11/18/2024,得,c,3,2，同理，用此方法可求出,c,2,和,c,1,的变化区间。,，要使 、同时小于等于零，解不等式组,2.4.2 资源限量,b,i,变化分析,为了使最优基,B,不变，求,b,i,的变化范围。,设,b,r,的增量为,b,r,，,b,的增量为 原线性规划的最优解为,X,，基变量为,X,B,=B,1,b，要使最优基,B,不变，即要求，,11/18/2024,因为,11/18/2024,所以,当,令,11/18/2024,因而要使得所有 必须满足,这个公式与求 的 上、下限的公式类似，比值的分子都小于等于零，分母是,B,1,中第,r,列的元素，大于等于比值小于零的最大值，小于等于比值大于零的最小值。当某个 时，可能上界或无下界。,【,例2.14,】求例2.13的,b,1,b,2,b,3,分别在什么范围内变化时，原最优基不变。,11/18/2024,【,解,】解：由表26知，最优基,B,、,B,1,及分别为,对于,b,1,：比值的分母取,B,1,的第一列，这里只有,11,=1，而,21,=,31,=0，则,11/18/2024,b,1,无上界，即b,1,5，因而,b,1,在 内变化时最优基不变。,对于,b,2,：比值的分母取,B,1,的第二列，则,即,b,2,在15，25上变化时最优基不变。,11/18/2024,对于,b,3,：比值的分母取,B,1,的第三列，有,故有 在0，20上变化时最优基不变。,灵敏度分析方法还可以分析工艺系数,a,ij,的变化对最优解的影响，对增加约束、变量或减少约束、变量等情形的分析，下面以一个例子来说明这些分析方法。,若线性规划模型是一个生产计划模型，当求出,c,j,或,b,i,的最大允许变化范围时，就可随时根据市场的变化来掌握生产计划的调整。,11/18/2024,【,例2.15,】考虑下列线性规划,求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。,（1）将目标函数改为；,（1）改变右端常数为:,11/18/2024,（3）改变目标函数,x,3,的系数为,c,3,=1;,（4）改变目标函数中,x,2,的系数为,c,2,=2；,（5）改变x,2,的系数为,（6）改变约束（1）为,（7）增加新约束,（8）增加新约束,11/18/2024,【,解,】加入松弛变量,x,4,、,x,5,、,x,6,，用单纯形法计算，最优表如27所示。,表27,C,j,2,-1,4,0,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,4,x,3,0,5/7,1,1/7,3/7,0,2,2,x,1,1,2/7,0,1/7,4/7,0,1,0,x,6,0,2,0,0,1,1,1,j,0,31/7,0,2/7,20/7,0,11/18/2024,最优解,X,=（1，0，2，0，0，1），最优值,Z,=10，最优基,（1）等价于 ，即将,c,j,改变为（2，1，4），其中,c,1,=2、,c,3,=4是基变量的系数，,c,2,=1是非基变量的系数，求得检验数,11/18/2024,这里表27的解不是最优，将上述检验数代替表27的检验数，再单纯形法继续迭代，计算结果如表28所示。,11/18/2024,表28,c,j,2,1,4,0,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,4,x,3,0,5/7,1,1/7,3/7,0,2,2,x,1,1,2/7,0,1/7,4/7,0,1,0,x,6,0,2,0,0,1,1,1,j,0,31/7,0,2/7,20/7,0,1,x,2,0,1,7/5,1/5,3/5,0,14/5,2,x,1,1,0,2/5,1/5,2/5,0,1/5,0,x,6,0,0,14/5,2/5,1/5,0,33/5,j,0,0,31/5,3/5,1/5,0,1,x,2,3/2,1,2,1/2,0,0,5/2,0,x,5,5/2,0,1,1/2,1,0,1/2,0,x,6,1/2,0,3,1/2,0,1,13/2,j,1/2,0,6,1/2,0,0,11/18/2024,最优解,（2）基变量的解为,基本解不可行，将求得的,X,B,代替表27中的常数项，用对偶单纯形法求解，其结果见表29所示。,11/18/2024,表29,C,j,2,1,4,0,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,4,x,3,0,5/7,1,1/7,3/7,0,22/7,2,x,1,1,2/7,0,1/7,4/7,0,6/7,0,x,6,0,2,0,0,1,1,2,j,0,31/7,0,2/7,20/7,0,4,x,3,0,0,1,1/7,1/14,5/14,17/7,2,x,1,1,0,0,1/7,3/7,1/7,4/7,1,x,2,0,1,0,0,1/2,1/2,1,j,0,0,0,2/7,9/14,31/14,11/18/2024,最优解,（3）由表27容易得到基变量,x,3,的系数,c,3,的增量变化范围是，,而,c,3,=1在允许的变化范围之外，故表27的解不是最优解。非基变量的检验数,x,4,进基，用单纯形法计算，得到表210。,11/18/2024,表210,X,B,x,1,x,2,x,3,x,4,x,5,x,6,b,x,3,0,5/7,1,1/7,3/7,0,2,x,1,1,2/7,0,1/7,4/7,0,1,x,6,0,2,0,0,1,1,1,j,0,16/7,0,1/7,11/7,0,x,4,0,5,7,1,3,0,14,x,1,1,1,1,0,1,0,3,x,6,0,2,0,0,1,1,1,j,0,3,1,0,2,0,最优解为,X,=（3，0，0，14，0，1）,，最优值z=6。,11/18/2024,（4）,c,2,是非基变量,x,2,的系数，由表211知，由 1变为2时，或直接求出,x,2,的检验数,从而最优解不变，即X=（1，0，2，0，0，1）。,11/18/2024,(5)这时目标函数的系数和约束条件的系数都变化了，同样求出,2,判别最优解是否改变。,x,2,进基，计算结果如表211所示,11/18/2024,表211,C,j,2,3,4,0,0,0,b,C,B,X,B,x,1,x,2,x,3,x,4,x,5,x,6,4,x,3,0,0,1,1/7,3/7,0,2,2,x,1,1,1,0,1/7,4/7,0,1,0,x,6,0,3,0,0,1,1,1,j,0,5,0,2/7,20/7,0,x,3,0,0,1,1/7,3/7,0,2,x,1,1,0,0,1/7,5/21,1/3,4/3,x,2,0,1,0,0,1/3,1/3,1/3,j,0,0,0,2/7,25/21,5/3,最优解,11/18/2024,（6）第一个约束变为 实际上是改变了,a,12,及,b,1,，这时要求,2,及,X,B,，判断解的情况。,因为 可行，所以最优解为,11/18/2024,。,应当注意，当 且 时用单纯形法继续迭代，当 且 不可行时用对偶单纯形法继续迭代，当 且 不可行时，需加入人工变量另找可行基.,（7）引入松弛变量,x,7,得,x,1,、,x,3,是基变量，利用表27消去,x,1,、,x,3,，得,x,7,为新的基变量，基本解X=（1，0，2，0，0，1，2）不可行，将上式加入表27中用对偶单纯形法迭代得到表9-12。,11/18/2024,表212,X,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,b,x,3,0,5/7,1,1/7,3/7,0,0,2,x,1,1,2/7,0,1/7,4/7,0,0,1,x,6,x,7,0,0,2,13/7,0,0,0,11/7,1,2/7,1,0,0,1,1,2,j,0,31/7,0,2/7,20/7,0,0,x,3,0,6/11,1,0,5/11,0,1/11,20/11,x,1,1,5/11,0,0,6/11,0,1/11,13/11,x,6,x,4,0,0,2,13/11,0,0,0,1,1,2/11,1,0,0,7/11,1,14/11,j,0,45/11,0,0,32/11,0,2/11,最优解,11/18/2024,（8）将原最优解代入约束 的左边有5122=110，满足新约束，故最优解不变。,上述,c,j,及,b,i,的最大允许变化范围是假定其它参数不变的前提下，单个参数的变化范围，当几个参数同时在各自范围内变化时，最优解或最优基有可能改变。,本节介绍了：,1.求参数,C,j,在何范围内变化时,最优解,不变；,2.求参数,b,i,在何范围内变化时,最优基,不变；,3.通过例题详细讲解了模型各因素变化后，最优解的求解方法。,11/18/2024,The End of Chapter 2,第三章 运输问题,Exit,1.注意最优解与最优基不变的区别；,2.掌握某个参数变化后，最优表中哪些数据会发生变化，如何变化；,3.模型发生变化后不是重新求解，而是在原模型的最优表中求出变化后的数据，根据变化条件，选择合适的方法继续计算。,MBA学员应掌握如何利用QSB软件中的修改（,Modify problem,）功能，进行灵敏度分析。,作业：P76 T2.8 2.9,11/18/2024,
展开阅读全文