北邮运筹学ch2-4灵敏度分析

北京邮电大学 运筹学,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,的变化范围。,10/5/2024,北京邮电大学 运筹学,设线性规划,其中,A,m,n,，,线性规划存在最优解，最优基的逆矩阵为,检验数为,要使最优解不变，即当,c,j,变化为 后，检验数仍然是小于等于零，即,这时分,c,j,是非基变量和基变量的系数两种情况讨论。,10/5/2024,北京邮电大学 运筹学,一、,c,j,是非基变量,x,j,的系数,即,c,j,的增量 不超过,c,j,的检验数的相反数时，最优解不变，否则最优解就要改变。,所以,10/5/2024,北京邮电大学 运筹学,二、,c,i,是基变量,x,i,的系数,因,c,i,C,B,，,所以每个检验数,j,中含有,c,i,当,c,i,变化为,c,i,后,j,同时变化，这时令,令,10/5/2024,北京邮电大学 运筹学,要使得所有 ，则有,【,例,2.13,】,线性规划,（,1,）求最优解；,（,2,）分别求,c,1,c,2,c,3,的变化范围，使得最优解不变。,10/5/2024,北京邮电大学 运筹学,【,解,】,（,1,）加入松弛变量,x,4,x,5,x,6,，,用单纯形法求解，最优表如表,2,6,所示。,表,2,6,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,。,10/5/2024,北京邮电大学 运筹学,（,2,）,x,2,为非基变量，,x,1,、,x,3,为基变量，则,c,2,变化范围是：,对于,c,1,：,表,2,6,是,x,1,对应行的系数只有一个负数,有两个正数,c,1,的变化范围是：,10/5/2024,北京邮电大学 运筹学,对于,c,3,：,表,2,6,中,x,3,对应行,c,3,无上界，即有,c,3,2,，,c,3,的变化范围是。,10/5/2024,北京邮电大学 运筹学,对,c,3,的变化范围，也可直接从表,2,6,推出，将,c,3,=3,写成,分别计算非基变量的检验数并令其小于等于零。,10/5/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,不变，即要求，,10/5/2024,北京邮电大学 运筹学,因为,10/5/2024,北京邮电大学 运筹学,所以,当,令,10/5/2024,北京邮电大学 运筹学,因而要使得所有 必须满足,这个公式与求 的 上、下限的公式类似，比值的分子都小于等于零，分母是,B,1,中第,r,列的元素，大于等于比值小于零的最大值，小于等于比值大于零的最小值。当某个 时，可能上界或无下界。,【,例,2.14,】,求例,2.13,的,b,1,b,2,b,3,分别在什么范围内变化时，原最优基不变。,10/5/2024,北京邮电大学 运筹学,【,解,】,解：由表,2,6,知，最优基,B,、,B,1,及分别为,对于,b,1,：,比值的分母取,B,1,的第一列，这里只有,11,=1,，而,21,=,31,=0,，,则,10/5/2024,北京邮电大学 运筹学,b,1,无上界，即,b,1,5,，,因而,b,1,在 内变化时最优基不变。,对于,b,2,：,比值的分母取,B,1,的第二列，则,即,b,2,在,15,，,25,上变化时最优基不变。,10/5/2024,北京邮电大学 运筹学,对于,b,3,：,比值的分母取,B,1,的第三列，有,故有 在,0,，,20,上变化时最优基不变。,灵敏度分析方法还可以分析工艺系数,a,ij,的变化对最优解的影响，对增加约束、变量或减少约束、变量等情形的分析，下面以一个例子来说明这些分析方法。,若线性规划模型是一个生产计划模型，当求出,c,j,或,b,i,的最大允许变化范围时，就可随时根据市场的变化来掌握生产计划的调整。,10/5/2024,北京邮电大学 运筹学,【,例,2.15,】,考虑下列线性规划,求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。,（,1,）将目标函数改为；,（,1,）改变右端常数为,:,10/5/2024,北京邮电大学 运筹学,（,3,）改变目标函数,x,3,的系数为,c,3,=1;,（,4,）改变目标函数中,x,2,的系数为,c,2,=2,；,（,5,）改变,x,2,的系数为,（,6,）改变约束（,1,）为,（,7,）增加新约束,（,8,）增加新约束,10/5/2024,北京邮电大学 运筹学,【,解,】,加入松弛变量,x,4,、,x,5,、,x,6,，,用单纯形法计算，最优表如,2,7,所示。,表,2,7,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,10/5/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,是非基变量的系数，求得检验数,10/5/2024,北京邮电大学 运筹学,这里表,2,7,的解不是最优，将上述检验数代替表,2,7,的检验数，再单纯形法继续迭代，计算结果如表,2,8,所示。,10/5/2024,北京邮电大学 运筹学,表,2,8,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,10/5/2024,北京邮电大学 运筹学,最优解,（,2,）基变量的解为,基本解不可行，将求得的,X,B,代替表,2,7,中的常数项，用对偶单纯形法求解，其结果见表,2,9,所示。,10/5/2024,北京邮电大学 运筹学,表,2,9,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,10/5/2024,北京邮电大学 运筹学,最优解,（,3,）由表,2,7,容易得到基变量,x,3,的系数,c,3,的增量变化范围是，,而,c,3,=1,在允许的变化范围之外，故表,2,7,的解不是最优解。非基变量的检验数,x,4,进基，用单纯形法计算，得到表,2,10,。,10/5/2024,北京邮电大学 运筹学,表,2,10,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,。,10/5/2024,北京邮电大学 运筹学,（,4,）,c,2,是非基变量,x,2,的系数，由表,2,11,知，由,1,变为,2,时，或直接求出,x,2,的检验数,从而最优解不变，即,X=,（,1,，,0,，,2,，,0,，,0,，,1,）。,10/5/2024,北京邮电大学 运筹学,(5),这时目标函数的系数和约束条件的系数都变化了，同样求出,2,判别最优解是否改变。,x,2,进基，计算结果如表,2,11,所示,10/5/2024,北京邮电大学 运筹学,表,2,11,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,最优解,10/5/2024,北京邮电大学 运筹学,（,6,）第一个约束变为 实际上是改变了,a,12,及,b,1,，,这时要求,2,及,X,B,，,判断解的情况。,因为 可行，所以最优解为,10/5/2024,北京邮电大学 运筹学,。,应当注意，当 且 时用单纯形法继续迭代，当 且 不可行时用对偶单纯形法继续迭代，当 且 不可行时,，,需加入人工变量另找可行基,.,（,7,）引入松弛变量,x,7,得,x,1,、,x,3,是基变量，利用表,2,7,消去,x,1,、,x,3,，,得,x,7,为新的基变量，基本解,X=,（,1,，,0,，,2,，,0,，,0,，,1,，,2,）,不可行，将上式加入表,2,7,中用对偶单纯形法迭代得到表,9-12,。,10/5/2024,北京邮电大学 运筹学,表,2,12,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