常用系统建模方法ppt课件.ppt

《常用系统建模方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《常用系统建模方法ppt课件.ppt（72页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、常用系统建模方法常用系统建模方法u主要参考资料主要参考资料齐欢，王小平齐欢，王小平.系统建模与仿真（第系统建模与仿真（第2 2版），第版），第2 2章章姜启源姜启源,谢金星谢金星 ,叶俊叶俊.数学模型（第数学模型（第3 3版），第版），第1 1章章1常用系统建模方法常用系统建模方法u1.1.系统模型的概述系统模型的概述u2.2.建模的逻辑思维方法建模的逻辑思维方法u3.3.图解建模法图解建模法u4.4.层次分析法层次分析法u5.5.聚类分析聚类分析21.1.系统模型的概述系统模型的概述u从现实对象到数学模型从现实对象到数学模型模型是为了一定目的，对客观事物的一部分进行简缩、抽象、模型是为了一定

2、目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物。模型集中反映了原型中人们需要提炼出来的原型的替代物。模型集中反映了原型中人们需要的那一部分特征。的那一部分特征。系系 统统模模 型型计算机计算机系统建模系统建模仿真实验仿真实验仿真建模仿真建模 建模仿真三要素及三个基本活动建模仿真三要素及三个基本活动31.1.系统模型的概述系统模型的概述u从现实对象到数学模型从现实对象到数学模型系统模型是研究和掌握系统运动规律的有力工具，系统模型是研究和掌握系统运动规律的有力工具，它是认识、分析、设计、预测、控制实际系统的基它是认识、分析、设计、预测、控制实际系统的基础，也是解决系统工程问题不可缺

3、少的技术手段。础，也是解决系统工程问题不可缺少的技术手段。建立有效且可靠的系统模型是系统研究者的首要任建立有效且可靠的系统模型是系统研究者的首要任务。务。数学模型是系统模型的最主要和最常用的表示方式。数学模型是系统模型的最主要和最常用的表示方式。41.1.系统模型的概述系统模型的概述u数学模型与数学建模数学模型与数学建模数学模型（数学模型（Mathematical ModelMathematical Model）对于一个现实对象，为了一个特定目的，根据其内在对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，规律，作出必要的简化假设，运用适当的数学工具，

4、得到的一个数学结构。得到的一个数学结构。数学建模（数学建模（Mathematical Modeling Mathematical Modeling）建立数学模型的全过程，包括表述、求解、解释、检建立数学模型的全过程，包括表述、求解、解释、检验等。验等。51.1.系统模型的概述系统模型的概述u一个简单的数学模型：一个简单的数学模型：“航行问题航行问题”甲乙两地相距甲乙两地相距750750千米，船从甲到乙顺水航行需千米，船从甲到乙顺水航行需3030小小时，从乙到甲逆水航行需时，从乙到甲逆水航行需5050小时，问船的速度是多小时，问船的速度是多少少?用用 x 表示船速，表示船速，y 表示水速，列出方

5、程：表示水速，列出方程：答：船速每小时答：船速每小时20千米千米/小时小时.x=20y=5求解求解61.1.系统模型的概述系统模型的概述u一个简单的数学模型：一个简单的数学模型：“航行问题航行问题”可以看出，上述过程的主要步骤如下：可以看出，上述过程的主要步骤如下：作出简化假设（船速、水速为常数）；作出简化假设（船速、水速为常数）；用符号表示有关量（用符号表示有关量（x,y表示船速和水速）；表示船速和水速）；用物理定律（匀速运动的距离等于速度乘以用物理定律（匀速运动的距离等于速度乘以 时间）列时间）列出数学式子（二元一次方程）；出数学式子（二元一次方程）；求解得到数学解答（求解得到数学解答（x

6、=20,y=5）；）；回答原问题（船速每小时回答原问题（船速每小时20千米千米/小时）。小时）。71.1.系统模型的概述系统模型的概述u数学模型的特点数学模型的特点模型的逼真性和可行性模型的逼真性和可行性模型的渐进性模型的渐进性模型的强健性模型的强健性模型的可转移性模型的可转移性模型的非预制性模型的非预制性模型的条理性模型的条理性模型的技艺性模型的技艺性模型的局限性模型的局限性81.1.系统模型的概述系统模型的概述u数学模型的分类数学模型的分类应用领域应用领域人口、交通、经济、生态人口、交通、经济、生态 数学方法数学方法初等数学、微分方程、规划、统计初等数学、微分方程、规划、统计 表现特性表现

7、特性确定和随机，静态和动态，离散和连续，确定和随机，静态和动态，离散和连续，线性和非线性线性和非线性了解程度了解程度白箱、灰箱、黑箱白箱、灰箱、黑箱91.1.系统模型的概述系统模型的概述u数学建模的基本方法数学建模的基本方法机理分析机理分析根据对客观事物特性的认识，找出反映内部机理的数量规根据对客观事物特性的认识，找出反映内部机理的数量规律。律。测试分析（实验统计建模）测试分析（实验统计建模）将对象看作将对象看作“黑箱黑箱”，通过对量测数据的统计分析，通过对量测数据的统计分析，找出与数据拟合最好的模型。找出与数据拟合最好的模型。二者结合二者结合用机理分析建立模型结构，用测试分析确定模型参数用机

8、理分析建立模型结构，用测试分析确定模型参数101.1.系统模型的概述系统模型的概述u数学建模的基本步骤数学建模的基本步骤模型准备模型准备模型假设模型假设模型构成模型构成模型求解模型求解模型分析模型分析模型检验模型检验模型应用模型应用111.1.系统模型的概述系统模型的概述u数学建模的基本步骤数学建模的基本步骤1 1）模型准备）模型准备了解实际背景了解实际背景明确建模目的明确建模目的搜集有关信息搜集有关信息掌握对象特征掌握对象特征模型准备模型准备模型假设模型假设模型构成模型构成模型求解模型求解模型分析模型分析模型检验模型检验模型应用模型应用形成一个比较清晰的形成一个比较清晰的“问题问题”121.

9、1.系统模型的概述系统模型的概述u数学建模的基本步骤数学建模的基本步骤2 2）模型假设）模型假设针对问题特点和建模目的，作出合理的、简化的假设针对问题特点和建模目的，作出合理的、简化的假设在合理与简化之间作出折中在合理与简化之间作出折中3 3）模型构成）模型构成用数学的语言、符号描述问题用数学的语言、符号描述问题发挥想像力发挥想像力使用类比法使用类比法尽量采用简单的数学工具尽量采用简单的数学工具模型准备模型准备模型假设模型假设模型构成模型构成模型求解模型求解模型分析模型分析模型检验模型检验模型应用模型应用131.1.系统模型的概述系统模型的概述u数学建模的基本步骤数学建模的基本步骤4 4）模型

10、求解）模型求解利用各种数学方法、软件和计算机技术利用各种数学方法、软件和计算机技术解析解、仿真解析解、仿真5 5）模型分析）模型分析例如，对结果的误差分析、统计分析、模型对数据的例如，对结果的误差分析、统计分析、模型对数据的稳定性分析稳定性分析6 6）模型检验）模型检验与实际现象、数据比较，检验模型的合理性、适用性与实际现象、数据比较，检验模型的合理性、适用性模型准备模型准备模型假设模型假设模型构成模型构成模型求解模型求解模型分析模型分析模型检验模型检验模型应用模型应用142.2.建模的逻辑思维方法建模的逻辑思维方法u建模是一项复杂的思维活动，也可以看成是一门建模是一项复杂的思维活动，也可以看

11、成是一门艺术，因而既没有统一的模式，也没有固定的方艺术，因而既没有统一的模式，也没有固定的方法，需要多方面的能力法，需要多方面的能力分析综合能力分析综合能力抽象概括能力抽象概括能力想象洞察能力想象洞察能力运用数学工具的能力运用数学工具的能力通过实践验证数学模型的能力通过实践验证数学模型的能力u通过实例研究，了解建模过程常用的思维方法，通过实例研究，了解建模过程常用的思维方法，包括抽象、归纳、演绎、类比等。包括抽象、归纳、演绎、类比等。152.2.建模的逻辑思维方法建模的逻辑思维方法u1)1)抽象抽象揭示事物的共性和联系的规律揭示事物的共性和联系的规律忽略每个具体事物的特殊性，着眼于整体和一般规

12、忽略每个具体事物的特殊性，着眼于整体和一般规律律实例研究：椅子能在不平的地面上放稳吗？实例研究：椅子能在不平的地面上放稳吗？把椅子往不平的地面上一放，通常只有三只脚着地，把椅子往不平的地面上一放，通常只有三只脚着地，放不稳，然而只要稍挪动几次，就可以四脚着地，放放不稳，然而只要稍挪动几次，就可以四脚着地，放稳了。为什么？稳了。为什么？16椅子能在不平的地面上放稳吗？椅子能在不平的地面上放稳吗？u问题分析问题分析涉及的对象：地面，椅子涉及的对象：地面，椅子椅子的位置和调整椅子的位置和调整放稳：椅子的四只脚着地放稳：椅子的四只脚着地u模型假设模型假设四条腿一样长，椅脚与地面点接触，四脚连线呈正四条

13、腿一样长，椅脚与地面点接触，四脚连线呈正方形方形;地面高度连续变化，可视为数学上的连续曲面地面高度连续变化，可视为数学上的连续曲面;地面相对平坦，使椅子在任意位置至少三只脚同时地面相对平坦，使椅子在任意位置至少三只脚同时着地。着地。17椅子能在不平的地面上放稳吗？椅子能在不平的地面上放稳吗？u模型构成模型构成用数学语言把椅子位置和四只用数学语言把椅子位置和四只脚着地的关系表示出来。脚着地的关系表示出来。1 1）椅子位置和调整的表述）椅子位置和调整的表述利用正方形（椅脚连线）的对利用正方形（椅脚连线）的对称性称性用用（对角线与对角线与x轴的夹角）表轴的夹角）表示椅子位置示椅子位置以中心为对称点，

14、正方形绕中以中心为对称点，正方形绕中心的旋转对应椅子位置的调整心的旋转对应椅子位置的调整xBADCODC B A 正方形正方形ABCD绕绕O点旋转点旋转18椅子能在不平的地面上放稳吗？椅子能在不平的地面上放稳吗？u模型构成模型构成2 2）椅脚着地的数学表示）椅脚着地的数学表示四只脚着地：椅脚与地面距离四只脚着地：椅脚与地面距离为零，距离是为零，距离是 的函数的函数xBADCODC B A 正方形正方形ABCD绕绕O点旋转点旋转四个距离四个距离(四只脚四只脚)两个距离两个距离正方形正方形对称性对称性f()：A,C 两脚与地面距离之和两脚与地面距离之和 g()：B,D 两脚与地面距离之和两脚与地面

15、距离之和 19椅子能在不平的地面上放稳吗？椅子能在不平的地面上放稳吗？u模型构成模型构成在此基础上，用数学语言把椅子位置和四只脚着在此基础上，用数学语言把椅子位置和四只脚着地的关系表示出来：地的关系表示出来：xBADCODC B A 正方形正方形ABCD绕绕O点旋转点旋转f(),g()是是连续函连续函数数对任意对任意,f()和和g()至少一个为至少一个为0地面为连续曲面地面为连续曲面 椅子在任意位置椅子在任意位置至少三只脚着地至少三只脚着地20椅子能在不平的地面上放稳吗？椅子能在不平的地面上放稳吗？u模型构成模型构成问题的形式化描述：问题的形式化描述：xBADCODC B A 正方形正方形AB

16、CD绕绕O点旋转点旋转已知：已知：f(),g()是是连续函数连续函数;对任意对任意，f()g()=0;且且 g(0)=0，f(0)0.证明：存在证明：存在 0，使，使f(0)=g(0)=0.21椅子能在不平的地面上放稳吗？椅子能在不平的地面上放稳吗？u模型求解模型求解主要思路主要思路xBADCODC B A 正方形正方形ABCD绕绕O点旋转点旋转将椅子将椅子旋转旋转900，对角线，对角线AC和和BD互换。互换。由由g(0)=0，f(0)0，知，知f(/2)=0,g(/2)0.令令h()=f()g(),则则h(0)0和和h(/2)0.由由 f,g的连续性知的连续性知 h为连续函数为连续函数,据连

17、续函数的基本性据连续函数的基本性质质,必存在必存在 0,使使h(0)=0,即即f(0)=g(0).因为因为f()g()=0,所以所以f(0)=g(0)=0.222.2.建模的逻辑思维方法建模的逻辑思维方法u2)2)归纳归纳从特殊的具体的认识推进到一般的抽象的认识的一从特殊的具体的认识推进到一般的抽象的认识的一种思维方式。种思维方式。立足于观察、经验或实验的基础上的；依据若干已立足于观察、经验或实验的基础上的；依据若干已知的不完全的现象推断尚属未知的现象。知的不完全的现象推断尚属未知的现象。实例研究：开普勒第三定律的发现实例研究：开普勒第三定律的发现23开普勒第三定律的发现开普勒第三定律的发现u

18、开普勒第一定律开普勒第一定律也称椭圆定律、轨道定律、行星定律。每一行星沿也称椭圆定律、轨道定律、行星定律。每一行星沿一个椭圆轨道环绕太阳，而太阳则处在椭圆的一个一个椭圆轨道环绕太阳，而太阳则处在椭圆的一个焦点上。焦点上。u开普勒第二定律开普勒第二定律在相等时间内，太阳和运动中的行星的连线（向量在相等时间内，太阳和运动中的行星的连线（向量半径）所扫过的面积都是相等的。半径）所扫过的面积都是相等的。24开普勒第三定律的发现开普勒第三定律的发现u开普勒第三定律开普勒第三定律也叫行星运动定律：绕以太阳为焦点的椭圆轨道运也叫行星运动定律：绕以太阳为焦点的椭圆轨道运行的所有行星，其各自椭圆轨道半长轴行的所

19、有行星，其各自椭圆轨道半长轴a的立方与周的立方与周期期T的平方之比是一个常量。的平方之比是一个常量。k为开普勒常数252.2.建模的逻辑思维方法建模的逻辑思维方法u3)3)演绎演绎由一般性的命题推出特殊命题的推理方法。由一般性的命题推出特殊命题的推理方法。典型的，如公理化的几何学典型的，如公理化的几何学实例研究：牛顿万有引力定律的演绎实例研究：牛顿万有引力定律的演绎26牛顿万有引力定律的演绎牛顿万有引力定律的演绎u模型假设模型假设开普勒第一、二、三定律开普勒第一、二、三定律牛顿运动第二定律牛顿运动第二定律a=F/m(F=m a)：物体加速度的大小跟作用力成正比，跟：物体加速度的大小跟作用力成正

20、比，跟物体的质量成反比，加速度的方向跟作用力的方向相同。物体的质量成反比，加速度的方向跟作用力的方向相同。极坐标系极坐标系(r,)太阳太阳(0,0)行星位置：向径行星位置：向径O(太阳太阳)P(行星行星)r27牛顿万有引力定律的演绎牛顿万有引力定律的演绎u模型假设模型假设O(太太阳阳)P(行星行星)ra长半轴长半轴,b短半轴短半轴,e离心率离心率1）行星运行轨道）行星运行轨道3）行星运行周期）行星运行周期 T2）单位时间）单位时间 扫过面积为常数扫过面积为常数 Am 行星质量行星质量 绝对常数绝对常数4）行星运行受力）行星运行受力 28u模型构成模型构成向径向径 的基向量的基向量（平面直角坐标

21、）（平面直角坐标）O(太阳太阳)P(行星行星)rxy29万有引力定律万有引力定律需证明需证明 4A2/p=kM（与哪一颗行星无关）（与哪一颗行星无关）A单位时间单位时间 扫过面积扫过面积O(太阳太阳)P(行星行星)rlp/22=pA302.2.建模的逻辑思维方法建模的逻辑思维方法u4)4)类比类比在两类不同的事物之间进行对比，找出若干相同或在两类不同的事物之间进行对比，找出若干相同或相似点之后，推测在其它方面也可能存在相同或相相似点之后，推测在其它方面也可能存在相同或相似之处的一种思维方式。似之处的一种思维方式。实例研究实例研究1）机械系统和电路系统的类比。）机械系统和电路系统的类比。2）方式

22、算法：遗传算法、蚁群优化算法、人工神经）方式算法：遗传算法、蚁群优化算法、人工神经网络、粒子群优化算法网络、粒子群优化算法(Particle Swarm Optimization)31PSOPSO算法算法uPSOPSO是一种基于群体智能的进化计算方法是一种基于群体智能的进化计算方法,由由KennedyKennedy和和EberhartEberhart博士于博士于19951995年提出。年提出。u基本原理基本原理将最优解的搜索类比于鸟群的捕食行将最优解的搜索类比于鸟群的捕食行为。为。设想一群鸟在随机搜寻食物，在这个设想一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有鸟都不知区域里只有一块食物

23、，所有鸟都不知道食物在哪里，但是他们知道当前的道食物在哪里，但是他们知道当前的位置离食物还有多远，那么找到食物位置离食物还有多远，那么找到食物的最优策略是什么呢的最优策略是什么呢?最简单有效的就最简单有效的就是搜寻目前离食物最近的鸟的周围区是搜寻目前离食物最近的鸟的周围区域，根据自己飞行的经验判断食物的域，根据自己飞行的经验判断食物的所在。所在。32u基本原理基本原理在在PSOPSO中，把一个优化问题看作是在空中觅食的鸟群，那么中，把一个优化问题看作是在空中觅食的鸟群，那么“食物食物”就就是优化问题的最优解，而在空中飞行的每一只觅食的是优化问题的最优解，而在空中飞行的每一只觅食的“鸟鸟”就是就

24、是PSOPSO算算法中在解空间中进行搜索的一个法中在解空间中进行搜索的一个“粒子粒子”(Particle)(Particle)。粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个被目标函数决定的和同伴的飞行经验来动态调整。所有的粒子都有一个被目标函数决定的适应值适应值(fitness value)(fitness value)，这个适应值用于评价粒子的，这个适应值用于评价粒子的“好坏好坏”程度。程度。每个粒子知道自己到目前为止发现的最好位置（每个粒子知道自己到目前为止发现的最

25、好位置（particle bestparticle best，记为，记为pbestpbest）和当前的位置，）和当前的位置，pbestpbest就是粒子本身找到的最优解，这个可以看作就是粒子本身找到的最优解，这个可以看作是粒子自己的飞行经验。是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置位置(global best(global best，记为，记为gbest)gbest)，gbestgbest是在是在pbestpbest中的最好值，即是全局最优中的最好值，即是全局最优解，这个可以看作是整个

26、群体的经验。解，这个可以看作是整个群体的经验。33u算法描述算法描述假设在一个假设在一个N维空间进行搜索，粒子维空间进行搜索，粒子i的信息可用两个的信息可用两个N维向量维向量来表示：来表示：第第i个粒子的位置可表示为个粒子的位置可表示为 速度为速度为 在找到两个最优解后，粒子即可根据下式来更新自己的速度和在找到两个最优解后，粒子即可根据下式来更新自己的速度和位置：位置：是粒子：是粒子i在第在第k次迭代中第次迭代中第d维的速度；维的速度；：是粒子：是粒子i在第在第k次迭代中第次迭代中第d维的当前位置；维的当前位置；(1)(2)w是惯性因子，是惯性因子，c1和和c2是学习因子或加速系数是学习因子或

27、加速系数34u算法描述算法描述352.2.建模的逻辑思维方法建模的逻辑思维方法u5)5)移植移植将一个或几个学科领域中的理论和行之有效的研究将一个或几个学科领域中的理论和行之有效的研究方法、研究手段移用到其它领域当中去，为解决其方法、研究手段移用到其它领域当中去，为解决其它学科领域中存在的疑难问题提供启发和帮助。它学科领域中存在的疑难问题提供启发和帮助。实例研究实例研究1）论文评价与谷歌）论文评价与谷歌PageRank方法方法2）计算圆周率的浦丰投针模型）计算圆周率的浦丰投针模型36浦丰投针模型浦丰投针模型dlxx矩形矩形G阴影阴影g373.3.图解建模法图解建模法u图解建模法是一种采用点和线

28、组成的、用以描述图解建模法是一种采用点和线组成的、用以描述系统的图形进行建模的方法，可用于描述自然界系统的图形进行建模的方法，可用于描述自然界和人类社会中的大量事物和事物之间的关系。和人类社会中的大量事物和事物之间的关系。u实例研究实例研究城市公共交通网络模型城市公共交通网络模型物品交换模型物品交换模型38城市公共交通网络模型城市公共交通网络模型39物品交换模型物品交换模型u问题问题甲有物品甲有物品X,乙有物品乙有物品Y,双方为满足更高的需要，商双方为满足更高的需要，商定相互交换一部分。研究实物交换方案。定相互交换一部分。研究实物交换方案。yxp.用用x,y分别表示甲分别表示甲(乙乙)占有占有

29、X,Y的数量。设交换前甲占的数量。设交换前甲占有有X的数量为的数量为x0,乙占有乙占有Y的的数量为数量为y0,作图：作图：若不考虑双方对若不考虑双方对X,Y的偏爱，则矩形内任一点的偏爱，则矩形内任一点 p(x,y)都是一种交换方案：甲占有都是一种交换方案：甲占有(x,y)，乙占有，乙占有(x0-x,y0-y)xyyo0 xo40u分析与建模分析与建模xyyoy1y20 x1x2xop1p2.甲的无差别曲线甲的无差别曲线如果甲占有如果甲占有(x1,y1)与占有与占有(x2,y2)具有同样的满意程度，即具有同样的满意程度，即p1,p2对甲是无差别的，对甲是无差别的，MN将将所有与所有与p1,p2无

30、差别的点连接无差别的点连接起来，得到一条无差别曲线起来，得到一条无差别曲线MN,线上各点的满意度相同线上各点的满意度相同,线的形状反映对线的形状反映对X,Y的偏爱程度，的偏爱程度，N1M1p3(x3,y3).比比MN各点满意度更高的点如各点满意度更高的点如p3，在另一条无差别曲线，在另一条无差别曲线M1N1上。上。于是形成一族无差别曲线（无数条）。于是形成一族无差别曲线（无数条）。41p1.p2.c1 y0 xf(x,y)=c1无差别曲线族的性质：无差别曲线族的性质：单调减单调减(x增加增加,y减小减小)下凸下凸(凸向原点凸向原点)互不相交互不相交在在p1点占有点占有x少、少、y多，多，宁愿以

31、较多的宁愿以较多的 y换取换取较少的较少的 x;在在p2点占有点占有y少、少、x多，多，就要以较多的就要以较多的 x换取换取较少的较少的 y。甲的无差别曲线族记作甲的无差别曲线族记作f(x,y)=c1c1满意度满意度（f 等满意度曲线）等满意度曲线）42xyOg(x,y)=c2c2 乙的无差别曲线族乙的无差别曲线族 g(x,y)=c2具有相同具有相同性质（形状可以不同）性质（形状可以不同）双方的交换路径双方的交换路径xyyoOxof=c1Oxyg=c2乙的无差别曲线族乙的无差别曲线族 g=c2(坐标坐标系系xOy,且反向）且反向）甲的无差别曲线族甲的无差别曲线族 f=c1ABp P 双方满意的

32、交换方案必双方满意的交换方案必在在AB（交换路径）上（交换路径）上因为在因为在AB外的任一点外的任一点p,(双方双方)满意度低于满意度低于AB上的点上的点p两族曲线切点连线记作两族曲线切点连线记作AB43ABp 交换方案的进一步确定交换方案的进一步确定交换方案交换方案 交换后甲的占有量交换后甲的占有量(x,y)0 x x0,0 y y0矩形内任一点矩形内任一点交换路交换路径径AB双方的无差别曲线族双方的无差别曲线族等价交等价交换原则换原则X,Y用货币衡量其价值，设交换用货币衡量其价值，设交换前前x0,y0价值相同，则等价交换原价值相同，则等价交换原则下交换路径为则下交换路径为:CD(x0,0)

33、,(0,y0)两点的连线两点的连线CDAB与与CD的的交点交点p设设X单价单价a,Y单价单价b,则等价交换下则等价交换下ax+by=s(s=ax0=by0)yyo0 xo.x444.4.层次分析法层次分析法u美国运筹学家匹茨堡大学教授萨蒂美国运筹学家匹茨堡大学教授萨蒂(T.L.Saaty)(T.L.Saaty)于于19701970年代为美国国防部研究年代为美国国防部研究“根据各个工业部门对国家福利根据各个工业部门对国家福利的贡献大小而进行电力分配的贡献大小而进行电力分配”课题时提出了层次分析法课题时提出了层次分析法AHP(Analytic Hierarchy Process)AHP(Analy

34、tic Hierarchy Process)。uAHPAHP是一种定性与定量相结合的、系统化、层次化的分是一种定性与定量相结合的、系统化、层次化的分析方法。析方法。将一个复杂的多目标决策问题作为一个系统，将目标分解为将一个复杂的多目标决策问题作为一个系统，将目标分解为多个目标或准则，进而分解为多指标（或准则、约束）的若多个目标或准则，进而分解为多指标（或准则、约束）的若干层次，通过定性指标模糊量化方法算出层次单排序（权数）干层次，通过定性指标模糊量化方法算出层次单排序（权数）和总排序，以作为多指标或多方案的优化决策。和总排序，以作为多指标或多方案的优化决策。454.4.层次分析法层次分析法u基

35、本步骤基本步骤目标层目标层O(选择旅游地选择旅游地)P2黄山黄山P1桂林桂林P3北戴河北戴河准则层准则层方案层方案层C3居住居住C1景色景色C2费用费用C4饮食饮食C5旅途旅途例例.选择旅游地选择旅游地如何在如何在3 3个目的地中按照景色、个目的地中按照景色、费用、居住条件等因素选择费用、居住条件等因素选择.46目标层目标层O(选择旅游地选择旅游地)P2黄山黄山P1桂林桂林P3北戴河北戴河准则层准则层方案层方案层C3居住居住C1景色景色C2费用费用C4饮食饮食C5旅途旅途“选择旅游地选择旅游地”思维过程的归纳思维过程的归纳将将决策问题分为决策问题分为3个层次：目标个层次：目标层层O，准则层，准

36、则层C，方案层，方案层P；每层；每层有若干元素，有若干元素，各层元素间的关系各层元素间的关系用相连的直线表示。用相连的直线表示。通过通过相互比较确定各准则对目标相互比较确定各准则对目标的权重，及各方案对每一准则的的权重，及各方案对每一准则的权重。权重。将将上述两组权重进行综合，确定上述两组权重进行综合，确定各方案对目标的权重。各方案对目标的权重。层次分析法将定性分析与定量分析结合起来完成以上步骤，层次分析法将定性分析与定量分析结合起来完成以上步骤，给出决策问题的定量结果。给出决策问题的定量结果。47构造判断（成对比较）矩阵构造判断（成对比较）矩阵心理学家认为成对比较的因素不宜超过心理学家认为成

37、对比较的因素不宜超过9个，即每层不要个，即每层不要超过超过9个因素。个因素。在在确确定定各各层层次次各各因因素素之之间间的的权权重重时时，如如果果只只是是定定性性的的结结果果，则则常常常常不不容容易易被被别别人人接接受受，因因而而，SantySanty等等人人提提出出“一致矩阵法一致矩阵法”，即：，即：1.1.不把所有因素放在一起比较，而是两两相互比较。不把所有因素放在一起比较，而是两两相互比较。2.2.对比时采用相对尺度，以尽可能减少性质不同的诸因对比时采用相对尺度，以尽可能减少性质不同的诸因 素相互比较的困难，以提高准确度。素相互比较的困难，以提高准确度。判断矩阵是表示本层所有因素针对上一

38、层某一个因素判断矩阵是表示本层所有因素针对上一层某一个因素的相对重要性的比较。判断矩阵的元素的相对重要性的比较。判断矩阵的元素aij用用Santy的的19标度方法给出。标度方法给出。48判断矩阵元素判断矩阵元素aij的标度方法的标度方法标度标度含义含义1表示两个因素相比，具有同样重要性表示两个因素相比，具有同样重要性3表示两个因素相比，一个因素比另一个因素稍微重要表示两个因素相比，一个因素比另一个因素稍微重要5表示两个因素相比，一个因素比另一个因素明显重要表示两个因素相比，一个因素比另一个因素明显重要7表示两个因素相比，一个因素比另一个因素强烈重要表示两个因素相比，一个因素比另一个因素强烈重要

39、9表示两个因素相比，一个因素比另一个因素极端重要表示两个因素相比，一个因素比另一个因素极端重要2，4，6，8上述两相邻判断的中值上述两相邻判断的中值倒数倒数因素因素i与与j比较的判断比较的判断aij，则因素，则因素j与与i比较的判断比较的判断aji=1/aij49 设要比较各准则设要比较各准则C1,C2,Cn对目标对目标O的重要性的重要性A成对比较阵成对比较阵要由要由A确定确定C1,Cn对对O的权的权向量向量目标层目标层O(选择旅游地选择旅游地)准则层准则层C3居住居住C1景色景色C2费用费用C4饮食饮食C5旅途旅途C1 C2 C3 C4 C5C1C2C3C4C5稍加分析就发现上述成对比较矩阵

40、有问题(成对比较不一致)A是正互反阵是正互反阵50成对比较的不一致情况成对比较的不一致情况一致比较一致比较允许不一致，但要确定不一致的允许范围允许不一致，但要确定不一致的允许范围C1 C2 C3 C4 C5C1C2C3C4C551考察完全一致的情况考察完全一致的情况可作为一个排序向量成对比较满足满足的正互反阵的正互反阵A A称一致阵。称一致阵。A的秩为的秩为1，A的唯一非零特征根为的唯一非零特征根为n 非零特征根非零特征根n所对应的特征向量归一化后可作为权向量所对应的特征向量归一化后可作为权向量对于不一致（但在允许范围内）的成对比较阵对于不一致（但在允许范围内）的成对比较阵A，SaatySaa

41、ty等人建议等人建议用对应于最大特征根用对应于最大特征根 的特征向量作为权向量的特征向量作为权向量w，即，即一致阵一致阵性质性质允许范围是多大？如何界定？允许范围是多大？如何界定？52一致性检验：对一致性检验：对A确定不一致的允许范围确定不一致的允许范围已知：已知：n 阶一致阵的唯一非零特征根为阶一致阵的唯一非零特征根为n可证：可证：n 阶正互反阵最大特征根阶正互反阵最大特征根 n,且且 =n时为一致阵时为一致阵因此，定义一致性指标因此，定义一致性指标:CI 越大，不一致越严重越大，不一致越严重53RI000.580.901.121.241.321.411.451.491.51 n123456

42、7891110定义一致性比率定义一致性比率 CR=CI/RI 当当CR0.1时，通过一致性检验时，通过一致性检验Saaty得到的结果如下得到的结果如下为衡量为衡量CI 的大小，引入随机一致性指标的大小，引入随机一致性指标 RI。方法如下：。方法如下：则可得一致性指标：则可得一致性指标：随机构造随机构造500500个成对比较矩阵：个成对比较矩阵：计算平均值：计算平均值：通过一致性检验之后，可用通过一致性检验之后，可用A A的归一化特征向量作为权向量，否则的归一化特征向量作为权向量，否则要重新构造成对比较矩阵要重新构造成对比较矩阵A A，对，对 aij 加以调整。加以调整。54“选择旅游地选择旅游

43、地”中中准则层对目标的权准则层对目标的权向量及一致性检验向量及一致性检验准则层对目标的准则层对目标的成对比较阵成对比较阵最大特征根最大特征根=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通过一致通过一致性检验性检验55正互反阵最大特征根和特征向量的简化计算正互反阵最大特征根和特征向量的简化计算 精确计算的复杂和不必要精确计算的复杂和不必要简化计算的思路：一致阵的任一列向量都是特征向量，一致性

44、尚简化计算的思路：一致阵的任一列向量都是特征向量，一致性尚好的正互反阵的列向量都应近似特征向量，可取其某种意义下的好的正互反阵的列向量都应近似特征向量，可取其某种意义下的平均。平均。和法和法取列向量的算术平均取列向量的算术平均列向量列向量归一化归一化求求行行和和归归一一化化精确结果精确结果:w=(0.588,0.322,0.090)T,=3.01056记第记第2层（准则）对第层（准则）对第1层（目标）的权向量为层（目标）的权向量为同样求第同样求第3层层(方案方案)对第对第2层每一元素层每一元素(准则准则)的权向量的权向量方案层对方案层对C1(景色景色)的的成对比较阵成对比较阵方案层对方案层对C

45、2(费用费用)的的成对比较阵成对比较阵CnBn最大特征根最大特征根 1=3.005 2=3.002 5=3.0 权向量权向量 w1(3)w2(3)w5(3)=(0.595，0.277，0.129)=(0.082，0.236，0.682)=(0.166，0.166，0.668)选择旅游地选择旅游地57第第3层对第层对第2层的计算结果层的计算结果 w w(2 2)0.2630.2630.5950.2770.1293.0050.0030.00100.00503.0020.6820.2360.0820.4750.47530.1420.4290.4290.0550.0553.0090.1750.1930

46、.6330.0900.09030.6680.1660.1660.1100.110组合权向量组合权向量RI=0.58(n=3),CIk 均可通过一致性检验均可通过一致性检验方案方案P1对目标的组合权重为对目标的组合权重为0.595 0.263+=0.300整个方案层对目标的组合权向量为整个方案层对目标的组合权向量为(0.300,0.246,0.456)T目标层目标层O(选择旅游地选择旅游地)P2黄山黄山P1桂林桂林P3北戴河北戴河准则层准则层方案层方案层C3居住居住C1景色景色C2费用费用C4饮食饮食C5旅途旅途0.2630.2630.4750.4750.0550.0550.0900.0900.

47、1100.1100.5950.0820.4290.6330.166通过比较可知，应该首选方案通过比较可知，应该首选方案P3584.4.层次分析法层次分析法u基本步骤基本步骤建立层次结构模型建立层次结构模型该结构图包括目标层，准则层，方案层。该结构图包括目标层，准则层，方案层。构造成对比较矩阵构造成对比较矩阵用成对比较法和用成对比较法和19尺度，构造各层对上一层每一因素的尺度，构造各层对上一层每一因素的成对比较阵。成对比较阵。3 3）计算权向量并作一致性检验）计算权向量并作一致性检验对每一成对比较阵计算最大特征根和特征向量，作一致性对每一成对比较阵计算最大特征根和特征向量，作一致性检验，若通过，

48、则特征向量为权向量。检验，若通过，则特征向量为权向量。4 4）计算组合权向量（作组合一致性检验）计算组合权向量（作组合一致性检验）组合权向量可作为决策的定量依据。组合权向量可作为决策的定量依据。595.5.聚类分析聚类分析u聚类分析聚类分析(cluster analysis)(cluster analysis)是研究是研究“物以类聚物以类聚”的一种方法，在不同的学科领域得到广泛研究：的一种方法，在不同的学科领域得到广泛研究：在统计学领域，与在统计学领域，与“回归分析回归分析”和和“判别分析判别分析”并并陈为多元分析的三大方法。陈为多元分析的三大方法。在机器学习在机器学习/数据挖掘领域，被叫做数

49、据挖掘领域，被叫做“无监督学习无监督学习”（unsupervised learningunsupervised learning），另一大类叫做），另一大类叫做“有监有监督学习督学习”（supervised learningsupervised learning）60图像分割中的应用图像分割中的应用聚类示意聚类示意社交网络中的应用社交网络中的应用基因分析基因分析615.5.聚类分析聚类分析u基本思想基本思想通过某种方式衡量数据对象之间的相似度。通过某种方式衡量数据对象之间的相似度。在此基础上，将数据对象分组，使得同一组的对象在此基础上，将数据对象分组，使得同一组的对象之间是相似的（越相似越好）

50、，而不同组中的对象之间是相似的（越相似越好），而不同组中的对象之间是不相似的（差别越大越好）。之间是不相似的（差别越大越好）。u主要有两种常见的方法主要有两种常见的方法迭代的动态聚类方法迭代的动态聚类方法非迭代的层次聚类方法非迭代的层次聚类方法62迭代的动态聚类方法迭代的动态聚类方法u要点要点选定某种距离度量作为样本间的相似性度量；选定某种距离度量作为样本间的相似性度量；确定样本合理的初始分类，包括代表点的选择，初确定样本合理的初始分类，包括代表点的选择，初始分类的方法选择等；始分类的方法选择等；确定某种评价聚类结果的准则函数，以调整初始分确定某种评价聚类结果的准则函数，以调整初始分类直到达到