《MPA定量分析方法课件》由会员分享，可在线阅读，更多相关《MPA定量分析方法课件（97页珍藏版）》请在金锄头文库上搜索。
1、杨健 中国人民大学 Renmin University of China,MPA定量分析方法,2,主讲人简介,杨健（英国兰卡斯特大学管理科学博士） 中国人民大学 公共管理学院MPA定量分析首席教授 公共管理定量分析研究所所长 电子政务博士生导师 金融信息中心主任 投资与证券主编 英国运筹学JORS国际顾问 国家高技术研究发展计划（863）评审专家 国家自然科学基金管理科学评审专家 企业年金投资管理机构评审专家,3,回头路,传言一：邓在一个地方视察，视察完毕后，人们安排他原路返回，邓发现回去的道路和来时一样很生气，令车停住，说，我一生从来不走回头路。 传言二：协兴街的老人说，属龙，他是从广安经渠
2、江到嘉陵江再到长江进入大海，龙归大海不回头，所以他不回家。,4,Graph Theory,图论是一门很有实用价值的学科，它在自然科学、社会科学等各领域方面均有很大应用，近年来它发展迅速，应用广泛，已渗透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学、运筹学以及数学的其它分支中，在工程和交通运输中均获得了重要应用。,5,起源,图论也是一门起源于游戏的学科，它起源于欧拉关于哥尼斯堡七桥问题的研究。哥尼斯堡是东普鲁士首府，普莱格尔河横贯其中，上有七座桥将河中的两个岛和河岸连接，一个散步者怎样才能走遍七座桥而每座桥只经过一次？,6,哥尼斯堡七桥问题（Konigsberg）,18世纪在哥尼斯堡
3、城(今俄罗斯加里宁格勒)有一条名叫普莱格尔（Pregel）的河流横经其中，河上有7座桥，将河中的两个岛和河岸连结，如图1所示。,图1,7,城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这个问题看起来似乎不难，但人们始终没有能找到答案。这就是七桥问题，一个著名的图论问题。,8,当欧拉（Euler）在1736年访问Konigsberg, Prussia (now Kaliningrad Russia)时，以深邃的洞察力很快证明了这样的走法不存在！欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。,9,Lonhar
4、dEuler，17071783,瑞士人欧拉是18世纪最杰出的数学家之一，他不但在数学上做出了伟大贡献， 而且把数学成功地应用到了其他领域。欧拉一生著书颇丰，其中有许多成为数学中的经典。,10,由于长期大量的写作，加上生活条件不良，他1735年患眼疾竟致右眼失明，并且于1771年左眼也完全失明。但他凭着惊人的记忆力和心算能力，通过与助手们讨论以及直接口授等方式，又完成了大量的科学著作，直至生命的最后一刻。,11,1736年欧拉向圣彼得堡科学院提交了一篇论文，欧拉把这个问题的物理背景变换并简化为一种数学设计（称作图或网络）：即把每一块陆地用一个点来代替，将每一座桥用连接相应的两个点的一条线来代替，
5、从而相当于得到一个图。欧拉证明了这个问题没有解。欧拉指出欧几里得几何并不适用于这个问题，因为桥不涉及“大小”，也不能用“量化计算”来解决。相反地，这问题属于“位置几何”（莱布尼茨描述拓扑学时首先使用的名称）。,12,欧拉还发现，不论什么形状的凸多面体，其顶点数v、棱数e、面数f之间总有 v-e+f=2这个关系。v-e+f被称为欧拉示性数，成为拓扑学的基础概念。 在数论中，欧拉首先引进了重要的欧拉函数(n)，用多种方法证明了费马小定理。以欧拉的名字命名的数学公式、定理等在数学书籍中随处可见。与此同时，他还在物理、天文、 建筑以至音乐、哲学方面取得了辉煌的成就。,13,欧拉是这样解决问题的：既然陆
6、地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D4个点，7座桥表示成7条连接这4个点的线，如图2所示。,图2,14,于是“七桥问题”就等价于图3中所画图形的一笔画问题了。,图3,15,欧拉注意到，每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。 除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。所以每行经一点时，计算两座桥（或线），从起点离开的线与最後回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。,16,图3的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走
7、遍7座桥，而每座桥只许通过一次的走法。欧拉对“七桥问题”的研究是图论研究的开始，同时也为拓扑学的研究提供了一个初等的例子。,17,哥尼斯堡七桥问题的解决远远超出了它的娱乐价值，由此提出的新思想则开辟了数学的一个新的领域图论。 当然游戏娱乐对于图论的作用并没有到此为止，此后许多著名的数学游戏成为图论和拓扑学发展的催化剂和导引，如哈密尔顿问题（绕行世界问题）、四色猜想等。,18,“迷路的旅行推销员”,1857年，爱尔兰数学家哈密尔顿(Hamilton)制作了一个“环球周游”的数学玩具。他用一个正十二面体的20个顶点代表世界上20个大城市，要求你沿着正十二面体的棱，从某个顶点（城市）出发，经过每个顶
8、点（城市）恰好一次，然后回到出发点。这样的路线被叫做哈密尔顿回路。 如何确定你画的简单图中是否有哈密尔顿回路，并找到一条回路？,19,毕达哥拉斯,毕达哥拉斯（Pythagoras，约公元前580公元前300）是著名的希腊哲学家、数学家、天文学家。生于希腊东部隆摩斯岛，卒于他林敦。早年曾受教于伊奧尼亚学派的安纳西曼德，以后游历埃及、巴比伦等地，学习古代流传下来的天文、数学知识。回乡后一度讲学，后为摆脱暴政，移居西西里岛，最后定居克罗托內，在那里广收门徒，建立一个宗教、政治、学术合一的秘密团体，后人称之为毕达哥拉斯学派，这个学派后来对柏拉图（Plato）产生很大的影响。,20,无论是解说外在物质世
9、界，还是描写内在精神世界，都不能没有数学!，最早悟出万事万物背后都有数的法则在起作用的，是生活在2500年前的古希腊数学家、哲学家毕达哥拉斯(公元前572前497)。 毕达哥拉斯出生在爱琴海中的萨摩斯岛(今希腊东部小岛)，自幼聪明好学，曾在名师门下学习几何学、自然科学和哲学。以后因为向往东方的智慧，经过万水千山来到巴比伦、印度和埃及，吸收了阿拉伯文明和印度文明甚至中国文明的丰富营养，大约在公元前530年又返回萨摩斯岛。后来又迁居意大利南部的克罗通，创建了自己的学派，一边从事教育，一边从事数学研究。 在几何学方面，毕达哥拉斯学派证明了“三角形内角之和等于两个直角”的论断；研究了黄金分割；发现了正
10、五角形和相似多边形的作法；还证明了正多面体只有五种正四面体、正六面体、正八面体、正十二面体和正二十面体。,21,22,23,推销员问题（哈密尔顿途径）,一个经典的数学问题：如果一个推销员要在许多个城市推销，每个城市必须而且只能经过一次，如何找到最短的路程？,24,并没有特定的公式可以对此进行计算，惟一的解决办法是找到所有可能的路程加以比较，选出最短的一种。 即使仅有四个城市，推销员也已面临着多种选择（确切地说，12种），这时候还能把所有可能的路程都找出来加以比较。但随着城市数目的增加，可能性也迅速膨胀，成指数增长，要把所有可能性都找出来，很快就变得不切实际了。,25,最近，加州大学圣地亚哥分校
11、的佩夫兹那（）实验室在美国科学院院刊宣布找到了一种进行序列组装的新办法。 他们把已有的基因组片段再进行一次切割，切割成大小一样的更小的片段。这样，他们就把基因组序列的“哈密尔顿途径”变成了“尤拉途径”：在此一途径中，每个城市不限定只能访问一次，想去多少次都可以，但是每一条路只能走一次。从这个网络中找出最短的路程的问题，被称为中国邮差问题。在数学上，要追踪中国邮差比追踪推销员容易得多。,26,原子结构、分子结构、晶体结构、有机物同分异构体等相关空间结构的想象、抽象、综合及计算,思维动作的层次较高，要加强对空间结构模型、图示的观察和分析,并注意及时延伸和拓展、要精选范例作剖析。应不断提高对物质三维
12、空间结构的剖析、综合和有关的计算能力。 范例1已知晶体硼原子组成的正十二面体，存在着20个等边三角形和一定数目顶角，每1个顶角上有1个硼原子，试通过观察下图，确定每1个结构单元由_个硼原子。,27,分析,可采用点归面、面归体的分析法。从图中可知，每个顶点上的硼原子都分属于5个正三角形所共有，故分归到每个三角形均为1/5，每个三角形有(1/5)3个硼原子，则每个结构单元所含硼原子数为：20(1/5)312个。答案12,28,四色问题,在给地图着色的时候，我们总是给相邻的不同区域涂上不同颜色，使用权这些区域之间有所区别。那么画一张地图，要用多少种颜色呢？,29,四色问题,30,1852年10月，刚
13、从伦敦大学毕业的青年数学家弗兰西斯古色利在为一张英国地图着色的时候，发现最多只要4种颜色，就能把相邻的国家区别出来了。古色利写信把自己的发现告诉在大学学习物理的弟弟弗雷德里克，弗雷德里克又向他的数学老师摩根提出，摩根又去请教哈密尔顿，并由此引发了一场长达120多年的证明大战。这就是著名的四色问题。,31,德摩尔根：地图四色定理,地图四色定理最先是由一位叫古德里（Francis Guthrie）的英国大学生提出来的。德摩尔根（A，DeMorgan，18061871）1852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。他在信中简述了自己证明四色定理的设想与感受。一个多世纪以
14、来，数学家们为证明这条定理绞尽脑汁，所引进的概念与方法刺激了拓扑学与图论的生长、发展。,32,以下摘录德摩尔根致哈密顿信的主要部分，译自J Fauve1 and J.Gray（eds.），The History of Mathematics ：A Reader，pp 597598。,德摩尔根致哈密顿的信（1852年10月23日） 我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。现在的问题是是否会出现需要五种或更多种颜色的情形。就我目前的
15、理解，若四个不订分割的区域两两具有公共边界线，则其中三个必包围第四个而使其不与任何第五个区域相毗邻。这事实若能成立，那么用四种颜色即可为任何可能的地图着色，使除了在公共点外同种颜色不会现画出三个两两具有公共边界的区域ABC，那么似乎不可能再画第四个区域与其他三个区域的每一个都有公共边界，除非它包围了其中一个区域（图2）。但要证明这一点却很棘手，我也不能确定问题复杂的程度一对此您的意见如何呢？并且此事如果当真，难道从未有人注意过吗？我的学生说这是在给一幅英国地图着色时提出的猜测。我越想越觉得这是显然的事情。如果您能举出一个简单的反例来，说明我像一头蠢驴，那我只好重蹈史芬克斯的复辙了。,33,34
16、,35,1879年，肯泊在一篇论文中发表了一个证明，1890年，希伍德指出了肯泊证明中的错误，同时也指出，肯泊的方法可以用来成功证明五色问题。 1976年美国伊利大学数学家阿佩尔（K. Appel）与哈肯（W. Haken）宣告借助电子计算机获得了四色定理的证明，三台计算机上花费了1200个小时计算，终于完成了四色定理的证明。 尽管如此，许多数学家还在寻求书面的证明。,36,简单的网络及其应用,简单的网络是包含有一些点和点与点之间的一些弧的一种图形。弧的两端之点称为结（或结点）。 一个结可由其所联结的弧的数目来识别，例如，三个弧的结称为3弧结，四个弧的结称为4弧结，n弧结。 当n为奇数时称为奇结；n为偶数时称为偶结。,37,设有两个网络，不管它们的形状如何不同，只要结和弧的数目相同，而且在连通关系上完全一样，便可视为相同的网络。,38,以上两图形状虽不同，然实质上是两个相同的网络，数学上称“拓朴等价”,在拓朴学中，点、线、面等都是可以在原空间中任意挪动伸缩的。所以，正方形与圆没有区别，碗和盘子也等价，钻石戒子与皮筋套也是一回事，重要的只是结构。只
