《(毕业设计论文)最大流问题及应用》由会员分享，可在线阅读，更多相关《(毕业设计论文)最大流问题及应用（36页珍藏版）》请在金锄头文库上搜索。
1、山 东 科 技 大 学本科毕业设计论文题 目 最大流问题以与应用学 院 名 称 数学与系统科学学院 专业班级 信息与计算科学2011级2班 学生#吕永强学 号 201101051416摘要网络流问题是运筹学的重要研究课题.最大流问题是网络流问题的一个重要的内容,应用极为广泛.研究最大流问题并将其应用到工业、工程、商业、农业,运输业等领域可给我们的生活带来很大方便.本论文讨论最大流问题,综述图论的历史背景、基本概念和基本知识；阐述网络的基本概念；介绍最大流问题的核心依据Ford-Fulkerson最大流最小割定理；综述解决最大流问题的 几种算法Ford-Fulkerson标号法、Edmonds-
2、Karp修正算法、Dinic算法,并比较各算法在解决不同问题中的优劣.为了更加明确的展现最大流问题在生产生活中的应用,本文例举了一个实际生活中的问题铁路货运列车的最优调度来突出研究最大流问题的重要意义,此实例需要求解的是在一定的限制条件下,设计出一个在一昼夜间能通过某段铁路的最多的货运列车数量并列出每 辆列车开出的时刻表.在此实例中,通过从实际问题中抽象出网络图,将实际问题转化为最大流问题并应用图的性质和Ford-Fulkerson标号法的算法依据,最终解决了问题.本文采用理论与 实例相结合,重在应用理论依据解决实际问题,具有较强的实践性,突出的是应用.AbstractThe network
3、flow problem is an important operational research subject. The maximum flow problem is an important content of network flow problem, which has widely applications. The research of maximum flow problem and its applications to industry, engineering,commerce, agriculture, transportation and other areas
4、 can bring us great convenience.The paper discusses the maximum flow problem, and summarizes the historical background of graph theory, basic concepts, basic knowledge and describes the basic concept of the network. The core basis of the maximum flow problem - Ford-Fulkerson maximum flow minimum cut
5、 theorem is introduced. Several algorithms for solving maximal-flow problem like Ford-Fulkerson labeling algorithm, Edmonds-Karp correct algorithm, Dinic algorithm are summarized in this paper. It also compares various algorithms to solve different problems in the pros and cons.In order to more clea
6、rly show the application of the maximum flow problem in the production life, the paper illustrates a real-life problem - -The optimal scheduling of railway freight train to highlight the importance of maximum flow. This instance is to be solved under certain constraints , to design the most freight
7、train numbers through the railway in a day and night and to list out the schedules for each train. In this instance, by abstracting the network diagram from the real problems, transform the actual problem into the maximum flow problem, and use the properties of graph and Ford-Fulkerson labeling algo
8、rithm, and ultimately solve the problem.In this paper, the combination of theory and examples focus on solving practical problems by applying theoretical basis. It has strong practicality and highlights the applications. 字典Keywords： Graph Network flow Maximum flow 目录第一章 绪论11.1 最大流问题的研究内容与背景11.2 最大流问
9、题的发展状况11.3 选题的意义2第二章 预备知识42.1 图论42.2 网络的基本概念62.3 最大流问题核心依据Ford-Fulkerson最大流最小割定理7第三章 最大流问题的几种算法93.1 标号法93.2 Edmonds-Karp修正算法113.3 Dinic算法15第四章 最大流问题的应用194.1 铁路货运列车的最优调度19第五章 结论30参 考 文 献31致谢辞32附录1英文原文33附录2中文译文37 / 第一章 绪论1.1 最大流问题的研究内容与背景最大流问题也就是是指网络分析问题的一类,它是在指定的条件下,要求通过网络的物流、能量流、信息流等流量为最大的问题.比如交通运输网
10、络中的人流、车流、物流,供水网络中的水流、金融系统中的现金流通信系统中的信息流等等,都属于最大流问题.图论是组合数 学的个分支与其他的数学分支如群论、矩阵论、概率论、拓扑学、数值分析有着密切的联系而且其应用十分广泛,是近年来较为活跃的数学分支之一.它的产生和 发展历经了二百多年的历史,瑞士数学家欧拉在1736年解决了当时颇为有名的一个数学难题,即哥尼斯城堡七桥问题,从而使他成了图论和拓扑学的创始人.早期的图论与数学游戏有密切的联系,如哈密尔顿 的周游世界问题、迷宫问题、博奕问题以与棋盘上马的行走路线之类的难题等吸引了许多学者.20世纪后,图论的应用渗透到许多其他学科领域,如物理、化学、信息学、
11、运筹学、博奕论、计算机网络、社会学以与集合论、矩阵论等.从20世纪50年代以后,由于计算机的迅速发展,有力地推动了图论的发展,使图论成为数学领域中发展最快的分支之一,也成为现代研究最大流问题的一个重要工具.1.2 最大流问题的发展状况最大流问题是早期的线性网络最优化的一个例子.最早研究这类问题的是美国学者希奇柯克Hitchcock,1941年他在研究生产组织和铁路运输方面的线性规划问题时提出运输问题的基本模 型；后来柯普曼Koopmans在1947年独立地提出运输问题并详细地对此问题加以讨论；从上世纪40年代早期开始,康脱洛维奇Kantorovich围绕着运输问题作了大量的研究,因此运输问题又
12、称为希奇柯克问题或康脱洛维奇问题.与 一般线性规划问题不同,它的约束方程组的系数矩阵具有特殊的结构,这就需要采用不同的甚至更为简便的求解方法来解决这种在实际工作中经常遇到的问题.运输问题不仅代表了物资合理调运、车辆合理调度等问题,有些其他类型的问题经过适当变换后也可以归结为运输问题.后来把这种解决线性网络最优化的方法与最大流问题相结合,同时推动了最大流问题的发展.最大流问题就是就是在一个有向连通图中,指定一点为发点,另一点为收点,其余的点为中间点,在所有的点 都能承载的情况下能通过此网络图的最大可行流,即发点发往收点的最大可行流.本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题
13、,提高生产的有效性和生产设备的有效利用率.最大流问题应用极为广泛,很多生活中的问题都可转化为最大流问题,其难点是从实际中抽象出最大流模型,即转化问题,且实践性较强,通过实例分析,更有利于对最大流问题的了解与应用.1.3 选题的意义在日常生活和生产中我们时常遇到一些网络图.如交通图、旅游线路图、管道系统图等.在优化理论 中所谓图就是上述各类图的抽象和概括,用图来描述我们的研究对象,以与这些对象之间的相互联系.例如旅游管理、网络通信、交通运输、金融系统等问题都可以用网络图来描述.最大流问题就是就是在一个有向连通图中,指定一点为发点,另一点为收点,其余的点为中间点,在所有的点 都能承载的情况下能通过
14、此网络图的最大可行流,即发点发往收点的最大可行流.本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题,提高生产的有效性和生产设备的有效利用率.最大流问题应用极为广泛,很多生活中的问题都可转化为最大流问题,其难点是从实际中抽象出最大流模型,即转化问题,且实践性较强,通过实例分析,更有利于对最大流问题的了解与应用.第二章预备知识2.1 图论所谓图论,顾名思义也就是是研究图的理论.图论中的图是由许多实际问题经过抽象而得到,由点与点与点之间的连线构成,它可以反映一些对象之间的关系.图形中的点表示对象,两点之间的有向或无向连线表示对象之间具有某种特定的关系.物质结构、电路网络、城市规划、交
15、通运输、信息传递、物资调配等都可以用点和线连 接起来的图进行模拟.这里所研究的图与平面几何中的图不同,这里只关心图中有多少个点,点与点之间有无连线,至于连线的方式是直线还是曲线,点与点的相对位置如何,都是无关紧要的.定义1：两点之间不带箭头的连线称为边,一条连接的边记为 ,表示边的集合.定义2：两点之间带箭头的连线称为弧,一条以为始点为终点的弧记为表示弧的集合.定义3：由点和边构成的图为无向图,记为；由点和弧构成的图为有向图,记为.定义4：在无向图中,若存在一个点边交错序列,满足,则称之为一条联结和的链,记为,若,则称之为圈.定义5：在有向图中,若存在一个点弧交错序列,弧的始点为,终点为,记为,则称这条点弧的交错序列为从到的一条路,记为.若路的第一点和最后一点相同,则称之为回路.链与路中的点互不相同,则为初等链,以后说到的链与路,均指初等链.定义6：如果对于一个无向图的每一条边,相应有一个权数,则称这样的图为赋权图,记为.定义7：如果对于一个有向图的每一条弧,相应有一个权数,称这样的图为网络,记为.一般在网络图中,每条弧的权,不是表示弧的长度、而是表示弧的宽度,即代表距离、费用、通过能力等等.例如,公路运输网络中路面的宽度或管道输送网络中管道的直径,它是单位时间内
