《《运筹学与最优化方法》课件概要》由会员分享,可在线阅读,更多相关《《运筹学与最优化方法》课件概要(110页珍藏版)》请在金锄头文库上搜索。
1、在管理中,人们常常需要对一些情况作出决策:例如企业的决策者要决定购置哪种设备,上马什么产品;经理要从若干求职者中决定录用哪些人员;地区、部门官员要对人口、交通、经济、环境等领域的发展规划作出决策。 在日常生活中也常会遇到,在多种类不同特征的商品中选购,报考学校选择志愿,毕业时选择工作岗位等。,第10章 层次分析,这一系列的问题,单纯靠构造一个数学模型来求解的方法往往是行不通的,而用完全主观的定夺也常常表现为举棋不定,而最终选择不理想,甚至不满意的决策方案。 面对这样的问题,运筹学者开始了对人们思维决策过程进行分析、研究。,美国运筹学家,T.L.Saaty等人在20世纪70年代提出了一种能有效处
2、理这类问题的实用方法,称之为层次分析法(AHP法)。 T.L.Saaty等曾把它用于电力工业计划,运输业研究,美国高等教育事业19852000展望,1985年世界石油价格预测等方面。,这种方法的特征:定性与定量相结合,把人们的思维过程层次化、数量化。 AHP法作为一种决策方法是在1982年11月召开的中美能源、资源、环境学术会议上,由Saaty学生H.Gholamnezhad首先向中国介绍的。以后层次分析法在中国得到很大的发展,很快应用到能源系统分析、城市规划、经济管理科研成果评价的许多领域。,运用AHP法进行决策时,大体可以分为以下4个步骤进行: (1)分析系统中各个因素的关系,建立系统的递
3、阶层次结构。 (2)对同一层次的各元素关于上一层次中某一准则的重要性进行两两比较,构造两两比较判断矩阵。,10.1 层次分析法的基本步骤,(3)由判断矩阵计算被比较元素对于该准则的相对权重。 (4)计算各层元素对系统目标的合成权重,并进行排序。,1.建立层次分析的结构模型 用AHP分析问题,首先要把问题条理化、层次化,构造层次分析的结构模型。这些层次大体上可分为3类。 ( 1)最高层:在这一层次中只有一个元素,一般是分析问题的预定目标或理想结果,因此又称目标层。,(2)中间层:这一层次包括了为实现目标所涉及的中间环节,它可由若干个层次组成,包括所需要考虑的准则、子准则,因此又称为准则层。 (3
4、)最底层:表示为实现目标可供选择的各种措施、决策、方案等,因此又称为措施层或方案层。 层次分析结构中各项称为此结构模型中的元素。,决策目标,准则1,方案1,准则m1,准则2,子准则1,方案2,子准则2,方案mr,子准则m2,方案层,准则层,目标层,10.1 层次分析法的基本步骤,注:层次之间的支配关系不一定是完全的,即可以有元素(非底层元素)并不支配下一层次的所有元素而只支配其中部分元素。这种自上而下的支配关系所形成的层次结构,我们称之为递阶层次结构。 递阶层次结构中的层次数与问题的复杂程度及分析的详尽程度有关,一般可不受限制。,为了避免由于支配的元素过多而给两两比较判断带来困难,每层次中各元
5、素所支配的元素一般地不要超过9个,若多于9个时,可将该层次再划分为若干子层。 例1 某顾客选购电冰箱时,对市场上正在出售的四种电冰箱考虑6项准则作为评价依据,得到如下层次分析模型:,目标层: 准则层: 方案层:,例2 选择科研课题: 某研究单位现有3个科研课题,限于人力物力,只能承担其中一个课题,如何选择? 考虑下列因素: 成果的贡献大小,对人才培养的作用,课题可行性。 在成果贡献方面考察:应用价值及科学。,意义(理论价值,对某科技领域的推动作用)。 在课题可行性方面考虑:难易程度(难易程度与自身的科技力量的一致性),研究周期(预计需要花费的时间),财政支持(所需经费、设备及经费来源,有关单位
6、支持情况等)。,目标层,方案层,准则层,例3 设某港务局要改善一条河道的过河运输条件,为此需要确定是否要建立桥梁或隧道以代替现有轮渡。 此问题中过河方式的确定取决于过河方式的效益与代价(即成本)。 通常我们用费效比(效益/代价)作为选择方案的标准。为此构造以下两个层次分析的结构模型。,10.1 层次分析法的基本步骤,准则层,过河的效益A,经济效益B1,社会效益B2,环境效益B3,桥梁D1,隧道D2,渡船D3,收 入,C2,岸间商业,C3,节省时间,C1,当地商业,C4,建筑就业,C5,安全可靠,C6,交往沟通,C7,自豪感,C8,舒 适,C9,进出方便,C10,美 化,C11,10.1 层次分
7、析法的基本步骤,方案层,目标层,10.1 层次分析法的基本步骤,目标层,准则层,方案层,2.构造判断矩阵 上、下层之间关系被确定之后,需确定与上层某元素z(目标A或某个准则z)相联系的下层元素(x1,x2,xn)各在上层元素z之中所占的比重。 方法:每次取2个元素,如xi,xj,以aij表示 xi 和 xj 对z的影响之比。这里得到的A=(aij)nn称为两两比较的判断矩阵。,10.1 层次分析法的基本步骤,Saaty建议用19及其倒数作为标度来确定aij的值,19比例标度的含义: xi比xj强(重要)的程度 xi/ xj 相等 稍强 强 很强 绝对强 aij 1 2 3 4 5 6 7 8
8、9 19标度的理由:两两比较的心理习惯, 显然,判断矩阵A的元素有如下特征:,10.1 层次分析法的基本步骤,1 aij0 2aji=1/aij 3aii=1 我们称判断矩阵A为正互反矩阵。,10.1 层次分析法的基本步骤,例如在例2中,准则层B对目标层作因素两两比较,并可建立下面判断矩阵: B1:B2为3 B1:B3为1 认为人才培养比另一项稍重要,另两项差不多相同重要。,10.1 层次分析法的基本步骤,判断矩阵 B1 B2 B3 B1 1 3 1 A= B2 1/3 1 1/3 B3 1 3 1,10.1 层次分析法的基本步骤,3.单一准则下元素相对排序权重计算及判断矩阵一致性检验 (1)
9、单一准则下元素排序 求判断矩阵A的最大特征值max及标准化(归一化)的特征向量W。向量W为同一层次中相应元素对于上一层次中某个因素相对重要性的排序权重。有wi0,i, 。,10.1 层次分析法的基本步骤,在构造判断矩阵,且各层元素间两两比较时,aij应有某种传递性质,即若甲比乙重要,乙比丙重要,合理地应有甲比丙更重要,在数值上表示为aijajk=aik 即 若xi与xj相比aij=3,xj与xk相比ajk=2,那么有传递性的判断应是xj与xk相比ajk=6 。,10.1 层次分析法的基本步骤,(2)判断矩阵的一致性概念 判断矩阵是各元素均为正数的矩阵,这种正矩阵有下列重要性质。,10.1 层次
10、分析法的基本步骤,定理1 设n阶方阵A为正矩阵, max为A的最大特征值,u =(u1,u2,un)T为max的相应特征向量。 max 0,ui 0,i =1,2,n max是单特征根(因此 u 除差一常数因子外是唯一的) ; A的任何其他特征值,有max| |。,10.1 层次分析法的基本步骤,定义 若正互反矩阵A满足aijajk=aik ,i ,j ,k =1,2,n ,则称A为一致阵。 一致阵的重要性质:设A是一致阵, 1A的转置亦是一致阵。 因为 aij=1/aji ,aij=1 ,i ,j=1,2,n; 由定义 aijajk=aik ,则显然。,10.1 层次分析法的基本步骤,2A的
11、每一行均为任意指定的另一行的正数倍,从而A的秩为1(即只有一个非零特征值,其余n1个为0特征值)。 考虑第行元素ai1,ai2,ain ,i=1,2,n; 对于第k行元素ak1,ak2,akn , j=1,2,n, aij=aikakj, 即第行各元素分别为第k行各元素的aik倍。,10.1 层次分析法的基本步骤,3A的最大特征根max= n,其余特征根皆为零。 4设u=(u1,u2,un)T是A对应max的特征向量,则aij=ui /uj , i ,j =1, 2, , n 容易验证:对于n及向量u=(u1,u2,un)T 若aij=ui /uj ,ij ,则 Au=nu (i, ),又由定
12、理1及性质2可知 max=n,u满足4。,10.1 层次分析法的基本步骤,5若A为判断矩阵,那么A对应于max =n 的标准化(归一化)特征向量 u=(u1, u2,un)T 就是一组排序权向量。 (归一化 )由性质4即知。 进一步地,有如下定理: 定理2 n阶正互反矩阵A=(aij)nn是一致阵的充分必要条件为max=n。,10.1 层次分析法的基本步骤,Proof : “必要性”即是上面性质3,已证。 “充分性”设A的最大特征值为max,相应特征向量u=(u1,un)T, Au= max u 。 分量形式:对 i =1,2,n,由定理1知ui0 于是max= 。 注意aii=1,max-1
13、= aij uj /ui 。,10.1 层次分析法的基本步骤,求和(把i=1,n的各式相加): nmax-n= aij uj /ui 注意 aji=1/aij 整理上式得 nmax-n= (aij uj /ui +1/ (aij uj /ui ) (*),10.1 层次分析法的基本步骤,式( ) 末端=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时等号成立。
14、,10.1 层次分析法的基本步骤,*,所以 aij ( uj /ui ),即aijajk=(ui /uj) (uj /uk)= uj /uk=ajk,故A是一致阵。 由于客观事物的复杂性与人的认识的多样性,我们得到的判断矩阵常常不具有传递性和一致性,但应该要求这些判断大体是一致的。 当判断矩阵过于偏离一致性时,它的可靠性值得怀疑,为此需要对判断矩阵进行一致性检验。,10.1 层次分析法的基本步骤,一致性检验步骤: (1)计算一致性指标C.I.=(max-n)/(n-1) (Consistency Index); (2)查找相应的平均随机一致性指标R.I.(Random Index); 115阶
15、正互反矩阵计算1000次得到的平均随 机一致性指标: 矩阵阶数 1 2 3 4 5 6 7 8 R.I. 0 0 0.52 0.89 1.12 1.26 1.36 1.41,10.1 层次分析法的基本步骤,矩阵阶数 9 10 11 12 13 14 15 R.I. 1.46 1.49 1.52 1.54 1.56 1.58 1.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个,对,10.1 层次分析法的基本步骤,角元为1,其余按正互反性得到)取充分大的子样计算所有的最大特征值,然后求平均即为max 。 (3)计算一致性比率C.R. (consistency ratio) C.R.