《北邮运筹学ch2-4灵敏度分析》由会员分享，可在线阅读，更多相关《北邮运筹学ch2-4灵敏度分析（34页珍藏版）》请在金锄头文库上搜索。
1、2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 1 of 34线性规划的灵敏度分析也称为敏感性分析，它是研究和 分析参数（cj，bi，aij）的波动对最优解的影响程度，主要 研究下面两个方面： （1）参数在什么范围内变化时，原最优解或最优基不变 ； （2）当参数已经变化时，最优解或最优基有何变化。当模型的参数发生变化后，可以不必对线性规划问题重新 求解，而用灵敏度分析方法直接在原线性规划取得的最优 结果的基础上进行分析或求解，既可减少计算量，又可事 先知道参数的变化范围，及时对原决策作出调整和修正。 2.4.1价值系数cj的变化分析为使最
2、优解不变，求cj的变化范围。Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 2 of 34设线性规划 其中Amn，线性规划存在最优解，最优基的逆矩阵为 检验数为 要使最优解不变，即当cj变化为 后，检验数 仍然是小于等于零，即这时分cj是非基变量和基变量的系数两种情况讨论。Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 3 of 34一、cj是非基变量xj的系数即cj的增量 不超过cj的检验数的相反数时，最优解不 变，否则最优解
3、就要改变。所以 Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 4 of 34二、ci是基变量xi的系数 因ciCB ，所以每个检验数j中含有c i,当c i变化为c i 后j同时 变化，这时令令Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 5 of 34要使得所有 ，则有【例2.13】线性规划（1）求最优解；（2）分别求c1,c2,c3的变化范围，使得最优解不变。Date北京邮电大学 运筹学2.4 灵敏度分析 Sensiti
4、vity Analysis Ch2 Dual ProblemPage 6 of 34 【解】（1）加入松弛变量x4,x5,x6，用单纯形法求解，最 优表如表26所示。表26Cj113000 b CBXBx1x2x3x4x5x60x402011151x111001153x301100115j030012 最优解X=（5，0，15） ; 最优值Z=50。Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 7 of 34（2）x2为非基变量，x 1、x 3为基变量，则c2变化范围是： 对于c1：表26是x 1对应行的系数
5、只有一个负数 ,有两个正 数 c1的变化范围是：Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 8 of 34对于c3：表26中x3对应行c3无上界，即有c32，c3的变化范围是。Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 9 of 34对c3的变化范围，也可直接从表26推出，将c3=3写成 分别计算非基变量的检验数并令其小于等于零。Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis C
6、h2 Dual ProblemPage 10 of 34得c32，同理，用此方法可求出c2和c1的变化区间。，要使 、 同时小于等于零，解不等式组2.4.2 资源限量bi变化分析为了使最优基B不变，求bi的变化范围。设br的增量为br，b的增量为 原线性规划的最优解为X，基变量为XB=B1b，要使最优基B不变，即要求，Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 11 of 34因为Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPag
7、e 12 of 34所以 当令Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 13 of 34因而要使得所有 必须满足这个公式与求 的 上、下限的公式类似，比值的分子都小于等于零，分母是B1中第r列的元素， 大于等于比值小于零的最大值，小于等于比值大于零的最小值。当某个 时， 可能上界或无下界。【例2.14】求例2.13的b1,b2,b3分别在什么范围内变化时 ，原最优基不变。Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 14
8、 of 34【解】解：由表26知，最优基B、B1及分别为对于b1：比值的分母取B1的第一列，这里只有11=1，而 21=31=0，则Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 15 of 34 b1无上界，即b15，因而b1在 内变化时最优基 不变。对于b2：比值的分母取B1的第二列， ，则即b2在15，25上变化时最优基不变。Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 16 of 34对于b3：比值的分母取B1的第三列
9、，有故有 在0，20上变化时最优基不变。灵敏度分析方法还可以分析工艺系数aij的变化对最优解 的影响，对增加约束、变量或减少约束、变量等情形的分 析，下面以一个例子来说明这些分析方法。若线性规划模型是一个生产计划模型，当求出cj或bi 的最大允许变化范围时，就可随时根据市场的变化来掌握 生产计划的调整。 Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 17 of 34【例2.15】考虑下列线性规划求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后 的最优解。（1）将目标函数改为；（1）改变右端常数为:D
10、ate北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 18 of 34（3）改变目标函数x3的系数为c3=1;（4）改变目标函数中x2的系数为c2=2；（5）改变x2的系数为（6）改变约束（1）为（7）增加新约束（8）增加新约束Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 19 of 34【解】加入松弛变量x4、x5、x6，用单纯形法计算，最优表如27所 示。 表27Cj2-14000bCBXBx1x2x3x4x5x64x305/71
11、1/73/7022x112/701/74/7010x60200111j031/702/720/70 Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 20 of 34最优解X=（1，0，2，0，0，1），最优值Z=10，最优基（1） 等价于 ，即将cj改变为（2，1，4），其中c1=2、c3=4是基变量的系数，c2=1是非基变量的系数，求得检验数Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 21 of 34这里表27的解不是最优
12、，将上述检验数代替表27的检验数，再 单纯形法继续迭代，计算结果如表28所示。Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 22 of 34表28 cj214000 bCBXBx1x2x3x4x5x6 4x305/711/73/702 2x112/701/74/701 0x60200111 j031/702/720/70 1x2017/51/53/5014/5 2x1102/51/52/501/5 0x60014/52/51/5033/5 j0031/53/51/50 1x23/2121/2005/20x55
13、/2011/2101/2 0x61/2031/20113/2j1/2061/200 Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 23 of 34最优解（2）基变量的解为基本解不可行，将求得的XB代替表27中的常数项，用对 偶单纯形法求解，其结果见表29所示。Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 24 of 34表29Cj214000 bCBXBx1x2x3x4x5x64x305/711/73/7022/72x112
14、/701/74/706/70x60200112j031/702/720/70 4x30011/71/145/1417/72x11001/73/71/74/71x201001/21/21j0002/79/1431/14 Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 25 of 34最优解（3）由表27容易得到基变量x3的系数c3的增量变化范围是， 而c3=1在允许的变化范围之外，故表27的解不是最优解。非基变 量的检验数x4进基，用单纯形法计算，得到表210。Date北京邮电大学 运筹学2.4 灵敏度分析 Se
15、nsitivity Analysis Ch2 Dual ProblemPage 26 of 34表210XBx1x2x3x4x5x6 bx305/711/73/702x112/701/74/701x60200111j016/701/711/70 x405713014x11110103x60200111j031020 最优解为X=（3，0，0，14，0，1），最优值z=6。Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 27 of 34（4）c2是非基变量x2的系数，由表211知， 由 1变为2时， 或直接求出x2的检验数从而最优解不变，即X=（1，0，2，0，0，1）。Date北京邮电大学 运筹学2.4 灵敏度分析 Sensitivity Analysis Ch2 Dual ProblemPage 28 of 34 (5)这时目标函数的系数和约束条件的系数都变化了，同样 求出2判别最优解是否改
