《信息与计算科学专业毕业论文——最大流问题及其应用》由会员分享，可在线阅读，更多相关《信息与计算科学专业毕业论文——最大流问题及其应用（33页珍藏版）》请在金锄头文库上搜索。
1、最大流问题及其应用西南林业大学理学院，中国云南昆明，650224摘要：网络流问题是运筹学的重要研究课题。最大流问题是网络流问题的一个重要的内容，应用极为广泛。研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便。 本论文讨论最大流问题，综述图论的历史背景、根本概念和根本知识；阐述网络的根本概念；介绍最大流问题的核心依据Ford-Fulkerson最大流最小割定理；综述解决最大流问题的几种算法Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法，并比拟各算法在解决不同问题中的优劣。为了更加明确的展现最大流问题在生产生活中的应用，
2、本文例举了一个实际生活中的问题铁路货运列车的最优调度来突出研究最大流问题的重要意义，此实例需要求解的是在一定的限制条件下，设计出一个在一昼夜间能通过某段铁路的最多的货运列车数量并列出每辆列车开出的时刻表。在此实例中，通过从实际问题中抽象出网络图，将实际问题转化为最大流问题并应用图的性质和Ford-Fulkerson标号法的算法依据，最终解决了问题。本文采用理论与实例相结合，重在应用理论依据解决实际问题，具有较强的实践性，突出的是应用。关键词：图 网络流 最大流 Maximum flow problem and its applications (Southwest Forestry Unive
3、rsity,Kunming,Yunnan,650224,China)Abstract: The network 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, engineeri
4、ng，commerce, agriculture, transportation and other areas 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 maxim
5、um flow problem - Ford-Fulkerson maximum flow minimum cut 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 diff
6、erent problems in the pros and cons.In order to more clearly 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 solve
7、d under certain constraints , to design the most freight 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
8、 the properties of graph and Ford-Fulkerson labeling algorithm, 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
9、： Graph Network flow Maximum flow 目录第一章 前言1 1 前言11.1 最大流问题的研究内容及背景1 1.2 最大流问题的开展状况2 1.3 选题的意义3第二章 预备知识4 1 图论4 2 网络的根本概念5 3 最大流问题核心依据Ford-Fulkerson最大流最小割定理6第三章 最大流问题的几种算法8 1 标号法(Ford-Fulkerson算法)9 标号法(Ford-Fulkerson算法)思想9 1.2 Ford-Fulkerson标号法的具体步骤9 2 Edmonds-Karp修正算法11 3 Dinic算法14 3.1 增量网络与分层增量网络14
10、3.2 Dinic算法的根本思想及具体步骤15第四章 最大流问题的应用17 1 铁路货运列车的最优调度17 1.1 问题表达17 1.2 问题分析17 1.3 问题求解20 1.4 问题总结25第五章 结论26参 考 文 献27指导老师简介28致谢.29第一章 前言1 前言1.1 最大流问题的研究内容及背景最大流问题是一类网络分析问题，它是指在一定的条件下,要求流过网络的物流、能量流、信息流等流量为最大的问题。比方交通运输网络中的人流、车流、物流、供水网络中的水流、金融系统中的现金流、通信系统中的信息流等等，都属于最大流问题参见文献1。在对最大流问题进行研究的过程中，人们建立了最大流问题较为完
11、善的理论，同时开发了大量的算法，如Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法等等，这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用。近年来，随着计算机科学技术和网络的快速开展，网络最大流问题得到了更深入的研究，并极大地推动了最大流问题的研究进展参见文献2-5。以图论理论根底来研究最大流问题是运筹学中的一种重要方法。在自然界和人类社会的实际生活中，用图形来描述某些对象(或事物)之间具有某种特定关系常常感到特别方便，例如用工艺流程图来描述某项工程中各工序之间的先后关系；用网络图来描述某通讯系统各小通讯站之间信息传递关系；用交通图来描述某
12、地区内各城市之间的铁路连接关系等等参见文献6-7。图论是组合数学的个分支，与其他的数学分支如群论、矩阵论、概率论、拓扑学、数值分析有着密切的联系，其应用十分广泛，是近年来较为活泼的数学分支之一参见文献8。它的产生和开展历经了二百多年的历史，瑞士数学家欧拉(LEuler)在1736年解决了当时颇为有名的一个数学难题，即哥尼斯城堡七桥问题，从而使他成了图论和拓扑学的创始人参见文献9-10。早期的图论与数学游戏有密切的联系，如哈密尔顿的周游世界问题、迷宫问题、博奕问题以及棋盘上马的行走路线之类的难题等吸引了许多学者。20世纪后，图论的应用渗透到许多其他学科领域，如物理、化学、信息学、运筹学、博奕论、
13、计算机网络、社会学以及集合论、矩阵论等。从20世纪50年代以后，由于计算机的迅速开展，有力地推动了图论的开展，使图论成为数学领域中开展最快的分支之一，也成为现代研究最大流问题的一个重要工具。1.2 最大流问题的开展状况最大流问题是早期的线性网络最优化的一个例子。最早研究这类问题的是美国学者希奇柯克Hitchcock，1941年他在研究生产组织和铁路运输方面的线性规划问题时提出运输问题的根本模型；后来柯普曼Koopmans在1947年独立地提出运输问题并详细地对此问题加以讨论；从上世纪40年代早期开始，康脱洛维奇Kantorovich围绕着运输问题作了大量的研究，因此运输问题又称为希奇柯克问题或
14、康脱洛维奇问题。与一般线性规划问题不同，它的约束方程组的系数矩阵具有特殊的结构，这就需要采用不同的甚至更为简便的求解方法来解决这种在实际工作中经常遇到的问题。运输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题。后来把这种解决线性网络最优化的方法与最大流问题相结合，同时推动了最大流问题的研究与进展。国外学者从算法角度考虑，对于最大流问题的求解提出了很多可行的解法，如表上作业法、图上求解法以及应用计算机实现的启发式多种算法等，其根本上可以总结如下：表上作业法是解决一般最大流问题最常用的解法，因其求解工作均在运输表上进行而得名。它是一种迭代算法，迭代步骤为：先按某种规那么找出一个初始解；再对现行解作最优性判别；假设该解不是最优解，就在表上对它进行调整改良，从而得出一个新解，再重复判别改良的过程，直至得到最大流问题的最优解为止。最短路线法。当某物资从出发地运往目的地，可有多条运输路线供选择，这时可构造费用网络图，用求最短路线的方法，选择最优的运输方案，需画出各种运输路线的线路图及图上每一条边或弧上的距离或费用也可以用邻接矩阵表示，然后用Dijkstra标号法或邻接矩阵法求最优运输路线。国内学者对于最大流问题的研究主要可以分为三个角度：一是在国外算法的根底上，对最大流问题算法的改良研究；二是从目标函数的角度，在最大流问题中
