目录

第一章 绪论 ................................................................................................................. 1

1.1 最大流问题的研究内容及背景 .................................................................... 1 1.2 最大流问题的发展状况 ................................................................................. 1 1.3 选题的意义 ........................................................................................................ 2

第二章 预备知识 ....................................................................................................... 4

2.1 图论 ...................................................................................................................... 4 2.2 网络的基本概念 ............................................................................................... 5 2.3 最大流问题核心依据——Ford-Fulkerson最大流最小割定理 ......... 7

第三章 最大流问题的几种算法 .................................................................... 9

3.1 标号法(Ford-Fulkerson算法) ...................................................................... 9 3.2 Edmonds-Karp修正算法 ........................................................................... 12 3.3 Dinic算法 ...................................................................................................... 15

第四章 最大流问题的应用 ............................................................................. 19

4.1 铁路货运列车的最优调度 ........................................................................... 19

第五章 结论 ............................................................................................................. 30 参 考 文 献 ............................................................................................................... 31 致谢辞 ............................................................................................................................. 32 附录1英文原文 ....................................................................................................... 33 附录2中文译文 ....................................................................................................... 37

山东科技大学本科毕业设计（论文）

第一章 绪论

1.1 最大流问题的研究内容及背景

最大流问题也就是是指网络分析问题的一类，它是在指定的条件下,要求通过网络的物流、能量流、信息流等流量为最大的问题。比如交通运输网络中的人流、车流、物流,供水网络中的水流、金融系统中的现金流通信系统中的信息流等等，都属于最大流问题。

图论是组合数 学的—个分支与其他的数学分支如群论、矩阵论、概率论、拓扑学、数值分析有着密切的联系而且其应用十分广泛，是近年来较为活跃的数学分支之一。它的产生和 发展历经了二百多年的历史，瑞士数学家欧拉(L．Euler)在1736年解决了当时颇为有名的一个数学难题，即哥尼斯城堡七桥问题，从而使他成了图论和拓扑学的创始人。早期的图论与数学游戏有密切的联系，如哈密尔顿 的周游世界问题、迷宫问题、博奕问题以及棋盘上马的行走路线之类的难题等吸引了许多学者。20世纪后，图论的应用渗透到许多其他学科领域，如物理、化学、信息学、运筹学、博奕论、计算机网络、社会学以及集合论、矩阵论等。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，使图论成为数学领域中发展最快的分支之一，也成为现代研究最大流问题的一个重要工具。

1.2 最大流问题的发展状况

最大流问题是早期的线性网络最优化的一个例子。最早研究这类问题的是美国学者希奇柯克（Hitchcock），1941年他在研究生产组织和铁路运

1

山东科技大学本科毕业设计（论文）

输方面的线性规划问题时提出运输问题的基本模 型；后来柯普曼（Koopmans）在1947年独立地提出运输问题并详细地对此问题加以讨论；从上世纪40年代早期开始，康脱洛维奇（Kantorovich）围绕着运输问题作了大量的研究，因此运输问题又称为希奇柯克问题或康脱洛维奇问题。与 一般线性规划问题不同，它的约束方程组的系数矩阵具有特殊的结构，这就需要采用不同的甚至更为简便的求解方法来解决这种在实际工作中经常遇到的问题。运输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题。后来把这种解决线性网络最优化的方法与最大流问题相结合，同时推动了最大流问题的发展。

最大流问题就是就是在一个有向连通图中，指定一点为发点，另一点 为收点，其余的点为中间点，在所有的点 都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流。本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题，提高生产的有效性和生产设备的有效利用率。

最大流问题应用极为广泛，很多生活中的问题都可转化为最大流问题，其难点是从实际中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。

1.3 选题的意义

在日常生活和生产中我们时常遇到一些网络图。如交通图、旅游线路图、管道系统图等。在优化理论 中所谓图就是上述各类图的抽象和概括，用图来描述我们的研究对象，以及这些对象之间的相互联系。例如旅游管理、网络通信、交通运输、金融系统等问题都可以用网络图来描述。

最大流问题就是就是在一个有向连通图中，指定一点为发点，另一点

2

山东科技大学本科毕业设计（论文）

为收点，其余的点为中间点，在所有的点 都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流。本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题，提高生产的有效性和生产设备的有效利用率。

最大流问题应用极为广泛，很多生活中的问题都可转化为最大流问题，其难点是从实际中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。

3

山东科技大学本科毕业设计（论文）

第二章 预备知识

2.1 图论

所谓“图论”，顾名思义也就是是研究“图”的理论。图论中的“图”是由许多实际问题经过抽象而得到，由点及点与点之间的连线构成，它可以反映一些对象之间的关系。图形中的点表示对象(如工序、选手、通讯站等)，两点之间的有向或无向连线表示对象之间具有某种特定的关系(如先后关系、胜负关系、传递关系、连接关系等)。

物质结构、电路网络、城市规划、交通运输、信息传递、物资调配等都可以用点和线连 接起来的图进行模拟。这里所研究的图与平面几何中的图不同，这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的vi,vj相对位置如何，都是无关紧要的。 定义1：两点之间不带箭头的连线称为边，一条连接vi,vj的边记为vs (或

[vi,vj])，表示边的集合。

定义2：两点之间带箭头的连线称为E?{e1,e2?,em}弧，一条以vi为始点vj 为终点的弧记为ai?(vi,vj),A?{a1,a2,?am}表示弧的集合。

定义3：由点和边构成的图为无向图，记为G?(V,E)；由点和弧构成的图为有向图，记为D?(V,A).

定义4：在无向图G中，若存在一个点边交错序列

(vi1,ei1,vi2,ei2,?vik?1,eik?1,vik)，满足

4