数学建模- 层次分析法,竞赛图

上传人:wm****3 文档编号:51723339 上传时间:2018-08-16 格式:PPT 页数:56 大小:894.50KB
返回 下载 相关 举报
数学建模- 层次分析法,竞赛图_第1页
第1页 / 共56页
数学建模- 层次分析法,竞赛图_第2页
第2页 / 共56页
数学建模- 层次分析法,竞赛图_第3页
第3页 / 共56页
数学建模- 层次分析法,竞赛图_第4页
第4页 / 共56页
数学建模- 层次分析法,竞赛图_第5页
第5页 / 共56页
点击查看更多>>
资源描述

《数学建模- 层次分析法,竞赛图》由会员分享,可在线阅读,更多相关《数学建模- 层次分析法,竞赛图(56页珍藏版)》请在金锄头文库上搜索。

1、第八章 离散模型8.1 层次分析模型8.2 循环比赛的名次y离散模型 离散模型:差分方程(第7章) 、整数规划(第4章)、图论、对 策论、网络流、 分析社会经济系统的有力工具 只用到代数、集合及图论(少许) 的知识8.1 层次分析模型背 景 日常工作、生活中的决策问题 涉及经济、社会等方面的因素 作比较判断时人的主观选择起相当大的作用,各因素的重要性难以量化 Saaty于1970年代提出层次分析法 AHP (Analytic Hierarchy Process) AHP一种定性与定量相结合的、系统化、层次化的分析方法目标层O(选择旅游地)P2 黄山P1 桂林P3 北戴河准则层方案层C3 居住C

2、1 景色C2 费用C4 饮食C5 旅途一. 层次分析法的基本步骤例. 选择旅游地如何在3个目的地中按照景色、 费用、居住条件等因素选择.“选择旅游地”思维过程的归 纳 将决策问题分为3个层次:目标层O,准则层C, 方案层P;每层有若干元素, 各层元素间的关系用相连的直线表示。 通过相互比较确定各准则对目标的权重,及各方案对每一准则的权重。 将上述两组权重进行综合,确定各方案对目标的权重。层次分析法将定性分析与定量分析结合起来完 成以上步骤,给出决策问题的定量结果。层次分析法的基本步骤 成对比较阵 和权向量元素之间两两对比,对比采用相对尺度设要比较各准则C1,C2, , Cn对目标O的重要性A成

3、对比较阵A是正互反阵要由A确定C1, , Cn对O的权向量选 择 旅 游 地成对比较的不一致情况一致比较不一致允许不一致,但要确定不一致的允许范围考察完全一致的情况成对比较阵和权向量成对比较完全一致的情况满足 的正互反阵A称一致阵,如 A的秩为1,A的唯一非零特征根为n A的任一列向量是对应于n 的特征向量 A的归一化特征向量可作为权向量对于不一致(但在允许范围内)的成对 比较阵A,建议用对应于最大特征根 的特征向量作为权向量w ,即一致阵 性质成对比较阵和权向量2 4 6 8比较尺度aij Saaty等人提出19尺度aij 取值 1,2, , 9及其互反数1,1/2, , 1/9尺度 1 3

4、 5 7 9 相同 稍强 强 明显强 绝对强aij = 1,1/2, ,1/9的重要性与上面相反 心理学家认为成对比较的因素不宜超过9个 用13,15,117,1p9p (p=2,3,4,5), d+0.1d+0.9 (d=1,2,3,4)等27种比较尺度对若干实例构造成对比较 阵,算出权向量,与实际对比发现, 19尺度较优。 便于定性到定量的转化:成对比较阵和权向量一致性检验对A确定不一致的允许范围已知:n 阶一致阵的唯一非零特征根为n可证:n 阶正互反阵最大特征根 n, 且 =n时为一致阵定义一致性指标:CI 越大,不一致越严重RI0 0 0.58 0.90 1.12 1.24 1.32

5、1.41 1.45 1.49 1.51n1 234567891110为衡量CI 的大小,引入随机一致性指标 RI随机模 拟得到aij , 形成A,计算CI 即得RI。定义一致性比率 CR = CI/RI 当CR3)个顶点的双向连通竞赛图,存在 正整数r,使邻接矩阵A 满足Ar 0,A称素阵 素阵A的最大特征根为正单 根,对应正特征向量S,且用S排名1234566支球队比赛结果排名次序为1,3, 2,5,4,6一般排名问题的算法:(1)构造有向竞赛图G=(V,E):将每个参赛者作为 G的一个顶点,即(2)将G的所有双向连通分图排序为(3)对G的至少有四个顶点的每一个双向连通分 图,求其邻接矩阵的

6、最大特征值所对应的特征向 量。按照特征向量分量的大小,依次定出该分图 对应参赛者的名次。对G的仅有三个顶点的双向连通分图,其对应参 赛者的名次并列。例:V1V1V3V3V5V5V2V2V4V4连通子图:V4V1,V2,V3,V5用竞赛图解决足球队排名问题:排名问题是根据各队相互比赛的成绩排出一个尽 可能反映各队真正实力的一个顺序。为此,我们提出 如下的一些基本原则:(1)一队排在另一队之前,不能只考虑这两队的战 绩,而应充分考虑这两队所有比赛场次的成绩。(2)要充分考虑对手的强弱因素。(3)如果两队之间由于种种原因,没有比赛或者双 方打成平局,就由这两队与其他队比赛的战绩来确定 它们的强弱。根

7、据上述原则,据比赛成绩表,构造竞赛图如下 :根据建边情况,可建立矩阵(4)参照上述方法得到的邻接阵,得到竞赛图 G.按照上述算法,经步骤(1)得到(5)针对竞赛图G,按照前述的排名方法进行排序 。T1T2T3T4T5T6T7T8T9T1 0T11T12T100111001 T2001110 T3110111011 T40000000000 T5001000 T6000110 T7111011111 T8101001 T900100111 T1010100011 T11000000 T12100010经过步骤(2)得到,经过步骤(3)得到邻接矩阵:T1T2T3T4T5T6T7T8T9T1 0T1

8、1T12T1010111001111 T2000111011011 T3110111011111 T4000000000000 T5000100000010 T6000110000011 T7111111011111 T8100111000011 T9000111010111 T10010111010011 T11000100000000 T12000110000010经过步骤(4)得到竞赛图G,T7,T3,T1,T9,T10,T2,T8,T6,T12,T5,T11,T4图G包含的连通分图:T7T3T1,T2,T8,T9,T10-双向连通分图T6,T12,T5,T11,T4-一条完全路径最终得到排名:缺点:(1)本方法不能有效的推广至N的队的情形 。(3)本方法对于问题中的第三问:对于数据的要求 不能给出有效的讨论。(2) 对于此算法,缺乏稳定性的讨论。

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 生活休闲 > 社会民生

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号