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

（毕业设计论文）最大流问题及应用山东科技大学本科毕业设计（论文）题目最大流问题以及应用学院名称数学与系统科学学院专业班级信息与计算科学2011级2班学生姓名吕永强学号201101051416摘要网络流问题是运筹学的重要研究课题。最大流问题是网络流问题的一个重要的内容，应用极为广泛。研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便。本论文讨论最大流问题，综述图论的历史背景、基本概念和基本知识;阐述网络的基本概念；介绍最大流问题的核心依据Ford-Fulkerson最大流最小割定理；综述解决最大流问题的几种算法Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法，并比较各算法在解决不同问题中的优劣。为了更加明确的展现最大流问题在生产生活中的应用，本文例举了一个实际生活中的问题一路货运列车的最优调度来突出研究最大流问题的重要意义，此实例需要求解的是在一定的限制条件下，设计出一个在一昼夜间能通过某段铁路的最多的货运列车数量并列出每辆列车开出的时刻表。在此实例中，通过从实际问题中抽象出网络图，将实际问题转化为最大流问题并应用图的性质和Ford-FUlkerson标号法的算法依据，最终解决了问题。本文采用理论与实例相结合，重在应用理论依据解决实际问题，具有较强的实践性，突出的是应用。Thenetworkflowproblemisanimportantoperationalresearchsubject.Themaximumflowproblemisanimportantcontentofnetworkflowproblem,whichhaswidelyapplications.Theresearchofmaximumflowproblemanditsapplicationstoindustry,engineering,commerce,agriculture,transportationandotherareascanbringusgreatconvenience.Thepaperdiscussesthemaximumflowproblem,andsummarizesthehistoricalbackgroundofgraphtheory,basicconcepts,basicknowledgeanddescribesthebasicconceptofthenetwork.Thecorebasisofthemaximumflowproblem--Ford-Fulkersonmaximumflowminimumcuttheoremisintroduced.Severalalgorithmsforsolvingmaximal-flowproblemlikeFord-Fulkersonlabelingalgorithm,Edmonds-Karpcorrectalgorithm,Dinicalgorithmaresummarizedinthispaper.Italsocomparesvariousalgorithmstosolvedifferentproblemsintheprosandcons.Inordertomoreclearlyshowtheapplicationofthemaximumflowproblemintheproductionlife,thepaperillustratesareal-lifeproblem--Theoptimalschedulingofrailwayfreighttraintohighlighttheimportanceofmaximumflow.Thisinstanceistobesolvedundercertainconstraints,todesignthemostfreighttrainnumbersthroughtherailwayinadayandnightandtolistouttheschedulesforeachtrain.Inthisinstance,byabstractingthenetworkdiagramfromtherealproblems,transformtheactualproblemintothemaximumflowproblem,andusethepropertiesofgraphandFord-Fulkersonlabelingalgorithm,andultimatelysolvetheproblem.Inthispaper,thecombinationoftheoryandexamplesfocusonsolvingpracticalproblemsbyapplyingtheoreticalbasis.Ithasstrongpracticalityandhighlightstheapplications.Keywords:GraphNetworkflowMaximumflow目录第一章绪论01.1最大流问题的研究内容及背景••••••••••••••••••••••••••••••0最大流问题的发展状况.....................................01选题的意义.................................................且TOC\o"1-5"\h\z第二章预备知识3_3图论.••..•..•.•..•.•..•..•..•.•..•.•..•..•..•.•..•.•..•..•..•网络的基本概念.............................................42.3最大流问题核心依据Ford-Fulkerson最大流最小割定理^\o"CurrentDocument"第三章最大流问题的几种算法88标号法（Ford-Fulkerson算法）\o"CurrentDocument"_—11Edmonds-Karp修正算法13Dinic算法.......••.••.••........••.••.••........••.••.••2\o"CurrentDocument"第四章最大流问题的应用184.1铁路货运列车的最优调度.............................•...18第五章结论...................................................•...28\o"CurrentDocument"参考文献29致谢辞30附录1英文原文•••••••••.•••••••••••••••.•••••••••••••••.••••••••••31附录2中文译文••••••••••••••••••••••••••••••••••••••••••••••••••••37第一章绪论1.1最大流问题的研究内容及背景最大流问题也就是是指网络分析问题的一类，它是在指定的条件下,要求通过网络的物流、能量流、信息流等流量为最大的问题。比如交通运输网络中的人流、车流、物流供水网络中的水流、金融系统中的现金流通信系统中的信息流等等，都属于最大流问题。图论是组合数学的一个分支与其他的数学分支如群论、矩阵论、概率论、拓扑学、数值分析有着密切的联系而且其应用十分广泛，是近年来较为活跃的数学分支之一。它的产生和发展历经了二百多年的历史，瑞士数学家欧拉(L.Euler)在1736年解决了当时颇为有名的一个数学难题，即哥尼斯城堡七桥问题，从而使他成了图论和拓扑学的创始人。早期的图论与数学游戏有密切的联系，如哈密尔顿的周游世界问题、迷宫问题、博奕问题以及棋盘上马的行走路线之类的难题等吸引了许多学者。20世纪后，图论的应用渗透到许多其他学科领域，如物理、化学、信息学、运筹学、博奕论、计算机网络、社会学以及集合论、矩阵论等。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，使图论成为数学领域中发展最快的分支之一，也成为现代研究最大流问题的一个重要工具。1.2最大流问题的发展状况最大流问题是早期的线性网络最优化的一个例子。最早研究这类问题的是美国学者希奇柯克(Hitchcock)，1941年他在研究生产组织和铁路运输方面的线性规划问题时提出运输问题的基本模型；后来柯普曼(Koopmans)在1947年独立地提出运输问题并详细地对此问题加以讨论;从上世纪40年代早期开始，康脱洛维奇(Kantorovich)围绕着运输问题作了大量的研究，因此运输问题又称为希奇柯克问题或康脱洛维奇问题。与一般线性规划问题不同，它的约束方程组的系数矩阵具有特殊的结构，这就需要采用不同的甚至更为简便的求解方法来解决这种在实际工作中经常遇到的问题。运输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题。后来把这种解决线性网络最优化的方法与最大流问题相结合，同时推动了最大流问题的发展。最大流问题就是就是在一个有向连通图中，指定一点为发点，另一点为收点，其余的点为中间点，在所有的点都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流。本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题，提高生产的有效性和生产设备的有效利用率。最大流问题应用极为广泛，很多生活中的问题都可转化为最大流问题，其难点是从实际中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。1.3选题的意义在日常生活和生产中我们时常遇到一些网络图。如交通图、旅游线路图、管道系统图等。在优化理论中所谓图就是上述各类图的抽象和概括，用图来描述我们的研究对象，以及这些对象之间的相互联系。例如旅游管理、网络通信、交通运输、金融系统等问题都可以用网络图来描述。最大流问题就是就是在一个有向连通图中，指定一点为发点，另一点为收点，其余的点为中间点，在所有的点都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流。本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题，提高生产的有效性和生产设备的有效利用率。最大流问题应用极为广泛，很多生活中的问题都可转化为最大流问题，其难点是从实际中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。第二章预备知识2.1图论所谓“图论”，顾名思义也就是是研究“图”的理论。图论中的“图”是由许多实际问题经过抽象而得到，由点及点与点之间的连线构成，它可以反映一些对象之间的关系。图形中的点表示对象（如工序、选手、通讯站等），两点之间的有向或无向连线表示对象之间具有某种特定的关系（如先后关系、胜负关系、传递关系、连接关系等）。物质结构、电路网络、城市规划、交通运输、信息传递、物资调配等都可以用点和线连接起来的图进行模拟。这里所研究的图与平面几何中的图不同，这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的七,匕相对位置如何，都是无关紧要的。定义1：两点之间不带箭头的连线称为边，一条连接七,%的边记为七（或［七,v］），表示边的集合。定义2：两点之间带箭头的连线称为E={e,e・..,e}弧,一条以v.为始点v.12mIj为终点的弧记为a=（v,v）,A={a,a,...a}表示弧的集合。iij12m定义3：由点和边构成的图为无向图，记为G=（V,E）；由点和弧构成的图为有向图，记为D=（V,A）.定义4:在无向图G中，若存在一个点边交错序列满足(v,e,v,e，…v,e,v)，iiiiiii1122k-1k-1kTOC\o"1-5"\h\ze=［v,u］（t=1,2,...k-1）,则称之为一条联结v和v的链’记为ttt+1L11k（v,v,...,v）,若v=v，则称之为圈。满足*，2，k\L定义5:在有向图D中，若存在一个点弧交错序列(v,a,v,a,...vi,a），弧a的始点为v，终点为v，记为L-1L-1\\\+1a=(v,v)，ltltlt+(v,a,v,a,...via=(v,v)，ltltlt+112k的点互不相同，则为初等链（路），以后说到的链与路，均指初等链（路）。定义6：如果对于一个无向图G的每一条边，相应有一个权数七，则称这样的图为赋权图，记为G=（V,E,C）。定义7：如果对于一个有向图D的每一条弧，相应有一个权数匕，称这样的图为网络，记为D=（V,A,C）。一般在网络图中，每条弧的权，不是表示弧的长度、而是表示弧的宽度，即代表距离、费用、通过能力（容量）等等。例如，公路运输网络中路面的宽度或管道输送网络中管道的直径，它是单位时间内允许通过实体的数量。所以将弧权称为弧的容量，网络称为容量网络（参见文献［17］）。定义8：在图仔中，若任何两个点之间至少有一条链（或一条路），则称G是连通图，否则，称为不连通图。2.2网络的基本概念假设要把起点的一批流转物运送到终点去，在每一弧上通过流转物的总量不能超过这条弧上的容量，问题是应该怎样安排运送，才能使从起点运送至终点的总量达到最大，这样的问题就称为网络上最大流问题，最大流问题是网络流问题中的一个非常重要的研究内容(参见文献[15])，以下讨论的网络均为只有一个发点七和一个收点二的容量网络D=(V,A,C)。定义9:对任意容量网络D=(V,A,C)中的弧(匕,v「有流量七，称集合f={f}为网络D上的一个流，称满足下列条件的流f为可行流：j容量限制条件：对D中每条弧(V,V)，有0<f<C；ij可ij平衡条件：①对中间点Vj，有£f=£fki(即中间点Vj的物资的输入量与输jk出量相等)。②对收、发点V,v有£f=£f=W(即从v点发出的物资TOC\o"1-5"\h\ztssijtsjj总量等于Vt点入的量)，W为网络流的总流量。在容量网络D=(V,A,C)中c表示弧(V,V)的容量，令X..为通过弧ijijij(V,V)的流量，显然有0<X<c，流｛X｝应遵守点守恒规则，即:Ijijijij+Wi=s£X-£X=\0i丰s,tJ]l-Wi=t称为守恒方程。定义10：对任意容量网络D=(V,A,C)，寻求一可行流f使得流量W取得极大值，这个可行流f便称为最大流。定义11：在容量网络D=(V,A,C)中，若p为网络中从发点七到收点Vt的一条路，给p定向为从七到Vt，p上的弧凡与p同向称为前向弧。凡与p反向称为后向弧，其集合分别用w和日-表示，f是一个可行流，如果满足0<f<c(v,v)即+<ijijijc>f>0(v,v)叩-ijijij则称R为从七到v,的(关于f的)增广链。定义12：在容量网络G=(V,A,C)中，若有弧集A为A的子集，将D分为两个子图D1,D2，其顶点集合分别记S,S，SS=V,SS=0，七,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中，从v到5vt的最大流｛f｝的流量等于分离v,v的最小割的容量。ijst证明：设在D中从vs到v,的任一可行流｛七｝的流量为W，最小割集为（S,S），最小割集的容量为c（s,S）。这个定理的证明分两步:⑴我们先证明W<c（S，S）:由守恒方程可得:w=Z(Zx„-Z»—xj)；ZZ(f)ijji-ijjiie^'^eSieSjeS=ZZ(x-x)(3.1)ieSjeS因此有：w=ZA，f）（蒙号蒙匕=c（s,S）。心jeSieSjeS心jeS⑵下面我们证明一个可行流是最大流，当且仅当不存在关于它的从七到匕的增广路径:必然性：显然，因为如果存在增广路径，还可以继续增广，流就不是最大流。充分性：假设可行流｛x｝是一个不存在关于它的增广路径的流，对于最小割集（S,S），有对任意i,jeS，存在从v,到七的增广路径，而对任意ieS,jeS，不存在从?.到v.的增广路径，由定义可知对任意ieS,jeS有：由公式(3.1)可知：W=ZZc=C(S,S)。ieSjeS即流的值等于割集的容量，定理得证。第三章最大流问题的几种算法最大流问题是社会经济生活和军事活动中经常出现的优化问题。如在经济建设和国防建设中，经常遇到一些物资调运的问题。如何制定调运方案，将物资尽快运到指定点，而且不影响费用的计划开销，即为最大流问题。下面用数学语言来说明最大流问题：设有一个有向连通图G（V,A），在V中指定一点称为发点s,和另外一点为收点t，其余的称为中间点，弧（arc）集A中每条弧（i，j）上有非负数％称为这弧的容量，记容量集为c=｛匕｝，称这样的图为一个网络，记为G（VA,c）（注：当（i，j）不是弧时匕=0）。在弧集A上的弧（i，j）定义一非负数f，称为弧（Lj）上的流量，流量的集合f=｛f｝称为网络的一个流，满足下列条件的称为可行流：j1）容量限制条件，所有的弧的流量f〃不大于弧的容量j2）平衡条件，对所有的中间点，流入的流量和等于流出的流量和，发点流出的流量F等于流进收点的总流量F.最大流问题就是求总流量最大达可行流。求解最大流问题存在许多算法，这一节将介绍几种常用算法。标号法（Ford-Fulkerson算法）Ford-Fulkerson标号法是一种找最大流f的算法。它是由Ford和Fulkerson于1957年最早提出的，其基本思想是从任意一个可行流出发寻找一条增广路径，并在这条增广路径上增加流量，于是便得到一个新的可行流，然后在这新的可行流的基础上再找一条新的增广路径，再增加流量……，继续这个过程，一直到找不到新的增广路径为止（参见文献［2］）。采用Ford-Fulkerson标号法求解最大流问题时，在标号过程中，一个点仅有下列三种状态之一：标号已检查（有标号且所有相邻点都标号了）；标号未检查（有标号，但某些相邻点未标号）；未标号（参见文献［6］）。Ford-Fulkerson标号算法分为两个过程：一是标号过程，通过标号过程找到一条增广路径；二是增广过程，沿着增广路径增加网络流流量的过程（参见文献［18］）。现在我们考虑只有一个发点七和一个收点匕的容量网络，应用Ford-Fulkerson标号算法求解它的最大流A:标号过程步骤0确定一初始可行流{f}，可以是零流。步骤1给发点V以标号［8,叩。步骤2选择一个已标号但未检查的点七，并作如下检查：对每一弧（v,V），若V未给标号，而且c>f时，即流出未饱ijjijij和弧，给vj以标号七,V」；对每一弧（v.,V.），若V.未给标号，而且f>0时，即流入非零流弧，给V以标号［七,-V.］；其中：―min{0,a},a="f若如）为流出未饱和弧jif若（V,V）为流入非零流弧1jiji步骤3重复步骤2直到收点匕被标号，或不再有顶点可以标号为止。如果点给了标号说明存在一条增广路径,故转向增广过程B。如若点yt不能获得标号，而且不存在其它可标号的顶点时，算法结束，所得到的流便是最大流。B：增广过程由终点yt开始，使用标号的第二个元素构造一条增广路径日（点vt的标号的第二个元素表示在路中倒数第二个点的下标，而这第二个点的标号的第二个元素表示倒数第三个点的下标等等），在曰上作调整得新的可行流｛f｝，（标号的第二个元素的正负号表示通过增加或减少弧流来增大流值）。ij令0为y标号的第一个元素的值，作t'f+0（vi,yj是日上前向孤f=<f-0（y.,y.）是日上后向孤'［f其它—以新的可行流｛f｝代替原来的可行流，去掉所有标号，转标号过程的步骤j1。采用Ford-Fulkerson标号算法求解最大流问题，同时得到一个最小割集。最小割集的意义是：网络从发点到收点的各个通路中，由容量决定其通过能力，通常我们将最小割集形象地称为这些通路的咽喉部分，或叫做“瓶颈”，它决定了整个网络的通过能力，即最小割集的容量的大小影响总的流量的提高。因此，为提高总的流量，必须首先考虑改善最小割集中各小弧的流量，提高它们的通过能力（参见文献［14］）。Edmonds-Karp修正算法2m，若增广路径选择得不好,即交替地采用sabeft和sdebct作为增广路径，则每次增广只能使总的流量增加1,当初始流选为零流，无疑需作2m1sabeft和sdebct交替作为增广路径时，be弧交替地以前向弧和后向弧出现。利用Ford-Fulkerson算法求解就很麻烦了（参见文献［8］）。对于Ford-FUlkerson算法，由于增广路径选取的任意性造成了该算法不是好算法，Edmonds和Karp对Ford-Fulkerson算法作修正，可概括为一句话：“先给标号的先扫描”。它的意思是对已给标号的顶点v进行扫描时，先对所有和vs先标记，所以应该先扫描，因此避免了Ford-Fulkerson算法那样交替地出现sabeft,sdebct的情况，也就避免了be弧交替地以前向弧和后向弧来回摇摆的局面。所以Edmonds-Karp的修正实质是对顶点给标记过程采用了“宽度优先”策略。使得流量增加总是沿着一条长度最短的路径从s流向t的（参见文献［3］）。现在我们仍考虑只有一个发点v^和一个收点vt的网络图，Edmonds-Karp修正算法的主要步骤是：确定一初始可行流f｝，其流量W（f）。检验当前所确定可行流是否是网络中的最大流，若不是，需进一步调整（检验一个可行流是否为最大流。只要检查一下当前可行流是否还存在增广路径，若存在，则说明当前可行流还不是最大流，否则是最大流）。将当前的可行流调整成一个流量更大的新可行流，再由②检验。同样地，我们通常用观察法确定网络的一个初始可行流。对于较为复杂的网络，至少能把初始可行流取为零流。通过在网络上标号的方法能系统地寻找出当前可行流的增广路径，它的基本思想是：从起点七起，逐步寻找七至各点匕间的增广路径，若能找到七至v的一条增广路径，则给点v标号骨，知（其中第一个标号七即为七至v这条增广路径上的最大可调整量，第二个标号以.则表示这条可行流上点v的前一点是以■点）。根据标号可反向追踪而写出这条增广路径。在逐步扩大已标号的过程中，一旦终点vt标上号，表示已找到一条由七至vt的增广路径。反之，如果标号过程进行至某一步中止了，而vt尚未标号，则表明对当前的可行流，网络中不存在任何增广路径。当前可行流即为最大流。Edmonds-Karp修正算法的具体步骤如下：①给发点v标号［3,v］，含义为v至v的增广路径已找到，前一点为v，SSSSS这条增广路径上的调整量为3。选与七关联的从七流出的未饱和弧（v,v）或流入v的非零流弧（v,v），给v标号［9,v］（对于流出弧）或sisisiis［七，-七］（对于流入弧）。其中9\C^-f若（v，v.）为流出未饱和弧:「if.若气，七）为流入非零弧

将顶点集分为互补的二个点集S、如其中S为已标号点集，宁为未标号点集；考虑所有这样的弧(v,v)或(v,v)，其中veS,veS。若弧(v,v)为iJJiijiJ从v流出的未饱和弧，则给v标号［9,v］。其中0=min{0,c-f}；iJJijiijij若弧(v,v)为流入v的非零流弧，则给v标号［9，-v］。其中jiijji0,=min{9.,f}。依此进行，得到的结果是：(a)S=0，说明网络中存在增广路径日，则由标号点反向追踪找出日，转第④步；(b)S=0，标号已进行不下去，说明对于当前可行流。网络中已无新的增广路径，当前可行流即为最大流，同时得到最小割集(S,S)。④调整过程：取0=min{6},'f+0ij令fj-f「°f(j(v,v.)是日上前向孤(v,v.)是日上后向孤其它得到新可行流{f.}，流量④调整过程：取0=min{6},'f+0ij令fj-f「°f(j用Edmonds-Karp修正算法求解最大流问题时，也可以得到一个最小割集。最小割集的意义同Ford-Fulkerson算法得到的最小割集的意义相同。Dinic算法Dinic于1970年提出了Ford-FUlkerson算法的改进算法，Dinic算法的特点是将顶点按其与发点的最短距离分层。Edmonds-Karp修正算法的实质也是一种分层，如果说Ford-Fulkerson算法是采用了深度优先策略。Edmonds-Karp修正算法则是用宽度优先取代了深度优先，Dinic算法则是兼取这两种方法。在分层时用的宽度优先法，而寻求增广路径时则采用深度优先策略(参见文献［3］)。定义13：给定一个带发点七和收点匕的容量网络D=(KA,C)及D上的A+(f)={(v,v)I(v,v)gA,f<c},可行流{f}后，我们定义］ijijij，因为D中lJA-(f)={(v,v)I(v,v)gA,f>0}plJJlJl任何一对顶点之间至多有一条弧，所以A+(f)A-(f)=0，记A(f)=A+(f)A-(f)，并且对一切%,vjgA(f)令c-f,［若(v,v)gA+(f).c=Ji^1Ljf，于是得一个带发点v和收点v的容量网lJf，若(v,v)gA-(f)stkJiiJ络D(f)=(V,A(f),C)，称之为D的关于可行流｛f｝的增量网络。为了介绍分层增量网络，我们先来介绍关于网络的一个算法——分层算法，它的基本思想是：的步骤0：把发点七标为“已标号未检查”，七口」层数h(s)=0。步骤1：在已标号未检查顶点中选取最早得到标号的顶点v，转步骤2；i如果所有标号顶点都已检查，转步骤3。步骤2：考察顶点vi的一切出弧(v,,vJ)，若vJ已标号，什么也不做；否则将v标为“已标号未检查”，并令h(J)=h(l)+1。当v,的所有出弧都考察完毕，把V,改为已检查，转步骤1。步骤3：如果有一些顶点没有标号，则从七到这些顶点不存在路；否则V,为D的根，h(i)为D中最短(v,V.)路的长。在增量网络D(f)中应用分层算法，可以求出从发点V到其余各顶点V,的最短路的长h(i)，h(i)就是顶点%(关于发点％)的层数。即V,就是D(f)的第h(i)层顶点。D(f)的第0层只有一个顶点，把顶点分层后，D(f)中的弧又可以分为三类：第一类为从第i层顶点到第i+1层顶点的弧；第二类为从第i层顶点到同一层顶点的弧；第三类为从第i层顶点到第j层顶点的弧(j<i)(参见文献[5])。定义14：对于带发点七和收点%的容量网络D=(V,A,C)，设关于可行流{f.}的增量网络D(f)=(V,A(f),C)，我们定义D(f)的子网络AD(f)=(V'(f),A(f),C)如下:V'(f)={%?}{vIh(i)<h(t)}A(f)={(V丹)1h(j)=h(i)+1<h(t),(V,V)GA(f)}{(v,V)1h(i)=h(t)-1,(v,V)GA(f)}ijijitit则ad(f)称为D的关于可行流{f..}的分层增量网络。其中第0层和第h(t)ij层分别只有一个顶点七和v「AD(f)的所有弧都是由第i层顶点指向第i+1层顶点i<h(t)。Dinic算法的基本思想及具体步骤Dinic算法的基本思想是：从带发点七和收点匕的容量网络D的任一可行流f0(例如零流)开始，构造D的关于f0的分层增量网络AD(匕)，在AD(匕)中找一条从七到匕的增广路径^，对f0沿^进行增广得到可行流f1，在AD(f)中删去p上容量最小的弧，并相应修改AD(f1)上弧的容000量，得到网络AD(f1)，然后可以在AD(f1)中再找一条从v到u的增广005t路径p，对f1沿p进行增广得到可行流f2，重复上述步骤依次得到D的00可行流f1,f2,,f广f，因为AD(f0)只有有限条弧，每次至少删去一条弧，所以在有限步后必然使余下的网络不再存在增广路径，vt在AD(f)中的层数一定大于它在AD(f0)中的层数；针对AD(f1)重复上面的做法，在有限次增广后一定会得到D的可行流人，使vt在AD(f2)中的层数更大。由于vt的层数最多为n-/n是网络D的顶点数)。因此经过有限步后得到D的可行流f'D中不再有f的增广链，这时f就是D的最大流。Dinic算法的具体步骤如下：步骤0:在网络D中任意取一个可行流f0作为初始可行流，令p=0,q=0,fp=/°步骤1：(作分层增量网络)根据fp作D的增量网络D(fp)，再利用分层算法构造分层增量网络AD(fp)，如果在作分层增量网络时v得不到标号，qt则算法结束，fp就是D的最大流；否则转步骤2°步骤2：(寻找增广路径)给发点v标号为［+3,叩，令i=s。如v^AD(fp)没有出弧，转⑤；否则在AD(fp)中任取V,的一条出弧(V,V.)，转③。设V的标号为［0,a］，其中a为V前面的节点，令0=min{0,c}，v.获iiiiijiij］得标号［0.,v］。如果j=t，转步骤3；否则令i=j，转②。设v的标号为［0,a］，如果a丰v，在AD(fp)中删去v的所有入弧，所iiiisqi得的网络仍记为AD(fp)，转②；否则置q=q+1，转步骤1。q步骤3：(增广)从顶点vt的标号中的第二个元素反向追踪，求出AD(fp)的增广路径^，在AD(fp)中把^上的每条弧的容量&.改为乌-气,删去容量为0的弧，同时把流fp增广为流fp+i，把AD(fp)中修改容量和删去弧后的网络记为AD(fp+i)，置p=p+1，去掉网络AD(fp)中所有顶点的标号，转步骤2。第四章最大流问题的应用4.1铁路货运列车的最优调度某地区A、B两市之间要修建一铁路，依据地势、环境、需求等因素，修建铁路的预定方案如下：（1）铁路的运行方式为客车与货运兼营的双轨铁路（单向单轨），在其运行的列车有旅客快车和货运列车，由于客车的运行时间是国家铁路部门早已排定的，不可更改，且规定客运优于货运，即货车在每站开出前应先明确在其到达前方车站前不会被客车赶上，否则在该站等候不能开车。又若货车的前方到达站如无停车岔道，则货车从本站开出前应明确在其前面两站的行程中不会被客车赶上否则在本站等候不能开车，余类推。（2）铁路线内有A、B、C、D四个站，各站的岔道数为n=5,n=7,n=9及n=11.这些岔道可供调车用，亦可供停车卸货及洗刷车辆用。（3）按早已排定的旅客快车时刻表，客车每天凌晨2:00从A站开出，以后每隔5小时开出一列，一昼夜共开出5列，当天最后一列的开车时间与翌晨第一列的开车时间相隔4小时。客车的行车时间在A、B站之间为3小时；在B、C站之间为2小时；在C、D站之间为5小时。（4）在不干扰客车运行的条件下，关于货运列车的初步安排为：每天0:00从人站发出一列，以后每隔2小时发出一列，货车的行车时间在A、8站之间为5小时；在B、C站之间为4小时；在C、D站之间为7小时。为了充分发挥该铁路线的货运能力，需要排定一张最优的货车运行时刻表，即要求每天发出最多的货运列车且不干扰已排定的客运列车。求解这个问题较为复杂，但可将其转化为网络最大流问题。（1）设A、B两市及其间的车站共^个。每个车站有气条岔道（k=1,2,3・・・D,可停放n冽列车。从第k站到第k+1站的行车时间货车为上个小时，客车为h'个小时。设T*为火车到达第k站并从第k站开出的时刻设T「为客车到达第k站并从第k站开出的时刻设Te为货车到达第k+1站并从第k+1站开出的时刻设T…为客车到达第k+1站并从第k+1站开出的时刻于是显然有T=T+1T'=T'+t'k+1kkk+1kk（2）若T,T与T',T'!有公共部分，则称T,T与T',T'屁相交的，kk+1k+1kk+1k+1否则成为不相交的。显然有当只Tk,Tk+1与T',TL］相交情况下客车才有可能（并非必然）在第嘲与地k+1站间追上货车。（3）在T,T与T',T'］相交情况下，t，t，T'，T'kk+1k+1kk+1kk+1

图4.11情况巧为途中货车追上了客车故不符合题意。情况I与情况II中在第k站与第k+1站间不发生在途中追上货车。而在情况B中必发生在第k站与第k+1站间客车在途中追上货车。于是有下列结论：若II',T'在II具］内，即T'>T及寸<T，则在第踊与第k+1kk+1kk+1kkk+1k+1站必发生客车追上货车情况。否则在第k站与第k+1站之间不发生客车追上货车情况。（4）绘制网络图用（k，Tk）表示第啪处于时刻Tk的状态，如在tk上图中各弧旁的数字为容量，因铁路线是单向单轨的，故水平方向的弧容量为1，垂直方向的弧的容量为各站的岔道数量，在列出全部状态的网络图中求最大流，此最大流即为允许开出的最多货运列车数。以货运列车的运行时间为基础绘制网络图。（1）令T,T,T,T为火车从某站开出或到达某站的时刻。依题意，若不ABCD受客车干扰则：ta=0:00,2:00,4:00t=5:00,7:00,9:00BTc=9:00,11:00,13:00tD=16:00,18:00,20:00于是货车在相邻两站的运行时间为（若不受客车干扰）：T,t]：康或扇]也,k,13]10,15112,17114,191虹扇231或项0,27〕TOC\o"1-5"\h\zABxx（25点即翌日1点，余类推）T,t]：（5,9][7,11]鱼』11,15]13,17]15,19]17,21]些3〕,[21,25]屁27]辰29]127,31BCxXT,T]：b,61匝,13,20115,22117,24119,261邑ME3,301E5,321E7,341E9,361[3CDxX(2)令T',T',T',T'为客车从某站开出或到达某站的时刻，依题意：ABCDt'=2:00,7:00,12:00,17:00,22:00At'=5:00,10:00,15:00,20:00,25:00(即1:00)B

tc=7:00,12:00,17:00,22:00,27:00（即3:00）tD=12:00,17:00,22:00,27:00（即3:00）,32:00（即8:00）于是客车在相邻两站之间的运行时间为：TA具Blb:00,5:0。］G:00,10:00】112:00,15:0。］117:00,20:00］卜2:00,25:00】1k:00,7:00】110:00,12:00】115:00,17:00】卜0:00,22:00】\15:00,27:00】3COAF2fl0*5,r4£iLiF5rSCO*5rS£ILI,3rr1LI：LI：I5rL12:Ll：lr14:0CrLr'18:0Cr20:0C［5,r22:Li：i〔1，匚、19:00(3)比较〔其'及J具］我们发现1?:00,10:00在16:00,11:00之内;ABAB［17:00,20:0。］在［16:00,21:00］比较［'具'及J具］,我们发现卜：00,12：00在b:00,13:00］之内；BCBC卜0:00,22:00在119:00,23:00］比较I具d与［c具D1我们发现卜2:00,17:00在h1：00,18:00］之内；0:00,27:00在E1:00,28:00］之内，其在图3中的表示同前。（5）做网络的发点七，并从七向A站的各状态节点作辅助弧，辅助弧的容量等于以A站的各状态节点为起点的各弧的容量的总和。作网络的收点七,并从。站的各状态节点向七作辅助弧。辅助弧的容量等于以D站个状态节点为终点的各弧的容量总和。I)以零流f={0,0,II）以F表示图3中第i行第例的节点。用Ford-Fulkerson标号法求得以下增广链并按0值进行调整。V(0,3*)V1(v14,1)V(0,3)W)V(0,3)V44(V43,1)V(0,3)匕(v54,1)V(0,3)WW匕(V64,1)V(0,3)(V,1)7,3"顷)Vs(0,3)(V,1)9,2V1,1(Vs,6)V21(V1,6)V1(V3,4,1)V3,1(V,6)V1(V44,1)V51(vs，6)V6,1(Vs,6)QU,6)V6,2(V6,1J)V7,2(V7/1)V4,2(V3,2J)MJ)V6,3(V6,2J)%4(V13,1)0=1V3,3(V2,3J)0=1V43(V42,1)0=1W/0=10=1V7,3(V7,2J)V(v,1)0=1V(V,6)V(V,1)V(V,1)8,1s8,28,18,28,2E，1)V(0,V(0,8)"s，6)匕叫0,4，DV(0,8)",V(0,8)",，6)⑩V(0,8)",1，6)V12,3(V12,2，1)99=1匕叫2,4，D以上10条增广链的调整量均为9=1七。故现行流即为最大流，其流量v(f)=f+f+f+f+f+f+f+fs,(1,1)s,(2,1)s,(3,1)s,(5,1)s,(6,1)s,(7,1)s,(8,1)s,(10,1)+f(111)+f(121)=1+1+1+1+1+1+1+1+1+1=10结论在本问题所给条件下各车站一昼夜中能开出的最多货运列车数位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方可继续前行。在14:00开出的货车，19:00到达B站时，须在岔道内停留到21:00方可继续前行。至此已求得一昼夜中从A站开出的10次货运列车的最优调度及最优运行时刻表。本问题看似简单，是个追赶问题，只要计算出货车与客车在两站之间的运行时间即可控制货车的开出时间，其实不然，此问题是在追赶问题的基础上求最多可开出的货车辆数，我们把该问题转化成为最大流问题，应用Ford-Fulkerson标号法解决了这一问题。通过对算法的分析求解制定出了货车运行的最大数量并列出货车运行时间表，可见最大流算法的有效性和实用性。第五章结论本课题主要以图论的知识为理论基础，来讨论最大流问题。最大流问题是一类应用极为广泛的问题，20世纪50年代福特(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。最大流问题的核心依据是Ford-FUlkerson最大流最小割定理，在这个定理的基础上，解决最大流问题的几种算法有Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法等本论文分别介绍了这几种算法，并举实例说明各个算法具体的解题过程，各算法的优劣各不相同，Ford-Fulkerson标号法是最原始的算法，由Ford和FUlkerson提出，Edmonds和Karp针对该算法增广路径选取的任意性这一缺点对它做了修正算法产生了Edmonds-Karp修正算法，而Dinic算法则兼取前两种算法的优点，是这三种算法中最有效的算法。最大流问题是网络流问题的一个重要的内容，研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便。在很多情况下，实际遇到的问题可能是很复杂的，甚至是无从下手，不过通过分析建立模型，如果可以建立成一个网络图，转化成为最大流问题，就会找到相应的解决方法。由此，最大流问题在现实生活中是非常重要的。参考文献熊义杰.运筹学教程.天津：国防工业出版社，2004徐俊明.图论及其应用.合肥：中国科学技术大学出版社，2005卢开澄.图论及其应用.北京：清华大学出版社，1984吴育华，杜纲.管理科学基础.天津：天津大学出版社，2001谢政，李建平.网络算法与复杂性理论.北京：国防科技大学出版社，1995刁在筠，郑汉鼎，刘家壮，刘桂真运筹学.第2版.北京：高等教育出版社，2001田丰，马仲蕃.图与网络流理论.北京：科学出版社，1987卜月华，吴建专.图论及其应用.南京：东南大学出版社，2000BondyJA,MutryUSR.GraphTheorywithApplications.LondonandBasingstoke:MacMillanPress,1976王树禾.图论及其算法.合肥：中国科学技术大学出版社，1990戴一奇.图论及其应用.北京：水利电力出版社，1988展丙军.运筹学.哈尔滨：哈尔滨地图出版社，2005《运筹学》教材编写组.运筹学.第3版.北京：清华大学出版社，2004胡运权.运筹学教程.北京：清华大学出版社，2007谢金星，邢文顺.网络优化.北京：清华大学出版社，2000李向东.运筹学：管理科学基础.北京：北京理工大学出版社，1990李建中，骆吉洲（译）.图论导引.北京：机械工业出版社，2006王朝瑞.图论.北京：北京工业学院出版社，1987致谢辞本科毕业论文即将完成，回顾我大学四年的学习生涯，我得到了众多老师的教诲，同学的支持和帮助，再次对他们表示中心的感谢。首先感谢我的导师王朝阳老师，他生活中待人十分热情诚恳，给予我无微不至的关怀和照顾；工作中他治学严谨，思维活跃，在研究课题阅读文献、论文写作上给予我许多指导和帮助，使我对数学的认识有了很大的提高，我将铭记恩师的教诲、关心和帮助。还要感谢大学四年来所有的老师，为我们打下坚实的数学专业知识基础，在论文的写作过程中，还要感谢班内同学的帮助，他们在我完成论文的过程中，给我提了许多宝贵的建议，正是因为有了你们的支持和鼓励。此次毕业设计才能够顺利的完成。感谢所有给予我帮助和锻炼的人。最后，衷心感谢所有老师对我的栽培、支持和鼓励，感谢所有朋友的关心和帮助。向在百忙中抽出时间对此论文进行评审并提出宝贵意见的各位专家表示衷心地感谢！衷心祝愿母校山东科技大学明天更加美好！附录1英文原文Maximumflowproblemintheintroduction,welistedoneofthelargestflowofgoodsdelivery.Ifthisissuealsoincludestheknownconditionsofdeliveryofeachunitwhilethecostofgoods,thenhowtotransport,togetthemosttraffic,andtransportationcoststoaminimum?Thisistheso-calledmaximumflowproblemminimumcost.Themaximumflowbasedonthedefinition,ifeachsideofafirst-priorityclaimtothenumberofc(e)(thattheedgecapacity)butalsohaveanotherweightsw(e)(thattheunitcostflow),andhasbeenseekingamaximumflowofthenetworkvalueofF,thentheminimumcostmaximumflowproblem,itisclearthefollowinglinearprogrammingmodelcanbeusedtodescribe:minZw(e)f(e)eeESatisfy0<f(e)<c(e)foralleeEf+(v)=f-(v)forallveVf+(x)=F(maximumflowconstraints)(Orf-(y)=F)AlgorithmideasSolvetheminimumcostmaximumflowproblem,therearetwogeneralways.Wayistouseamaximumflowalgorithmtocalculatethemaximumflow,andthenbasedonthecostside,checkwhetheritispossibletobalancetheflowbyadjustingtheflowside,sothattoreducethetotalcost?Aslongasthereisapossibility,onsuchadjustments.Afteradjustingforanewmaximumflow.Then,onthebasisofthenewflowtocontinuetocheckandadjust.Thisiterationcontinuesuntilnoadjustmentmaybe,theywillhavetheminimumcostmaximumflow.Thecharacteristicsofthislineofthoughtistomaintainthefeasibilityoftheproblem(alwaysmaintainmaximumflow),topromoteoptimal.Solutiontoanotherandinfrontofthemaximumflowalgorithm,introducedasimilarlineofthought,firstofall,giventhegeneralflowastheinitialflowofzero.Thecostoftheflowtozero,ofcourse,isthesmallestcost.AndthenfindasourcetotheMeetingPointbyflowchain,butbytherequirementsofthischainmustbeastreamflowofallchaincostsbyaminimum.Ifwecanfindoutbyflowchain,thechainintheflowbyincreasingflow,anewflow.Theflowwillbetreatedastheinitialflow,continuetosearchforlinksbyincreasingstreamflow.Thisiterationcontinues,untilfoundbyflowchain,thentheflowistheminimumcostmaximumflow.Ideaofthecharacteristicsofthisalgorithmistomaintaintheoptimalsolutionof(eachofthenewfeesarethesmalleststreamflow),butgraduallyclosetothefeasiblesolution(uptomaximumflowisafeasiblesolutionwhen).Asaresultofthesecondalgorithmandhasintroducedclosetothemaximumflowalgorithmandthealgorithmbyfindingtheminimumcostflowchain,canbeturnedintoasourcetofindtheshortestpathtotheMeetingPoint,sothisalgorithmhere.Inthisalgorithm,inordertoseektoincreasetheminimumcostflowchain,thecurrentflowofeach,accompaniedbytheneedtoestablishanetworkflowbytheflownetwork.Forexample,Figure1isanetworkGofminimumcostflow,nexttoparametersc(e),f(e),w(e),andFigure2isthenetworkflowbytheflownetworkG'.Bythepeak-flownetworkandthesameastheoriginalnetwork.Bythefollowingprinciplesinaccordancewiththeestablishmentofthenetworkedgeflow:IfGintheedge(u,v)isnotenoughtraffic,thatis,f(u,v)<e(u,v),thenG'inthebuildingedge(u,v),EmpoweringW(u,v)=w(u,v);edgeofGif(u,v)hasbeentheflow,thatis,f(u,v)>0,thenG'inthebuildingedge(u,v),toempowertheW(u,v)二一w(u,v).Theestablishmentofthenetworkbystreaming,youcanseekinthisnetworktotheMeetingPointsourceshortestpath,asdecidedbyflowpath,andthenintheoriginalnetworkbyflowinthispath.Here,theuseofmaximumflowalgorithmisstilltheprincipleofincreasingflow,butthecostmustbeselectedbythesmallestchainbystreamflow.Calculation,thereisaneedtoaddresstheproblem.ThisisthestreamnetworkbyG'therighttohaveanegativeside,thuslabelinglawcannotbedirectlyappliedtofindxtojoftheshortestpath,usingtherightofothernegativesidecomputingnetworkapproachtotheshortestpathxtojtofindtheshortestpath,willgreatlyreducethecomputationalefficiency.Inordertostillusethelabelingmethodtocalculatetheshortestpath,eachflowsetupbythenetworktoachievetheshortestpath,thenetworkGcanbetherightofw(e)anamendmenttodosobythestreamtobuildthenetworkwillnotbeanegativerightside,andguaranteetheshortestpathdoesnotchange.Thismodifiedmethoddescribedbelow.Whentheflowvalueiszero,thefirstbuiltbytheshortestpathforflownetwork,theresultofnon-negativerightside,ofcourse,canbeusedtocalculatelabelinglaw.InordertoincreaseflownetworkaftertheestablishmentofanegativetimeisnotrightsideoftheapproachtakenistohavestreamGedge(f(e)>0)therighttow(e)amendmentto0.Tothisend,eachtimeaflownetworkobtainedbytheshortestpath,thefollowingcomputingGintherightsideofthenewW'(u,v):w"(w,v)=L(u)-L(v)+w(u,v)(*)WhereL(u),L(v)-calculationofG'oftheshortestpathxtojwhenuandvthevalueofthelabel.Forthefirsttimeiftheshortestpath(u,v)istheflowpathbytheedge,then,accordingtotheshortestpathalgorithmmusthaveL(v)=L(u)+W(u,