第八章-离散模型

2023/2/6信息学院张玉杰第八章离散模型8.1

层次分析模型8.2循环比赛的名次y2023/2/6信息学院张玉杰离散模型

离散模型：差分方程、整数规划、图论、对策论、网络流、…

…

分析社会经济系统的有力工具

只用到代数、集合及图论的少许知识2023/2/6信息学院张玉杰8.1层次分析模型一问题的提出日常生活中有许多决策问题。决策是指在面临多种方案时需要依据一定的标准选择某一种方案。例1购物买钢笔，一般要依据质量、颜色、实用性、价格、外形等方面的因素选择某一支钢笔。买饭，则要依据色、香、味、价格等方面的因素选择某种饭菜。例2旅游假期旅游，是去苏州，还是去北戴河，或者是去桂林，一般会依据景色、费用、饮食、居住、旅途等因素选择去哪个地方。2023/2/6信息学院张玉杰例3择业面临毕业，可能有高校、科研单位、企业等可以去选择，一般依据工作环境、工资待遇、发展前途、住房条件等因素择业。例4科研课题的选择由于经费等因素，有时不能同时开展几个课题，一般依据课题的可行性、应用价值、理论价值、被培养人才等因素进行选题。2023/2/6信息学院张玉杰面临各种各样的方案，要进行比较、判断、评价、最后作出决策。这个过程主观因素占有相当的比重，给用数学方法解决问题带来不便。T.L.saaty于20世纪七十年代提出了层次分析法（AnalyticHierarchyProcess,AHP),即定性和定量相结合的、系统化的、层次化的分析方法。

层次分析法2023/2/6信息学院张玉杰层次分析法的广泛应用

应用领域：经济计划和管理，能源政策和分配，人才选拔和评价，生产决策，交通运输，科研选题，产业结构，教育，医疗，环境，军事等。

处理问题类型：决策、评价、分析、预测等。

建立层次分析结构模型是关键一步，要有主要决策层参与。

构造成对比较阵是数量依据，应由经验丰富、判断力强的专家给出。2023/2/6信息学院张玉杰

递阶层次结构模型AB2BmC1C2C3CnB1……目标层准则层方案层2023/2/6信息学院张玉杰二层次分析法的基本步骤买钢笔质量颜色价格外形实用可供选择的笔1建立层次分析结构模型

一般分为三层，最上面为目标层，最下面为方案层，中间是准则层或指标层。例1的层次结构模型

准则层

方案层目标层2023/2/6信息学院张玉杰选择旅游地景色费用居住饮食旅途苏州、北戴河、桂林例2

层次结构模型准则层方案层目标层2023/2/6信息学院张玉杰国家综合实力国民收入军事力量科技水平社会稳定对外贸易美、俄、中、日、德等大国例1

国家实力分析目标层准则层方案层2023/2/6信息学院张玉杰例2

工作选择工作选择贡献收入发展声誉关系位置供选择的岗位2023/2/6信息学院张玉杰例3

横渡江河、海峡方案的抉择过河的代价

A经济代价

B1环境代价B3社会代价B2投入资金C1操作维护C2冲击渡船业C3冲击生活方式C4交通拥挤C5居民搬迁C6汽车排放物C7对水的污染C8对生态的破坏C9桥梁D1隧道D2渡船D2子准则层2023/2/6信息学院张玉杰待评价的科技成果直接经济效益

C11间接经济效益

C12社会效益

C13学识水平

C21学术创新

C22技术水平

C23技术创新

C24效益C1水平C2规模C3科技成果评价例4科技成果的综合评价子准则层2023/2/6信息学院张玉杰若上层的每个因素都支配着下一层的所有因素，或被下一层所有因素影响，称为完全层次结构，否则称为不完全层次结构。例:评价教师贡献的层次结构贡献O教学C1科研C2P2P1P3P4不完全层次结构2023/2/6信息学院张玉杰更复杂的层次结构更复杂的层次结构：层内各元素间存在相互影响或支配；层间存在反馈或循环。制动底盘车轮方向盘发动机减震装置刹车转向运行加速性能汽车行驶性能汽车1汽车2汽车n……2023/2/6信息学院张玉杰设某层有个因素，2构造成对比较矩阵要比较它们对上一层某一准则（或目标）的影响程度，确定在该层中相对于某一准则所占的比重。（即把个因素对上层某一目标的影响程度排序）用表示第个因素相对于第个因素的比较结果，则则称为成对比较矩阵。上述比较是两两因素之间进行的比较，比较时取1~9尺度。2023/2/6信息学院张玉杰１３５７９尺度第个因素与第个因素的影响相同第个因素比第个因素的影响稍强第个因素比第个因素的影响强第个因素比第个因素的影响明强第个因素比第个因素的影响绝对地强含义比较尺度：（1~9尺度的含义）2,4,6,8表示第个因素相对于第个因素的影响介于上述两个相邻等级之间。不难定义以上各尺度倒数的含义，根据。由上述定义知，成对比较矩阵比如，例2的旅游问题中，第二层A的各因素对目标层Z的影响两两比较结果如下：满足以下性质

ZA1A2A3A4A5A1A2A3A4A511/2433217551/41/711/21/31/31/52111/31/5311分别表示景色、费用、居住、饮食、旅途。称为正互反阵。2023/2/6信息学院张玉杰

由上表，可得成对比较矩阵旅游问题的成对比较矩阵共有6个（一个5阶，5个3阶）。问题：两两进行比较后，怎样才能知道，下层各因素对上层某因素的影响程度的排序结果呢？2023/2/6信息学院张玉杰3计算权向量及一致性检验层次单排序：确定下层各因素对上层某因素影响程度的过程。用权值表示影响程度，先从一个简单的例子看如何确定权值。例如一块石头重量记为1，打碎分成个小块，各块的重量分别记为：则可得成对比较矩阵由右面矩阵可以看出，2023/2/6信息学院张玉杰即，但在例2的成对比较矩阵中，在正互反矩阵中，若,则称为一致阵。一致阵的性质：5.的任一列(行)都是对应于特征根的特征向量。2023/2/6信息学院张玉杰若成对比较矩阵是一致阵，则可取对应于最大特征根的归一化特征向量，且定理：阶互反阵的最大特征根，当且仅当时，为一致阵。表示下层第个因素对上层某因素影响程度的权值。若成对比较矩阵不是一致阵，Saaty等人建议用其最大特征根对应的归一化特征向量作为权向量，则这样确定权向量的方法称为特征根法.2023/2/6信息学院张玉杰由于连续的依赖于，则比大的越多，的不一致性越严重。用最大特征值对应的特征向量作为被比较因素对上层某因素影响程度的权向量，其不一致程度越大，引起的判断误差越大。因而可以用数值的大小来衡量的不一致程度。定义一致性指标其中为的对角线元素之和，也为的特征根之和。2023/2/6信息学院张玉杰则可得一致性指标定义随机一致性指标随机构造500个成对比较矩阵随机一致性指标RI的数值：n1234567891011RI000.580.901.121.241.321.411.451.491.512023/2/6信息学院张玉杰一致性检验：利用一致性指标和一致性比率<0.1及随机一致性指标的数值表，对进行检验的过程。一般地，当一致性比率的不一致程度在容许范围之内，可用其归一化特征向量作为权向量，否则要重新构造成对比较矩阵，对加以调整。时，认为

层次分析法2023/2/6信息学院张玉杰4计算组合权向量

确定某层所有因素对于总目标相对重要性的排序权值过程，称为层次总排序

从最高层到最低层逐层进行。设：

对总目标Z的权向量为的层次权向量为2023/2/6信息学院张玉杰层次总排序的一致性检验设层对上层(层)中因素的层次单排序一致性指标为，随机一致性指为，则层次总排序的一致性比率为：当时，认为层次总排序通过一致性检验。到此，根据最下层（决策层）的层次总排序做出最后决策。2023/2/6信息学院张玉杰1.建立层次结构模型

该结构图包括目标层，准则层，方案层。层次分析法的基本步骤归纳如下3.计算单排序权向量并做一致性检验2.构造成对比较矩阵从第二层开始用成对比较矩阵和1~9尺度。对每个成对比较矩阵计算最大特征值及其对应的特征向量，利用一致性指标、随机一致性指标和一致性比率做一致性检验。若检验通过，特征向量（归一化后）即为权向量；若不通过，需要重新构造成对比较矩阵。2023/2/6信息学院张玉杰计算最下层对最上层总排序的权向量。4.计算总排序权向量并做一致性检验进行检验。若通过，则可按照总排序权向量表示的结果进行决策，否则需要重新考虑模型或重新构造那些一致性比率较大的成对比较矩阵。利用总排序一致性比率2023/2/6信息学院张玉杰三层次分析法建模举例旅游问题(1)建模分别分别表示景色、费用、居住、饮食、旅途。分别表示苏州、北戴河、桂林。2023/2/6信息学院张玉杰（2）构造成对比较矩阵2023/2/6信息学院张玉杰(3)计算层次单排序的权向量和一致性检验成对比较矩阵的最大特征值权向量(特征向量)a=（0.4658，0.8409，0.0951，0.1733，0.1920）2023/2/6信息学院张玉杰表明通过了一致性验证。故则该特征值对应的归一化特征向量权向量归一化2023/2/6信息学院张玉杰组合权向量第1层O第2层C1,…Cn第3层P1,…Pm第2层对第1层的权向量第3层对第2层各元素的权向量构造矩阵则第3层对第1层的组合权向量2023/2/6信息学院张玉杰组合权向量记第2层（准则）对第1层（目标）的权向量为同理求第3层(方案)对第2层每一元素(准则)的权向量方案层对C1(景色)的成对比较阵方案层对C2(费用)的成对比较阵…C5…B5最大特征根1

2

…

5

权向量w1(3)w2(3)…

w5(3)权向量w1(3)w2(3)…

w5(3)2023/2/6信息学院张玉杰第3层对第2层的计算结果k10.5950.2770.1293.0050.0030.00100.00503.0020.6820.2360.082230.1420.4290.42933.0090.1750.1930.633430.6680.1660.1665组合权向量RI=0.58(n=3),

CIk

均可通过一致性检验

w(2)

0.2630.4750.0550.0990.110方案P1对目标的组合权重为0.5950.263+0.0820.475+0.429

0.055+0.6330.099+0.1660.110=0.3002023/2/6信息学院张玉杰(I)方案层对目标的组合权向量(0.300,0.246,0.456)T计算层次总排序权值和一致性检验(II)总排序的一致性检验2023/2/6信息学院张玉杰(0.300,0.246,0.456)'作为最后决策的依据P3>P1>P2最后决策去桂林旅游满足一致性检验2023/2/6信息学院张玉杰四层次分析法的优点和局限性1系统性

层次分析法把研究对象作为一个系统，按照分解、比较判断、综合的思维方式进行决策，成为继机理分析、统计分析之后发展起来的系统分析的重要工具。

2实用性层次分析法把定性和定量方法结合起来，能处理许多用传统的最优化技术无法着手的实际问题，应用范围很广，同时，这种方法使得决策者与决策分析者能够相互沟通，决策者甚至可以直接应用它，这就增加了决策的有效性。2023/2/6信息学院张玉杰3简洁性

具有中等文化程度的人即可以了解层次分析法的基本原理并掌握该法的基本步骤，计算也非常简便，并且所得结果简单明确，容易被决策者了解和掌握。以上三点体现了层次分析法的优点，该法的局限性主要表现在以下几个方面：第一只能从原有的方案中优选一个出来，没有办法得出更好的新方案。2023/2/6信息学院张玉杰第二该法中的比较、判断以及结果的计算过程都是粗糙的，不适用于精度较高的问题。第三从建立层次结构模型到给出成对比较矩阵，人主观因素对整个过程的影响很大，这就使得结果难以让所有的决策者接受。当然采取专家群体判断的办法是克服这个缺点的一种途径。2023/2/6信息学院张玉杰实例

某单位拟从三名干部中提拔一人担任领导工作，干部的优劣（由上级人事部门提出），用六个属性来衡量：健康状况、业务知识、写作水平、口才、政策水平、工作作风，分别用p1、p2、p3、p4、p5、p6表示。判断矩阵如下