第_10_讲次课程名称：《运筹学》授课题目灵敏度分析本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，了解灵敏度分析的主要内容，掌握其方法。[重点及难点】对aij，bi，cj的分析内容[本讲课程的引入]在以前讨论线性规划问题时，假定aij，bi，cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，ci值就会变化；aij往往是因工艺条件的改变而改变；bi是根据资源投入的经济效果决定的一种决策选择。因此提出这样两个问题：当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。[本讲课程的内容]当线性规划间题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。当然可以用单纯形法从头计算，以便得到新的最优解，这样做很麻烦，而且也没有必要。因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关。因此，可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按表2-4中几种情况进行处理。原问题对偶问题结论或继续计算的步骤可行解可行解表中的解仍是最优解可行解非可行解用单纯形法继续送代求最优解非可行解可行解用对偶单纯形法继续选代求最优解非可行解非可行解引入人工变量编制新单纯形表求最优解表 2-4（一）资源数量变化的分析资源数量变化是指常数br发生变化，即br'=br十△br。并假设规划问题的其它系数都不变。这样使最终表中原问题的解相应地变化为
课程名称：《运筹学》 第 10 讲次 授课题目 灵敏度分析 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，了解灵敏度分析的主要内容，掌握其方法。 [重点及难点] 对 aij ，bi ，cj 的分析 内 容 [本讲课程的引入] 在以前讨论线性规划问题时，假定 aij ，bi ，cj 都是常数。但实际上这些系数往往是估计值和 预测值。如市场条件一变，cj 值就会变化；aij 往往是因工艺条件的改变而改变；bi 是根据资源投入 的经济效果决定的一种决策选择。因此提出这样两个问题：当这些系数有一个或几个发生变化时，已 求得的线性规划问题的最优解会有什么变化；或者这些系数在什么范围内变化时，线性规划问题的最 优解或最优基不变。 [本讲课程的内容] 当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。当然可以用 单纯形法从头计算，以便得到新的最优解，这样做很麻烦，而且也没有必要。因在单纯形法迭代时， 每次运算都和基变量的系数矩阵 B 有关。因此，可以把发生变化的个别系数，经过一定计算后直接 填入最终计算表中，并进行检查和分析，可按表 2-4 中几种情况进行处理。 表 2-4 （一）资源数量变化的分析 资源数量变化是指常数 br 发生变化，即 br′＝br＋Δbr。并假设规划问题的其它系数都不变。 这样使最终表中原问题的解相应地变化为 原问题 对偶问题 结论或继续计算的步骤 可行解 可行解 表中的解仍是最优解 可行解 非可行解 用单纯形法继续迭代求最优解 非可行解 可行解 用对偶单纯形法继续迭代求最优解 非可行解 非可行解 引入人工变量编制新单纯形表求最优解
内容XB=B-1(b+△b)这里△b=（0，△br，，0）T。只要XB'≥0，最终表中检验数不变，则最优基不变。但最优解的值发生了变化，所以XB为新的最优解。资源数量及新的最优解的值可允许变化范围用以下方法确定。B-1(b+△b)=B-l b + B-l△b=B-l b+B-l（O,,△br,,0)T-B b +Abr (alr ,, air ,, amr) T这时在最终表中求得的b'列所有元素bi+air△br≥0，i=1，2，，m。由此可得：max （-bi' /airlair >0)≤ br ≤ min (-bi' /air|air <0 }例对例1.1的右端项进行敏感性分析。解：家具厂间题的最优单纯形表：503000B-"bXX4eCBXBX2X33020011-2X2501510-1/23/2Xi135000-5-1521）对b1进行分析：1对应基的第一列，B11=αl3=1，β21=α23=-0.5max(-00,-20/1)≤Ab1 ≤min(+oo, -15/(-0.5))20≤b1 ≤302）对b2进行分析：i=2对应基的第二列，β12=α14=-2，β22=α24=1.5max(-00, -15/1.5)≤b2 <min(+0, -20/(-2))10≤b2≤10(二)价值系数变化的分析分别就价值系数cj对应的是非基变量和基变量两种情况来讨论(1)当cj对应的是非基变量xi的系数，这时它在计算表中对应的检验数是：
内 容 XB′＝B （b＋Δb） 这里Δb＝（0，.Δbr，.，0）T。只要 XB′≥0，最终表中检验数不变，则最优基不变。 但最优解的值发生了变化，所以 XB′为新的最优解。资源数量及新的最优解的值可允许 变化范围用以下方法确定。 B （b＋Δb）= B b ＋ B Δb = B b ＋ B （0，.，Δbr，.，0）T = B b ＋Δbr（a1r ，.，air ，.，amr）T 这时在最终表中求得的 b＇列所有元素 bi＇ ＋ airΔbr ≥0 ，i = 1，2 ，.，m 。由此可 得： max｛－bi＇ / air | air ＞0｝≤ Δbr ≤ min｛－bi＇ / air | air ＜0 例: 对例 1.1 的右端项进行敏感性分析。 解：家具厂问题的最优单纯形表： 1) 对 b1 进行分析： i=1 对应基的第一列，11=13=1，21= 23 = -0.5 max{-,-20/1} b1 min{+, -15/(-0.5)} 20 b1 30 2）对 b2 进行分析： i = 2 对应基的第二列，12 = 14 = -2，22 = 24 = 1.5 max{-, -15/1.5} b2 min{+, -20/(-2)} 10 b2 10 （二） 价值系数变化的分析 分别就价值系数 cj 对应的是非基变量和基变量两种情况来讨论。 （1） 当 cj 对应的是非基变量 xj 的系数，这时它在计算表中对应的检验数是： -1 -1 -1 -1 -1 -1 -1 50 30 0 0 cB xB B -1b x1 x2 x3 x4 30 x2 20 0 1 1 -2 50 x1 15 1 0 -1/2 3/2 j 1350 0 0 -5 -15
内容O j= cj — CBB-I Pj当cj变化cj后，要保证最终表中这个检验数仍为非正，即oj'=cj+△cj—CBB-Pj≤0当△cj≤一oj时，可以维持原最优解不变。否则，xj将成为进基变量。2)当cr是基变量xr的系数，crECB，cr变化△cr，引起CB变化，△CB=(0，"，△cr，，0)，这时基变量的检验数仍为0，所有非基变量的检验数发生变化。O' =Cj—（CB + △CB)B-I Pj= Cj-CB ElPj—△CBBI Pj=Oj(O,,Acr,.,)(aij'，azj'，,ami') T=oj-Acr一ari'当cr变化△cr后，若要求原最优解不变，最终表中的检验数应满足oj'=oj-△crarj"≤0于是可确定△cr的变化范围max (oj/arj'larj’>0)≤ Acr ≤min（oj/arj"larj'<02例对例1.1的目标函数系数进行敏感性分析。解：家具厂问题的最优单纯形表：050300B-b0XBX1X2X3X4CB302011-20X2105015-1/23/2xi013500-5-152icl:xl 在基的第二行(r-2)，非基变量下标k=3和4,o23=-1/2,o24=3/2,可得max (-c0, -15/1.5)≤△cl≤min(+o0,-5/(-0.5))-10≤cl≤10c2：x2在基的第一行，r=1，α13=1,α14=-2，可得：max(-o0,(-5)/(1)△<c2≤min(+o0,(-15)/(-2)-5≤△c2≤7.5
内 容 σj = cj － CBB Pj 当 cj 变化Δcj 后，要保证最终表中这个检验数仍为非正，即 σj′= cj ＋Δcj － CBB Pj ≤0 当Δcj ≤ －σj 时，可以维持原最优解不变。否则，xj 将成为进基变量。 （2）当 cr 是基变量 xr 的系数，cr ∈ CB ，cr 变化Δcr，引起 CB 变化，ΔCB =（0，.， Δcr，.，0），这时基变量的检验数仍为 0，所有非基变量的检验数发生变化。 σj′= cj －（CB ＋ ΔCB）B Pj = cj－CB B Pj－ΔCBB Pj =σj － （0，.，Δcr，.，0）（a1j＇ ，a2j＇ ，.，amj＇）T =σj－Δcr arj＇ 当 cr 变化Δcr 后，若要求原最优解不变，最终表中的检验数应满足 σj′=σj－Δcrarj＇ ≤0 于是可确定Δcr 的变化范围 max｛σj / arj＇ | arj＇ ＞0｝≤ Δcr ≤ min｛σj / arj＇ | arj＇ ＜0 例: 对例 1.1 的目标函数系数进行敏感性分析。 解：家具厂问题的最优单纯形表： c1: x1 在基的第二行(r=2), 非基变量下标 k=3 和 4, 23= -1/2, 24=3/2,可得: max {-, -15/1.5} c1 min{+, -5/(-0.5)} -10 c1 10 c2 ：x2 在基的第一行，r＝1，13＝1， 14＝-2，可得： max{-,(-5)/(1)}c2min{+,(-15)/(-2)} -5 c2 7.5 -1 -1 -1 -1 -1 50 30 0 0 cB xB B -1b x1 x2 x3 x4 30 x2 20 0 1 1 -2 50 x1 15 1 0 -1/2 3/2 j 1350 0 0 -5 -15
内容（三）技术系数的变化举例说明：假设例1中产品I的技术系数向量变为P1=（4，5，2）T，每件获利为4元。试问该厂应如何安排最优生产方案？以x1代替xl，计算BP1=（1.25，—3.5，1.375）T。x1＇的检验数为cl—CBBPI=4—（1.5，0.125，0）·（4，5，2）T=-2.625。将这些数字填入表1-5的x1列的位置，得表2-5表2-500430cj→CBxIx2x3XBbx4x52401/40x11.250-3.5-21/20xS401213x21.3751/2-1/80-140-1/80-2.625-3/2-Z用x1＇替换xl，得表2-643000cj--Mx1'x23x5x6CBXBbx44x1'0.667100.330-0.3303000.33x22.6671-0.167-100010x412.6671.6670.83000-M+3-0.83-0.33-2从表2-6可见原问题与对偶问题都是非可行解。于是引入人工变量x6。表2-6中x2所在行，用方程表示时为一x2—0.5x3+0.4x4+x6=2.4从表2-6可见原问题与对偶问题都是非可行解。于是引入人工变量x6。表2-6中x2所在行，用方程表示时为一x2—0.5x3+0.4x4+x6=2.4从表2-6可见原问题与对偶问题都是非可行解。于是引入人工变量x6。表2-6中x2
内 容 （三）技术系数的变化 举例说明：假设例 1 中产品Ⅰ的技术系数向量变为 P1′=（4，5，2）T ，每件获利 为 4 元。试问该厂应如何安排最优生产方案？ 以 x1′代替 x1，计算 B P1′= （1.25，－3.5，1.375）T。 x1′的检验数 为 c1′－ CBB P1′= 4－（1.5，0.125，0）·（4，5，2）T = -2.625。将这些数字填入 表 1-5 的 x1 列的位置，得表 2-5 表 2-5 用 x1′替换 x1 ，得表 2-6 从表 2-6 可见原问题与对偶问题都是非可行解。于是引入人工变量 x6 。表 2-6 中 x2 所在行，用方程表示时为 －x2 －0.5x3 ＋0.4x4 ＋x6 = 2.4 从表 2-6 可见原问题与对偶问题都是非可行解。于是引入人工变量 x6 。表 2-6 中 x2 所在行，用方程表示时为 －x2 －0.5x3 ＋0.4x4 ＋x6 = 2.4 从表 2-6 可见原问题与对偶问题都是非可行解。于是引入人工变量 x6 。表 2-6 中 x2 cj→ 4 3 0 0 0 θ CB XB b x1′ x2 x3 x4 x5 2 x1 4 1.25 0 0 1/4 0 0 x5 4 -3.5 0 -2 1/2 1 3 x2 2 1.375 1 1/2 -1/8 0 - z -14 -2.625 0 -3/2 -1/8 0 cj→ 4 3 0 0 0 -M CB XB b x1′ x2 x3 x4 x5 x6 4 x1′ 0.667 1 0 0.33 0 -0.33 0 3 x2 2.667 0 1 -0.167 0 0.33 -1 0 x4 12.667 0 0 1.667 1 0.83 0 - z 0 0 -0.83 0 -0.33 -M+3
内容所在行，用方程表示时为-x2—0.5x3+0.4x4+x6=2.4将 x6作为基变量代替 x2填入表2-6，得表2-7。2：04300ci--Mx1x2x3bx4x5x6CBXB0004x1'3.210.20X515.200-21.2 1002.40-1-0.51-Mx60.4003-M-0.5M0-z-0.8+0.4M这时可按单纯形法求解，经选代后得最优解，如表2-8：4300ci-0-MXBx1'x2x3x4x5CBbx64xI'10000.6670.33-0.333010x22.667-0.1670.33-10x4001.66710.83012.66700-z-0.830-0.33-M+3（四）增加新变量的灵敏度分析在管理中经常遇到的问题：已知一种新产品的技术经济指标，在原有最优生产计划的基础上，怎样最方便地决定该产品是否值得投入生产，可在原线性规划中引入新的变量；无论增加什么样的新变量，新问题的目标函数只能向好的方向变化。例：家具厂设计了一种新柜子，市场售价为100元，生产一个柜子需9个木工工时，3.5个油漆工工时。问柜子是否应投产？解：令x5代表柜子产量，新模型为：maxz=50x1+30x2+ 100x5s.t.4xl+3x2+x3+9x5=1202xl+x2+x4+3.5x5=50x1,x2,x3,x4,x5 ≥0新变量及其系数放在原单纯形表的最后一列，新向量需经过左乘基的逆矩阵后才能写入最优单纯形表：
内 容 所在行，用方程表示时为 －x2 －0.5x3 ＋0.4x4 ＋x6 = 2.4 将 x6 作为基变量代替 x2 ，填入表 2-6，得表 2-7 。 cj→ 4 3 0 0 0 -M CB XB b x1′ x2 x3 x4 x5 x6 4 x1′ 3.2 1 0 0 0.2 0 0 0 x5 15.2 0 0 -2 1.2 1 0 -M x6 2.4 0 -1 -0.5 0.4 0 1 - z 0 3-M -0.5M -0.8+0.4M 0 0 这时可按单纯形法求解，经迭代后得最优解，如表 2-8： （四）增加新变量的灵敏度分析 在管理中经常遇到的问题：已知一种新产品的技术经济指标，在原有最优生产计划的 基础上，怎样最方便地决定该产品是否值得投入生产，可在原线性规划中引入新的变量 ； 无论增加什么样的新变量，新问题的目标函数只能向好的方向变化。 例: 家具厂设计了一种新柜子，市场售价为 100 元，生产一个柜子需 9 个木工工时，3.5 个 油漆工工时。问柜子是否应投产？ 解：令 x5 代表柜子产量，新模型为： max z = 50x1+30x2 + 100x5 s.t. 4x1 + 3x2+ x3 + 9 x5 = 120 2x1 + x2 + x4+3.5x5 = 50 x1 , x2 , x3 , x4 , x5 0 新变量及其系数放在原单纯形表的最后一列，新向量需经过左乘基的逆矩阵后才能写入最 优单纯形表： cj→ 4 3 0 0 0 -M CB XB b x1′ x2 x3 x4 x5 x6 4 x1′ 0.667 1 0 0.33 0 -0.33 0 3 x2 2.667 0 1 -0.167 0 0.33 -1 0 x4 12.667 0 0 1.667 1 0.83 0 - z 0 0 -0.83 0 -0.33 -M+3