《运筹学》课程教学资源（试卷习题）重点难点考点剖析

重点难点考点部析一、关于单纯形法的补充说明1.无穷多最优解与唯一最优解的判别法则设X*是线性规划问题的基B对应的可行解，（1）所有检验数≤0，有非基变量x的检验数等于0，且确定的θ>0，则问题有无穷多最优解：（2）所有非基变量的检验数0<0，则问题有唯一最优解。证明（1）此时按法则1，Xi已是最优解，设目标函数最优值为2，以x为换入变量进行迭代运算，可得另一基可行解X**，由于α=0，换入x后，目标函数值不变，故X**也是最优解。所以对于区间[0，1]之中的所有实数α，αX*+（1一α）X**都是最优解。（2）设Y*是线性规划问题的任意一个最优解，则有：YBz = CY*= (CR,CN=C,Y,+CY,=C,B"b+(C-C,B-'N)y,=C,B-"b 所NYu以(C-C,BN)~=0，故Y=0，而AY"=(B,N)=BY=b，所以Y，=B-"b=X，因此最优解唯一。例1求解线性规划间题maxz=2x+x,+4x,+x4X+x +x=1-2x4 =12x, + X2[,x2,x≥0的最优解的类型。解：取x3，x2作为基变量，直接列表求解：表1单纯形表214ci1CBXBbX1x2x4X34011[1]1X30-211-21X25000-1oj201111X1130120X25000-1gj在初始表中，所有0,≤0，所以初始基可行解就是最优解，X"=(0,1,1,0)T，2=5。由于非基变量xi的检验数1=0，把xi作为入基变量，x3作为出基变量换基迭代，得到第二表，从中得到另一个最优解X2*=(1,3,0,0)T。则凸组合aX+(1一α)X2（0≤α≤1)都是原规划的最优解。2.关于退化解的说明例2求解线性规划问题

重点难点考点剖析 一、关于单纯形法的补充说明 1．无穷多最优解与唯一最优解的判别法则 设 X*是线性规划问题的基 B 对应的可行解，（1）所有检验数σj≤0，有非基变量 xk 的 检验数等于 0，且确定的  0 ，则问题有无穷多最优解；（2）所有非基变量的检验数σj<0， 则问题有唯一最优解。 证明 （1）此时按法则 1，X1已是最优解，设目标函数最优值为 z *，以 xk 为换入变量进 行迭代运算，可得另一基可行解 X**，由于σk=0，换入 xk 后，目标函数值不变，故 X**也 是最优解。所以对于区间[0，1]之中的所有实数α，αX*+（1－α）X**都是最优解。 （2）设 Y*是线性规划问题的任意一个最优解，则有：   C Y C Y C B b C C B NY C B b Y z CY C ,C B * B N B N * N N * B B N* B N * 1 1 1 * YB                  所 以   0 1    * CN CB B N YN ， 故  0 * YN ， 而   BY b Y AY B,N *B * * B          0 ， 所 以 *B * YB  B b  X 1 ，因此最优解唯一。 例 1 求解线性规划问题                 0 2 - 2 1 1 2 4 1 2 3 4 1 2 4 1 3 4 1 2 3 4 x ,x ,x ,x x x x x x x max z x x x x 的最优解的类型。 解： 取 x3，x2作为基变量，直接列表求解： 表 1 单纯形表 cj 2 1 4 1 CB XB b x1 x2 x3 x4 4 1 x3 x2 1 1 [1] -2 0 1 1 0 1 -2 σj 5 0 0 0 -1 2 1 x1 x2 1 3 1 0 0 1 1 2 1 0 σj 5 0 0 0 -1 在初始表中，所有σj≤0，所以初始基可行解就是最优解，X1 *=(0,1,1,0)T，z *=5。由于 非基变量 x1的检验数σ1=0，把 x1作为入基变量，x3作为出基变量换基迭代，得到第二表， 从中得到另一个最优解 X2 *=(1,3,0,0)T。则凸组合αX1 *+(1－α)X2 * (0≤α≤1)都是原规划 的最优解。 2．关于退化解的说明 例 2 求解线性规划问题

maxz=x,+x2+4x,-X4[x+x -x4=2X+x,+x=2[X.x2,X3,x4≥0解：取x1，X2作为基变量，直接列表求解：表2退化线性规划的单纯形法114-1CjXB6CBXiX2X4X31210-1[1] xi210111X242oj00-142101-1X301-110[2] X28-20010j241/21/210X3-10-1/21/201X48-3/2-1/200aj从第二个单纯形表看到，可行解中有等于0的基变量（x2=0）。这样的基可行解称为退化可行解。在有退化解的情况下，当换出变量正好是其值为0的变量时，迭代前后目标函数值不会发生变。此时就可能出现这样的情况：经过若干次选代之后，又转回到原来的基可行解，计算过程出现循环，无法得到最优解。人们已经发现了这样的实例。为了防止循环，最简单的方法是对代法则作如下修改和补充。（1）若有几个变量的检验数大于0，选其中下标最小者入基；（2）若有几个比值均为最小时，选对应下标最小的变量出基。按上述法则去做，一定能防止循环。但在实际问题中，循环是极为罕见的，平常人们还是采用原法则进行计算。3.目标函数是求最小值的情况线性规划的标准形式也可以取作求最小值，只是在判别最优解时的检验数与求最大值的检验数相差一个符号，即所有≥0，则已得最优解；否则，进行换基送代，换入变量确定法则改为：如果minglo，<0=0k，则x为换入变量。单纯形法的其他计算过程完全无须改变

                0 2 2 4 1 2 3 4 2 3 4 1 3 4 1 2 3 4 x ,x ,x ,x x x x x x x max z x x x x 解：取 x1，x2作为基变量，直接列表求解： 表 2 退化线性规划的单纯形法 cj 1 1 4 -1 CB XB b x1 x2 x3 x4 1 1 x1 x2 2 2 1 0 0 1 [1] 1 -1 1 σj 4 0 0 2 -1 4 1 x3 x2 2 0 1 -1 0 1 1 0 -1 [2] σj 8 -2 0 0 1 4 -1 x3 x4 2 0 1/2 -1/2 1/2 1/2 1 0 0 1 σj 8 -3/2 -1/2 0 0 从第二个单纯形表看到，可行解中有等于 0 的基变量（x2=0）。这样的基可行解称为退 化可行解。在有退化解的情况下，当换出变量正好是其值为 0 的变量时，迭代前后目标函数 值不会发生变。此时就可能出现这样的情况：经过若干次迭代之后，又转回到原来的基可行 解，计算过程出现循环，无法得到最优解。人们已经发现了这样的实例。为了防止循环，最 简单的方法是对迭代法则作如下修改和补充。 （1）若有几个变量的检验数大于 0，选其中下标最小者入基； （2）若有几个比值均为最小时，选对应下标最小的变量出基。 按上述法则去做，一定能防止循环。但在实际问题中，循环是极为罕见的，平常人们还 是采用原法则进行计算。 3．目标函数是求最小值的情况 线性规划的标准形式也可以取作求最小值，只是在判别最优解时的检验数与求最大值的 检验数相差一个符号，即所有σj≥0，则已得最优解；否则，进行换基迭代，换入变量确定 法则改为：如果  j j  k j min    0   ，则 xk为换入变量。单纯形法的其他计算过程完全无 须改变

二、灵敏度分析和影子价格-案例分析一企业利用甲、乙、丙三种资源，生产A、B、C三种产品，两种资源的数量、产品的单耗以及现有资源数量如下表：表3原材料消耗单产原料总量位BcA消(吨)品原耗料甲13190乙21480115丙45543单位产品收益（万元）问题：（1）怎么安排生产使总收益最大？（2）确定每种原材料的影子价格。（3）产品价格在什么范围波动时不影响最优解？（4）原材料在什么范围波动时不影响产品结构？（5）增加原材料丁的强制性约束2x+x2+3x，=70的约束，对最优解是否有影响，如果有影响，确定新的最优解和影子价格。（6）如果产品的研发使产品C的消耗系数改变到（4，1，1）T，产品质量也有改善，所以价格有原来的3万元增加到了5万元，该研发成果是否可以采纳？分析：设产品A、B、C的产量分别为x1I、x2、x3，则问题归结为求maxz=5x,+4x2+3x3[x +3x, +x,≤902x,+x,+4x,≤80Xi+X2+5x≤45[x,x, ≥0用QSB求解得表4最优解对应的单纯形表X1X2X3Slack_C1Slack_C2Slack_C33.00BasisCi5.004.00000R.H.S.Ratio0Slack_C100-16.001.002.00-5.0025.00X101.001.0035.005.001.000-1.000X24.0001.006.00-1.002.0010.0000-1.00COzO0-16.00-3.00215.00

二、灵敏度分析和影子价格——案例分析 一企业利用甲、乙、丙三种资源，生产 A、B、C 三种产品，两种资源的数量、产品的 单耗以及现有资源数量如下表： 表 3 原材料消耗 A B C 原料总量 （吨） 甲 乙 丙 1 2 1 3 1 1 1 4 5 90 80 45 单位产品收益（万元） 5 4 3 问题： （1）怎么安排生产使总收益最大？ （2）确定每种原材料的影子价格。 （3）产品价格在什么范围波动时不影响最优解？ （4）原材料在什么范围波动时不影响产品结构？ （5）增加原材料丁的强制性约束 2x1  x2  3x3  70 的约束，对最优解是否有影响，如 果有影响，确定新的最优解和影子价格。 （6）如果产品的研发使产品 C 的消耗系数改变到（4，1，1）T，产品质量也有改善，所以 价格有原来的 3 万元增加到了 5 万元，该研发成果是否可以采纳？ 分析：设产品 A、B、C 的产量分别为 x1、x2、x3，则问题归结为求                   0 5 45 2 4 80 3 90 5 4 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 x ,x x x x x x x x x x max z x x x 用 QSB 求解得 表 4 最优解对应的单纯形表 产 品 单 位 消 原 耗 料

表5最优解综合表16200912:35:12SundayAugustDecisionSolutionUnit Cost orTotalReducedBasisAllowableAllowableVariableValueProfit cli)ContributionCostStatusMin. clilMax.cli)1X135.005.0004.008.00175.00basic2X2010.004.0040.002.505.00basic3X303.000-16.00-M19.00at bound215.00ObjectiveFunction[Max.] =LeftRight HandSlackShadowAllowableAllowableConstraintHandDirectionSideMin.RHSMax.RHSorSurplusPriceC165.00<=90.000M25.0065.002C280.0080.0001.0067.5090.00<=3C3045.00<=45.003.0040.0050.00从表5看出：(1)当xI=35，x2=10，x3=0时收益最大，最大收益是≥=215。(2)影子价格yI=0，y2=1，y3=3。（3）产品A的价格在[4，8]范围内，产品B的价格在[2.5，5]范围内，产品C的价格在（一8，19）范围内（注意这里指的是单个产品的价格波动情况）波动时不会影响最优解。（4）原材料甲有剩余，剩余量是25，所以原材料甲在（65，8）范围内波动时部位影响原最优解；原材料乙没有剩余，它的波动会影响最优解，但是在[67.5，90]之间波动时不会改变原来生产的产品结构：原材料内也没有剩余，它的波动也会影响最优解，但是在[40，50]】之间波动时不会改变原来生产的产品结构（5）最优解xI=35，x2=10，x3=0不满足约束条件2x,+xz+3x=70，所以给约束已经影响了最优解。在该约束中添加人工变量x7，并将该约束条件放到表4中得：表6添加约束条件的灵敏度分析表543000-MCBXBx3B-bX2x4xsx6X1X72-5000-161025X45-13510-1010X140160-12010x2230-M100170X7600-160-1-302152-50000125-16x451I0-101-1035x141I02006[-1] 10 x2-M00-10-101-10x7000-160-1-3021502000-181-55X4

表 5 最优解综合表 从表 5 看出： （1） 当 x1=35，x2=10，x3=0 时收益最大，最大收益是 z = 215。 （2） 影子价格 y1=0，y2=1，y3=3。 （3）产品 A 的价格在 [4，8] 范围内，产品 B 的价格在 [2.5，5] 范围内，产品 C 的 价格在 （－∞，19] 范围内（注意这里指的是单个产品的价格波动情况）波动时不会影响 最优解。 （4）原材料甲有剩余，剩余量是 25，所以原材料甲在（65，∞） 范围内波动时部位 影响原最优解；原材料乙没有剩余，它的波动会影响最优解，但是在 [67.5，90] 之间波动 时不会改变原来生产的产品结构；原材料丙也没有剩余，它的波动也会影响最优解，但是在 [40，50] 之间波动时不会改变原来生产的产品结构 （5）最优解 x1=35，x2=10，x3=0 不满足约束条件 2x1  x2  3x3  70 ，所以给约束 已经影响了最优解。在该约束中添加人工变量 x7，并将该约束条件放到表 4 中得： 表 6 添加约束条件的灵敏度分析表 5 4 3 0 0 0 -M CB XB x1 x2 x3 x4 x5 x6 x7 B -1b 0 x4 0 0 -16 1 2 -5 0 25 5 x1 1 0 -1 0 1 -1 0 35 4 x2 0 1 6 0 -1 2 0 10 -M x7 2 1 3 0 0 0 1 70 σ 0 0 -16 0 -1 -3 0 215 0 x4 0 0 -16 1 2 -5 0 25 5 x1 1 0 -1 0 1 -1 0 35 4 x2 0 1 6 0 [-1] 2 0 10 -M x7 0 0 -1 0 -1 0 1 -10 σ 0 0 -16 0 -1 -3 0 215 0 x4 0 0 -18 1 0 -5 2 5

-200510-1251X17240100-120X20001010-110X50000-150-3-M-1205所以，增加约束条件2x，+x，+3x，=70后的最优解为x1=25，x2-20，x3=0，最大收益是==205：此时原材料甲剩余5个单位，影子价格y1=0，原材料乙剩余10个单位，影子价格y2=0，原材料丙没有剩余，影子价格y3=3，原材料丁没有剩余，影子价格y4=1，（6）这是非基变量的技术系数波动的情况，我们直接计算改变量的检验数(4121B-100(4)15-(0,5,4)CRB-==1>0-Ca=C(1)(1)将向量（1，0，1）T换入最优表中得：所以，研制成果可以采纳，表7研发成果分析表550004B-"bCBXBXIX2x3x4x5x6200011-525x4510001-135x101024[1]-110 x200-301-1215000013-7-115x4510001-135x12.50110-110x30022500-10-5采纳研制的新成果后，最优解为xi=35，x2=0，x3=10，最大收益是：=225；此时原材料甲剩余15个单位，影子价格y1=0，原材料乙没有剩余，影子价格y2=0，原材料丙没有剩余，影子价格y3=5由于非基变量xs的检验数为0，故该问题有无穷多个解，继续换基送代得：研发成果分析表表8500540XBB-bCBxiX2X6x3x4x500-101[3] -715x4001510-135x102105011-1X32250000-50-1

5 x1 1 0 -2 0 0 -1 1 25 4 x2 0 1 7 0 0 2 -1 20 0 x5 0 0 1 0 1 0 -1 10 σ 0 0 -15 0 0 -3 -M-1 205 所以，增加约束条件 2x1  x2  3x3  70 后的最优解为 x1=25，x2=20，x3=0，最大收 益是 z = 205；此时原材料甲剩余 5 个单位，影子价格 y1 = 0，原材料乙剩余 10 个单位，影 子价格 y2 = 0，原材料丙没有剩余，影子价格 y3 = 3，原材料丁没有剩余，影子价格 y4 =1， （6）这是非基变量的技术系数波动的情况，我们直接计算改变量的检验数                               1 0 1 1 1 4 0 1 2 0 1 1 1 2 5 1 1 4 1 B   1 0 1 0 1 5 0 5 4 1 1 4 1 1 1                     c C B , ,  B 所以，研制成果可以采纳，将向量（1，0，1）T 换入最优表中得： 表 7 研发成果分析表 5 4 5 0 0 0 CB XB x1 x2 x3 x4 x5 x6 B-1b 0 x4 0 0 1 1 2 -5 25 5 x1 1 0 0 0 1 -1 35 4 x2 0 1 [1] 0 -1 2 10 σ 0 0 1 0 -1 -3 215 0 x4 0 -1 0 1 3 -7 15 5 x1 1 0 0 0 1 -1 35 5 x3 0 1 1 0 -1 2 10 σ 0 -1 0 0 0 -5 225 采纳研制的新成果后，最优解为 x1=35，x2=0，x3=10，最大收益是 z = 225；此时原材料 甲剩余 15 个单位，影子价格 y1 = 0，原材料乙没有剩余，影子价格 y2 = 0，原材料丙没有剩 余，影子价格 y3 = 5 由于非基变量 x5 的检验数为 0，故该问题有无穷多个解，继续换基迭代得： 表 8 研发成果分析表 5 4 5 0 0 0 CB XB x1 x2 x3 x4 x5 x6 B -1b 0 x4 0 -1 0 1 [3] -7 15 5 x1 1 0 0 0 1 -1 35 5 x3 0 1 1 0 -1 2 10 σ 0 -1 0 0 0 -5 225