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

《《MPA定量分析方法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、杨健中国人民大学RenminUniversityofChinaMPA定量分析方法主讲人简介杨健（英国兰卡斯特大学管理科学博士）中国人民大学公共管理学院MPA定量分析首席教授公共管理定量分析研究所所长电子政务博士生导师金融信息中心主任《投资与证券》主编英国运筹学JORS国际顾问国家高技术研究发展计划（863）评审专家国家自然科学基金管理科学评审专家企业年金投资管理机构评审专家2回头路传言一：邓小平在一个地方视察，视察完毕后，人们安排他原路返回，邓小平发现回去的道路和来时一样很生气，令车停住，说，我一生从来不走回头路。传言二：协兴街的老人说，小平属龙，他是从广安经渠江

2、到嘉陵江再到长江进入大海，龙归大海不回头，所以他不回家。3GraphTheory图论是一门很有实用价值的学科，它在自然科学、社会科学等各领域方面均有很大应用，近年来它发展迅速，应用广泛，已渗透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学、运筹学以及数学的其它分支中，在工程和交通运输中均获得了重要应用。4起源图论也是一门起源于游戏的学科，它起源于欧拉关于哥尼斯堡七桥问题的研究。哥尼斯堡是东普鲁士首府，普莱格尔河横贯其中，上有七座桥将河中的两个岛和河岸连接，一个散步者怎样才能走遍七座桥而每座桥只经过一次？5哥尼斯堡七桥问题（Konigsberg）18世纪在

3、哥尼斯堡城(今俄罗斯加里宁格勒)有一条名叫普莱格尔（Pregel）的河流横经其中，河上有7座桥，将河中的两个岛和河岸连结，如图1所示。图16城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这个问题看起来似乎不难，但人们始终没有能找到答案。这就是七桥问题，一个著名的图论问题。7当欧拉（Euler）在1736年访问Konigsberg,Prussia(nowKaliningradRussia)时，以深邃的洞察力很快证明了这样的走法不存在！欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究

4、。8LéonhardEuler，1707～1783瑞士人欧拉是18世纪最杰出的数学家之一，他不但在数学上做出了伟大贡献，而且把数学成功地应用到了其他领域。欧拉一生著书颇丰，其中有许多成为数学中的经典。9由于长期大量的写作，加上生活条件不良，他1735年患眼疾竟致右眼失明，并且于1771年左眼也完全失明。但他凭着惊人的记忆力和心算能力，通过与助手们讨论以及直接口授等方式，又完成了大量的科学著作，直至生命的最后一刻。101736年欧拉向圣彼得堡科学院提交了一篇论文，欧拉把这个问题的物理背景变换并简化为一种数学设计（称作图或网络）：即把每一块陆地用一个点来代替，将每一座

5、桥用连接相应的两个点的一条线来代替，从而相当于得到一个图。欧拉证明了这个问题没有解。欧拉指出欧几里得几何并不适用于这个问题，因为桥不涉及“大小”，也不能用“量化计算”来解决。相反地，这问题属于“位置几何”（莱布尼茨描述拓扑学时首先使用的名称）。11欧拉还发现，不论什么形状的凸多面体，其顶点数v、棱数e、面数f之间总有v-e+f=2这个关系。v-e+f被称为欧拉示性数，成为拓扑学的基础概念。在数论中，欧拉首先引进了重要的欧拉函数φ(n)，用多种方法证明了费马小定理。以欧拉的名字命名的数学公式、定理等在数学书籍中随处可见。与此同时，他还在物理、天文、建筑以至音乐、哲学

6、方面取得了辉煌的成就。12欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D4个点，7座桥表示成7条连接这4个点的线，如图2所示。图213于是“七桥问题”就等价于图3中所画图形的一笔画问题了。图314欧拉注意到，每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。所以每行经一点时，计算两座桥（或线），从起点离开的线与最後回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。15图3

7、的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走遍7座桥，而每座桥只许通过一次的走法。欧拉对“七桥问题”的研究是图论研究的开始，同时也为拓扑学的研究提供了一个初等的例子。16哥尼斯堡七桥问题的解决远远超出了它的娱乐价值，由此提出的新思想则开辟了数学的一个新的领域—图论。当然游戏娱乐对于图论的作用并没有到此为止，此后许多著名的数学游戏成为图论和拓扑学发展的催化剂和导引，如哈密尔顿问题（绕行世界问题）、四色猜想等。17“迷路的旅行推销员”1857年，爱尔兰数学家哈密尔顿(Hamilton)制作了一个“环球周游”的数学玩具。他用一个正十二面体的20个顶

8、点代表世界