运筹学：ch2-4 灵敏度分析.ppt
34页
线性规划的灵敏度分析也称为敏感性分析，它是研究和分析参数（cj，bi，aij）的波动对最优解的影响程度，主要研究下面两个方面：（1）参数在什么范围内变化时，原最优解或最优基不变；（2）当参数已经变化时，最优解或最优基有何变化当模型的参数发生变化后，可以不必对线性规划问题重新求解，而用灵敏度分析方法直接在原线性规划取得的最优结果的基础上进行分析或求解，既可减少计算量，又可事先知道参数的变化范围，及时对原决策作出调整和修正2.4.12.4.1价值系数价值系数cj的变化分析的变化分析 为使最优解不变，求cj的变化范围2.4灵敏度分析9/10/2024 设线性规划 其中Am×n，线性规划存在最优解，最优基的逆矩阵为 检验数为 要使最优解不变，即当cj变化为 后，检验数仍然是小于等于零，即这时分cj是非基变量和基变量的系数两种情况讨论9/10/2024 一、cj是非基变量xj的系数即cj的增量 不超过cj的检验数的相反数时，最优解不变，否则最优解就要改变所以 9/10/2024 二、ci是基变量xi的系数因ci∈CB ，所以每个检验数λj中含有c i,当c i变化为c i＋ 后λj同时变化，这时令令9/10/2024 要使得所有 ，则有【例例2.13】线性规划（1）求最优解；（2）分别求c1,c2,c3的变化范围，使得最优解不变。
9/10/2024 【解解】（1）加入松弛变量x4,x5,x6，用单纯形法求解，最优表如表2－6所示表2－6Cj113000bCBXBx1x2x3x4x5x60x40－201－1－151x111001－153x301100115λj0－300－1－2 最优解X=（5，0，15） ; 最优值Z=509/10/2024 （2）x2为非基变量，x 1、x 3为基变量，则c2变化范围是：对于c1：表2－6是x 1对应行的系数只有一个负数 ,有两个正数 c1的变化范围是：9/10/2024 对于c3：表2－6中x3对应行Δc3无上界，即有Δc3≥－2，c3的变化范围是9/10/2024 对c3的变化范围，也可直接从表2－6推出，将c3=3写成 分别计算非基变量的检验数并令其小于等于零9/10/2024 得Δc3≥－2，同理，用此方法可求出c2和c1的变化区间要使 、 同时小于等于零，解不等式组2.4.2 资源限量bi变化分析为了使最优基B不变，求bi的变化范围 设br的增量为Δbr，b的增量为 原线性规划的最优解为X，基变量为XB=B－1b，要使最优基B不变，即要求，9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 11 of 34因为9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 12 of 34所以 当令9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 13 of 34因而要使得所有 必须满足这个公式与求 的 上、下限的公式类似，比值的分子都小于等于零，分母是B－1中第r列的元素， 大于等于比值小于零的最大值，小于等于比值大于零的最小值。
当某个 时， 可能上界或无下界 【例例2.14】求例2.13的b1,b2,b3分别在什么范围内变化时，原最优基不变9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 14 of 34 【解解】解：由表2－6知，最优基B、B－1及分别为对于b1：比值的分母取B－1的第一列，这里只有β11=1，而β21=β31=0，则9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 15 of 34Δb1无上界，即Δb1≥－5，因而b1在 内变化时最优基不变 对于b2：比值的分母取B－1的第二列， ，则即b2在[15，25]上变化时最优基不变9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 16 of 34 对于b3：比值的分母取B－1的第三列，有故有 在[0，20]上变化时最优基不变。
灵敏度分析方法还可以分析工艺系数aij的变化对最优解的影响，对增加约束、变量或减少约束、变量等情形的分析，下面以一个例子来说明这些分析方法 若线性规划模型是一个生产计划模型，当求出cj或bi的最大允许变化范围时，就可随时根据市场的变化来掌握生产计划的调整 9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 17 of 34【例例2.15】考虑下列线性规划求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解1）将目标函数改为；（1）改变右端常数为:9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 18 of 34 （3）改变目标函数x3的系数为c3=1; （4）改变目标函数中x2的系数为c2=2；（5）改变x2的系数为（6）改变约束（1）为（7）增加新约束 （8）增加新约束9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 19 of 34【解解】加入松弛变量x4、x5、x6，用单纯形法计算，最优表如2－7所示。
表2－7Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/70－1/74/7010x60－200－111λj0－31/70－2/7－20/70 9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 20 of 34最优解X=（1，0，2，0，0，1），最优值Z=10，最优基（1） 等价于 ，即将cj改变为（－2，1，－4），其中c1=－2、c3=－4是基变量的系数，c2=1是非基变量的系数，求得检验数9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 21 of 34这里表2－7的解不是最优，将上述检验数代替表2－7的检验数，再单纯形法继续迭代，计算结果如表2－8所示9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 22 of 34表2－8cj－21－4000bCBXBx1x2x3x4x5x6－4x305/711/73/702－2x112/70－1/74/7010x60－200－111λj031/702/720/70 1x2017/51/53/5014/5－2x110－2/5－1/52/501/50x60014/52/51/5033/5λj00－31/5－3/51/50 1x2－3/2121/2005/20x55/20－1－1/2101/20x6－1/2031/20113/2λj－1/20－6－1/200 9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 23 of 34最优解（2）基变量的解为基本解不可行，将求得的XB代替表2－7中的常数项，用对偶单纯形法求解，其结果见表2－9所示。
9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 24 of 34表2－9Cj2－14000bCBXBx1x2x3x4x5x64x305/711/73/7022/72x112/70－1/74/706/70x60－200－11－2λj0－31/70－2/7－20/70 4x30011/71/145/1417/72x1100－1/73/71/74/7－1x201001/2－1/21λj000－2/7－9/14－31/14 9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 25 of 34最优解（3）由表2－7容易得到基变量x3的系数c3的增量变化范围是， 而c3=1在允许的变化范围之外，故表2－7的解不是最优解非基变量的检验数x4进基，用单纯形法计算，得到表2－109/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 26 of 34表2－10XBx1x2x3x4x5x6 bx305/711/73/702x112/70－1/74/701x60－200－111λj0－16/701/7－11/70 x405713014x11110103x60－200－111λj0－3－10－20 最优解为X=（3，0，0，14，0，1）‘，最优值z=6。
9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 27 of 34（4）c2是非基变量x2的系数，由表2－11知， 由 －1变为2时， 或直接求出x2的检验数从而最优解不变，即X=（1，0，2，0，0，1）9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 28 of 34(5)这时目标函数的系数和约束条件的系数都变化了，同样求出λ2判别最优解是否改变x2进基，计算结果如表2－11所示9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 29 of 34表2－11 Cj234000bCBXBx1x2x3x4x5x64x30011/73/7022x11－10－1/74/7010x60300－111λj050－2/7－20/70 x30011/73/702 x1100－1/75/211/34/3 x20100－1/31/31/3λj000－2/7－25/21－5/3 最优解9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 30 of 34（6）第一个约束变为 实际上是改变了a12及b1，这时要求λ2及XB，判断解的情况。
因为 可行，所以最优解为9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 31 of 34应当注意，当 且 时用单纯形法继续迭代，当 且 不可行时用对偶单纯形法继续迭代，当 且 不可行时，需加入人工变量另找可行基.（7）引入松弛变量x7得x1、x3是基变量，利用表2－7消去x1、x3，得x7为新的基变量，基本解X=（1，0，2，0，0，1，－2）不可行，将上式加入表2－7中用对偶单纯形法迭代得到表9-129/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 32 of 34表2－12XBx1x2x3x4x5x6x7bx305/711/73/7002x112/70－1/74/7001x6x700－2－13/7000－11/7－12/710011－2λj0－31/70－2/7－20/700 x306/11105/1101/1120/11x115/11006/110－1/1113/11x6x400－213/110001－1－2/11100－7/11114/11λj0－45/1100－32/110－2/11 最优解9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 33 of 34（8）将原最优解代入约束 的左边有5×1－2×2=1<10，满足新约束，故最优解不变。
上述cj及bi的最大允许变化范围是假定其它参数不变的前提下，单个参数的变化范围，当几个参数同时在各自范围内变化时，最优解或最优基有可能改变本节介绍了：1.求参数Cj在何范围内变化时最优解最优解不变；2.求参数bi在何范围内变化时最优基最优基不变；3.通过例题详细讲解了模型各因素变化后，最优解的求解方法9/10/2024 §2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 34 of 34The End of Chapter 2 第三章第三章 运输问题运输问题Exit1.注意最优解与最优基不变的区别；2.掌握某个参数变化后，最优表中哪些数据会发生变化，如何变化；3.模型发生变化后不是重新求解，而是在原模型的最优表中求出变化后的数据，根据变化条件，选择合适的方法继续计算MBA学员应掌握如何利用QSB软件中的修改（ Modify problem ）功能，进行灵敏度分析作业：P76 T2.8 2.99/10/2024 。
