常用系统建模方法.ppt

常用系统建模方法,主要参考资料齐欢，王小平.系统建模与仿真（第2版），第2章姜启源,谢金星,叶俊.数学模型（第3版），第1章,1,常用系统建模方法,1.系统模型的概述2.建模的逻辑思维方法3.图解建模法4.层次分析法5.聚类分析,2,1.系统模型的概述,从现实对象到数学模型模型是为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物。模型集中反映了原型中人们需要的那一部分特征。,3,1.系统模型的概述,从现实对象到数学模型系统模型是研究和掌握系统运动规律的有力工具，它是认识、分析、设计、预测、控制实际系统的基础，也是解决系统工程问题不可缺少的技术手段。建立有效且可靠的系统模型是系统研究者的首要任务。数学模型是系统模型的最主要和最常用的表示方式。,4,1.系统模型的概述,数学模型与数学建模数学模型（MathematicalModel）对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，得到的一个数学结构。数学建模（MathematicalModeling）建立数学模型的全过程，包括表述、求解、解释、检验等。,5,1.系统模型的概述,一个简单的数学模型：“航行问题”甲乙两地相距750千米，船从甲到乙顺水航行需30小时，从乙到甲逆水航行需50小时，问船的速度是多少?,6,用x表示船速，y表示水速，列出方程：,答：船速每小时20千米/小时.,x=20y=5,1.系统模型的概述,一个简单的数学模型：“航行问题”可以看出，上述过程的主要步骤如下：作出简化假设（船速、水速为常数）；用符号表示有关量（x,y表示船速和水速）；用物理定律（匀速运动的距离等于速度乘以时间）列出数学式子（二元一次方程）；求解得到数学解答（x=20,y=5）；回答原问题（船速每小时20千米/小时）。,7,1.系统模型的概述,数学模型的特点模型的逼真性和可行性模型的渐进性模型的强健性模型的可转移性,8,模型的非预制性模型的条理性模型的技艺性模型的局限性,1.系统模型的概述,数学模型的分类应用领域人口、交通、经济、生态数学方法初等数学、微分方程、规划、统计表现特性确定和随机，静态和动态，离散和连续，线性和非线性了解程度白箱、灰箱、黑箱,9,1.系统模型的概述,数学建模的基本方法机理分析根据对客观事物特性的认识，找出反映内部机理的数量规律。测试分析（实验统计建模）将对象看作“黑箱”，通过对量测数据的统计分析，找出与数据拟合最好的模型。二者结合用机理分析建立模型结构，用测试分析确定模型参数,10,1.系统模型的概述,数学建模的基本步骤,11,1.系统模型的概述,数学建模的基本步骤1）模型准备了解实际背景明确建模目的搜集有关信息掌握对象特征,12,形成一个比较清晰的“问题”,1.系统模型的概述,数学建模的基本步骤2）模型假设针对问题特点和建模目的，作出合理的、简化的假设在合理与简化之间作出折中3）模型构成用数学的语言、符号描述问题发挥想像力使用类比法尽量采用简单的数学工具,13,1.系统模型的概述,数学建模的基本步骤4）模型求解利用各种数学方法、软件和计算机技术解析解、仿真5）模型分析例如，对结果的误差分析、统计分析、模型对数据的稳定性分析6）模型检验与实际现象、数据比较，检验模型的合理性、适用性,14,2.建模的逻辑思维方法,建模是一项复杂的思维活动，也可以看成是一门艺术，因而既没有统一的模式，也没有固定的方法，需要多方面的能力分析综合能力抽象概括能力想象洞察能力运用数学工具的能力通过实践验证数学模型的能力通过实例研究，了解建模过程常用的思维方法，包括抽象、归纳、演绎、类比等。,15,2.建模的逻辑思维方法,1)抽象揭示事物的共性和联系的规律忽略每个具体事物的特殊性，着眼于整体和一般规律实例研究：椅子能在不平的地面上放稳吗？把椅子往不平的地面上一放，通常只有三只脚着地，放不稳，然而只要稍挪动几次，就可以四脚着地，放稳了。为什么？,16,椅子能在不平的地面上放稳吗？,问题分析涉及的对象：地面，椅子椅子的位置和调整放稳：椅子的四只脚着地模型假设四条腿一样长，椅脚与地面点接触，四脚连线呈正方形;地面高度连续变化，可视为数学上的连续曲面;地面相对平坦，使椅子在任意位置至少三只脚同时着地。,17,椅子能在不平的地面上放稳吗？,模型构成用数学语言把椅子位置和四只脚着地的关系表示出来。1）椅子位置和调整的表述利用正方形（椅脚连线）的对称性用（对角线与x轴的夹角）表示椅子位置以中心为对称点，正方形绕中心的旋转对应椅子位置的调整,18,正方形ABCD绕O点旋转,椅子能在不平的地面上放稳吗？,模型构成2）椅脚着地的数学表示四只脚着地：椅脚与地面距离为零，距离是的函数,19,正方形ABCD绕O点旋转,四个距离(四只脚),两个距离,f()：A,C两脚与地面距离之和,g()：B,D两脚与地面距离之和,椅子能在不平的地面上放稳吗？,模型构成在此基础上，用数学语言把椅子位置和四只脚着地的关系表示出来：,20,f(),g()是连续函数,对任意,f()和g()至少一个为0,地面为连续曲面,椅子在任意位置至少三只脚着地,椅子能在不平的地面上放稳吗？,模型构成问题的形式化描述：,21,已知：f(),g()是连续函数;对任意，f()g()=0;且g(0)=0，f(0)0.证明：存在0，使f(0)=g(0)=0.,椅子能在不平的地面上放稳吗？,模型求解主要思路,22,将椅子旋转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为连续函数,据连续函数的基本性质,必存在0,使h(0)=0,即f(0)=g(0).因为f()g()=0,所以f(0)=g(0)=0.,2.建模的逻辑思维方法,2)归纳从特殊的具体的认识推进到一般的抽象的认识的一种思维方式。立足于观察、经验或实验的基础上的；依据若干已知的不完全的现象推断尚属未知的现象。实例研究：开普勒第三定律的发现,23,开普勒第三定律的发现,开普勒第一定律也称椭圆定律、轨道定律、行星定律。每一行星沿一个椭圆轨道环绕太阳，而太阳则处在椭圆的一个焦点上。开普勒第二定律在相等时间内，太阳和运动中的行星的连线（向量半径）所扫过的面积都是相等的。,24,开普勒第三定律的发现,开普勒第三定律也叫行星运动定律：绕以太阳为焦点的椭圆轨道运行的所有行星，其各自椭圆轨道半长轴a的立方与周期T的平方之比是一个常量。,25,k为开普勒常数,2.建模的逻辑思维方法,3)演绎由一般性的命题推出特殊命题的推理方法。典型的，如公理化的几何学实例研究：牛顿万有引力定律的演绎,26,牛顿万有引力定律的演绎,模型假设开普勒第一、二、三定律牛顿运动第二定律a=F/m(F=ma)：物体加速度的大小跟作用力成正比，跟物体的质量成反比，加速度的方向跟作用力的方向相同。,27,极坐标系(r,),太阳(0,0),行星位置：向径,牛顿万有引力定律的演绎,模型假设,28,a长半轴,b短半轴,e离心率,1）行星运行轨道,3）行星运行周期T,2）单位时间扫过面积为常数A,m行星质量,绝对常数,4）行星运行受力,模型构成,29,向径的基向量（平面直角坐标）,x,y,30,万有引力定律,需证明4A2/p=kM（与哪一颗行星无关）,A单位时间扫过面积,2.建模的逻辑思维方法,4)类比在两类不同的事物之间进行对比，找出若干相同或相似点之后，推测在其它方面也可能存在相同或相似之处的一种思维方式。实例研究1）机械系统和电路系统的类比。2）方式算法：遗传算法、蚁群优化算法、人工神经网络、粒子群优化算法(ParticleSwarmOptimization),31,PSO算法,PSO是一种基于群体智能的进化计算方法,由Kennedy和Eberhart博士于1995年提出。基本原理,32,将最优解的搜索类比于鸟群的捕食行为。设想一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有鸟都不知道食物在哪里，但是他们知道当前的位置离食物还有多远，那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域，根据自己飞行的经验判断食物的所在。,基本原理在PSO中，把一个优化问题看作是在空中觅食的鸟群，那么“食物”就是优化问题的最优解，而在空中飞行的每一只觅食的“鸟”就是PSO算法中在解空间中进行搜索的一个“粒子”(Particle)。粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个被目标函数决定的适应值(fitnessvalue)，这个适应值用于评价粒子的“好坏”程度。每个粒子知道自己到目前为止发现的最好位置（particlebest，记为pbest）和当前的位置，pbest就是粒子本身找到的最优解，这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(globalbest，记为gbest)，gbest是在pbest中的最好值，即是全局最优解，这个可以看作是整个群体的经验。,33,算法描述,34,假设在一个N维空间进行搜索，粒子i的信息可用两个N维向量来表示：第i个粒子的位置可表示为速度为在找到两个最优解后，粒子即可根据下式来更新自己的速度和位置：,：是粒子i在第k次迭代中第d维的速度；：是粒子i在第k次迭代中第d维的当前位置；,(1),(2),w是惯性因子，c1和c2是学习因子或加速系数,算法描述,35,2.建模的逻辑思维方法,5)移植将一个或几个学科领域中的理论和行之有效的研究方法、研究手段移用到其它领域当中去，为解决其它学科领域中存在的疑难问题提供启发和帮助。实例研究1）论文评价与谷歌PageRank方法2）计算圆周率的浦丰投针模型,36,浦丰投针模型,37,x,矩形G,阴影g,=2/,3.图解建模法,图解建模法是一种采用点和线组成的、用以描述系统的图形进行建模的方法，可用于描述自然界和人类社会中的大量事物和事物之间的关系。实例研究城市公共交通网络模型物品交换模型,38,城市公共交通网络模型,39,物品交换模型,问题甲有物品X,乙有物品Y,双方为满足更高的需要，商定相互交换一部分。研究实物交换方案。,40,用x,y分别表示甲(乙)占有X,Y的数量。设交换前甲占有X的数量为x0,乙占有Y的数量为y0,作图：,若不考虑双方对X,Y的偏爱，则矩形内任一点p(x,y),都是一种交换方案：甲占有(x,y)，乙占有(x0-x,y0-y),分析与建模,41,甲的无差别曲线,如果甲占有(x1,y1)与占有(x2,y2)具有同样的满意程度，即p1,p2对甲是无差别的，,线上各点的满意度相同,线的形状反映对X,Y的偏爱程度，,比MN各点满意度更高的点如p3，在另一条无差别曲线M1N1上。于是形成一族无差别曲线（无数条）。,42,无差别曲线族的性质：,单调减(x增加,y减小),下凸(凸向原点),互不相交,在p1点占有x少、y多，宁愿以较多的y换取较少的x;,在p2点占有y少、x多，就要以较多的x换取较少的y。,甲的无差别曲线族记作,f(x,y)=c1,c1满意度,（f等满意度曲线）,43,乙的无差别曲线族g(x,y)=c2具有相同性质（形状可以不同）,双方的交换路径,乙的无差别曲线族g=c2(坐标系xOy,且反向）,甲的无差别曲线族f=c1,双方满意的交换方案必在AB（交换路径）上,因为在AB外的任一点p,(双方)满意度低于AB上的点p,两族曲线切点连线记作AB,44,p,交换方案的进一步确定,交换方案交换后甲的占有量(x,y),0xx0,0yy0矩形内任一点,交换路径AB,等价交换原则,X,Y用货币衡量其价值，设交换前x0,y0价值相同，则等价交换原则下交换路径为:,(x0,0),(0,y0)两点的连线CD,AB与CD的交点p,设X单价a,Y单价b,则等价交换下ax+by=s(s=ax0=by0),4.层次分析法,美国运筹学家匹茨堡大学教授萨蒂(T.L.Saaty)于1970年代为美国国防部研究“根据各个工业部门对国家福利的贡献大小而进行电力分配”课题时提出了层次分析法AHP(AnalyticHierarchyProcess)。AHP是一种定性与定量相结合的、系统化、层次化的分析方法。将一个复杂的多目标决策问题作为一个系统，将目标分解为多个目标或准则，进而分解为多指标（或准则、约束）的若干层次，通过定性指标模糊量化方法算出层次单排序（权数）和总排序，以作为多指标或多方案的优化决策。,45,4.层次分析法,基本步骤,46,目标层,O(选择旅游地),准则层,方案层,例.选择旅游地,如何在3个目的地中按照景色、费用、居住条件等因素选择.,47,“选择旅游地”思维过程的归纳,将决策问题分为3个层次：目标层O，准则层C，方案层P；每层有若干元素，各层元素间的关系用相连的直线表示。,通过相互比较确定各准则对目标的权重，及各方案对每一准则的权重。,将上述两组权重进行综合，确定各方案对目标的权重。,层次分析法将定性分析与定量分析结合起来完成以上步骤，给出决策问题的定量结果。,48,构造判断（成对比较）矩阵,心理学家认为成对比较的因素不宜超过9个，即每层不要超过9个因素。,在确定各层次各因素之间的权重时，如果只是定性的结果，则常常不容易被别人接受，因而，Santy等人提出“一致矩阵法”，即：1.不把所有因素放在一起比较，而是两两相互比较。2.对比时采用相对尺度，以尽可能减少性质不同的诸因素相互比较的困难，以提高准确度。,判断矩阵是表示本层所有因素针对上一层某一个因素的相对重要性的比较。判断矩阵的元素aij用Santy的19标度方法给出。,49,判断矩阵元素aij的标度方法,50,设要比较各准则C1,C2,Cn对目标O的重要性,A成对比较阵,要由A确定C1,Cn对O的权向量,稍加分析就发现上述成对比较矩阵有问题(成对比较不一致),51,成对比较的不一致情况,允许不一致，但要确定不一致的允许范围,52,考察完全一致的情况,可作为一个排序向量,成对比较,A的秩为1，A的唯一非零特征根为n,非零特征根n所对应的特征向量归一化后可作为权向量,对于不一致（但在允许范围内）的成对比较阵A，Saaty等人建议用对应于最大特征根的特征向量作为权向量w，即,一致阵性质,允许范围是多大？如何界定？,53,一致性检验：对A确定不一致的允许范围,已知：n阶一致阵的唯一非零特征根为n,可证：n阶正互反阵最大特征根n,且=n时为一致阵,因此，定义一致性指标:,CI越大，不一致越严重,54,定义一致性比率CR=CI/RI,当CR0.1时，通过一致性检验,Saaty得到的结果如下,为衡量CI的大小，引入随机一致性指标RI。方法如下：,则可得一致性指标：,随机构造500个成对比较矩阵：,计算平均值：,通过一致性检验之后，可用A的归一化特征向量作为权向量，否则要重新构造成对比较矩阵A，对aij加以调整。,55,“选择旅游地”中准则层对目标的权向量及一致性检验,准则层对目标的成对比较阵,最大特征根=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,通过一致性检验,56,正互反阵最大特征根和特征向量的简化计算,精确计算的复杂和不必要,简化计算的思路：一致阵的任一列向量都是特征向量，一致性尚好的正互反阵的列向量都应近似特征向量，可取其某种意义下的平均。,和法取列向量的算术平均,精确结果:w=(0.588,0.322,0.090)T,=3.010,57,记第2层（准则）对第1层（目标）的权向量为,同样求第3层(方案)对第2层每一元素(准则)的权向量,方案层对C1(景色)的成对比较阵,方案层对C2(费用)的成对比较阵,最大特征根1=3.0052=3.0025=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),选择旅游地,58,第3层对第2层的计算结果,组合权向量,RI=0.58(n=3),CIk均可通过一致性检验,方案P1对目标的组合权重为0.5950.263+=0.300,整个方案层对目标的组合权向量为(0.300,0.246,0.456)T,0.263,0.475,0.055,0.090,0.110,0.595,0.082,0.429,0.633,0.166,通过比较可知，应该首选方案P3,4.层次分析法,基本步骤建立层次结构模型该结构图包括目标层，准则层，方案层。构造成对比较矩阵用成对比较法和19尺度，构造各层对上一层每一因素的成对比较阵。3）计算权向量并作一致性检验对每一成对比较阵计算最大特征根和特征向量，作一致性检验，若通过，则特征向量为权向量。4）计算组合权向量（作组合一致性检验）组合权向量可作为决策的定量依据。,59,5.聚类分析,聚类分析(clusteranalysis)是研究“物以类聚”的一种方法，在不同的学科领域得到广泛研究：在统计学领域，与“回归分析”和“判别分析”并陈为多元分析的三大方法。在机器学习/数据挖掘领域，被叫做“无监督学习”（unsupervisedlearning），另一大类叫做“有监督学习”（supervisedlearning）,60,61,图像分割中的应用,聚类示意,社交网络中的应用,基因分析,5.聚类分析,基本思想通过某种方式衡量数据对象之间的相似度。在此基础上，将数据对象分组，使得同一组的对象之间是相似的（越相似越好），而不同组中的对象之间是不相似的（差别越大越好）。主要有两种常见的方法迭代的动态聚类方法非迭代的层次聚类方法,62,迭代的动态聚类方法,要点选定某种距离度量作为样本间的相