《MPA定量分析方法》PPT课件.ppt

杨健 中国人民大学 Renmin University of China,MPA定量分析方法,2,主讲人简介,杨健（英国兰卡斯特大学管理科学博士） 中国人民大学 公共管理学院MPA定量分析首席教授 公共管理定量分析研究所所长 电子政务博士生导师 金融信息中心主任 投资与证券主编 英国运筹学JORS国际顾问 国家高技术研究发展计划（863）评审专家 国家自然科学基金管理科学评审专家 企业年金投资管理机构评审专家,3,回头路,传言一：邓小平在一个地方视察，视察完毕后，人们安排他原路返回，邓小平发现回去的道路和来时一样很生气，令车停住，说，我一生从来不走回头路。 传言二：协兴街的老人说，小平属龙，他是从广安经渠江到嘉陵江再到长江进入大海，龙归大海不回头，所以他不回家。,4,Graph Theory,图论是一门很有实用价值的学科，它在自然科学、社会科学等各领域方面均有很大应用，近年来它发展迅速，应用广泛，已渗透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学、运筹学以及数学的其它分支中，在工程和交通运输中均获得了重要应用。,5,起源,图论也是一门起源于游戏的学科，它起源于欧拉关于哥尼斯堡七桥问题的研究。哥尼斯堡是东普鲁士首府，普莱格尔河横贯其中，上有七座桥将河中的两个岛和河岸连接，一个散步者怎样才能走遍七座桥而每座桥只经过一次？,6,哥尼斯堡七桥问题（Konigsberg）,18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)有一条名叫普莱格尔（Pregel）的河流横经其中，河上有7座桥，将河中的两个岛和河岸连结，如图1所示。,图1,7,城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这个问题看起来似乎不难，但人们始终没有能找到答案。这就是七桥问题，一个著名的图论问题。,8,当欧拉（Euler）在1736年访问Konigsberg, Prussia (now Kaliningrad Russia)时，以深邃的洞察力很快证明了这样的走法不存在！欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。,9,Lonhard Euler，17071783,瑞士人欧拉是18世纪最杰出的数学家之一，他不但在数学上做出了伟大贡献， 而且把数学成功地应用到了其他领域。欧拉一生著书颇丰，其中有许多成为数学中的经典。,10,由于长期大量的写作，加上生活条件不良，他1735年患眼疾竟致右眼失明，并且于1771年左眼也完全失明。但他凭着惊人的记忆力和心算能力，通过与助手们讨论以及直接口授等方式，又完成了大量的科学著作，直至生命的最后一刻。,11,1736年欧拉向圣彼得堡科学院提交了一篇论文，欧拉把这个问题的物理背景变换并简化为一种数学设计（称作图或网络）：即把每一块陆地用一个点来代替，将每一座桥用连接相应的两个点的一条线来代替，从而相当于得到一个图。欧拉证明了这个问题没有解。欧拉指出欧几里得几何并不适用于这个问题，因为桥不涉及“大小”，也不能用“量化计算”来解决。相反地，这问题属于“位置几何”（莱布尼茨描述拓扑学时首先使用的名称）。,12,欧拉还发现，不论什么形状的凸多面体，其顶点数v、棱数e、面数f之间总有 v-e+f=2这个关系。v-e+f被称为欧拉示性数，成为拓扑学的基础概念。 在数论中，欧拉首先引进了重要的欧拉函数(n)，用多种方法证明了费马小定理。以欧拉的名字命名的数学公式、定理等在数学书籍中随处可见。与此同时，他还在物理、天文、 建筑以至音乐、哲学方面取得了辉煌的成就。,13,欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D4个点，7座桥表示成7条连接这4个点的线，如图2所示。,图2,14,于是“七桥问题”就等价于图3中所画图形的一笔画问题了。,图3,15,欧拉注意到，每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。 除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。所以每行经一点时，计算两座桥（或线），从起点离开的线与最後回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。,16,图3的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走遍7座桥，而每座桥只许通过一次的走法。欧拉对“七桥问题”的研究是图论研究的开始，同时也为拓扑学的研究提供了一个初等的例子。,17,哥尼斯堡七桥问题的解决远远超出了它的娱乐价值，由此提出的新思想则开辟了数学的一个新的领域图论。 当然游戏娱乐对于图论的作用并没有到此为止，此后许多著名的数学游戏成为图论和拓扑学发展的催化剂和导引，如哈密尔顿问题（绕行世界问题）、四色猜想等。,18,“迷路的旅行推销员”,1857年，爱尔兰数学家哈密尔顿(Hamilton)制作了一个“环球周游”的数学玩具。他用一个正十二面体的20个顶点代表世界上20个大城市，要求你沿着正十二面体的棱，从某个顶点（城市）出发，经过每个顶点（城市）恰好一次，然后回到出发点。这样的路线被叫做哈密尔顿回路。 如何确定你画的简单图中是否有哈密尔顿回路，并找到一条回路？,19,毕达哥拉斯,毕达哥拉斯（Pythagoras，约公元前580公元前300）是著名的希腊哲学家、数学家、天文学家。生于希腊东部隆摩斯岛，卒于他林敦。早年曾受教于伊奧尼亚学派的安纳西曼德，以后游历埃及、巴比伦等地，学习古代流传下来的天文、数学知识。回乡后一度讲学，后为摆脱暴政，移居西西里岛，最后定居克罗托內，在那里广收门徒，建立一个宗教、政治、学术合一的秘密团体，后人称之为毕达哥拉斯学派，这个学派后来对柏拉图（Plato）产生很大的影响。,20,无论是解说外在物质世界，还是描写内在精神世界，都不能没有数学!，最早悟出万事万物背后都有数的法则在起作用的，是生活在2500年前的古希腊数学家、哲学家毕达哥拉斯(公元前572前497)。 毕达哥拉斯出生在爱琴海中的萨摩斯岛(今希腊东部小岛)，自幼聪明好学，曾在名师门下学习几何学、自然科学和哲学。以后因为向往东方的智慧，经过万水千山来到巴比伦、印度和埃及，吸收了阿拉伯文明和印度文明甚至中国文明的丰富营养，大约在公元前530年又返回萨摩斯岛。后来又迁居意大利南部的克罗通，创建了自己的学派，一边从事教育，一边从事数学研究。 在几何学方面，毕达哥拉斯学派证明了“三角形内角之和等于两个直角”的论断；研究了黄金分割；发现了正五角形和相似多边形的作法；还证明了正多面体只有五种正四面体、正六面体、正八面体、正十二面体和正二十面体。,21,22,23,推销员问题（哈密尔顿途径）,一个经典的数学问题：如果一个推销员要在许多个城市推销，每个城市必须而且只能经过一次，如何找到最短的路程？,24,并没有特定的公式可以对此进行计算，惟一的解决办法是找到所有可能的路程加以比较，选出最短的一种。 即使仅有四个城市，推销员也已面临着多种选择（确切地说，12种），这时候还能把所有可能的路程都找出来加以比较。但随着城市数目的增加，可能性也迅速膨胀，成指数增长，要把所有可能性都找出来，很快就变得不切实际了。,25,最近，加州大学圣地亚哥分校的佩夫兹那（ ）实验室在美国科学院院刊宣布找到了一种进行序列组装的新办法。 他们把已有的基因组片段再进行一次切割，切割成大小一样的更小的片段。这样，他们就把基因组序列的“哈密尔顿途径”变成了“尤拉途径”：在此一途径中，每个城市不限定只能访问一次，想去多少次都可以，但是每一条路只能走一次。从这个网络中找出最短的路程的问题，被称为中国邮差问题。在数学上，要追踪中国邮差比追踪推销员容易得多。,26,原子结构、分子结构、晶体结构、有机物同分异构体等相关空间结构的想象、抽象、综合及计算,思维动作的层次较高，要加强对空间结构模型、图示的观察和分析,并注意及时延伸和拓展、要精选范例作剖析。应不断提高对物质三维空间结构的剖析、综合和有关的计算能力。 范例1已知晶体硼原子组成的正十二面体，存在着20个等边三角形和一定数目顶角，每1个顶角上有1个硼原子，试通过观察下图，确定每1个结构单元由_个硼原子。,27,分析,可采用点归面、面归体的分析法。从图中可知，每个顶点上的硼原子都分属于5个正三角形所共有，故分归到每个三角形均为1/5，每个三角形有(1/5)3个硼原子，则每个结构单元所含硼原子数为： 20(1/5)312个。 答案12,28,四色问题,在给地图着色的时候，我们总是给相邻的不同区域涂上不同颜色，使用权这些区域之间有所区别。那么画一张地图，要用多少种颜色呢？,29,四色问题,30,1852年10月，刚从伦敦大学毕业的青年数学家弗兰西斯古色利在为一张英国地图着色的时候，发现最多只要4种颜色，就能把相邻的国家区别出来了。古色利写信把自己的发现告诉在大学学习物理的弟弟弗雷德里克，弗雷德里克又向他的数学老师摩根提出，摩根又去请教哈密尔顿，并由此引发了一场长达120多年的证明大战。这就是著名的四色问题。,31,德摩尔根：地图四色定理,地图四色定理最先是由一位叫古德里（Francis Guthrie）的英国大学生提出来的。德摩尔根（A，DeMorgan，18061871）1852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。他在信中简述了自己证明四色定理的设想与感受。一个多世纪以来，数学家们为证明这条定理绞尽脑汁，所引进的概念与方法刺激了拓扑学与图论的生长、发展。,32,以下摘录德摩尔根致哈密顿信的主要部分，译自 J Fauve1 and J.Gray（eds.），The History of Mathematics ：A Reader，pp 597598。,德摩尔根致哈密顿的信（1852年10月23日） 我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。现在的问题是是否会出现需要五种或更多种颜色的情形。就我目前的理解，若四个不订分割的区域两两具有公共边界线，则其中三个必包围第四个而使其不与任何第五个区域相毗邻。这事实若能成立，那么用四种颜色即可为任何可能的地图着色，使除了在公共点外同种颜色不会现画出三个两两具有公共边界的区域ABC，那么似乎不可能再画第四个区域与其他三个区域的每一个都有公共边界，除非它包围了其中一个区域（图2）。但要证明这一点却很棘手，我也不能确定问题复杂的程度一对此您的意见如何呢？并且此事如果当真，难道从未有人注意过吗？我的学生说这是在给一幅英国地图着色时提出的猜测。我越想越觉得这是显然的事情。如果您能举出一个简单的反例来，说明我像一头蠢驴，那我只好重蹈史芬克斯的复辙了。,33,34,35,1879年，肯泊在一篇论文中发表了一个证明，1890年，希伍德指出了肯泊证明中的错误，同时也指出，肯泊的方法可以用来成功证明五色问题。 1976年美国伊利大学数学家阿佩尔（K. Appel）与哈肯（W. Haken）宣告借助电子计算机获得了四色定理的证明，三台计算机上花费了1200个小时计算，终于完成了四色定理的证明。 尽管如此，许多数学家还在寻求书面的证明。,36,简单的网络及其应用,简单的网络是包含有一些点和点与点之间的一些弧的一种图形。弧的两端之点称为结（或结点）。 一个结可由其所联结的弧的数目来识别，例如，三个弧的结称为3弧结，四个弧的结称为4弧结，n弧结。 当n为奇数时称为奇结；n为偶数时称为偶结。,37,设有两个网络，不管它们的形状如何不同，只要结和弧的数目相同，而且在连通关系上完全一样，便可视为相同的网络。,38,以上两图形状虽不同，然实质上是两个相同的网络，数学上称“拓朴等价”,在拓朴学中，点、线、面等都是可以在原空间中任意挪动伸缩的。所以，正方形与圆没有区别，碗和盘子也等价，钻石戒子与皮筋套也是一回事，重要的只是结构。只要不破坏原来的结构，凡可通过连续伸缩互相变化的东西都等价。,39,比如有一类大家都见过的套环游戏，这种游戏一般是用铁丝做成许多圈套交错“套”在一起，要求你把其中的一个套取出来（这种游戏中最古老也最有名的是九连环）。 许多人看见这种游戏，总是不加思索就开始穿插，往往是几十分钟以后还在那里把铁丝环穿来插去，不得要领。如果有了拓朴的思想，把铁丝环画在纸上。然后该延长的地方延长，该缩小的地方缩小，你就会发现问题变得一目了然，容易得多了。,40,九连环协会会歌,坎坎连环兮，置之铁之端兮。九环扣且连猗。 不上不下，胡连好九连环兮？不拉不损，胡瞻尔环有裂痕兮？彼小人兮，用暴力兮！ 九连环兮，环相扣兮。上上下下，旦复旦兮。,41,益智玩具很多是民间长期流传的，或是在其基础上开发研制的，具有非常浓厚的民族文化色彩，有一定的智能性和挑战性。这类玩具质地多为木制和铁制，适合当前一部分成人厌倦冷冰冰的机器、渴望回归自然的心理。 益智玩具主要包括棋类如围棋、象棋，插接类如鲁班锁、鲁班球，拼板类如华容道、七巧板，迷宫类，缝隙类如鸳鸯扣及拓朴类。,42,43,44,由定义，图中A、C、E、F为偶结，B、G为奇结，H和D分别为始点和终点。,作为一个图，其图形还必须满足以下条件： （1）每条边都有两个端点（可以重合）作为结点；（2）各条边之间互不相交。 图中与一个结点相连结的边数称为这个结点的度数。度数为偶数的点叫做偶结点。度数为奇数的点称为奇结点。,45,一个图能否一笔画出的规律,（1） 一个图若能一笔画出，首先必定是个连通图； （2） 一个连通图，若没有奇结点（即全是偶结点），那么这个图一定可以一笔画成，而且可以从任一偶结点出发，一笔画成回到出发点； （3）一个连通图，若只有两个奇结点，那么这个图也可以一笔画成，而且只能从某一奇结点出发一笔画成，到另一奇结点结束。 （4）一个图，若奇结点个数多于两个，那么这个图一定不能一笔画成。,46,一个可以一笔画成而没有重复笔划的网络称为“连绘网络”，如图（11-3）所示。亦称一笔画：“一笔一个回头鸟”？,47,问题：下列图形是不是连绘网络?,48,连绘网络,如果一个连绘网络没有起点和终点（即起点和终点在同一个结上），称为连绘闭路网络；始点和终点不在同一结上的连绘网络，称为连绘开路网络。 理论证明：连绘闭路网络的结必然全部是偶结，连绘开路网络只能有两个奇结，否则就不能连绘。,49,利用简单网络的上述特性，可以解决某些具体问题：例如巡回路线问题等。 大街小巷的交叉点有的是奇结（T字口、三岔口、五岔口），有的是偶结（十字口、四岔口、厂形转角）。 你走过哪些城市的街道？,50,巡逻队,在巡回中，如果没有奇结，不论从哪一点出发，是可以不走重复路而能走遍全部街巷回返出发点的。如右图。,51,52,“连绘开路网络的奇结只有两个”,如果街巷有奇结，那就要根据“连绘开路网络的奇结只有两个”的原则，把多于两个的全部奇结在交通图上用虚线一对一对地联结起来。那么，虚线就是要走重复路（回头路）的路线。,53,例1、下列各图哪些能一笔画出，哪些不能？,54,解：（3）（5）没有奇结点，全是偶结点，它可以从任一点出发，一笔画成后回到起点；（1）（6）均有两个奇结点，它们可以从任一奇结点出发，一笔画成后回到另一结点处；（3）（4）（7）均有两个以上的奇结点，它们不可能一笔画成。,55,例、下图表示一个展览馆的平面图，其中共有5个展室，每个展室都有一个门通向室外。问：能否设计一条参观路线，一次不重复地穿过每一个门并能回到原地。,56,解：将5个展室看作5个点，室外看作一个点F，每道门看作连结两点间的线，从而得到右图。在右图中共有6个奇结点，所以不可能不重复地一笔画出。即在左图中不可能设计一条不重复地穿过每一道门的参观路线。,57,清彩繪絹本江西全省圖說 （局部，16621731年）藏大英圖書館。,筑路、辟路、修路、走路，是人类永远不停在做着的事情，也是人类文明演进过程中的一项鲜明指标。 人们为了不同的目的，利用各式各样的交通工具，在各式各样的道路上，川流不息的奔走着。,58,一、货郎问题,59,60,如上图有四个奇结，若要使它成为连绘开路网络，需把两个奇结用虚线联系起来，因C和D之间的距离比AD及BD都短，故作虚线CD。这样，从A或B出发到B或A，只要在CD一段重复走一次，就能以最短路线走遍街巷。,61,联结原则,如奇结超过四个时，可把奇结成对地联结起来，联结时有如下两条原则必须遵循： （1）联线不得有重迭线段； （2）在每一个环路中，联线的总长度不得超过环路全长的一半。,62,63,上图中的虚线是根据以上两条原则画的。这样的联结法就是最短的路线。 除了画虚线部分以外，其余的街巷都不必走重复路线便可走遍全部街道。,64,讨论案例：如下图的网络代表一个邮递路线，数字表示弧的长短（不按比例尺）。试找出最短路程和邮局。,65,图中共有A、B、C、D、F、G六个奇结，所以，必须把两对奇结联结起来，使可减少四个奇结，使网络变成连绘开路。 联结奇结应考虑从最短距离开始，故联结FC（2）和GD（3）。 在传递时，应以A或B为起点，以B或A为终点，并且在DG和CF各重复行走一次，其余的路线可单行而不重复，故最短的巡回路线为： AEDGDCFCBFGEFAB,66,67,二、最短路径问题,68,设图（11-9）为A、B两城间的公路网，C、D、E是三个中途站。弧旁的数字代表两站间距离的公里数（不按比例尺）。 试求A、B间的最短连接路程。,69,70,解决方案,从图形来分析，ED这条路线是多余的。 所以，ACDB是A、B间的最短联结线，全长46公里。,71,故事新编,72,出国访问! 飞机失事!,73,原始森林!,74,75,76,巫师智慧!,77,酋长女儿? 隔壁姐姐?,78,网络大法!,如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径，我们也可以将一个有向图看作一个流网络来解决另一类型的问题。流网络比较适合用来模拟液体流经管道、电流在电路网络中的运动、信息网络中信息的传递等等类似的过程。,79,参看下图，给定一个有向图G=(V,E)，把图中的边看作管道，每条边上有一个权值，表示该管道的流量上限。给定源点s和汇点t，现在假设在s处有一个水源，t处有一个蓄水池，问从s到t的最大水流量是多少，类似于这类的问题都可归结为网络流问题。,80,81,在流网络中，每条有向边可以被看导管。每根导管有一个固定的容量，代表物质流经这个导管的最大速率，例如一个管道每小时最多能流过200加仑液体或者一根电线最多能承载20安培的电流。流网络中的顶点可以看作是导管的连接处。除了源点和汇点之外，物质流进每个点的速率必须等于流出这个点的速率。如果我们把研究的物质特化为电流，这种“流的保持”属性就好像电路中的基尔霍夫电流定律一样。,82,下面我们用数学语言来进行相关概念的定义,设G=(V,E)是一个流网络，设c(u, v)0 表示从u到v的管道的流量上限。设s为源，t为汇。G的流是一个函数f: VV R，且满足下面三个特征： 1. 容量限制：对于所有的 u,v V, 要求f(u, v) = c(u, v) 2. 斜对称性：对于所有的 u,v V, 要求f(u, v) = - f(v, u)3.流的保持：对于所有的 u V - s, t，要求： f(u, v) = 0(vV) f(u,v)称为从结点u到v的网络流，它可以为正也可以为负。流 f 的值定义为：|f| = f(s, v)(vV)即从源出发的所有流的总和。最大流问题就是找出给定流网络的最大流。网络流问题可以归结为一类特殊的线性规划问题。,83,解决最大流问题常用算法一览,解决最大流问题的常用到Ford-Fulkerson方法，之所以称其方法而不是算法，是因为在这种思想下包含着若干种时间复杂度不同的实现，其中较多地是使用Edmonds-Karp算法。与此相对，Push-relabel算法采用了与Ford-Fulkerson方法完全不同的思考角度，降低了渐进意义下的时间复杂度。而relabel-to-front算法则是对Push-relabel算法的改良和精炼，效率更佳。 关于这三种常用算法的时间复杂度可见下表：（其中V表示图的顶点数，E表示边数） 算法名称Edmonds-Karp算法一般性的push-relabel算法relabel-to-front算法时间复杂度O(V*E2)O(V2*E)O(V3)可以看出，当给定的有向图比较稀疏时，三种算法的效率不会相差太多，但当网络稠密时，relabel-to-front算法在效率上有着明显的优势。,84,三、运输量问题：瓶颈,图（11-10）代表一个铁路网，弧旁的数字表示该段铁路每日能作的单行最高运输量（以万吨计）。 请问由A到B的每日最高运输量是多少?,85,86,87,原则：“刀刀见血，例无虚发”,事实上，焦恩俊的武功一塌糊涂，前不久他在拍另一部戏时，导演一声“开始”，他的枪就向摄像机的镜头掷了过去，只听得“嘭”的一声，长枪的枪头穿入摄像机镜头的保护中，离镜头只有0.01毫米的距离，太悬了。可见，“小李飞刀”也是徒有虚名呀。,88,最大流最小分割法,89,解决方案:最大流最小分割,在A、B之间任何处作种种虚线，把各段铁路路线截成两段。 从图上可知，各虚线所截断的铁路的单行最高运输之和（自左至右）分别为32、65、31、40、24，其中以65为最大，24为最小。 根据“最大流最小分割”的定理，24万吨是A、B间的每日最大流。,90,求网络的最小费用最大流,91,Ford和Fulkerson迭加算法,基本思路：把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流. 迭加算法： 1) 给定目标流量F或,给定最小费用的初始可行流fij=0 2) 若V(f)=F,停止,f为最小费用流;否则转(3). 3) 构造fij 相应的新的费用有向图W(fij),在W(fij)寻找Vs到Vt的最小费用有向路P(最短路),沿P增加流f的流量直到F,转(2);若不存在从Vs到Vt的最小费用的有向路P,停止.f就是最小费用最大流. 具体解题步骤： 设图中双线所示路径为最短路径，费用有向图为W（fij）,92,在图(a)中给出零流 f,在图(b)中找到最小费用有向路,修改图(a)中的可行流,=min4,3,5=3,得图(c),再做出(c)的调整容量图,再构造相应的新的最小费用有向路得图(d), 修改图(c)中的可行流, =m