运筹学与最优化方法第9章.ppt

第九章层次分析,TheAnalyticHierarchyProcess(AHP),第九章层次分析,在管理中，人们常常需要对一些情况作出决策：例如企业的决策者要决定购置哪种设备，上马什么产品；经理要从若干求职者中决定录用哪些人员；地区、部门官员要对人口、交通、经济、环境等领域的发展规划作出决策。在日常生活中也常会遇到，在多种类不同特征的商品中选购。报考学校选择志愿。毕业时选择工作岗位等。,这一系列的问题，单纯靠构造一个数学模型来求解的方法往往行不通，而用完全主观的定夺也常常表现为举棋不定，而最终选择不理想，甚至不满意的决策方案。面对这样的问题，运筹学者开始了对人们思维决策过程进行分析、研究。,第九章层次分析,美国运筹学家，T.L.Saaty等人在九十年代提出了一种能有效处理这类问题的实用方法，称之为层次分析法（AHP法）T.L.Saaty等曾把它用于电力工业计划，运输业研究，美国高等教育事业1985-2000展望，1985年世界石油价格预测等方面。,第九章层次分析,这种方法的特征：定性与定量相结合，把人们的思维过程层次化，数量化。AHP法作为一种决策方法是在1982年11月召开的中美能源、资源、环境学术会议上，有Saaty学生H.Gholamnezhad首先向中国介绍的。以后层次分析法在中国得到很大的发展，很快应用到能源系统分析，城市规划，经济管理科研成果评价的许多领域。,第九章层次分析,9.1层次分析法的基本步骤运用AHP法进行决策时，大体可以分为4个步骤进行：（1）分析系统中各个因素的关系，建立系统的递阶层次结构；（2）对同一层次的各元素关于上一层次中某一准则的重要性进行两两比较，构造两两比较判断矩阵；,第九章层次分析,（3）由判断矩阵计算被比较元素对于该准则的相对权重；（4）计算各层元素对系统目标的合成权重，并进行排序。,第九章层次分析,一、建立层次分析的结构模型：用AHP分析问题，首先要把问题条理化、层次化，构造层次分析的结构模型。这些层次大体上可分为3类：1、最高层：在这一层次中只有一个元素，一般是分析问题的预定目标或理想结果，因此又称目标层；,第九章层次分析,2、中间层：这一层次包括了为实现目标所涉及的中间环节，它可由若干个层次组成，包括所需要考虑的准则，子准则，因此又称为准则层；3、最底层：表示为实现目标可供选择的各种措施、决策、方案等，因此又称为措施层或方案层。层次分析结构中各项称为此结构模型中的元素。,第九章层次分析,决策目标,准则1,方案1,准则m1,准则2,子准则1,方案2,子准则2,方案mr,子准则m2,方案层,准则层,目标层,第九章层次分析,注：层次之间的支配关系不一定是完全的，即可以有元素（非底层元素）并不支配下一层次的所有元素而只支配其中部分元素。这种自上而下的支配关系所形成的层次结构，我们称之为递阶层次结构。递阶层次结构中的层次数与问题的复杂程度及分析的详尽程度有关，一般可不受限制。,第九章层次分析,为了避免由于支配的元素过多而给两两比较判断带来困难，每层次中各元素所支配的元素一般地不要超过9个，若多于9个时，可将该层次再划分为若干子层。例1、某顾客选购电冰箱时，对市场上正在出售的四种电冰箱考虑6项准则作为评价依据，得到如下层次分析模型：,第九章层次分析,目标层：准则层：方案层：,第九章层次分析,例2、选择科研课题：某研究单位现有3个科研课题，限于人力物力，只能承担其中一个课题，如何选择？考虑下列因素：成果的贡献大小，对人材培养的作用，课题可行性。在成果贡献方面考察：应用价值及科学,第九章层次分析,意义（理论价值，对某科技领域的推动作用）；在课题可行性方面考虑：难易程度（难易程度与自身的科技力量的一致性），研究周期（预计需要花费的时间），财政支持（所需经费，设备及经费来源，有关单位支持情况等）。,第九章层次分析,目标层,第九章层次分析,方案层,准则层,例3、设某港务局要改善一条河道的过河运输条件，为此需要确定是否要建立桥梁或隧道以代替现有轮渡。此问题中过河方式的确定取决于过河方式的效益与代价（即成本）。通常我们用费效比（效益/代价）作为选择方案的标准。为此构造以下两个层次分析的结构模型。,第九章层次分析,准则层,过河的效益A,经济效益B1,社会效益B2,环境效益B3,桥梁D1,隧道D2,渡船D3,收入,c2,岸间商业,c3,节省时间,c1,当地商业,c4,建筑就业,c5,安全可靠,c6,交往沟通,c7,自豪感,c8,舒适,c9,进出方便,c10,美化,c11,第九章层次分析,方案层,目标层,第九章层次分析,目标层,准则层,方案层,二、构造判断矩阵：上、下层之间关系被确定之后，需确定与上层某元素Z（目标A或某个准则Z）相联系的下层元素（x1，x2，xn)各在上层元素Z之中所占的比重。方法：每次取2个元素，如xi，xj，以aij表示xi和xj对Z的影响之比。这里得到的A=(aij)nn称为两两比较的判断矩阵。,第九章层次分析,Saaty建议用19及其倒数做为标度来确定aij的值，19比例标度的含义：xi比xj强（重要）的程度xi/xj相等稍强强很强绝对强aij12345678919标度的理由：两两比较的心理习惯，显然，判断矩阵A的元素有如下特征：,第九章层次分析,1aij02aji=1/aij3aii=1我们称判断矩阵A为正互反矩阵。,第九章层次分析,例如在例2中，准则层B对目标层作因素两两比较，并可建立下面判断矩阵：B1：B2为3B1：B3为1认为人才培养比另二项稍重要，另二项差不多相同重要。,第九章层次分析,判断矩阵B1B2B3B1131A=B21/311/3B3131,第九章层次分析,三、单一准则下元素相对排序权重计算及判断矩阵一致性检验：1、单一准则下元素排序：求判断矩阵A的最大特征值max及标准化（归一化）的特征向量W。W的向量为同一层次中相应元素对于上一层次中某个因素相对重要性的排序权重。有wi0，i，。,第九章层次分析,在构造判断矩阵时，各层元素间两两比较时，aij应有某种传递性质，即若甲比乙重要，乙比丙重要，合理地应有甲比丙更重要，在数值上表示为aijajk=aik即若xi与xj相比aij=3，xj与xk相比ajk=2，那么有传递性的判断应xj与xk相比，ajk=6。,第九章层次分析,2、判断矩阵的一致性概念：判断矩阵是各元素均为正数的矩阵这种正矩阵有下列重要性质。,第九章层次分析,定理设n阶方阵A为正矩阵，max为A的最大模特征值，u=（u1，u2，un)T为max的相应特征向量。、max0，ui0，i=1，2，n、max是单特征根；（因此u除差一常数因子外是唯一的）、A的任何其它特征值，有max|。,第九章层次分析,定义：若正互反矩阵A满足aijajk=aiki，j，k=1，2，n则称A为一致阵。一致阵的重要性质：设A是一致阵，1A的转置亦是一致阵；aij=1/aji，aij=1，i，j=1，2，n；由定义aijajk=aik则显然,第九章层次分析,2A的每一行均为任意指定的另一行的正数倍，从而A的秩为1。（即只有一个非零特征值，其余n-1个为0特征值）；考虑第行元素ai1，ai2，ain对于第k行元素ak1，ak2，aknj=1，2，n，aij=aikakj即第行各元素分别为第k行各元素的aik倍。,第九章层次分析,3A的最大特征根max=n，其余特征根皆为零；4设u=(u1，u2，un)T是A对应max的特征向量，则aij=ui/uji，j=1,2,n容易验证：对于n及向量u=(u1，u2，un)T若aij=ui/ujij则Au=nu(i，)又由定理1及性质2可知max=n，u满足4,第九章层次分析,5若A为判断矩阵，那么A对应于max=n的标准化（归一化）特征向量u=(u1，u2，un)T就是一组排序权向量。（归一化）由性质4即知。1.2进一步地有如下定理定理2、n阶正互反矩阵A=（aij)nn是一致阵的充分必要条件为max=n,第九章层次分析,Proof:“必要性”即是上面性质3已证“充分性”设A的最大特征值为max，相应特征向量u=(u1，un)TAu=maxu分量形式：对i=1，2，n由定理1知ui0，于是max=注意aij=1，max-1=aijuj/ui,第九章层次分析,求和（把i=1，n的各式相加）：nmax-n=aijuj/ui注意aji=1/aij整理上式得：nmax-n=(aijuj/ui+1/aijuj/ui)(),第九章层次分析,*,()式末端=n2-n=n(n-1)注意：当x0时x+(1/x)2当且仅当x=1时等号成立。于是：aij(uj/ui)+(1/aij)(uj/ui)2()式右端2=2(n-1)+(n-2)+2+1=n(n-1)=左端当且仅当aij(uj/ui)=1时等号成立,第九章层次分析,*,*,aij(uj/ui)即aijajk=(ui/uj)(uj/uk)=uj/uk=ajk故A是一致阵。由于客观事物的复杂性与人的认识的多样性，我们得到的判断矩阵常常不具有传递性和一致性，但应该要求这些判断大体是一致的。当判断矩阵过于偏离一致性时，它的可靠性值得怀疑，为此需对判断矩阵进行一致性检验。,第九章层次分析,一致性检验步骤：、计算一致性指标C.I.=(max-n)/(n-1)(ConsisTeneyIndex)、查找相应的平均随机一致性指标R.I.(RandomIndex)115阶正互反矩阵计算1000次得到的平均随机一致性指标：矩阵阶数12345678R.I.000.520.891.121.261.361.41,第九章层次分析,矩阵阶数9101112131415R.I.1.461.491.521.541.561.581.59计算：R.I.=(max-n)/(n-1)，max为m次判断矩阵max的平均值。max产生方法：取定阶数n，随机构造正互反矩阵=（ij)nn，ij在1,2,9,1/2,1/3,1/9这17个数中随机抽取，,第九章层次分析,(只需取n(n-1)/2个，对角元为1，其余按正互反性得到）取充分大的子样计算所有的最大特征值，然后求平均即为max。、计算一致性比率C.R.(consistencyratio)C.R.=C.I./R.I.当C.R.23n有n个线性无关的特征向量u1，u2，unx(0)Rn，则可表示为x(0)=iui,第九章层次分析,利用迭代公式x(k+1)=Ax(k)k=0，1，得到点列x(0)，x(1)，x(2)，显然，x(k+1)=A(k)x0=Akiui=iAkui=iikui=ikiui+i(i/1)kui,第九章层次分析,由于i/11，i=2，3，n当k充分大时有Akx(0)1k1u1于是(Ak+1x(0)i/(Akx(0)i1i=1，2，n特别地，当(Akx(0)j=1时(Ak+1x(0)j1Ak+1x(0)即为特征向量。,第九章层次分析,例：131A=1/311/3取初始向量x=(1，0，0)T131ix1x2x3y1y2y301001001111/3111/311231311/313331311/313,第九章层次分析,第九章层次分析,max=3，u=(3，1，3)T归一化：w=(3/7，1/7，3/7)T,、实用方法,第九章层次分析,此法当矩阵一致性较好时，收敛很快。在实用上常用下面的一些更为简单的方法（仅对近似一致性矩阵适应）。2、方根法：步骤：、求Mi=(aij)1/ni=1，2，n、标准化（归一化）：Wi=Mi/Mj、max=（1/n）(AW)i/Wi,第九章层次分析,EX.131M1=1.4422A=1/311/3M2=0.4807131M3=1.4422w1=0.4286归一化：w2=0.1428w3=0.4286Aw=(1.2856，0.4285，1.2856)Tmax=2.9999,第九章层次分析,3、和积法：步骤：、求（每列归一化）bij=aij/akji，j=1，2n、行求和Mi=biji=1，2，n再归一化：Wi=Mi/Mji=1，2，n、max=(1/n)(AW)i/Wi,第九章层次分析,例：1313/73/73/7M1=9/7A=1/311/3B=1/71/71/7M2=3/71313/73/73/7M3=9/7Mj=3w2=1/7Aw=(9/7，3/7，9/7)Tw3=3/7max=3显然，当A是一致阵时，max=n，对归一化的waij=wi/wj,第九章层次分析,w1=3/7,方根法：Mi=(aij)1/n=Wi/SS=(Wj)1/ni=1，2，n归一化后w即为(w1，w2，wn)Tmax=(1/n)(Aw)i/wi(Aw=nw)=n2/n=n,第九章层次分析,和积法：akj=wk/wjbij=aij/akj=wi/wkMi=bij=(nwi)/wk归一化后w即为(w1，w2，wn)T同理max=n当A近似一致阵时，这些量是近似的。例：125A=1/2131/51/31,第九章层次分析,用幂法：取x(0)=(1，0，0)Tkx1x2x3y1y2y301001100110.50.2110.50.2231.60.566731.5333.188933.01111.60.56673.01111.5314.188243.00371.59590.56533.00371.5313.188253.00371.59590.56533.0037,第九章层次分析,max=3.0037C.I.=(max-3)/(3-1)=0.00185C.R.=C.I./R.I.=0.00185/0.52=0.0036满足一致阵要求。u=(3.0037，1.5959，0.5653)T归一化得：w=(0.5816，0.3090，0.1094)T,第九章层次分析,用方根法：、M1=2.1544M2=1.1447M3=0.4055、归一化：M1+M2+M3=3.7046w1=2.1544/3.7046=0.5815w2=1.1447/3.7046=0.3090w3=0.4055/3.07046=0.1095w=(0.5815，0.3090，0.1095)T,第九章层次分析,3,3,3,3,、Aw=(1.7470，0.9283，0.3388)T11.74700.92830.328830.58150.30900.10953.0037,第九章层次分析,max=,+,+,=,用和积法：、1250.58820.60.5556A=1/213B=0.29410.30.33331/51/310.11770.10.1111、行求和M=(1.7438，0.9274，0.3288)TM1+M2+M3=3归一化：w=(0.5813，0.3091，0.1096)T,第九章层次分析,列归一化,、Aw=(1.7475，0.9286，0.3289)T11.74750.92860.328930.58130.30910.10963.0038,第九章层次分析,max=,+,+,=,二、残缺判断与群组决策：1、残缺判断及处理方法：应用AHP进行决策时，每个准则应有一个判断矩阵，需进行n(n-1)/2次两两比较(判断矩阵的上或下三角)。当层次很多，因素复杂时，判断量很大，可能出现某个参与决策的专家对某些判断缺少把握，或不想发表意见，使判断矩阵残缺。,第九章层次分析,可接受的残缺判断矩阵若任一残缺元素都可通过已给出的元素间接获得的残缺判断矩阵。根据一致性的条件：间接获得的元素指，若aij缺少可由aij=aikakj或更一般地aij=aikakkakkakj得到。,第九章层次分析,1,1,2,3,2,s,可接受的残缺矩阵的排序向量计算常用的有特征根方法，对数最小二乘法及最小偏差法等。特征根法：设A对应max的特征向量w=(w1，w2，wn)T由一致性条件知aij=wi/wj，特征根法即把缺少的的元素用wi/wj来替代。,第九章层次分析,设原判断矩阵A=(aij)nn构造辅助矩阵C=(cij)nn使cij=aij,aij0wi/wj,aij=0例：设120A=1212是可接受的残缺矩阵0121,第九章层次分析,辅助矩阵12w1w3C=1/212w1w31/21解特征根问题：cw=maxw展开：左=（2w1+2w2，1/2w1+w2+2w3，1/2w2+2w3)T=max(w1,w2,w3)T解得：max=3w=(0.5714，0.2857，,0.1429）T,第九章层次分析,可以看出:C的特征值问题等价于220=1/21201/22的特征值问题（Aw=maxw与Cw=maxw相同）,第九章层次分析,故只需求下列矩阵的特征值及特征向量=(aij)nnaij当aij0，ijaij=0当aij=0mi+1当ij时，mi为第i行中残缺元素的个数求解w=maxw可得不完整信息下的排列向量,第九章层次分析,(3)一致性检验：max-nC.I.=(n-1)-（）当C.R.=C.I./R.I.0.1时认为有满意的一致性。,第九章层次分析,2.群组决策：为使决策科学化、民主化，一个复杂系统通常是由多个决策者（专家）或决策部门参与决策的。群组决策问题是指采取一定的方法以使决策者的决策综合成一个较合理的结果的过程。,第九章层次分析,应做好如下工作：重视并做好专家咨询工作；、合理选择咨询对象；（专长及熟悉的领域）、创造适合于咨询工作的良好环境；（介绍AHP方法，提供信息，独立思考）、正确的咨询方法；（通过咨询确定递阶层次结构，设计好表格）,第九章层次分析,、及时分析专家咨询信息，必要时要进行反馈及多轮次咨询群组决策综合分析方法：两类方法：、将各专家的判断矩阵综合，得到综合判断矩阵，再计算排序。,第九章层次分析,、先求各专家判断矩阵的排序向量，再综合成群组排序向量。设S个专家的判断矩阵：Ak=(aij(k)k=1,2,S分别求出它们各自的排序向量wk=(w1(k)，w2(k)wn(k)T,实用中倾向第类方法！,(k),第九章层次分析,再记平均综合向量为w=(w1,w2,wn)T方法1.加权几何平均综合排序向量法：计算wj=wj/（归一化）其中，k0且k为第k个决策者的权重.,j=1,2.n,第九章层次分析,对可采用性的考察：计算wj的标准差：j=其相应于新的总体判断矩阵A=(aij)(aij=wi/wj)的总体标准差：,第九章层次分析,(K),2,ij=个体标准差：（k)=,当总体标准差满足要求时，这组群组判断可采用，当个体标准差(k)满足要求时，认为第k个决策者的决策可通过，否则将信息反馈给有关专家，供修改时参考。,第九章层次分析,(K),2,方法2.加权算术平均综合向量法：计算W=1Wj(1)+2Wj(2)+sWj(s)k0，可类似地根据，式判断可采用性。,第九章层次分析,9.3应用举例一、某工厂有一笔企业留成利润，要决定如何使用。供选择方案：作奖金，集体福利设施，引入设备技术建立如下层次分析模型：,第九章层次分析,目标层：准则层C：方案层P：,第九章层次分析,A-C判断矩阵:AC1C2C3w(2)C111/51/30.105C25130.637C331/310.258max=3.038归一化特征向量w(2)C.I.=0.019C.R.=0.032760.1满意的一致性,第九章层次分析,C1-P:C1P1P2U1(3)P111/30.75P2310.75max=2C.I.=0,第九章层次分析,C2-P:C2P2P3U2(3)P211/50.167P3510.833max=2C.I.=0,第九章层次分析,C3-P:C3P1P3U3(3)P1120.667P21/210.333max=2C.I.=0,第九章层次分析,0.2500.667U(3)=0.750.1670.33300.8330w(3)=U(3)w(2)=(0.198，0.27，0.531)T得到P3优于P1又优于P2，从分配上可以用53.1%来引进新设备，新技术；用19.8%来发奖金；用29.1%来改善福利。,第九章层次分析,二、层次分析法对于下面几种情况的优化问题特别适用：问题中除可计量的量外，还存在不可计量的量时，可用AHP通过对不可计量的量与可计量的量的相对比较，而获得相对的量测；当优化问题的结构难以事先确定，而在很大程度上取决于决策者的经验时；,第九章层次分析,各变量不独立，有内部相关性时；目标与约束，约束与约束之间紧密联系时；多目标问题；,第九章层次分析,在用AHP法解决优化问题时，常用的有两种方式：当模型中涉及不可计量的量时，用AHP法的比例标度来确定目标函数，约束函数的权重（系数）直接采用AHP模型AHP法有广泛的应用前景，可以用来决定其它方面的一些问题。下面举一个解决优化问题的例子。,第九章层次分析,例：最佳食品搭配问题！假设某人有3种食品可供选择：肉，面包，蔬菜它们所含营养成分及单价如下表：食品维生素A维生素B2热量单价搭配量（国际（毫克/克）（千卡/克）（元/克）单价/克）肉0.35270.00212.860.0055X1面包00.00062.760.0012X2蔬菜25.00.0020.250.0014X3,第九章层次分析,该人体重55公斤，每天对各种营养的最小需求为：维生素A：7500国际单位维生素B2：1.6338毫克热量：2050千卡问题：应如何搭配食品？（自然的想法是：使在保证营养的情况下支出最小）,第九章层次分析,容易建立如下线性规划模型：minZ=0.0055x1+0.0012x2+0.0014x3s.t.0.3527x1+25.0 x375000.0021x1+0.0006x2+0.002x31.63382.86x1+2.76x2+0.25x32050 x1，x2，x30利用单纯形法可得解x*=(0,689.44,610.67)Tz*1.67,第九章层次分析,即，不吃肉，面包689.44克，蔬菜610.67克，每日支出1.67元。显然这个最优方案是行不通的，它没有考虑本人对食品的偏好。我们可根据偏好加约束:x1140,x2450,x3不限得到线性规划解：x*=(245.44,450.00424.19)TZ*=2.48元,第九章层次分析,其次，在这里各营养成分被看成同样重要，起决定因素的是支出。但实际上，营养价值与支出都需考虑，只是地位（权重）不同。这样无法建立目标函数。下面用层次分析法来处理问题：层次结构：,第九章层次分析,每日需求R,支出C,营养N,维生素A,维生素B2,维生素Q,肉me,面包br,蔬菜ve,第九章层次分析,对于一个中等收入的人，满足营养要求比支出更重要。于是：RNCw(2)N130.75C1/310.25,max=2C.I.=0,第九章层次分析,NAB2Qw1(3)A1120.4B21120.4Q1/21/210.2max=3C.I.=0,第九章层次分析,0.40w(3)=0.400.250.200.25=(0.3,0.3,0.15,0.25)T01最底层（方案层）对准则层的单排列权重，只需对题目给的数据归一化即可。由于要支出最小价格倒数，价格倒数归一：(181.818，833.333，714.286)T于是得到,第九章层次分析,AB2QC(价格)me0.01390.44680.48720.1057U(4)br0.00000.12770.47020.4819ve0.9861