中国高校课件下载中心 》 教学资源 》 大学文库

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

文档信息
资源类别:文库
文档格式:PDF
文档页数:11
文件大小:265.28KB
团购合买:点击进入团购
内容简介
《运筹学》课程教学资源(试卷习题)重点难点考点剖析
刷新页面文档预览

重点难点考点部析一、关于单纯形法的补充说明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

050-1/301/3 -7/3X4151/3 30x110-1/304/31550-1/311/30-7/3x30022500>0-5得到另一个最优解为xi=30,x2=0,x3=15,从而可以得到无穷多个最优解。三、表上作业法中需要说明的问题(1)无穷多最优解当选代到运输问题的最优解时,如果有某非基变量的检验数等于零,则说明该运输问题有多重(无穷多)最优解,如上述例题4.1。(2)退化当运输问题某部分产地的产量和,与某一部分销地的销量和相等时,在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列,这时就出现了退化。在运输问题中,退化解是时常发生的。为了使表上作业法的迭代工作进行下去,退化时应在同时划去的一行或一列中的某个格中填入数字0,表示这个格中的变量是取值为0的基变量,使迭代过程中基可行解的分量恰好为(m+n-1)个。四、动态规划求解一一复合系统工作可靠性问题某个机器工作系统由n个部件串联而成,其中只要有一个部件失效,则整个系统不能正常工作,因此为了提高系统工作的可靠性,在设计时,每个主要部件上都装有备用元件,一旦某个主要部件失效,备用元件会自动投入系统工作,显然备用元件越多,系统工作可靠性越大,但是备用元件越多,系统的成本、重量、体积相应增大,工作精度降低,因此在上述限制条件下,应选择合理的备用元件数,使整个系统的工作可靠性最大。例3某电子仪器由三个串联的组件(j=1,2,3)构成,因而有一个组件失效,仪器即无法工作。为提高该仪器可靠性,每个组件中可增加并联的备用条件数。用R,代表各组件的可靠性,k,代表j组中并联的元件数,c,代表并联不同元件时第j各组件的相应费用,有关数据见表9。若限定用于仪器中组件的总费用不超过1000元。试确定使该仪器可靠性为最高的设计方案。表9j=1j=2j=3组件k,RCIC,C3R2R,11000.83000.50.620020.82000.85000.740030.90.90.9300600500解:(1)建立动态规划模型对第k个组件确定并联元件数作为第k个阶段的决策,k=1,2,3;S一一对第k,k+1,,3个组件确定并联元件数时可用的费用

0 x4 0 -1/3 0 1/3 1 -7/3 5 5 x1 1 1/3 0 -1/3 0 4/3 30 5 x3 0 -1/3 1 1/3 0 -7/3 15 σ 0 -1 0 0 0 -5 225 得到另一个最优解为 x1=30,x2=0,x3=15,从而可以得到无穷多个最优解。 三、表上作业法中需要说明的问题 (1)无穷多最优解 当迭代到运输问题的最优解时,如果有某非基变量的检验数等于零,则说明该运输问题 有多重(无穷多)最优解,如上述例题 4.1。 (2)退化 当运输问题某部分产地的产量和,与某一部分销地的销量和相等时,在迭代过程中有可 能在某个格填入一个运量时需同时划去运输表的一行和一列,这时就出现了退化。在运输问 题中,退化解是时常发生的。为了使表上作业法的迭代工作进行下去,退化时应在同时划去 的一行或一列中的某个格中填入数字 0,表示这个格中的变量是取值为 0 的基变量,使迭代 过程中基可行解的分量恰好为 (m  n 1) 个。 四、动态规划求解——复合系统工作可靠性问题 某个机器工作系统由 n 个部件串联而成,其中只要有一个部件失效,则整个系统不能正 常工作,因此为了提高系统工作的可靠性,在设计时,每个主要部件上都装有备用元件,一 旦某个主要部件失效,备用元件会自动投入系统工作,显然备用元件越多,系统工作可靠性 越大,但是备用元件越多,系统的成本、重量、体积相应增大,工作精度降低,因此在上述 限制条件下,应选择合理的备用元件数,使整个系统的工作可靠性最大。 例 3 某电子仪器由三个串联的组件( j  1,2,3)构成,因而有一个组件失效,仪器 即无法工作。为提高该仪器可靠性,每个组件中可增加并联的备用条件数。用 Rj 代表各组 件的可靠性, j k 代表 j 组中并联的元件数, j c 代表并联不同元件时第 j 各组件的相应费用, 有关数据见表 9。若限定用于仪器中组件的总费用不超过 1 000 元。试确定使该仪器可靠性 为最高的设计方案。 表 9 组件 j k j  1 j  2 j  3 R1 C1 R2 C2 R3 C3 1 2 3 0.6 0.8 0.9 100 200 300 0.8 0.8 0.9 300 500 600 0.5 0.7 0.9 200 400 500 解:(1)建立动态规划模型 对第 k 个组件确定并联元件数作为第 k 个阶段的决策, k 1,2,3; k s ——对第 k , k +1,.,3 个组件确定并联元件数时可用的费用

S,=1000,s2 (700,800,900),s, (200,300,400,500,600)u一一第k个组件并联不同数目的元件时的费用,U,={u,|u, =100,200,300且u,≤ si),U,=(uz [uz =300,500,600且uz≤s2)U,=(uslu,=200,400,500且u,≤s),且sk+=S-uk阶段指标函数R(u)=R最优指标函数f(s)表示“第k个阶段状态为S,时采取最优子策略到过程结束时的最高可靠性”J4(s4)=1fr(sk)= max(R : fk+1(Sk+1)),ueUk(2)采用逆序算法k=3时,f(s,)=maxR,得表10。ugeU,表10R,usJs(s,)u,200500S34002000. 50. 52000. 5 3000. 52004000. 50. 70. 74000. 50. 70.95000. 95006000. 50. 70.90.9500k=2时,f,(s2)=max(R2f(s,)),得表11ueU2表11R2- fs(ss)u2J2(s2)u2300500600S27000. 493000.7X0.70.8X0.58000. 633000.7×0.90.8×0.50.9×0.59000.633000.7X0.90.8×0.70.9×0.5fi(s.)=max[R,·f2(s2)),得表6-19k=1时,MED表6-19

1000, {700,800,900}, {200,300,400,500,600} s1  s2  s3  k u ——第 k 个组件并联不同数目的元件时的费用, { | 100,200,300 }, { | 300,500,600 } 1 1 1 1 1 2 2 2 2 2 U  u u  且u  s U  u u  且u  s k k uk U3  {u3 | u3  200,400,500且u3  s3},且s 1  s  阶段指标函数 R uk  Rk ( ) 最优指标函数 ( ) k k f s 表示“第 k 个阶段状态为 k s 时采取最优子策略到过程结束时的最 高可靠性” ( ) max{ ( )}, 1 1    k k k u U k k f s R f s k k f 4 (s4 )  1 (2) 采用逆序算法 k  3 时, ( ) max , 3 3 3 3 3 f s R u U  得表 10。 表 10 u3 3 s R3 ( ) 3 3 f s  3 u 200 400 500 200 300 400 500 600 0.5 0.5 0.5 0.5 0.5 0.7 0.7 0.7 0.9 0.9 0.5 0.5 0.7 0.9 0.9 200 200 400 500 500 k  2时, ( ) max{ ( )} 2 2 2 3 3 2 2 f s R f s u U    ,得表 11 表 11 2 u 2 s ( ) 2 3 3 R  f s ( ) 2 2 f s  2 u 300 500 600 700 800 900 0.7×0.7 0.7×0.9 0.7×0.9 0.8×0.5 0.8×0.5 0.8×0.7 0.9×0.5 0.9×0.5 0.49 0.63 0.63 300 300 300 k 1时, ( ) max{ ( )}, 1 1 1 2 2 f s R f s uk Dk    得表 6-19 表 6-19

R - f2(s2)ufi(s.)ui100200300S10002000.6×0.630.8×0.630.9×0.490.504最优策略为:u,=200,u,=300,u,=500,即第1,2,3个组件应分别并联2个、1个、3个,才能使仪器的可靠性达到最高,此值为0.504。五、利用层次分析法解决较复杂的决策问题1.层次分析法层次分析法(AnalyticHierarchyProcess,AHP)于20世纪70年代中期由美国运筹学家塞蒂(T.L:Saaty)正式提出,它是一种定性和定量相结合的、系统化、层次化的分析方法,用来解决结构较为复杂,准则较多且不易量化的决策问题。层次分析法具有很强的灵活性、实用性和有效性,其基本思路与人对一个复杂的决策问题的思维、判断过程大体上是一样的,对于决策过程中的量化处理,层次分析法以合乎逻辑的方式运用决策者的主观判断来衡量各个指标的相对重要性。层次分析法的基本步骤包括:第1步建立层次结构模型在深入分析实际问题的基础上,将各个相关因素按照不同属性自上而下地分解成若干层次,同一层的诸因素从属于上一层的因素或对上层因素有影响,同时又支配下一层的因素或受到下层因素的作用。最上层为目标层,是整个问题的总目标,通常只有1个因素;最下层为方案层,是解决问题的所有候选方案;中间为准则层,是实现总目标必须考虑的所有标准,可以有一个或几个层次。第2步构建成对比较矩阵从层次结构模型的第2层开始,比较同一层次第i个元素与第个元素相对于上一层某个元素的重要性,比较量化值用ai表示,设共有n个元素参与比较,则得到成对比较矩阵:A=(aj)nxnaj通常在1~9及其倒数间取值,具体意义如下:aj=1,1元素与j元素同等重要;aj=3,i元素比j元素略微重要;aj=5,i元素比j元素重要;aj=7,i元素比元素重要得多;aj=9,i元素比元素极其重要;aj=2n(n=1,2,3,4),i元素比j元素的重要性介于2n-1和2n+1之间;aji=/ay,a=l。第3步计算权向量并做一致性检验计算每个成对比较矩阵的最大特征根入max及对应的特征向量w=(w,w2,,wn)T。由于构建成对比较矩阵时可能出现判断上的不一致,因此需要对其做一致性检验,若检验通过,特征向量即为权向量,即W1,W2,,W给出了同一层诸因素相对于上一层某个因素的按重要程度的一个排序:若检验未通过,需重新构建成对比较矩阵。对于最大特征根及特征向量的计算,可采用线性代数方法求得,在实际应用中,通常采用近似方法计算,主要有方根法与和积法

u1 1 s ( ) 1 2 2 R  f s ( ) 1 1 f s  1 u 100 200 300 1000 0.6×0.63 0.8×0.63 0.9×0.49 0.504 200 最优策略为: 200, 300, 500, 1  2  3     u u u 即第1,2,3 个组件应分别并联 2 个、1 个、3 个, 才能使仪器的可靠性达到最高,此值为 0.504。 五、利用层次分析法解决较复杂的决策问题 1. 层次分析法 层次分析法(Analytic Hierarchy Process,AHP)于 20 世纪 70 年代中期由美国运筹学家 塞蒂(T.L.Saaty)正式提出,它是一种定性和定量相结合的、系统化、层次化的分析方 法,用来解决结构较为复杂,准则较多且不易量化的决策问题。 层次分析法具有很强的灵活性、实用性和有效性,其基本思路与人对一个复杂的决策问 题的思维、判断过程大体上是一样的,对于决策过程中的量化处理,层次分析法以合乎逻辑 的方式运用决策者的主观判断来衡量各个指标的相对重要性。 层次分析法的基本步骤包括: 第 1 步 建立层次结构模型 在深入分析实际问题的基础上,将各个相关因素按照不同属性自上而下地分解成若干层 次,同一层的诸因素从属于上一层的因素或对上层因素有影响,同时又支配下一层的因素或 受到下层因素的作用。最上层为目标层,是整个问题的总目标,通常只有 1 个因素;最下层 为方案层,是解决问题的所有候选方案;中间为准则层,是实现总目标必须考虑的所有标准, 可以有一个或几个层次。 第 2 步 构建成对比较矩阵 从层次结构模型的第 2 层开始,比较同一层次第 i 个元素与第 j 个元素相对于上一层某 个元素的重要性,比较量化值用 aij表示,设共有 n 个元素参与比较,则得到成对比较矩阵: A =(aij)n×n aij通常在 1~9 及其倒数间取值,具体意义如下: aij = 1,i 元素与 j 元素同等重要; aij = 3,i 元素比 j 元素略微重要; aij = 5,i 元素比 j 元素重要; aij = 7,i 元素比 j 元素重要得多; aij = 9,i 元素比 j 元素极其重要; aij = 2n(n = 1,2,3,4),i 元素比 j 元素的重要性介于 2n-1 和 2n+1 之间; aji = 1/ aij,aii = 1。 第 3 步 计算权向量并做一致性检验 计算每个成对比较矩阵的最大特征根λmax 及对应的特征向量 w =(w1,w2,.,wn)T。 由于构建成对比较矩阵时可能出现判断上的不一致,因此需要对其做一致性检验,若检验通 过,特征向量即为权向量,即 w1,w2,.,wn给出了同一层诸因素相对于上一层某个因素的 按重要程度的一个排序;若检验未通过,需重新构建成对比较矩阵。 对于最大特征根及特征向量的计算,可采用线性代数方法求得,在实际应用中,通常采 用近似方法计算,主要有方根法与和积法

1)方根法计算wiw/=/ayi=1,,nV j=l将wi规范化,得到wiw,Wi=i=l,",nwi=l2)和积法按列将比较矩阵A规范化,有ajaj'=ak=l计算wiw/=i=l,"", n将wi规范化,得到wiw'Wi=i=l,",n最大特征根入max的计算(对上述两种方法一致)Zaw1J=lAmax=2w,fel对于一致性检验,需计算一致性指标CICI=(Λmaxn)/ (n-1)一般只要CI≤0.1,就可以认为比较矩阵的一致性是满意的。第4步计算组合权向量并决策设当前层次上的因素为C1,,Cn,相关上一层因素为Bi,,Bm,已经计算得到Bi,,Bm的权重分别为bi,,bm,及Ci,,Cn对每个B的权向量w=(w',w2,,w,)T,则当前层每个因素的组合权系数为:

1)方根法 计算 wi′ wi′ =  n j ij n a 1 i = 1,.,n 将 wi′ 规范化,得到 wi wi =    n i i i w w 1 i = 1,.,n 2)和积法 按列将比较矩阵 A 规范化,有 aij′ =  n k kj ij a a 1 计算 wi′ wi′ =   n j aij 1 i = 1,.,n 将 wi′ 规范化,得到 wi wi =    n i i i w w 1 i = 1,.,n 最大特征根λmax的计算(对上述两种方法一致) λmax =     n i i n j ij j nw a w 1 1 对于一致性检验,需计算一致性指标 CI CI =(λmax-n)/(n-1) 一般只要 CI≤0.1,就可以认为比较矩阵的一致性是满意的。 第 4 步 计算组合权向量并决策 设当前层次上的因素为 C1,.,Cn,相关上一层因素为 B1,.,Bm,已经计算得到 B1,., Bm 的权重分别为 b1,.,bm,及 C1,.,Cn 对每个 Bi 的权向量 wi =(wi1,wi2,.,win)T, 则当前层每个因素的组合权系数为:

Ebwi,b.w.,..,Ebwii=li=liel如此一层层自上而下求下去,一直到最底层(方案层)所有因素的组合权系数求出来为止,它就是各方案优先程度的一个排序,可以据此进行决策。若计D为第k层次上所有因素对上一层相关因素的权向量按列构成的矩阵,则k层次的组合权系数向量为:W=DkX D- X.XD2X Di其中Di=(1)2.应用举例:供应链合作伙伴选择问题(1)建立层次结构模型供应链合作伙伴选择问题一般划分为三个层次,以某供应商选择问题为例,其层次结构模型如图1所示::选择供应商信息共享能力订货提前期研发能力价质量格供应商A供应商B供应商C供应商D图 11)目标层一一选择合作伙伴2)准则层一一选择合作伙伴需要考虑的标准一候选合作伙伴3)方案层一(2)构建成对比较矩阵第二层(准则层)的5个因素相对于总目标的成对比较矩阵如下:价格质量订货提前期研发能力信息共享能力1/312价格11/5质量31331/311/311/53订货提前期53515研发能力1/21/31/31/51信息共享能力第三层(方案层)的4个因素相对于上一层每个因素的成对比较矩阵如下:

m i i biw 1 1 , m i i biw 1 2 ,.,m i i biwn 1 如此一层层自上而下求下去,一直到最底层(方案层)所有因素的组合权系数求出来为 止,它就是各方案优先程度的一个排序,可以据此进行决策。 若计 Dk 为第 k 层次上所有因素对上一层相关因素的权向量按列构成的矩阵,则 k 层次 的组合权系数向量为: Wk = Dk × Dk-1 × . × D2 × D1 其中 D1 =(1) 2. 应用举例:供应链合作伙伴选择问题 (1)建立层次结构模型 供应链合作伙伴选择问题一般划分为三个层次,以某供应商选择问题为例,其层次结构 模型如图 1 所示:: 图 1 1)目标层——选择合作伙伴 2)准则层——选择合作伙伴需要考虑的标准 3)方案层——候选合作伙伴 (2)构建成对比较矩阵 第二层(准则层)的 5 个因素相对于总目标的成对比较矩阵如下: 价格 质量 订货提前期 研发能力 信息共享能力 价格 1 1/3 1 1/5 2 质量 3 1 3 1/3 3 订货提前期 1 1/3 1 1/5 3 研发能力 5 3 5 1 5 信息共享能力 1/2 1/3 1/3 1/5 1 第三层(方案层)的 4 个因素相对于上一层每个因素的成对比较矩阵如下: 选择供应商 供应商 A 供应商 B 供应商 C 供应商 D 价 格 质 量 订 货 提 前 期 研 发 能 力 信 息 共 享 能 力

共11页,试读已结束,阅读完整版请下载
刷新页面下载完整文档
VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
相关文档