图论论文.doc

课程名称 图论入门 论文题目 图论在物流 物配送上的应用 指导教师 刘颖 学院 管理学院 姓名 郭凤午 学号 2011030284 图论在物流货物配送中的应用摘 要：最短路径问题对于节约人们的时间成本具有重要意义。最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。它可被用来解决厂区布局、管路铺设、线路安装等实际问题。本文介绍了图论的起源和发展、最短路径问题及其算法，并应用图论最短路径问题的分析方法解决物流货物配送中问题。1 引言数学是一门古老的学科，它已经有了几千年的历史。然而，图论作为数学的一个分支，却只有200多年的历史，但是其发展十分迅速。图论是以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系。事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟，而且它具有形象直观的特点，在图中点的位置和线的长短曲直无关紧要1。图论的发展大力地推进了科学文明的进步，解决了很多实际应用问题。图论是数学领域中发展最快的分支之一，它以图为研究对象。图论中的图是有若干给定的点及连接两点的线所构成的图形，这种图形常用来描述某些事物之间的某种特定关系，用来代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论本身是应用数学的一部分，因此，历史上图论曾经被好多位数学家各自独立的建立过。关于图论的文字记载最早出现在欧拉1736年的论文中，他所考虑的原始问题有很强的实际背景。 数学史上著名的七桥问题欧拉只用了一步就证明了不重复地通过7座桥的路线是根本不存在的!这是拓扑学研究的先声。图的染色问题一直是图论研究的焦点问题。数学家赫伍德成功地运用肯普的方法证明了五色定理，即一张地图能够用五种或者更少的颜色染色。美国伊利诺斯大学的黑肯和阿佩尔，经过四年的艰苦工作终于完成了四色猜想的证明。正是上述那些似乎没有多大意义的游戏的抽象与论证的方法，开创了图论科学的研究。2图论的起源与发展。第一阶段是从1736年到19世纪中叶。1736年是图论的历史元年，当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题。 东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔河的两岸，河中有一个岛，于是城市被河的分支和岛分成了四个部分，各部分通过7座桥彼此相通。如同德国其他城市的居民一样，该城的居民喜欢在星期日绕城散步。于是产生了这样一个问题：从四部分陆地任一块出发，按什么样的路线能做到每座桥经过一次且仅一次返回出发点。这就是有名的哥尼斯堡七桥问题。 哥尼斯堡七桥问题看起来不复杂，因此立刻吸引所有人的注意，但是实际上很难解决。 瑞士数学家(Leonhard Euler)在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。这篇论文被公认为是图论历史上的第一篇论文，Euler也因此被誉为图论之父。 欧拉把七桥问题抽象成数学问题-一笔画问题，并给出一笔画问题的判别准则，从而判定七桥问题不存在解。Euler是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线，则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点出发，通过每边一次且仅一次返回原出发点的路线(回路)是否存在？Euler证明这样的回路是不存在的。 第二阶段是从19世纪中叶到1936年。图论主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四色问题(1852年)和Hamilton环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫将树的概念和理论应用于工程技术的电网络方程组的研究。1857年英国的凯莱也独立地提出了树的概念，并应用于有机化合物的分子结构的研究中。1936年匈牙利的数学家哥尼格写出了第一本图论专著有限图与无限图的理论。标志着图论作为一门独立学科。第三阶段是1936年以后。由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的发展。特别是电子计算机的大量应用，使大规模问题的求解成为可能。实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都是很复杂的，需要计算机的帮助才有可能进行分析和解决。目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用。 进入20世纪以来, 科学家们对四色猜想的证明基本上是按照肯普的想法在进进行。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的过程。1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，做了100亿判断，终于完成了四色定理的证明。不过不少数学家并不满足与计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。 我们看到，正是上述那些似乎没有多大意义的游戏的抽象与论证的方法，开创了图论科学的研究。遗憾的是，由于当时社会生产落后，对图论知识的要求甚寡，这一学科的发展颇为迟缓，甚至处于停滞状态。此后的一百多年，图论经历了一场爆炸性的发展，终于成长为数学科学中一门独立的学科。它的主要分支有图论、超图理论、极值图论、算法图论、网络图论和随机图论等。近几十年来，图论在科学界可以说是异军突起，活跃非常。3图论基本概念3. 1图的定义有序三元组G = 称为一个图，其中：（1） V(G)=v1，v2，vn是有穷非空集，称为顶点集，其元素叫做图的顶点； （2） E(G)=e1，e2，en称为边集，其元素叫做图的边；（3） (G)；EVV是从边集E到顶点集V的有序或者无序对集合的影射，称为关联函数。3. 2图的分类在图G中，与V中的有序偶（vi，vj）对应的边e称为图的有向边（或弧），而与V中顶点的无序偶对应的边e称为图形的无向边，每一条边都是无向边的图，叫做无向图，记为G = （V，E）；每一条边都是有向边的图叫做有向图，记为D =（V，E）；既有无向边又有有向边的图叫做混合图。3. 3权如果图G中任意一条边（vi ，vj）上都附有一个数Wij，则称这样的图G为赋权图，Wij称为边（vi，vj）上的权（weight）。4最短路径问题最短路径问题（shortest path problem）是图论中的一个基本问题。在赋权图（weighted graph）中，每条边都有一个数值权（weight，代表其长度、成本、时间等），找出两节点之间总权和最小的路径就是最短路径问题。最短路径算法包括指定顶点对之间的最短路径算法和所有顶点间的最短路径算法，前者对于运输的合理化具有重要理论意义，而后者的意义在于选择合理的中转中心，使得总的费用最少。在图论中最典型的两种求最短路径算法分别是Dijkstra算法和Floyd算法，其中Dijkstra算法适用于前者，而Floyd算法适用于后者。物流货物配送中心的选址问题就是所有顶点间的最短路径问题，在本文中使用的算法就是最具有代表性的Floyd算法。4.1 Floyd算法的基本思想全部顶点间最短路径算法具有代表性的是1962年由福劳德（Floyd）提出的算法。他的主要思想是从代表任意2个顶点vi到vj的距离的带权邻接矩阵开始，每次插入一个顶点vk，然后将vi到vj间的已知最短路径与插入顶点vk作为中间顶点（一条路径中除始点和终点外的其他顶点）时可能产生的vi到vj路径距离比较，取较小值以得到新的距离矩阵，如此循环迭代下去，依次构造出n个矩阵D(1)，D(2)，D(n)，当所有的顶点均作为任意2个矩阵vi到vj中间顶点时得到的最后的带权邻接矩阵D(n)就反映了所有顶点对之间的最短距离信息，成为图G的距离矩阵。最后对G中各行元素求和值并比较大小，决定单个或多个最佳的点。4.2 Floyd算法 1.算法内容： 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。图用邻接距阵G表示出来，如果从Vi到Vj有路可达，则Gi,j=d，d表示该路的长度；否则Gi,j=无穷大。 定义一个距阵D用来记录所插入点的信息，Di,j表示从Vi到Vj需要经过的点，初始化Di,j=j。 把各个顶点插入图中，比较插点后的距离与原来的距离，Gi,j = min( Gi,j, Gi,k+Gk,j )，如果Gi,j的值变小，则Di,j=k。 在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为V5,V3,V1，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。 2.构造距离矩阵的原理对一个有n个顶点的图G，将顶点用n个整数（从1到n）进行编号。把G的带权邻接矩阵W作为距离的初值，即D(0)=(dij(0)n x m=W。第一步构造D(1)=(dij(1)n x m ，其中dij(1)=min dij(0)，di1(0)+d1j(0) 是从vi到vj的只允许以v1作为中间点的路径中最短路长度。第二步构造D(2)=(dij(2)n x m ，其中dij(2)=min dij(1)，di2(1)+d2j(1) 是从vi到vj的只允许以v1 、v2作为中间点的路径中最短路长度。第n步构造D(n)=(dij(n)n x m ，其中dij(n)=min dij(n)，din(n)+dnj(n) 是从vi到vj的只允许以v1、v2、vn作为中间点的路径中最短路长度，即是从vi到vj中间可插入任何顶点的路径中最短路的长度，因此D(n)即是距离矩阵。5 在物流货物配送中的应用某物流公司考虑在开发区建立物流网并选取一个总的配送中心。物流货物配送中心的选址问题中，点表示可供选址的物流分公司，而其间的连线表示运输费用，其需求点之间运费如图1所示（英文字母为可选物流分公司，数字为相邻站点之间的运费）。在物流配送中心的选址中，要求该中转站到其他站点的距离最短，即运输费用最少，这里通过运用最短路径Floyd算法可以求出该网点布局的最佳中转站。 图a 物流网络的拓扑结构首先，确定矩阵D(0)其中若顶点vi（编号i）到vj（编号j）有边相连，则dij(0)等于该边边权，否则dij(0)=而dii(0)=0。由图1写出其初值带权邻接矩阵D(0)：然后，对k=1，2，3，n依次利用算法原理中第n步递归公式，由已知的Dn-1各元素确定Dn的各元素值。插入顶点a后D(1)的各元素和相应的最短路径因为对称性，D(1)的第一行元素和第一列元素与D(0)相同，D(1)的主对角线上的元素均为0，所以只需计算其余6个元素的值：由此可知，依次插入b，c，d，e，可得不断更新的距离矩阵：最终求得距离矩阵D(5)的各元素值就是相应顶点间的最短路径。最后，计算第i行各元素值之和C(vi)即为vi 到其他各点的运费的总和。由计算可知，a到其他点的费用和为C(a)=33，同理C(b)=27，C(c)=18，C(d)=21，C(e)=33，比较可知c到其他各点的费用最小（若有最小总费用相等情形，可作为备选点）。因此本例就经济因素而言，c点为物流配送中心是最优的。6 结论图论在我们生活中的应用比比皆是，解决了很多实际问题。本文采用图论中最短路径Floyd算法，用于解决以最小运费为最优目标的物流配送中心的选址问题，能一次性地确定任意两点间的最短距离(费用)，算法不仅适应于静态的选址，也适应动态多站点网络规划。该方法不仅适用于此处，还能够方便解决