(毕业设计论文)最大流问题及应用

山 东 科 技 大 学

本科毕业设计（论文）

题 目 最大流问题以及应用

学 院 名 称 数学与系统科学学院 专业班级 信息与计算科学2011级2班 学生姓名 吕永强 学 号 201101051416

摘要

网络流问题是运筹学的重要研究课题。最大流问题是网络流问题的一个重要的内容，应用极为广泛。研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便。

本论文讨论最大流问题，综述图论的历史背景、基本概念和基本知识；阐述网络的基本概念；介绍最大流问题的核心依据——Ford-Fulkerson最大流最小割定理；综述解决最大流问题的 几种算法Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法，并比较各算法在解决不同问题中的优劣。

为了更加明确的展现最大流问题在生产生活中的应用，本文例举了一个实际生活中的问题——铁路货运列车的最优调度来突出研究最大流问题的重要意义，此实例需要求解的是在一定的限制条件下，设计出一个在一昼夜间能通过某段铁路的最多的货运列车数量并列出每 辆列车开出的时刻表。在此实例中，通过从实际问题中抽象出网络图，将实际问题转化为最大流问题并应用图的性质和Ford-Fulkerson标号法的算法依据，最终解决了问题。

本文采用理论与 实例相结合，重在应用理论依据解决实际问题，具有较强的实践性，突出的是应用。

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, engineering，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 maximum 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 different 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 solved 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 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： Graph Network flow Maximum flow

目录

第一章 绪论 ................................................................................................................. 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

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

运送至终点的总量达到最大，这样的问题就称为网络上最大流问题，最大流问题是网络流问题中的一个非常重要的研究内容（参见文献[15]），以下讨论的网络均为只有一个发点vs和一个收点vt的容量网络D?(V,A,C)。 定义9：对任意容量网络D?(V,A,C)中的弧(vi,vj)有流量fij，称集合

f?{fij}为网络D上的一个流，称满足下列条件的流f为可行流：

(1)容量限制条件：对D中每条弧(vi,vj)，有0?fij?cij； (2)平衡条件：

①对中间点vi，有?jfi??ikf(即中间点vi的物资的输入量与输出

jk量相等)。

②对收、发点vt,vs有?fsi??fjt?W(即从vs点发出的物资总量

ij等于vt点入的量) ，W为网络流的总流量。

在容量网络D?(V,A,C)中cij表示弧(vi,vj)的容量，令xij为通过弧

(vi,vj)的流量，显然有0?xij?cij，流{xij}应遵守点守恒规则，即：

??W?x?x??ij?ji?0??W?称为守恒方程。

定义10：对任意容量网络D?(V,A,C)，寻求一可行流f使得流量W取得 极大值，这个可行流f便称为最大流。

定义11：在容量网络D?(V,A,C)中，若?为网络中从发点vs到收点vt的一条路，给?定向为从vs到vt，?上的弧凡与?同向称为前向弧。凡与?反

6

i?si?s,t

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

向称为后向弧，其集合分别用??和??表示，f是一个可行流，如果满足

???0?fij?cij(vi,vj)?? ????cij?fij?0(vi,vj)??则称?为从vs到vt的(关于f的)增广链。

定义12：在容量网络G?(V,A,C)中，若有弧集A'为A的子集，将D分为两个子图D1,D2，其顶点集合分别记S,S，S?S?V,S?S??，vs,vt分别属于S,S，满足：①D(V,A?A')不连通；②A''为A'的真子集，而D(V,A?A'')仍连通，则称A'为D的割集，记A'?(S,S)。

割集(S,S)中所有始点在S，终点在S的边的容量之和，称为(S,S)的割集容量，记为C(S,S)。

2.3 最大流问题核心依据——Ford-Fulkerson最大流最小割定

理

Ford-Fulkerson最大流最小割定理是由Ford和Fulkerson在1956年提出的，是图论的核心定理。

定理1：（Ford-Fulkerson最大流最小割定理）任一容量网络D中，从vs到vt 的最大流{fij}的流量等于分离vs,vt的最小割的容量。

证明：设在D中从vs到vt的任一可行流{xij}的流量为W，最小割集为

(S,S)，最小割集的容量为C(S,S)。这个定理的证明分两步：

7

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

? 我们先证明W?C(S,S)：

由守恒方程可得：

W??(?xij??xji)i?Sjj???(xij?xji)???(xij?xji)

i?Sj?Si?Sj?S???(xij?xji)i?Sj?S(3.1)因此有：W???(xij?xji)???xij???cij?C(S,S)。

i?Sj?Si?Sj?Si?Sj?S? 下面我们证明一个可行流是最大流，当且仅当不存在关于它的从的增广路径：

vs到

vt必然性：显然，因为如果存在增广路径，还可以继续增广，流就不是最大流。

充分性：假设可行流{xij}是一个不存在关于它的增广路径的流，对于最小割集(S,S)，有对任意i,j?S，存在从vi到vj的增广路径，而对任意不存在从vi到vj的增广路径，由定义可知对任意i?S,j?S有： i?S,j?S，

xij?cij,xji?0

由公式(3.1)可知：W???cij?C(S,S)。

i?Sj?S即流的值等于割集的容量，定理得证。

8

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

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

最大流问题是社会经济生活和军事活动中经常出现的优化问题。如在经济建设和国防建设中，经常遇到一些物资调运的问题。如何制定调运方案，将物资尽快运到指定点，而且不影响费用的计划开销，即为最大流问题。下面用数学语言来说明最大流问题：

1.设有一个有向连通图G(V,A)，在V中指定一点称为发点s,和另外一点为收点t，其余的称为中间点，弧（arc）集A中每条弧（i，j）上有非负数cij称为这弧的容量，记容量集为c={cij}，称这样的图为一个网络，记为G(V,A, c)（注：当（i，j）不是弧时cij=0）。

2.在弧集A上的弧（i，j）定义一非负数fij，称为弧（i，j）上的流量，流量的集合f={fij}称为网络的一个流，满足下列条件的称为可行流：

1）容量限制条件，所有的弧的流量fij不大于弧的容量cij； 2）平衡条件，对所有的中间点，流入的流量和等于流出的流量和，发点流出的流量F等于流进收点的总流量F.

最大流问题就是求总流量最大达可行流。

求解最大流问题存在许多算法，这一节将介绍几种常用算法。

3.1 标号法(Ford-Fulkerson算法)

3.1.1标号法(Ford-Fulkerson算法)思想

Ford-Fulkerson标号法是一种找最大流f的算法。它是由Ford和Fulkerson于1957年最早提出的，其基本思想是从任意一个可行流出发寻

9

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

找—条增广路径，并在这条增广路径上增加流量，于是便得到一个新的可行流，然后在这新的可行流的基础上再找一条新的增广路径，再增加流量……，继续这个过程，一直到找不到新的增广路径为止（参见文献[2]）。

采用Ford-Fulkerson标号法求解最大流问题时，在标号过程中，一个点仅有下列三种状态之一：标号已检查(有标号且所有相邻点都标号了)；标号未检查(有标号，但某些相邻点未标号)；未标号（参见文献[6]）。

Ford-Fulkerson标号算法分为两个过程：一是标号过程，通过标号过程找到一条增广路径；二是增广过程，沿着增广路径增加网络流流量的过程（参见文献[18]）。现在我们考虑只有一个发点vs和一个收点vt的容量网络，应用Ford-Fulkerson标号算法求解它的最大流

3.1.2 Ford-Fulkerson标号法的具体步骤 A:标号过程

步骤0 确定一初始可行流{fij}，可以是零流。 步骤1 给发点vs以标号[?,vs]。

步骤2 选择一个已标号但未检查的点vi，并作如下检查：

① 对每一弧(vi,vj)，若vj未给标号，而且cij?fij时，即流出未饱和弧,给vj以标号[?j,vi]；

② 对每一弧(vj,vi)，若vj未给标号，而且fji?0时，即流入非零流弧，给vj以标号[?j,?vi]；

??cij?fij其中：?j?min{?i,?},?????fji10

若(vi,vj)为流出未饱和弧若(vj,vi)为流入非零流弧

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

步骤3 重复步骤2直到收点vt被标号，或不再有顶点可以标号为止。 如果点给了标号说明存在一条增广路径，故转向增广过程B。如若点vt不能获得标号，而且不存在其它可标号的顶点时，算法结束，所得到的流便是最大流。 B：增广过程

由终点vt开始，使用标号的第二个元素构造一条增广路径?(点vt的标号的第二个元素表示在路中倒数第二个点的下标，而这第二个点的标号的第二个元素表示倒数第三个点的下标等等)，在?上作调整得新的可行流

{fij}，(标号的第二个元素的正负号表示通过增加或减少弧流来增大流值)。令?为vt标号的第一个元素的值，作

?fij??(vi,vj)是?上前向弧??fij??fij??(vj,vi)是?上后向弧???fij其它

以新的可行流{fij}代替原来的可行流，去掉所有标号，转标号过程的步骤1。

采用Ford-Fulkerson标号算法求解最大流问题，同时得到一个最小割集。最小割集的意义是：网络从发点到收点的各个通路中，由容量决定其通过能力，通常我们将最小割集形象地称为这些通路的咽喉部分，或叫做“瓶颈”，它决定了整个网络的通过能力，即最小割集的容量的大小影响总的流量的提高。因此，为提高总的流量，必须首先考虑改善最小割集中各小弧的流量，提高它们的通过能力（参见文献[14]）。

11

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

3.2 Edmonds-Karp修正算法

Ford-Fulkerson标号算法理论上存在着严重的弱点，以下图3.2.1为例各边上的权是它们的容量，其最大流流量为2m，若增广路径选择得不好,即交替地采用sabeft和sdebct作为增广路径，则每次增广只能使总的流量增加1,当初始流选为零流，无疑需作2m?1次的增加流量才能使之达到最大，可见Ford-Fulkerson算法的时间复杂度不仅依赖于网络的规模(即依赖于网络点数和边数)，还和各边的容量有关,而容量可以是任意的正整数。如图3.2.1中，当sabeft和sdebct交替作为增广路径时，be弧交替地以前向弧和后向弧出现。利用Ford-Fulkerson算法求解就很麻烦了（参见文献[8]）。

对于Ford-Fulkerson算法,由于增广路径选取的任意性造成了该算法不是好算法，Edmonds和Karp对Ford-Fulkerson算法作修正，可概括为一句话：“先给标号的先扫描”。它的意思是对已给标号的顶点v进行扫描时，先对所有和v邻接的未给标号的顶点给予标号。具体的说图3.2.1的例子，顶点s先标记，所以应该先扫描，因此避免了Ford-Fulkerson算法那样交替地出现sabeft,sdebct的情况，也就避免了be弧交替地以前向弧和后向弧来回摇摆的局面。所以Edmonds-Karp的修正实质是对顶点给标记过程采用了“宽度优先”策略。使得流量增加总是沿着一条长度最短的路径从s流向t的（参见文献[3]）。

s m m d 12 a m m b m c m 1 m e 图3.2.1 m f t 山东科技大学本科毕业设计（论文）

现在我们仍考虑只有一个发点vs和一个收点vt的网络图，Edmonds-Karp修正算法的主要步骤是： ① 确定一初始可行流{fij}，其流量W(f)。

② 检验当前所确定可行流是否是网络中的最大流，若不是，需进一步调整

(检验一个可行流是否为最大流。只要检查一下当前可行流是否还存在增广路径，若存在，则说明当前可行流还不是最大流，否则是最大流)。 ③ 将当前的可行流调整成一个流量更大的新可行流，再由②检验。

同样地，我们通常用观察法确定网络的—个初始可行流。对于较为复杂的网络，至少能把初始可行流取为零流。通过在网络上标号的方法能系统地寻找出当前可行流的增广路径，它的基本思想是：从起点vs起，逐步寻找vs至各点vi间的增广路径，若能找到vs至vi的一条增广路径，则给点vi标号[?i,?i]（其中第一个标号?i即为vs至vi这条增广路径上的最大可调整量，第二个标号?i则表示这条可行流上点vi的前一点是?i点）。根据标号可反向追踪而写出这条增广路径。在逐步扩大已标号的过程中，一旦终点vt标上号，表示已找到一条由vs至vt的增广路径。反之，如果标号过程进行至某一步中止了，而vt尚未标号，则表明对当前的可行流，网络中不存在任何增广路径。当前可行流即为最大流。Edmonds-Karp修正算法的具体步骤如下：

① 给发点vs标号[?,vs]，含义为vs至vs的增广路径已找到，前一点为vs，这条增广路径上的调整量为?。选与vs关联的从vs流出的未饱和弧

13

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

(vs,vi)或流入vs的非零流弧(vi,vs)，给vi标号[?i,vs] (对于流出弧)或

[?i,?vs] (对于流入弧)。

??csi?fsi若(vs,vi)为流出未饱和弧其中：?i??

??fsi若(vi,vs)为流入非零弧② 将顶点集分为互补的二个点集S、S，其中S为已标号点集，S为未标号点集；

③ 考虑所有这样的弧(vi,vj)或(vj,vi)，其中vi?S,vj?S。若弧(vi,vj)为从vi流出的未饱和弧，则给vj标号[?j,vi]。其中?j?min{?i,cij?fij}；若弧(vj,vi)为流入vi的非零流弧，则给vj标号[?j,?vi]。其中

?j?min{?i,fij}。依此进行，得到的结果是：

(a)S??，说明网络中存在增广路径?，则由标号点反向追踪找出?，转第④步；

(b)S??，标号已进行不下去，说明对于当前可行流。网络中已无新的增广路径，当前可行流即为最大流，同时得到最小割集(S,S)。

?fij????④ 调整过程：取??min{?j}，令fij??fij??vj?????fij(vi,vj)是?上前向弧(vj,vi)是?上后向弧 其它得到新可行流{fij}，流量W(f)?W(f)??，即比原可行流流量增加了?，再转①步。

用Edmonds-Karp修正算法求解最大流问题时，也可以得到一个最小割集。最小割集的意义同Ford-Fulkerson算法得到的最小割集的意义相同。

14

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

3.3 Dinic算法

Dinic于1970年提出了Ford-Fulkerson算法的改进算法，Dinic算法的特点是将顶点按其与发点的最短距离分层。Edmonds-Karp修正算法的实质也是一种分层，如果说Ford-Fulkerson算法是采用了深度优先策略。Edmonds-Karp修正算法则是用宽度优先取代了深度优先，Dinic算法则是兼取这两种方法。在分层时用的宽度优先法，而寻求增广路径时则采用深度优先策略（参见文献[3]）。 3.3.1 增量网络与分层增量网络

定义13：给定一个带发点vs和收点vt的容量网络D?(V,A,C)及D上的

???A(f)?{(vi,vj)|(vi,vj)?A,fij?cij}可行流{fij}后，我们定义??，因为D中任

??A(f)?{(vi,vj)|(vj,vi)?A,fji?0}何一对顶点之间至多有一条弧，所以A?(f)?A?(f)??，记

A(f)??A(f?)?A(f，

并且对一切

(vi,vj)?A(f)令

???cij?fij,若(vi,vj)?A(f)，于是得一个带发点vs和收点vt的容量网络cij???，若(vi,vj)?A(f)??fjiD(f)?(V,A(f),C)，称之为D的关于可行流{fij}的增量网络。

为了介绍分层增量网络，我们先来介绍关于网络的一个算法——分层算法，它的基本思想是：

步骤0：把发点vs标为“已标号未检查”，vs的层数h(s)?0。

步骤1：在已标号未检查顶点中选取最早得到标号的顶点vi，转步骤2；如

果所有标号顶点都已检查，转步骤3。

步骤2：考察顶点vi的一切出弧(vi,vj)，若vj已标号，什么也不做；否则将

15

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

vj标为“已标号未检查”，并令h(j)?h(i)?1。当vi的所有出弧都考察完毕，把vi改为已检查，转步骤1。

步骤3：如果有—些顶点没有标号，则从vs到这些顶点不存在路；否则vi为

D的根，h(i)为D中最短(vs,vi)路的长。

在增量网络D(f)中应用分层算法，可以求出从发点vs到其余各顶点vi的最短路的长h(i)，h(i)就是顶点vi（关于发点vs）的层数。即vi就是D(f)的第h(i)层顶点。D(f)的第0层只有一个顶点，把顶点分层后，D(f)中

的弧又可以分为三类：

第一类为从第i层顶点到第i?1层顶点的弧； 第二类为从第i层顶点到同一层顶点的弧；

第三类为从第i层顶点到第j层顶点的弧(j?i)（参见文献[5]）。 定义14：对于带发点vs和收点vt的容量网络D?(V,A,C)，设关于可行流

{fij}的增量网络D(f)?(V,A(f)，,C我)们定义D(f)的子网络

AD(f)?(V'(f),A'(f),C)如下：

V'(f)?{vt}?{vi|h(i)?h(t)}A'(f)?{(vi,vj)|h(j)?h(i)?1?h(t),(vi,vj)?A(f)}?{(vi,vt)|h(i)?h(t)?1,(vi,vt)?A(f)}则AD(f)称为D的关于可行流{fij}的分层增量网络。其中第0层和第h(t)层分别只有一个顶点vs和vt，AD(f)的所有弧都是由第i层顶点指向第i?1层顶点i?h(t)。

3.2 Dinic算法的基本思想及具体步骤

16

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

Dinic算法的基本思想是：从带发点vs和收点vt的容量网络D的任一可行流f0 (例如零流)开始，构造D的关于f0的分层增量网络AD(f0)，在

AD(f0)中找一条从vs到vt的增广路径?，对f0沿?进行增广得到可行流

f01，在AD(f0)中删去?上容量最小的弧，并相应修改AD(f01)上弧的容量，

得到网络AD(f01)，然后可以在AD(f01)中再找一条从vs到vt的增广路径?，对f01沿?进行增广得到可行流f02，重复上述步骤依次得到D的可行流

f01,f02,?,f0p?f1，因为AD(f0)只有有限条弧，每次至少删去一条弧，所以在有限步后必然使余下的网络不再存在增广路径，vt在AD(f1)中的层数一定大于它在AD(f0)中的层数；针对AD(f1)重复上面的做法，在有限次增广后一定会得到D的可行流f2，使vt在AD(f2)中的层数更大。由于vt的层数最多为n?1（n是网络D的顶点数）。因此经过有限步后得到D的可行流fk，

D中不再有fk的增广链，这时fk就是D的最大流。Dinic算法的具体步骤

如下：

步骤0：在网络D中任意取—个可行流f0作为初始可行流，令

p?0,q?0,qfp?0f。

步骤1：(作分层增量网络)根据fqp作D的增量网络D(fqp)，再利用分层算 法构造分层增量网络AD(fqp)，如果在作分层增量网络时vt得不到标号，则 算法结束，fqp就是D的最大流；否则转步骤2。 步骤2：(寻找增广路径)

17

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

①给发点vs标号为[??,vs]，令i?s。

②如vi在AD(fqp)没有出弧，转⑤；否则在AD(fqp)中任取vi的一条出弧

(vi,vj)，转③。

③设vi的标号为[?i,?i]，其中?i为vi前面的节点，令?j?min{?i,cij}，vj获

] 得标号 [?j,vi。

④如果j?t，转步骤3；否则令i?j，转②。

⑤设vi的标号为[?i,?i]，如果?i?vs，在AD(fqp)中删去vi的所有入弧，所 得的网络仍记为AD(fqp)，转②；否则置q?q?1，转步骤1。

步骤3：（增广）从顶点vt的标号中的第二个元素反向追踪，求出AD(fqp)的增广路径?，在AD(fqp)中把?上的每条弧的容量cij改为cij??t，删去容量为0的弧，同时把流fqp增广为流fqp?1，把AD(fqp)中修改容量和删去弧后的网络记为AD(fqp?1)，置p?p?1，去掉网络AD(fqp)中所有顶点的标号，转步骤2。

18

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

第四章 最大流问题的应用

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

4.1.1 问题叙述

某地区A、B两市之间要修建一铁路，依据地势、环境、需求等因素，修建铁路的预定方案如下：

（1）铁路的运行方式为客车与货运兼营的双轨铁路（单向单轨），在其运行的列车有旅客快车和货运列车，由于客车的运行时间是国家铁路部门早已排定的，不可更改，且规定客运优于货运，即货车在每站开出前应先明确在其到达前方车站前不会被客车赶上，否则在该站等候不能开车。又若货车的前方到达站如无停车岔道，则货车从本站开出前应明确在其前面两站的行程中不会被客车赶上否则在本站等候不能开车，余类推。 （2）铁路线内有A、B、C、D四个站，各站的岔道数为

nA?5,nB?7,nC?9及nD?11.

这些岔道可供调车用，亦可供停车卸货及洗刷车辆用。

（3）按早已排定的旅客快车时刻表，客车每天凌晨2:00从A站开出，以后每隔5小时开出一列，一昼夜共开出5列，当天最后一列的开车时间与翌晨第一列的开车时间相隔4小时。客车的行车时间在A、B站之间为3小时；在B、C站之间为2小时；在C、D站之间为5小时。

（4）在不干扰客车运行的条件下，关于货运列车的初步安排为：每天0:00从A站发出一列，以后每隔2小时发出一列，货车的行车时间在A、B站之间为5小时；

在B、C站之间为4小时；在C、D站之间为7小时。

19

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

为了充分发挥该铁路线的货运能力，需要排定一张最优的货车运行时刻表，即要求每天发出最多的货运列车且不干扰已排定的客运列车。 4.1.2 问题分析

求解这个问题较为复杂，但可将其转化为网络最大流问题。 （1）设A、B两市及其间的车站共P个。每个车站有nk条岔道（k=1,2,3…P）,可停放nk列列车。从第k站到第k+1站的行车时间货车为tk个小时，客车为tk' 个小时。

设?k为火车到达第k站并从第k站开出的时刻 设?k为客车到达第k站并从第k站开出的时刻 设?k?1为货车到达第k+1站并从第k+1站开出的时刻 设?k?1为客车到达第k+1站并从第k+1站开出的时刻 于是显然有?k?1??k?tk ?k'?1??k'?tk'

（2）若??k,?k?1?与?',?'k?1有公共部分，则称??k,?k?1?与?',?'k?1是相交的，否则成为不相交的。显然有当只??k,?k?1?与?',?'k?1相交情况下客车才有可能（并非必然）在第k站与地k+1站间追上货车。

（3）在??k,?k?1?与?',?'k?1相交情况下，?k，?k?1，?k，?k?1间的相交关系

'''????????'可由图4.1.1所示：

20

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

图4.11

情况Ⅵ为途中货车追上了客车故不符合题意。情况Ⅰ与情况Ⅱ中在第k站与第k+1站间不发生在途中追上货车。而在情况Ⅲ中必发生在第k站与第k+1

21

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

站间客车在途中追上货车。 于是有下列结论：

若??'k,?'k?1?在??k,?k?1?内，即?'k??k及?'k?1??k?1，则在第k站与第k+1站必发生客车追上货车情况。否则在第k站与第k+1站之间不发生客车追上货车情况。 （4）绘制网络图

用（k，?k）表示第k站处于时刻?k的状态，如在?k=2.3在（k，2.6），（k，6.6）状态开出的货车不会再途中被客车追上，则在图中表现为（k，2.6）及（k，6.6）两节点为起点的两条水平方向的直线弧，而在（k，4.6）状态下开出的货车会在途中被客车追上，则不能从该点引出水平方向的直线弧（图4.1.2），垂直方向的直线弧并联着同一车站的相邻状态。

22

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

图4.1.2

上图中各弧旁的数字为容量，因铁路线是单向单轨的，故水平方向的弧容量为1，垂直方向的弧的容量为各站的岔道数量，在列出全部状态的网络图中求最大流，此最大流即为允许开出的最多货运列车数。 4.1.3 问题求解

以货运列车的运行时间为基础绘制网络图。

（1）令?A,?B,?C,?D为火车从某站开出或到达某站的时刻。依题意，若不受客车干扰则：

23

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

?A=0:00,2:00,4:00…… ?B=5:00,7:00,9:00……

?C=9:00,11:00,13:00…… ?D=16:00,18:00,20:00……

于是货车在相邻两站的运行时间为（若不受客车干扰）：

??A,?B?:?0,5?,?2,7?,?4,9?,?6,11?,?8,13?,?10,15?,?12,17?,?14,19?,?16,21?,?18,23?,?20,15?,?22,27???(25点即翌日1点，余类推)

????B,?C?:?5,9?,?7,11?,?9,13?,?11,15?,?13,17?,?15,19?,?17,21?,?19,23?,?21,25?,?23,27?,?25,29?,?27,31

????C,?D?:?9,6?,?11,18?,?13,20?,?15,22?,?17,24?,?19,26?,?21,28?,?23,30?,?25,32?,?27,34?,?29,36?,?3(2)令?A,?B,?C,?D为客车从某站开出或到达某站的时刻，依题意：

''''?A'=2:00,7:00,12:00,17:00,22:00 ?B'=5:00,10:00,15:00,20:00,25:00(即1:00)

?C'=7:00,12:00,17:00,22:00,27:00（即3:00）

?D'=12:00,17:00,22:00,27:00（即3:00），32:00（即8:00）

于是客车在相邻两站之间的运行时间为：

??

'A,?B:?2:00,5:00?,?7:00,10:00?,?12:00,15:00?,?17:00,20:00?,?22:00,25:00?'???

'B,?C:?5:00,7:00?,?10:00,12:00?,?15:00,17:00?,?20:00,22:00?,?25:00,27:00??24

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

??'C,?D'?

:?7:00,12:00?,?12:00,17:00?,?17:00,22:00?,?22:00,27:00?,?27:00,32:00?

图4.1.3

（3）比较?A,?B及??A,?B?,我们发现?7:00,10:00?在?6:00,11:00?之内;

''??25

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

?17:00,20:00?在?16:00,21:00?之内。这说明若A站在6:00及16:00开出两列

货车，则该两列货车在到达B站前，必会被客车撞上。故这两次货运列车是不可行的。这表示在以货运列车的运行时刻为基础的网络图（图4.1.3）中为（A,6:00）及（A，16:00）两节点前未引出水平方向的直线弧。该图的各个节点中仅注明货运列车从该站开出或到达该站的时刻，站名省略了。 比较?B,?C及??B,?C?,我们发现?7:00,12：00?在?9:00,13:00?之内；

''???20:00,22:00?在?19:00,23:00?之内，其在图4.1.3中的表示同前。

比较?C,?D与??C,?D?,我们发现?12:00,17:00?在?11：00,18:00?之内；

''???22:00,27:00?在?21:00,28:00?之内，其在图3中的表示同前。

（4）图4.1.3中各水平方向的直线弧的容量均为1。如前所述，它表示在该时间内，货车在相邻两站的行程中不会被客车追上，故可顺利地到达前方车站。垂直方向的直线弧的通量表示各站的岔道数。

（5）做网络的发点vs，并从vs向A站的各状态节点作辅助弧，辅助弧的容量等于以A站的各状态节点为起点的各弧的容量的总和。作网络的收点vt，并从D站的各状态节点向vt作辅助弧。辅助弧的容量等于以D站个状态节点为终点的各弧的容量总和。

（6）求图4.1.3所示容量网络的最大流

Ⅰ）以零流f={0,0,…………0}为初始流，但图4.1.3的各弧旁省略了零流量。

Ⅱ）以vij表示图3中第i行第j列的节点。用Ford-Fulkerson标号法求得以下增广链并按?值进行调整。

①vs(0,?*) v1,1(vs,6) v1,2(v1,1,1) v1,3(v1,2,1) v1,4(v1,3,1)

26

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

v1(v1,4,1) ??1 ②vs(0,?) v2,1(v1,6) v2,2(v2,1,1) v2,3(v2,2,1) v3,3(v2,3,1) v3,4(v3,3,1) v1(v3,4,1) ??1 ③vs(0,?) v3,1(vs,6) v3,2(v3,1,1) v4,2(v3,2,1) v4,3(v4,2,1) v4,4(v4,3,1) ④vs(0,?) vt(v5,4,1) ⑤vs(0,?) v6,4(v6,3,1)

vt(v6,4,1) ⑥vs(0,?) v8,3(v7,3,1)

v8,4(v8,3,1) ⑦vs(0,?) v9,3(v9,2,1)

v9,4(v9,2,1) ⑧vs(0,?) v10,4(v10,3,1)

vt(v10,4,1) v1(v4,4,1) ??1

v5,1(vs,6) v5,2(v5,1,1) v5,3(v5,2,1) v5,4(v5,3,1) ??1 v6,1(vs,6) v6,2(v6,1,1) v6,3(v6,2,1)

??1 v7,1(vs,6) v7,2(v7,1,1) v7,3(v7,2,1)

vt(v8,4,1) ??1 v8,1(vs,6) v8,2(v8,1,1) v8,2(v8,2,1)

v9,4(v9,3,1) vt(v9,4,1) ??1 v10,1(vs,6) v10,2(v10,1,1) v10,3(v10,2,1)

??1

27

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

⑨vs(0,?) v11,1(vs,6) v11,2(v11,1,1) v11,3(v11,2,1)

v11,4(v11,3,1)

vt(v11,4,1) ??1 ⑩vs(0,?) v12,1(vs,1,6) v12,2(v12,1,1) v12,3(v12,2,1)

v12,4(v12,3,1)

vt(v12,4,1) ??1 以上10条增广链的调整量均为??1。用它对初始流（零流）进行调整后，结果如图4.1.3所示。若对现行流继续标号，则只有A站的12个状态节点获得标号，即标号中断，不能延伸达vt。故现行流即为最大流，其流量

v(f)?fs,(1,1)?fs,(2,1)?fs,(3,1)?fs,(5,1)?fs,(6,1)?fs,(7,1)?fs,(8,1)?fs,(10,1)?fs,(11,1)?fs,(12,1)?1?1?1?1?1?1?1?1?1?1?10

结论 在本问题所给条件下各车站一昼夜中能开出的最多货运列车数位10列。

现由图4.1.3将A站以昼夜中能开出的10列货车的运行时刻及调度情况阐述如（货车一昼夜中在其他各站点的运行及调度情况可由同图作类似阐述）

①在0:00,8:00,10:00,18:00,20:00,22:00时刻所开出的货车在各站点均畅通。

②在2:00开出的货车，11:00到达C站时须在岔道内停留到13:00方可继续前行。

③在4:00开出的货车，9:00到达B站时，须在岔道内停留到11:00方可继续前行。

④在12:00开出的货车，21:00到达C站时，须在岔道内停留到23:00方可

28

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

继续前行。

⑤在14:00开出的货车，19:00到达B站时，须在岔道内停留到21:00方可继续前行。

至此已求得一昼夜中从A站开出的10次货运列车的最优调度及最优运行时刻表。

仿此，由图4.1.3可求得从其他各站点开出货车的最优调度及最优运行时刻表。

4.1.4 问题总结

本问题看似简单，是个追赶问题，只要计算出货车与客车在两站之间的运行时间即可控制货车的开出时间，其实不然，此问题是在追赶问题的基础上求最多可开出的货车辆数，我们把该问题转化成为最大流问题，应用Ford-Fulkerson标号法解决了这一问题。通过对算法的分析求解制定出了货车运行的最大数量并列出货车运行时间表，可见最大流算法的有效性和实用性。

29

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

第五章 结论

本课题主要以图论的知识为理论基础，来讨论最大流问题。最大流问题是一类应用极为广泛的问题，20世纪50年代福特(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。

最大流问题的核心依据是Ford-Fulkerson最大流最小割定理，在这个定理的基础上，解决最大流问题的几种算法有Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法等本论文分别介绍了这几种算法，并举实例说明各个算法具体的解题过程，各算法的优劣各不相同，

Ford-Fulkerson标号法是最原始的算法，由Ford和Fulkerson提出，Edmonds和Karp针对该算法增广路径选取的任意性这一缺点对它做了修正算法产生了Edmonds-Karp修正算法，而Dinic算法则兼取前两种算法的优点，是这三种算法中最有效的算法。

最大流问题是网络流问题的一个重要的内容，研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便。

在很多情况下，实际遇到的问题可能是很复杂的，甚至是无从下手，不过通过分析建立模型，如果可以建立成一个网络图，转化成为最大流问题，就会找到相应的解决方法。由此，最大流问题在现实生活中是非常重要的。

30

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

参 考 文 献

[1] 熊义杰．运筹学教程．天津：国防工业出版社，2004

[2] 徐俊明. 图论及其应用. 合肥：中国科学技术大学出版社，2005 [3] 卢开澄. 图论及其应用. 北京：清华大学出版社，1984 [4] 吴育华，杜纲．管理科学基础．天津：天津大学出版社，2001 [5] 谢政，李建平. 网络算法与复杂性理论. 北京：国防科技大学出版社，1995

[6] 刁在筠，郑汉鼎，刘家壮，刘桂真. 运筹学. 第2版. 北京：高等教育出版社，2001

[7] 田丰，马仲蕃. 图与网络流理论. 北京：科学出版社，1987 [8] 卜月华，吴建专. 图论及其应用. 南京：东南大学出版社， 2000 [9] Bondy JA, Mutry USR. Graph Theory with Applications. London and Basingstoke: MacMillan Press, 1976

[10] 王树禾. 图论及其算法. 合肥：中国科学技术大学出版社，1990 [11] 戴一奇. 图论及其应用. 北京：水利电力出版社，1988 [12] 展丙军．运筹学．哈尔滨：哈尔滨地图出版社，2005

[13] 《运筹学》教材编写组. 运筹学. 第3版. 北京: 清华大学出版社，2004 [14] 胡运权．运筹学教程．北京：清华大学出版社，2007 [15] 谢金星，邢文顺. 网络优化. 北京：清华大学出版社，2000 [16] 李向东. 运筹学：管理科学基础. 北京：北京理工大学出版社，1990 [17] 李建中, 骆吉洲(译). 图论导引. 北京：机械工业出版社，2006 [18] 王朝瑞. 图论. 北京：北京工业学院出版社，1987

31

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

致谢辞

本科毕业论文即将完成，回顾我大学四年的学习生涯，我得到了众多老师的教诲，同学的支持和帮助，再次对他们表示中心的感谢。

首先感谢我的导师王朝阳老师，他生活中待人十分热情诚恳，给予我无微不至的关怀和照顾；工作中他治学严谨，思维活跃，在研究课题阅读文献、论文写作上给予我许多指导和帮助，使我对数学的认识有了很大的提高，我将铭记恩师的教诲、关心和帮助。

还要感谢大学四年来所有的老师，为我们打下坚实的数学专业知识基础，在论文的写作过程中，还要感谢班内同学的帮助，他们在我完成论文的过程中，给我提了许多宝贵的建议，正是因为有了你们的支持和鼓励。此次毕业设计才能够顺利的完成。

感谢所有给予我帮助和锻炼的人。

最后，衷心感谢所有老师对我的栽培、支持和鼓励，感谢所有朋友的关心和帮助。向在百忙中抽出时间对此论文进行评审并提出宝贵意见的各位专家表示衷心地感谢！

衷心祝愿母校山东科技大学明天更加美好！

32

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

附录1英文原文

Maximum flow problem in the introduction, we listed one of the largest flow of goods delivery. If this issue also includes the known conditions of delivery of each unit while the cost of goods, then how to transport, to get the most traffic, and transportation costs to a minimum? This is the so-called maximum flow problem minimum cost. The maximum flow based on the definition, if each side of a first-priority claim to the number of c(e)(that the edge capacity) but also have another weights w(e) (that the unit cost flow), and has been seeking a maximum flow of the network value of F, then the minimum cost maximum flow problem, it is clear the following linear programming model can be used to describe:

min?w(e)f(e) e?E

Satisfy 0?f(e)?c(e) for all e?E

f?(v)?f?(v)

for all v?V f?(x)?F(maximum flow constraints)(Orf?(y)?F) Algorithm ideas Solve the minimum cost maximum flow problem, there are two general ways. Way is to use a maximum flow algorithm to calculate the maximum flow, and then based on the cost side, check whether it is possible to balance the flow by adjusting the flow side, so that to reduce the total cost? As long as there is a possibility, on such adjustments. After adjusting for a new maximum flow. Then, on the basis of the new flow to continue to check and adjust. This iteration continues until no adjustment may be, they will have the minimum cost maximum flow. The characteristics of this line of thought is to

33

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

maintain the feasibility of the problem (always maintain maximum flow), to promote optimal. Solution to another and in front of the maximum flow algorithm, introduced a similar line of thought, first of all, given the general flow as the initial flow of zero. The cost of the flow to zero, of course, is the smallest cost. And then find a source to the Meeting Point by flow chain, but by the requirements of this chain must be a stream flow of all chain costs by a minimum. If we can find out by flow chain, the chain in the flow by increasing flow, a new flow. The flow will be treated as the initial flow, continue to search for links by increasing stream flow. This iteration continues, until found by flow chain, then the flow is the minimum cost maximum flow. Idea of the characteristics of this algorithm is to maintain the optimal solution of (each of the new fees are the smallest stream flow), but gradually close to the feasible solution (up to maximum flow is a feasible solution when). As a result of the second algorithm and has introduced close to the maximum flow algorithm and the algorithm by finding the minimum cost flow chain, can be turned into a source to find the shortest path to the Meeting Point, so this algorithm here. In this algorithm, in order to seek to increase the minimum cost flow chain, the current flow of each, accompanied by the need to establish a network flow by the flow network. For example, Figure 1 is a network G of minimum cost flow, next to parameters c(e),f(e), w(e), and Figure 2 is the network flow by the flow network G '. By the peak-flow network and the same as the original network. By the following principles in accordance with the establishment of the network edge flow:

If G in the edge (u,v) is not enough traffic, that is, f(u,v)?e(u,v), then

34

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

G 'in the building edge (u,v), Empoweringw'(u,v)?w(u,v); edge of G if

(u,v) has been the flow, that is, f(u,v)?0, then G' in the building edge (u,v), to empower the w'(u,v)??w(u,v).

The establishment of the network by streaming, you can seek in this network to the Meeting Point source shortest path, as decided by flow path, and then in the original network by flow in this path. Here, the use of maximum flow algorithm is still the principle of increasing flow, but the cost must be selected by the smallest chain by stream flow. Calculation, there is a need to address the problem. This is the stream network by G 'the right to have a negative side, thus labeling law can not be directly applied to find x to y of the shortest path, using the right of other negative side computing network approach to the shortest path x to yto find the shortest path, will greatly reduce the computational efficiency. In order to still use the labeling method to calculate the shortest path, each flow set up by the network to achieve the shortest path, the network G can be the right of w(e) an amendment to do so by the stream to build the network will not be a negative right side, and guarantee the shortest path does not change. This modified method described below. When the flow value is zero, the first built by the shortest path for flow network, the result of non-negative right side, of course, can be used to calculate labeling law. In order to increase flow network after the establishment of a negative time is not right side of the approach taken is to have stream G edge (f (e)> 0) the right to w (e) amendment to 0. To this end, each time a flow network obtained by the shortest path, the following computing G in the right side of the new

35

本文来源：https://www.bwwdw.com/article/7yv.html