《数学建模》课件：第8章 离散模型(投影版)

1、数 学 建 模,主讲教师：邵红梅,第八章 离散模型,层次分析模型,日常工作、生活中的决策问题,涉及经济、社会等方面的因素,作比较判断时人的主观选择起相当大的作用，各因素的重要性难以量化,Saaty于1970年代提出层次分析法AHP(Analytic Hierarchy Process),AHP一种定性与定量相结合的、系统化、层次化的分析方法,层次分析模型,层次分析模型,选择旅游地,如何在3个目的地中按照景色、费用、居住条件等因素选择.,层次分析模型,思维过程,将决策问题分解为3个层次，最上层为目标层，即选择旅游地，最下层为方案层，有P1，P2，P33个供选择地点，中间层为准则层，有景色、费用、

2、居住、饮食、旅途5个准则，各层间的联系用相连的直线表示。,通过相互比较确定各准则对于目标的权重，及各方案对于每一准则的权重。这些权重在人的思维过程中通常是定性的，而在层次分析法中则要给出得到权重的定量方法。,将方案层对准则层的权重及准则层对目标层的权重进行综合，最终确定方案层对目标层的权重。在层次分析法中要给出进行综合的计算方法。,层次分析法将定性分析与定量计算结合起来完成上述步骤，给出决策结果。,层次分析模型,层次分析法的基本步骤,成对比较矩阵和权向量,不把所有因素放在一起比较，而是两两相互对比,对比时采用相对尺度，以尽可能地减少性质不同的诸因素相互比较的困难，提高准确度。,人们凭自己的经验

3、和知识进行判断， 当因素较多时给出的结果往往是不全面和不准确的， 如果只是定性的结果，则常常不容易被别人接受。,假设要比较某一层n个因素C1，C2，Cn对上层一个因素O的影响，如旅游决策问题中比较景色等5个准则在选择旅游地目标中的重要性。,每次取两个因素Ci和Cj，用aij表示Ci和Cj对O的影响之比，全部比较结果可用成对比较矩阵 。,正互反矩阵,层次分析模型,比较尺度,Saaty等人提出用1 9尺度，即aij的取值范围是1，2，9及其互反数1，12，19。,在进行定性的成对比较时，人们头脑中通常有5种明显的等级，用1 9尺度可以方便地表示如下：,心理学家认为，进行成对比较的因素太多，将超出人

4、的判断能力，最多大致在72范围。如以9个为限，用19尺度表示它们之间的差别正合适。,Saaty曾用13，15，117，(d + 0.1) (d + 0.9) (d = 1，2，3 ,4 )，1p 9p ( p = 2，3，4，5)等共27种比较尺度，对在不同实例构造成对比较阵，并算出权向量。与实际对比发现，19尺度不仅在较简单的尺度中最好，而且结果并不劣于较复杂的尺度。,aij =1，1/2，1/9：Ci与Cj的影响之比为上面aij的互反数,层次分析模型,怎样由成对比较阵确定诸因素C1 ，Cn对上层因素O的权重呢?,C1与C2之比为1：2,C1与C3之比为4：1,C2与C3之比应为8：1,不一

5、致,允许不一致，但要确定不一致的允许范围,考察完全一致的情况,设想把一块单位重量的大石头O砸成n块小石头C1 ，Cn，如果精确地称出它们的重量为w1 ，wn，在作成对比较时令aij = wi / wj,权重用向量w = (w1 ，w2，wn)T 表示,A的各个列向量与w仅相差一个比例因子,层次分析模型,aij = wi / wj,ajk = wj / wk,aij ajk=(wi / wj) (wj / wk)= wi / wk= aik,如果一个正互反阵A满足aij ajk = aik , i，j，k = 1，2，n则A称为一致性矩阵，简称一致阵。,一致阵,n阶一致阵A有下列性质,A的秩为1

6、，A的惟一非零特征根为n,A的任一列向量都是对应于特征根n的特征向量,A的归一化特征向量可作为权向量,表示诸因素C1 ，Cn对上层因素O的权重,对于不一致(但在允许范围内)的成对比较阵A，建议用对应于最大特征根的特征向量作为权向量w ，即A w = A ,因为矩阵A的特征根和特征向量连续地依赖于矩阵的元素aij， 所以当aij离一致性的要求不远时， A的特征根和特征向量也与一致阵的相差不大。,由成对比较阵求权向量的特征根法,层次分析模型,一致性检验,对A确定不一致的允许范围,n阶一致阵A的惟一非零特征根为n,n 阶正互反阵A的最大特征根n，而当= n时A是一致阵,稍后将加以证明,连续地依赖于a

7、ij,比n大得越多，A的不一致程度越严重，用特征向量作为权向量引起的判断误差越大。,可以用 n数值的大小来衡量A的不一致程度,定义,为一致性指标,CI = 0时A为一致阵；CI越大A的不一致程度越严重。,A的n个特征根之和等于n，所以CI相当于除外其余n1个特征根的平均值。,A的n个特征根之和等于A的迹,层次分析模型,为了确定A的不一致程度的容许范围，需找出衡量A的一致性指标CI的标准。,引入随机一致性指标RI,随机地构造正互反阵A (它的元素aij ( i j )从19，11/9中随机取值),计算A的一致性指标CI,A是非常不一致的，它的CI相当大。如此构造相当多的A，用它们的CI的平均值作

8、为随机一致性指标,表中n = 1，2时RI = 0，是因为1，2阶的正互反阵总是一致阵。,对于n3的成对比较阵A，将它的一致性指标CI与同阶(指n相同)的随机一致性指标RI之比称为一致性比率CR。,A的不一致程度在容许范围之内，可用其特征向量作为权向量：通过一致性检验,0.1的选取是带有一定主观信度的,层次分析模型,“选择旅游地”中准则层对目标的权向量及一致性检验,最大特征根=5.073,权向量(特征向量)w =(0.263,0.475,0.055,0.090,0.110)T,一致性指标,随机一致性指标RI=1.12 (查表),一致性比率CR=0.018/1.12=0.0160.1,通过一致性

9、检验,当检验不通过时， 要重新进行成对比较， 或对已有的A进行修正。,层次分析模型,组合权向量,记第2层(准则)对第1层(目标)的权向量为w(2) = (w1(2) ，w2(2)，wn(2)T,用同样的方法构造第3层(方案层)对第2层的每一个准则的成对比较阵,这里矩阵Bk ( k = l，5)中的元素bij(k)是方案(旅游地)Pi与Pj对于准则Ck(景色、费用等)的优越性的比较尺度。,层次分析模型,n = 3时随机一致性指标RI = 0.58，所以面的CI k均可通过一致性检验。,W(2) =(0.263,0.475,0.055,0.090,0.110)T,由各准则对目标的权向量w(2)和各

10、方案对每一准则的权向量wk(3)(k = 1，5)， 计算各方案对目标的权向量，称为组合权向量，记作w(3)。 对于方案P1，它在景色等5个准则中的权重用wk(3)的第1个分量表示(表中wk(3)的第1行)， 而5个准则对于目标的权重又用权向量w(2)表示， 所以方案P1在目标中的组合权重应为它们相应项的两两乘积之和。,方案P1对目标的组合权重,0.5950.263+0.0820.475+0.4290.055+0.6330.099+0.1660.110 = 0.300,同样可以算出P2，P3在目标中的组合权重为0.246和0.456，于是组合权向量w(3) = (0.300，0.246，0.4

11、56)T。,层次分析模型,对于3个层次的决策问题，若第1层只有1个因素，第2、3层分别有n，m个因素,记第2，3层对第1，2层的权向量分别为,w(2) = (w1(2)，wn(2)T wk(3) = (wk1(3)，wkm(3)T ，k = 1，2，n,以wk(3)为列向量构成矩阵,W(3) = w1(3)，wn(3) ,第3层对第1层的组合权向量为,w(3) = W(3) w(2),若共有s层，则第k层对第1层(设只有1个因素)的组合权向量满足,w(k) = W(k) w(k1) ，k = 3，4，s,其中W(k)是以第k层对第k 1层的权向量为列向量组成的矩阵。,最下层(第s层)对最上层的

12、组合权向量为w(s) = W(s) W(s-1) W(3) w(2),层次分析模型,组合一致性检验,在重大决策时，除了对每个成对比较阵进行一致性检验外，还常要进行组合一致性检验，以确定组合权向量是否可以作为最终的决策依据。,组合一致性检验可逐层进行,若第p层的一致性指标为CI1(p)，CIn(p)(n是第p 1层因素的数目)，随机一致性指标为PI1(p)，PIn(p)，定义,CI(p) = CI1(p)，CIn(p)w(p-1) ，RI(p) = RI1(p)，RIn(p)w(p-1),第p层的组合一致性比率为,第p层通过组合一致性检验的条件为CR(p) 0.1,定义最下层(第s层)对第1层的

13、组合一致性比率为,仅当CR*适当地小时，才认为整个层次的比较判断通过一致性检验。,旅游决策问题中可以算出CI(3) = 0.00176，RI(3) = 0.58CR(3) = 0.003。 前面已经有CR(2) = 0.016，于是CR*= 0.019，组合一致性检验通过， 前面得到的组合权向量w(3)可以作为最终决策的依据。,层次分析模型,层次分析法的基本步骤,建立层次结构模型,构造成对比较阵,计算权向量并做一致性检验,计算组合权向量并做组合一致性检验,深入分析实际问题，将有关因素自上而下分层（目标准则或指标方案或对象），上层受下层影响，而层内各因素基本上相对独立。,用成对比较法和19尺度，

14、构造各层对上一层每一因素的成对比较阵。,对每一成对比较阵计算最大特征根和特征向量，作一致性检验，若通过，则特征向量为权向量。,组合权向量可作为决策的定量依据。,层次分析模型,层次分析法的广泛应用,应用领域：经济计划和管理，能源政策和分配，人才选拔和评价，生产决策，交通运输，科研选题，产业结构，教育，医疗，环境，军事等。,处理问题类型：决策、评价、分析、预测等。,建立层次分析结构模型是关键一步，要有主要决策层参与。,构造成对比较阵是数量依据，应由经验丰富、判断力强的专家给出。,层次分析模型,层次分析法的若干问题,正互反阵的最大特征根是否为正数？特征向量是否为正向量？一致性指标能否反映正互反阵接近

15、一致阵的程度？,怎样简化计算正互反阵的最大特征根和特征向量？,为什么用特征向量作为权向量？,当层次结构不完全或成对比较阵有空缺时怎样用层次分析法？,层次分析模型,正互反阵最大特征根和对应特征向量的性质,正互反阵是否存在正的最大特征根和正的特征向量？,一致性指标的大小是否反映它接近一致阵的程度？,定理1 对于正矩阵A(A的所有元素为正数)，,A的最大特征根是正单根；,A对应正特征向量w(w的所有分量为正数)；,其中e=(1，1，1)T， w是对应的归一化特征向量。,定理2 n阶正互反阵A的最大特征根n；当 = n时A是一致阵。,n阶正互反阵A是一致阵的充要条件为，A的最大特征根 = n。,和法取

16、列向量的算术平均,层次分析模型,正互反阵最大特征根和特征向量的实用算法,成对比较阵是通过定性比较得到的比较粗糙的量化结果，对它作精确计算是不必要的，所以完全可以用简便的近似方法计算其特征根和特征向量。,将A的每一列向量归一化得,对,按行求和得,将,归一化,w = (w1,w2,，wn)T即为近似特征向量；,计算,作为最大特征根的近似值。,这个方法实际上是将A的列向量归一化后取平均值，作为A的特征向量。,层次分析模型,幂法迭代算法,任取n维归一化初始向量w(0),计算,归一化，即令,对于预先给定的精度，当,时，w(k+1)即为所求的特征向量；否则返回b；,计算最大特征根,层次分析模型,精确计算给

17、出w = (0.588，0.322，0.090)T， = 3.010。二者相比，相差甚微。,列向量 归一化,按行求和,归一化,以和法计算一个例子,层次分析模型,为什么用成对比较阵的特征向量作为权向量,当成对比较阵A是一致阵时，aij与权向量w = (w1，wn)T的关系满足aij = wi / wj,当A不是一致阵时，权向量w的选择应使得aij与wi / wj相差(对所有的i，j)尽量地小。,如果从拟合的角度看，确定w可以化为最小二乘问题,非线性最小二乘,对数最小二乘,最小二乘权向量一般与特征根法得到的不同,与根法得到结果的相同,层次分析模型,不完全层次结构中组合权向量的计算,完全层次结构：上

18、层每一元素与下层所有元素相关联,出现在各准则层中的不完全性，将不支配的那些因素的权向量分量简单地置0，就可以用完全层次结构的办法处理。,如果不完全结构出现在准则层与方案层之间,学校要评价教师的贡献，粗略地只考虑教学与科研两个指标，若P1，P2，P3，P4 4位教师中P1，P2只从事教学，P3只搞科研，P4则二者兼顾，C1，C2支配因素的数目不等。,层次分析模型,先看看将不支配因素的权向量分量简单置0,设C1，C2对第1层的权向量w(2) = (w1(2)，w2(2)T已经确定,C1支配第3层的因素P1，P2，P3，C2支配P3，P4,记两个权向量为w1(3) = (w11(3)，w12(3)，

19、w13(3)，0)T和w2(3) = (0，0，w23(3)，w24(3)T,w(3) = W(3) w(2) ，W(3) = (w1(3)，w2(3)T,考察一个特殊情况：教学与科研两个准则的重要性相同，即w(2) =(1/2，1/2)T，4位教师不论从事教学或科研，能力都相同，即w1(3) = (1/3，1/3，1/3，0)T，w2(3) = (0，0，1/2，1/2)T。,公正的评价应是，被安排只搞教学或科研的P1，P2，P4 3人的贡献相同，而P3的贡献为他们的一倍。,w(3) = (1/6，1/6，5/12，1/4)T,层次分析模型,怎样才能得到合理的结果呢?,支配因素越多，权重越大

20、的修正办法,支配元素越多，权重越小的修正办法,用支配因素的数量对权向量w(2)进行加权，修正为,计算w(3),C1，C2支配因素的数量分别记为n1，n2,n1 = 3，n2 = 2,w(3) = (1/5，1/5，2/5，1/5)T,右端的分母是归一化的需要,用支配因素数量的倒数对w(2)加权,层次分析模型,成对比较阵残缺时的处理,某种原因会无法或不愿对某两个因素给出相互对比的结果aij，于是成对比较阵出现残缺(不能补0，因为要求aij0),记由A要计算的权向量为w = (w1，w2，w3)T，用w1 / w3代替残缺的a13是合理的,表示残缺,辅助矩阵,C w = w,将A修正,不难验证,w = (0.5714，0.2857，0.14