运筹学 北京邮电大学.ch2-4

1、 线性规划的灵敏度分析也称为敏感性分析，它是研究和分析参数（cj，bi，aij）的波动对最优解的影响程度，主要研究下面两个方面：（1）参数在什么范围内变化时，原最优解或最优基不变；（2）当参数已经变化时，最优解或最优基有何变化。当模型的参数发生变化后，可以不必对线性规划问题重新求解，而用灵敏度分析方法直接在原线性规划取得的最优结果的基础上进行分析或求解，既可减少计算量，又可事先知道参数的变化范围，及时对原决策作出调整和修正。2.4.1价值系数cj的变化分析 为使最优解不变，求cj的变化范围。8/1/2022 设线性规划 其中Amn，线性规划存在最优解，最优基的逆矩阵为 检验数为 要使最优解不变

2、，即当cj变化为 后，检验数仍然是小于等于零，即这时分cj是非基变量和基变量的系数两种情况讨论。8/1/2022一、cj是非基变量xj的系数即cj的增量 不超过cj的检验数的相反数时，最优解不变，否则最优解就要改变。所以 8/1/2022 二、ci是基变量xi的系数因ciCB ，所以每个检验数j中含有c i,当c i变化为c i 后j同时变化，这时令令8/1/2022要使得所有 ，则有【例2.13】线性规划（1）求最优解；（2）分别求c1,c2,c3的变化范围，使得最优解不变。8/1/2022【解】（1）加入松弛变量x4,x5,x6，用单纯形法求解，最优表如表26所示。表26Cj113000b

3、CBXBx1x2x3x4x5x60 x402011151x111001153x301100115j030012最优解X=（5，0，15） ; 最优值Z=50。8/1/2022（2）x2为非基变量，x 1、x 3为基变量，则c2变化范围是：对于c1：表26是x 1对应行的系数只有一个负数 ,有两个正数 c1的变化范围是：8/1/2022对于c3：表26中x3对应行c3无上界，即有c32，c3的变化范围是。8/1/2022 对c3的变化范围，也可直接从表26推出，将c3=3写成 分别计算非基变量的检验数并令其小于等于零。8/1/2022得c32，同理，用此方法可求出c2和c1的变化区间。，要使 、

4、 同时小于等于零，解不等式组2.4.2 资源限量bi变化分析为了使最优基B不变，求bi的变化范围。 设br的增量为br，b的增量为 原线性规划的最优解为X，基变量为XB=B1b，要使最优基B不变，即要求，8/1/2022因为8/1/2022所以 当令8/1/2022因而要使得所有 必须满足这个公式与求 的 上、下限的公式类似，比值的分子都小于等于零，分母是B1中第r列的元素， 大于等于比值小于零的最大值，小于等于比值大于零的最小值。当某个 时， 可能上界或无下界。 【例2.14】求例2.13的b1,b2,b3分别在什么范围内变化时，原最优基不变。8/1/2022 【解】解：由表26知，最优基B

5、、B1及分别为对于b1：比值的分母取B1的第一列，这里只有11=1，而21=31=0，则8/1/2022b1无上界，即b15，因而b1在 内变化时最优基不变。 对于b2：比值的分母取B1的第二列， ，则即b2在15，25上变化时最优基不变。8/1/2022 对于b3：比值的分母取B1的第三列，有故有 在0，20上变化时最优基不变。 灵敏度分析方法还可以分析工艺系数aij的变化对最优解的影响，对增加约束、变量或减少约束、变量等情形的分析，下面以一个例子来说明这些分析方法。 若线性规划模型是一个生产计划模型，当求出cj或bi的最大允许变化范围时，就可随时根据市场的变化来掌握生产计划的调整。 8/1

6、/2022【例2.15】考虑下列线性规划求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。（1）将目标函数改为；（1）改变右端常数为:8/1/2022 （3）改变目标函数x3的系数为c3=1; （4）改变目标函数中x2的系数为c2=2；（5）改变x2的系数为（6）改变约束（1）为（7）增加新约束 （8）增加新约束8/1/2022【解】加入松弛变量x4、x5、x6，用单纯形法计算，最优表如27所示。表27Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/701/74/7010 x60200111j031/702/720/708/1/

7、2022最优解X=（1，0，2，0，0，1），最优值Z=10，最优基（1） 等价于 ，即将cj改变为（2，1，4），其中c1=2、c3=4是基变量的系数，c2=1是非基变量的系数，求得检验数8/1/2022这里表27的解不是最优，将上述检验数代替表27的检验数，再单纯形法继续迭代，计算结果如表28所示。8/1/2022表28cj214000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/701/74/7010 x60200111j031/702/720/701x2017/51/53/5014/52x1102/51/52/501/50 x60014/52/51/50

8、33/5j0031/53/51/501x23/2121/2005/20 x55/2011/2101/20 x61/2031/20113/2j1/2061/2008/1/2022最优解（2）基变量的解为基本解不可行，将求得的XB代替表27中的常数项，用对偶单纯形法求解，其结果见表29所示。8/1/2022表29Cj214000bCBXBx1x2x3x4x5x64x305/711/73/7022/72x112/701/74/706/70 x60200112j031/702/720/704x30011/71/145/1417/72x11001/73/71/74/71x201001/21/21j000

9、2/79/1431/148/1/2022最优解（3）由表27容易得到基变量x3的系数c3的增量变化范围是， 而c3=1在允许的变化范围之外，故表27的解不是最优解。非基变量的检验数x4进基，用单纯形法计算，得到表210。8/1/2022表210XBx1x2x3x4x5x6 bx305/711/73/702x112/701/74/701x60200111j016/701/711/70 x405713014x11110103x60200111j031020 最优解为X=（3，0，0，14，0，1），最优值z=6。8/1/2022（4）c2是非基变量x2的系数，由表211知， 由 1变为2时， 或直

10、接求出x2的检验数从而最优解不变，即X=（1，0，2，0，0，1）。8/1/2022(5)这时目标函数的系数和约束条件的系数都变化了，同样求出2判别最优解是否改变。x2进基，计算结果如表211所示8/1/2022表211 Cj234000bCBXBx1x2x3x4x5x64x30011/73/7022x11101/74/7010 x60300111j0502/720/70 x30011/73/702x11001/75/211/34/3x201001/31/31/3j0002/725/215/3最优解8/1/2022（6）第一个约束变为 实际上是改变了a12及b1，这时要求2及XB，判断解的情况

11、。因为 可行，所以最优解为8/1/2022。应当注意，当 且 时用单纯形法继续迭代，当 且 不可行时用对偶单纯形法继续迭代，当 且 不可行时，需加入人工变量另找可行基.（7）引入松弛变量x7得x1、x3是基变量，利用表27消去x1、x3，得x7为新的基变量，基本解X=（1，0，2，0，0，1，2）不可行，将上式加入表27中用对偶单纯形法迭代得到表9-12。8/1/2022表212XBx1x2x3x4x5x6x7bx305/711/73/7002x112/701/74/7001x6x700213/700011/712/7100112j031/702/720/700 x306/11105/1101

12、/1120/11x115/11006/1101/1113/11x6x400213/11000112/111007/11114/11j045/110032/1102/11最优解8/1/2022（8）将原最优解代入约束 的左边有5122=110，满足新约束，故最优解不变。 上述cj及bi的最大允许变化范围是假定其它参数不变的前提下，单个参数的变化范围，当几个参数同时在各自范围内变化时，最优解或最优基有可能改变。本节介绍了：1.求参数Cj在何范围内变化时最优解不变；2.求参数bi在何范围内变化时最优基不变；3.通过例题详细讲解了模型各因素变化后，最优解的求解方法。8/1/2022The End of Chapter 2