最大流问题以及应用信息与计算科学毕业设计论文.doc 44页

'山东科技大学本科毕业设计（论文）题目最大流问题以及应用学院名称数学与系统科学学院专业班级信息与计算科学2011级2班学生姓名吕永强学号201101051416 摘要网络流问题是运筹学的重要研究课题。最大流问题是网络流问题的一个重要的内容，应用极为广泛。研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便。本论文讨论最大流问题，综述图论的历史背景、基本概念和基本知识；阐述网络的基本概念；介绍最大流问题的核心依据——Ford-Fulkerson最大流最小割定理；综述解决最大流问题的几种算法Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法，并比较各算法在解决不同问题中的优劣。为了更加明确的展现最大流问题在生产生活中的应用，本文例举了一个实际生活中的问题——铁路货运列车的最优调度来突出研究最大流问题的重要意义，此实例需要求解的是在一定的限制条件下，设计出一个在一昼夜间能通过某段铁路的最多的货运列车数量并列出每辆列车开出的时刻表。在此实例中，通过从实际问题中抽象出网络图，将实际问题转化为最大流问题并应用图的性质和Ford-Fulkerson标号法的算法依据，最终解决了问题。本文采用理论与实例相结合，重在应用理论依据解决实际问题，具有较强的实践性，突出的是应用。 AbstractThenetworkflowproblemisanimportantoperationalresearchsubject.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.Ithasstrongpracticalityand highlightstheapplications.Keywords：GraphNetworkflowMaximumflow 目录第一章绪论....................................................................................................................11.1最大流问题的研究内容及背景......................................................................11.2最大流问题的发展状况...................................................................................11.3选题的意义...........................................................................................................2第二章预备知识.........................................................................................................42.1图论........................................................................................................................42.2网络的基本概念.................................................................................................52.3最大流问题核心依据——Ford-Fulkerson最大流最小割定理..........7第三章最大流问题的几种算法......................................................................93.1标号法(Ford-Fulkerson算法)........................................................................93.2Edmonds-Karp修正算法..............................................................................123.3Dinic算法.........................................................................................................15第四章最大流问题的应用...............................................................................194.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图论所谓“图论”，顾名思义也就是是研究“图”的理论。图论中的“图”是由许多实际问题经过抽象而得到，由点及点与点之间的连线构成，它可以反映一些对象之间的关系。图形中的点表示对象(如工序、选手、通讯站等)，两点之间的有向或无向连线表示对象之间具有某种特定的关系(如先后关系、胜负关系、传递关系、连接关系等)。物质结构、电路网络、城市规划、交通运输、信息传递、物资调配等都可以用点和线连接起来的图进行模拟。这里所研究的图与平面几何中的图不同，这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的v,v相对位置如何，都是无关紧要的。ij定义1：两点之间不带箭头的连线称为边，一条连接v,v的边记为v(或ijs[v,v])，表示边的集合。ij定义2：两点之间带箭头的连线称为E{e,e,e}弧，一条以v为始点v12mij为终点的弧记为a(v,v),A{a,a,a}表示弧的集合。iij12m定义3：由点和边构成的图为无向图，记为G(V,E)；由点和弧构成的图为有向图，记为D(V,A).定义4：在无向图G中，若存在一个点边交错序列(v,e,v,e,v,e,v)，满足i1i1i2i2ik1ik1ik4 山东科技大学本科毕业设计（论文）e[v,v](t1,2,k1)，则称之为一条联结v和v的链，记为ititit1i1ik(v,v,,v),若vv，则称之为圈。i1i2iki1ik定义5：在有向图D中，若存在一个点弧交错序列(v,a,v,a,v,a)，弧a的始点为v，终点为v，记为i1i1i2i2ik1ik1ititit1a(v,v)，则称这条点弧的交错序列为从v到v的一条路，记为ititit1i1ik(v,v,,v)。若路的第一点和最后一点相同，则称之为回路。链与路中i1i2ik的点互不相同，则为初等链(路)，以后说到的链与路，均指初等链(路)。定义6：如果对于一个无向图G的每一条边，相应有一个权数w，则称这ij样的图为赋权图，记为G(V,E,C)。定义7：如果对于一个有向图D的每一条弧，相应有一个权数c，称这样ij的图为网络,记为D(V,A,C)。一般在网络图中，每条弧的权，不是表示弧的长度、而是表示弧的宽度，即代表距离、费用、通过能力(容量)等等。例如，公路运输网络中路面的宽度或管道输送网络中管道的直径，它是单位时间内允许通过实体的数量。所以将弧权称为弧的容量，网络称为容量网络（参见文献[17]）。定义8：在图G中，若任何两个点之间至少有一条链（或一条路），则称G是连通图，否则，称为不连通图。2.2网络的基本概念假设要把起点的一批流转物运送到终点去，在每一弧上通过流转物的总量不能超过这条弧上的容量，问题是应该怎样安排运送，才能使从起点5 山东科技大学本科毕业设计（论文）运送至终点的总量达到最大，这样的问题就称为网络上最大流问题，最大流问题是网络流问题中的一个非常重要的研究内容（参见文献[15]），以下讨论的网络均为只有一个发点v和一个收点v的容量网络D(V,A,C)。st定义9：对任意容量网络D(V,A,C)中的弧(v,v)有流量f，称集合ijijf{f}为网络D上的一个流，称满足下列条件的流f为可行流：ij(1)容量限制条件：对D中每条弧(v,v)，有0fc；ijijij(2)平衡条件：①对中间点vi，有fijfki(即中间点vi的物资的输入量与输出jk量相等)。②对收、发点vt,vs有fsifjtW(即从vs点发出的物资总量ij等于v点入的量)，W为网络流的总流量。t在容量网络D(V,A,C)中c表示弧(v,v)的容量，令x为通过弧ijijij(v,v)的流量，显然有0xc，流{x}应遵守点守恒规则，即：ijijijijWisxijxji0is,tWit称为守恒方程。定义10：对任意容量网络D(V,A,C)，寻求一可行流f使得流量W取得极大值，这个可行流f便称为最大流。定义11：在容量网络D(V,A,C)中，若为网络中从发点v到收点v的st一条路，给定向为从v到v，上的弧凡与同向称为前向弧。凡与反st6 山东科技大学本科毕业设计（论文）向称为后向弧，其集合分别用和表示，f是一个可行流，如果满足0fc(v,v)ijijijcf0(v,v)ijijij则称为从v到v的(关于f的)增广链。st"定义12：在容量网络G(V,A,C)中，若有弧集A为A的子集，将D分为两个子图D,D，其顶点集合分别记S,S，SSV,SS，v,v分别12st""""属于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到vst的最大流{f}的流量等于分离v,v的最小割的容量。ijst证明：设在D中从v到v的任一可行流{x}的流量为W，最小割集为stij(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)(3.1)iSjS因此有：W(xijxji)xijcijC(S,S)。iSjSiSjSiSjSvv⑵下面我们证明一个可行流是最大流，当且仅当不存在关于它的从s到t的增广路径：必然性：显然，因为如果存在增广路径，还可以继续增广，流就不是最大流。充分性：假设可行流{x}是一个不存在关于它的增广路径的流，对于最小ij割集(S,S)，有对任意i,jS，存在从v到v的增广路径，而对任意ijiS,jS，不存在从v到v的增广路径，由定义可知对任意iS,jS有：ijxc,x0ijijji由公式(3.1)可知：WcijC(S,S)。iSjS即流的值等于割集的容量，定理得证。8 山东科技大学本科毕业设计（论文）第三章最大流问题的几种算法最大流问题是社会经济生活和军事活动中经常出现的优化问题。如在经济建设和国防建设中，经常遇到一些物资调运的问题。如何制定调运方案，将物资尽快运到指定点，而且不影响费用的计划开销，即为最大流问题。下面用数学语言来说明最大流问题：1.设有一个有向连通图G(V,A)，在V中指定一点称为发点s,和另外一点为收点t，其余的称为中间点，弧（arc）集A中每条弧（i，j）上有非负数c称为这弧的容量，记容量集为c={c}，称这样的图为一个网络，记为ijijG(V,A,c)（注：当（i，j）不是弧时c=0）。ij2.在弧集A上的弧（i，j）定义一非负数f，称为弧（i，j）上的流量，ij流量的集合f={f}称为网络的一个流，满足下列条件的称为可行流：ij1）容量限制条件，所有的弧的流量f不大于弧的容量c；ijij2）平衡条件，对所有的中间点，流入的流量和等于流出的流量和，发点流出的流量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]）。现在我们考虑只有一个发点v和一个收点v的容量网络，st应用Ford-Fulkerson标号算法求解它的最大流3.1.2Ford-Fulkerson标号法的具体步骤A:标号过程步骤0确定一初始可行流{f}，可以是零流。ij步骤1给发点v以标号[,v]。ss步骤2选择一个已标号但未检查的点v，并作如下检查：i1对每一弧(v,v)，若v未给标号，而且cf时，即流出未饱ijjijij和弧,给v以标号[,v]；jji2对每一弧(v,v)，若v未给标号，而且f0时，即流入非零jijji流弧，给v以标号[,v]；jjicf若(v,v)为流出未饱和弧ijijij其中：min{,},jifji若(vj,vi)为流入非零流弧10 山东科技大学本科毕业设计（论文）步骤3重复步骤2直到收点v被标号，或不再有顶点可以标号为止。t如果点给了标号说明存在一条增广路径，故转向增广过程B。如若点vt不能获得标号，而且不存在其它可标号的顶点时，算法结束，所得到的流便是最大流。B：增广过程由终点v开始，使用标号的第二个元素构造一条增广路径(点v的标tt号的第二个元素表示在路中倒数第二个点的下标，而这第二个点的标号的第二个元素表示倒数第三个点的下标等等)，在上作调整得新的可行流{f}，(标号的第二个元素的正负号表示通过增加或减少弧流来增大流值)。ij令为v标号的第一个元素的值，作tf(v,v)是上前向弧ijijff(v,v)是上后向弧ijijjifij其它以新的可行流{f}代替原来的可行流，去掉所有标号，转标号过程的步骤ij1。采用Ford-Fulkerson标号算法求解最大流问题，同时得到一个最小割集。最小割集的意义是：网络从发点到收点的各个通路中，由容量决定其通过能力，通常我们将最小割集形象地称为这些通路的咽喉部分，或叫做“瓶颈”，它决定了整个网络的通过能力，即最小割集的容量的大小影响总的流量的提高。因此，为提高总的流量，必须首先考虑改善最小割集中各小弧的流量，提高它们的通过能力（参见文献[14]）。11 山东科技大学本科毕业设计（论文）3.2Edmonds-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]）。abcmmmms1tmmmmdef图3.2.112 山东科技大学本科毕业设计（论文）现在我们仍考虑只有一个发点v和一个收点v的网络图，stEdmonds-Karp修正算法的主要步骤是：1确定一初始可行流{f}，其流量W(f)。ij2检验当前所确定可行流是否是网络中的最大流，若不是，需进一步调整(检验一个可行流是否为最大流。只要检查一下当前可行流是否还存在增广路径，若存在，则说明当前可行流还不是最大流，否则是最大流)。3将当前的可行流调整成一个流量更大的新可行流，再由②检验。同样地，我们通常用观察法确定网络的—个初始可行流。对于较为复杂的网络，至少能把初始可行流取为零流。通过在网络上标号的方法能系统地寻找出当前可行流的增广路径，它的基本思想是：从起点v起，逐步s寻找v至各点v间的增广路径，若能找到v至v的一条增广路径，则给点vsisii标号[,]（其中第一个标号即为v至v这条增广路径上的最大可调整iiisi量，第二个标号则表示这条可行流上点v的前一点是点）。根据标号可iii反向追踪而写出这条增广路径。在逐步扩大已标号的过程中，一旦终点v标t上号，表示已找到一条由v至v的增广路径。反之，如果标号过程进行至st某一步中止了，而v尚未标号，则表明对当前的可行流，网络中不存在任t何增广路径。当前可行流即为最大流。Edmonds-Karp修正算法的具体步骤如下：1给发点v标号[,v]，含义为v至v的增广路径已找到，前一点为v，sssss这条增广路径上的调整量为。选与v关联的从v流出的未饱和弧ss13 山东科技大学本科毕业设计（论文）(v,v)或流入v的非零流弧(v,v)，给v标号[,v](对于流出弧)或sisisiis[,v](对于流入弧)。iscf若(v,v)为流出未饱和弧sisisi其中：ifsi若(vi,vs)为流入非零弧2将顶点集分为互补的二个点集S、S，其中S为已标号点集，S为未标号点集；3考虑所有这样的弧(v,v)或(v,v)，其中vS,vS。若弧(v,v)为ijjiijij从v流出的未饱和弧，则给v标号[,v]。其中min{,cf}；ijjijiijij若弧(v,v)为流入v的非零流弧，则给v标号[,v]。其中jiijjimin{,f}。依此进行，得到的结果是：jiij(a)S，说明网络中存在增广路径，则由标号点反向追踪找出，转第④步；(b)S，标号已进行不下去，说明对于当前可行流。网络中已无新的增广路径，当前可行流即为最大流，同时得到最小割集(S,S)。f(v,v)是上前向弧ijij4调整过程：取min{}，令ff(v,v)是上后向弧jijijjivjfij其它得到新可行流{f}，流量W(f)W(f)，即比原可行流流量增加了，ij再转①步。用Edmonds-Karp修正算法求解最大流问题时，也可以得到一个最小割集。最小割集的意义同Ford-Fulkerson算法得到的最小割集的意义相同。14 山东科技大学本科毕业设计（论文）3.3Dinic算法Dinic于1970年提出了Ford-Fulkerson算法的改进算法，Dinic算法的特点是将顶点按其与发点的最短距离分层。Edmonds-Karp修正算法的实质也是一种分层，如果说Ford-Fulkerson算法是采用了深度优先策略。Edmonds-Karp修正算法则是用宽度优先取代了深度优先，Dinic算法则是兼取这两种方法。在分层时用的宽度优先法，而寻求增广路径时则采用深度优先策略（参见文献[3]）。3.3.1增量网络与分层增量网络定义13：给定一个带发点v和收点v的容量网络D(V,A,C)及D上的stA(f){(v,v)|(v,v)A,fc}ijijijij可行流{fij}后，我们定义，因为D中任A(f){(v,v)|(v,v)A,f0}ijjiji何一对顶点之间至多有一条弧，所以A(f)A(f)，记A(f)A(f)A(f)，并且对一切(v,v)A(f)令ijcf,若(v,v)A(f)ijijijc，于是得一个带发点v和收点v的容量网络ijstf，若(v,v)A(f)jiijD(f)(V,A(f),C)，称之为D的关于可行流{f}的增量网络。ij为了介绍分层增量网络，我们先来介绍关于网络的一个算法——分层算法，它的基本思想是：步骤0：把发点v标为“已标号未检查”，v的层数h(s)0。ss步骤1：在已标号未检查顶点中选取最早得到标号的顶点v，转步骤2；如i果所有标号顶点都已检查，转步骤3。步骤2：考察顶点v的一切出弧(v,v)，若v已标号，什么也不做；否则将iijj15 山东科技大学本科毕业设计（论文）v标为“已标号未检查”，并令h(j)h(i)1。当v的所有出弧都考察完毕，ji把v改为已检查，转步骤1。i步骤3：如果有—些顶点没有标号，则从v到这些顶点不存在路；否则v为siD的根，h(i)为D中最短(v,v)路的长。si在增量网络D(f)中应用分层算法，可以求出从发点v到其余各顶点vsi的最短路的长h(i)，h(i)就是顶点v（关于发点v）的层数。即v就是D(f)isi的第h(i)层顶点。D(f)的第0层只有一个顶点，把顶点分层后，D(f)中的弧又可以分为三类：第一类为从第i层顶点到第i1层顶点的弧；第二类为从第i层顶点到同一层顶点的弧；第三类为从第i层顶点到第j层顶点的弧(ji)（参见文献[5]）。定义14：对于带发点v和收点v的容量网络D(V,A,C)，设关于可行流st{f}的增量网络D(f)(V,A(f),C)，我们定义D(f)的子网络ij""AD(f)(V(f),A(f),C)如下："V(f){v}{v|h(i)h(t)}ti"A(f){(v,v)|h(j)h(i)1h(t),(v,v)A(f)}{(v,v)|h(i)h(t)1,(v,v)A(f)}ijijitit则AD(f)称为D的关于可行流{f}的分层增量网络。其中第0层和第h(t)ij层分别只有一个顶点v和v，AD(f)的所有弧都是由第i层顶点指向第i1st层顶点ih(t)。3.2Dinic算法的基本思想及具体步骤16 山东科技大学本科毕业设计（论文）Dinic算法的基本思想是：从带发点v和收点v的容量网络D的任一st可行流f(例如零流)开始，构造D的关于f的分层增量网络AD(f)，在000AD(f)中找一条从v到v的增广路径，对f沿进行增广得到可行流0st011f，在AD(f)中删去上容量最小的弧，并相应修改AD(f)上弧的容量，00011得到网络AD(f)，然后可以在AD(f)中再找一条从v到v的增广路径，00st12对f沿进行增广得到可行流f，重复上述步骤依次得到D的可行流0012pf,f,,ff，因为AD(f)只有有限条弧，每次至少删去一条弧，所以00010在有限步后必然使余下的网络不再存在增广路径，v在AD(f)中的层数一t1定大于它在AD(f)中的层数；针对AD(f)重复上面的做法，在有限次增广01后一定会得到D的可行流f，使v在AD(f)中的层数更大。由于v的层数2t2t最多为n1（n是网络D的顶点数）。因此经过有限步后得到D的可行流f，kD中不再有f的增广链，这时f就是D的最大流。Dinic算法的具体步骤kk如下：步骤0：在网络D中任意取—个可行流f作为初始可行流，令0pp0,q0,ff。q0pp步骤1：(作分层增量网络)根据f作D的增量网络D(f)，再利用分层算qqp法构造分层增量网络AD(f)，如果在作分层增量网络时v得不到标号，则qtp算法结束，f就是D的最大流；否则转步骤2。q步骤2：(寻找增广路径)17 山东科技大学本科毕业设计（论文）①给发点v标号为[,v]，令is。sspp②如v在AD(f)没有出弧，转⑤；否则在AD(f)中任取v的一条出弧iqqi(v,v)，转③。ij③设v的标号为[,]，其中为v前面的节点，令min{,c}，v获iiiiijiijj得标号[,v]。ji④如果jt，转步骤3；否则令ij，转②。p⑤设v的标号为[,]，如果v，在AD(f)中删去v的所有入弧，所iiiisqip得的网络仍记为AD(f)，转②；否则置qq1，转步骤1。qp步骤3：（增广）从顶点v的标号中的第二个元素反向追踪，求出AD(f)的tqp增广路径，在AD(f)中把上的每条弧的容量c改为c，删去容量qijijtpp1p为0的弧，同时把流f增广为流f，把AD(f)中修改容量和删去弧后qqqp1p的网络记为AD(f)，置pp1，去掉网络AD(f)中所有顶点的标号，qq转步骤2。18 山东科技大学本科毕业设计（论文）第四章最大流问题的应用4.1铁路货运列车的最优调度4.1.1问题叙述某地区A、B两市之间要修建一铁路，依据地势、环境、需求等因素，修建铁路的预定方案如下：（1）铁路的运行方式为客车与货运兼营的双轨铁路（单向单轨），在其运行的列车有旅客快车和货运列车，由于客车的运行时间是国家铁路部门早已排定的，不可更改，且规定客运优于货运，即货车在每站开出前应先明确在其到达前方车站前不会被客车赶上，否则在该站等候不能开车。又若货车的前方到达站如无停车岔道，则货车从本站开出前应明确在其前面两站的行程中不会被客车赶上否则在本站等候不能开车，余类推。（2）铁路线内有A、B、C、D四个站，各站的岔道数为n5,n7,n9及n11.ABCD这些岔道可供调车用，亦可供停车卸货及洗刷车辆用。（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站开出的时刻于是显然有t""t"k1kkk1kk（2）若,与","有公共部分，则称,与","是相交的，kk1k1kk1k1否则成为不相交的。显然有当只,与","相交情况下客车才有可kk1k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+121 山东科技大学本科毕业设计（论文）站间客车在途中追上货车。于是有下列结论：若","在,内，即"及"，则在第k站与第k+1kk1kk1kkk1k1站必发生客车追上货车情况。否则在第k站与第k+1站之间不发生客车追上货车情况。（4）绘制网络图用（k，）表示第k站处于时刻的状态，如在=2.3在（k，2.6），kkk（k，6.6）状态开出的货车不会再途中被客车追上，则在图中表现为（k，2.6）及（k，6.6）两节点为起点的两条水平方向的直线弧，而在（k，4.6）状态下开出的货车会在途中被客车追上，则不能从该点引出水平方向的直线弧（图4.1.2），垂直方向的直线弧并联着同一车站的相邻状态。22 山东科技大学本科毕业设计（论文）图4.1.2上图中各弧旁的数字为容量，因铁路线是单向单轨的，故水平方向的弧容量为1，垂直方向的弧的容量为各站的岔道数量，在列出全部状态的网络图中求最大流，此最大流即为允许开出的最多货运列车数。4.1.3问题求解以货运列车的运行时间为基础绘制网络图。（1）令,,,为火车从某站开出或到达某站的时刻。依题意，若不ABCD受客车干扰则：23 山东科技大学本科毕业设计（论文）=0:00,2:00,4:00……A=5:00,7:00,9:00……B=9:00,11:00,13:00……C=16:00,18:00,20:00……D于是货车在相邻两站的运行时间为（若不受客车干扰）：6,1116,21,:0,5,2,7,4,9,,8,13,10,15,12,17,14,19,,18,23,20,15,22,27AB(25点即翌日1点，余类推)9,1319,23,:5,9,7,11,,11,15,13,17,15,19,17,21,,21,25,23,27,25,29,27,31BC11,1821,28,:9,6,,13,20,15,22,17,24,19,26,,23,30,25,32,27,34,29,36,31CD""""(2)令,,,为客车从某站开出或到达某站的时刻，依题意：ABCD"=2:00,7:00,12:00,17:00,22:00A"=5:00,10:00,15:00,20:00,25:00(即1:00)B"=7:00,12:00,17:00,22:00,27:00（即3:00）C"=12:00,17:00,22:00,27:00（即3:00），32:00（即8:00）D于是客车在相邻两站之间的运行时间为："",:2:00,5:00,7:00,10:00,12:00,15:00,17:00,20:00,22:00,25:00AB",:5:00,7:00,10:00,12:00,15:00,17:00,20:00,22:00,25:00,27:00BC24 山东科技大学本科毕业设计（论文）"",CD:7:00,12:00,12:00,17:00,17:00,22:00,22:00,27:00,27:00,32:00图4.1.3""（3）比较,及,,我们发现7:00,10:00在6:00,11:00之内;ABAB25 山东科技大学本科毕业设计（论文）17:00,20:00在16:00,21:00之内。这说明若A站在6:00及16:00开出两列货车，则该两列货车在到达B站前，必会被客车撞上。故这两次货运列车是不可行的。这表示在以货运列车的运行时刻为基础的网络图（图4.1.3）中为（A,6:00）及（A，16:00）两节点前未引出水平方向的直线弧。该图的各个节点中仅注明货运列车从该站开出或到达该站的时刻，站名省略了。""比较,及,,我们发现7:00,12：00在9:00,13:00之内；BCBC20:00,22:00在19:00,23:00之内，其在图4.1.3中的表示同前。""比较,与,,我们发现12:00,17:00在11：00,18:00之内；CDCD22:00,27:00在21:00,28:00之内，其在图3中的表示同前。（4）图4.1.3中各水平方向的直线弧的容量均为1。如前所述，它表示在该时间内，货车在相邻两站的行程中不会被客车追上，故可顺利地到达前方车站。垂直方向的直线弧的通量表示各站的岔道数。（5）做网络的发点v，并从v向A站的各状态节点作辅助弧，辅助弧的容ss量等于以A站的各状态节点为起点的各弧的容量的总和。作网络的收点v，t并从D站的各状态节点向v作辅助弧。辅助弧的容量等于以D站个状态节点t为终点的各弧的容量总和。（6）求图4.1.3所示容量网络的最大流Ⅰ）以零流f={0,0,…………0}为初始流，但图4.1.3的各弧旁省略了零流量。Ⅱ）以v表示图3中第i行第j列的节点。用Ford-Fulkerson标号法求得以ij下增广链并按值进行调整。*①v(0,)v(v,6)v(v,1)v(v,1)v(v,1)s1,1s1,21,11,31,21,41,326 山东科技大学本科毕业设计（论文）v(v,1)111,4②v(0,)v(v,6)v(v,1)v(v,1)v(v,1)s2,112,22,12,32,23,32,3v(v,1)v(v,1)13,43,313,4③v(0,)v(v,6)v(v,1)v(v,1)v(v,1)s3,1s3,23,14,23,24,34,2v(v,1)v(v,1)14,44,314,4④v(0,)v(v,6)v(v,1)v(v,1)v(v,1)s5,1s5,25,15,35,25,45,3v(v,1)1t5,4⑤v(0,)v(v,6)v(v,1)v(v,1)s6,1s6,26,16,36,2v(v,1)6,46,3v(v,1)1t6,4⑥v(0,)v(v,6)v(v,1)v(v,1)s7,1s7,27,17,37,2v(v,1)8,37,3v(v,1)v(v,1)18,48,3t8,4⑦v(0,)v(v,6)v(v,1)v(v,1)s8,1s8,28,18,28,2v(v,1)9,39,2v(v,1)v(v,1)v(v,1)19,49,29,49,3t9,4⑧v(0,)v(v,6)v(v,1)v(v,1)s10,1s10,210,110,310,2v(v,1)10,410,3v(v,1)1t10,427 山东科技大学本科毕业设计（论文）⑨v(0,)v(v,6)v(v,1)v(v,1)s11,1s11,211,111,311,2v(v,1)11,411,3v(v,1)1t11,4⑩v(0,)v(v,6)v(v,1)v(v,1)s12,1s,112,212,112,312,2v(v,1)12,412,3v(v,1)1t12,4以上10条增广链的调整量均为1。用它对初始流（零流）进行调整后，结果如图4.1.3所示。若对现行流继续标号，则只有A站的12个状态节点获得标号，即标号中断，不能延伸达v。故现行流即为最大流，其流量tv(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f111111111110s,(11,1)s,(12,1)结论在本问题所给条件下各车站一昼夜中能开出的最多货运列车数位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]BondyJA,MutryUSR.GraphTheorywithApplications.LondonandBasingstoke:MacMillanPress,1976[10]王树禾.图论及其算法.合肥：中国科学技术大学出版社，1990[11]戴一奇.图论及其应用.北京：水利电力出版社，1988[12]展丙军．运筹学．哈尔滨：哈尔滨地图出版社，2005[13]《运筹学》教材编写组.运筹学.第3版.北京:清华大学出版社，2004[14]胡运权．运筹学教程．北京：清华大学出版社，2007[15]谢金星，邢文顺.网络优化.北京：清华大学出版社，2000[16]李向东.运筹学：管理科学基础.北京：北京理工大学出版社，1990[17]李建中,骆吉洲(译).图论导引.北京：机械工业出版社，2006[18]王朝瑞.图论.北京：北京工业学院出版社，198731 山东科技大学本科毕业设计（论文）致谢辞本科毕业论文即将完成，回顾我大学四年的学习生涯，我得到了众多老师的教诲，同学的支持和帮助，再次对他们表示中心的感谢。首先感谢我的导师王朝阳老师，他生活中待人十分热情诚恳，给予我无微不至的关怀和照顾；工作中他治学严谨，思维活跃，在研究课题阅读文献、论文写作上给予我许多指导和帮助，使我对数学的认识有了很大的提高，我将铭记恩师的教诲、关心和帮助。还要感谢大学四年来所有的老师，为我们打下坚实的数学专业知识基础，在论文的写作过程中，还要感谢班内同学的帮助，他们在我完成论文的过程中，给我提了许多宝贵的建议，正是因为有了你们的支持和鼓励。此次毕业设计才能够顺利的完成。感谢所有给予我帮助和锻炼的人。最后，衷心感谢所有老师对我的栽培、支持和鼓励，感谢所有朋友的关心和帮助。向在百忙中抽出时间对此论文进行评审并提出宝贵意见的各位专家表示衷心地感谢！衷心祝愿母校山东科技大学明天更加美好！32 山东科技大学本科毕业设计（论文）附录1英文原文Maximumflowproblemintheintroduction,welistedoneofthelargestflowofgoodsdelivery.Ifthisissuealsoincludestheknownconditionsofdeliveryofeachunitwhilethecostofgoods,thenhowtotransport,togetthemosttraffic,andtransportationcoststoaminimum?Thisistheso-calledmaximumflowproblemminimumcost.Themaximumflowbasedonthedefinition,ifeachsideofafirst-priorityclaimtothenumberofc(e)(thattheedgecapacity)butalsohaveanotherweightsw(e)(thattheunitcostflow),andhasbeenseekingamaximumflowofthenetworkvalueofF,thentheminimumcostmaximumflowproblem,itisclearthefollowinglinearprogrammingmodelcanbeusedtodescribe:minw(e)f(e)eESatisfy0f(e)c(e)foralleEf(v)f(v)forallvVf(x)F(maximumflowconstraints)(Orf(y)F)AlgorithmideasSolvetheminimumcostmaximumflowproblem,therearetwogeneralways.Wayistouseamaximumflowalgorithmtocalculatethemaximumflow,andthenbasedonthecostside,checkwhetheritispossibletobalancetheflowbyadjustingtheflowside,sothattoreducethetotalcost?Aslongasthereisapossibility,onsuchadjustments.Afteradjustingforanewmaximumflow.Then,onthebasisofthenewflowtocontinuetocheckandadjust.Thisiterationcontinuesuntilnoadjustmentmaybe,theywillhavetheminimumcostmaximumflow.Thecharacteristicsofthislineofthoughtisto33 山东科技大学本科毕业设计（论文）maintainthefeasibilityoftheproblem(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),then34 山东科技大学本科毕业设计（论文）G"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,thuslabelinglawcannotbedirectlyappliedtofindxtoyoftheshortestpath,usingtherightofothernegativesidecomputingnetworkapproachtotheshortestpathxtoytofindtheshortestpath,willgreatlyreducethecomputationalefficiency.Inordertostillusethelabelingmethodtocalculatetheshortestpath,eachflowsetupbythenetworktoachievetheshortestpath,thenetworkGcanbetherightofw(e)anamendmenttodosobythestreamtobuildthenetworkwillnotbeanegativerightside,andguaranteetheshortestpathdoesnotchange.Thismodifiedmethoddescribedbelow.Whentheflowvalueiszero,thefirstbuiltbytheshortestpathforflownetwork,theresultofnon-negativerightside,ofcourse,canbeusedtocalculatelabelinglaw.InordertoincreaseflownetworkaftertheestablishmentofanegativetimeisnotrightsideoftheapproachtakenistohavestreamGedge(f(e)>0)therighttow(e)amendmentto0.Tothisend,eachtimeaflownetworkobtainedbytheshortestpath,thefollowingcomputingGintherightsideofthenew35 山东科技大学本科毕业设计（论文）w""(u,v):w""(u,v)L(u)L(v)w(u,v)(*)WhereL(u),L(v)-calculationofG"oftheshortestpathxtoywhenuandvthevalueofthelabel.Forthefirsttimeiftheshortestpath(u,v)istheflowpathbytheedge,then,accordingtotheshortestpathalgorithmmusthaveL(v)L(u)w"(u,v)L(u)w(u,v),substitutinginto(*)typemustw""(u,v)0.If(u,v)ratherthanbythesideofflowpath,itmusthave:L(v)L(u)w(u,v)Intothe(*)-type,therew(u,v)0.Showsthatthefirstamendmenttow(e),againsteitherside,therearew(e)0,andastreamside(bysidechainflow),therewillbew(e）0.Calculatedaftereachiteration,iff(u,v)0,bytheneedtoestablishthenetworkflow(u,v)edge,edgeweightsw"(u,v)w(u,v)0thatis,therightwillnotbeanegativeside.Inaddition,thecalculationofeachiterationwith(*)fixesallthew(e),itisnotdifficulttoprovethattoeachpathxtoy,itsallthesametoincreasethepathlengthL(x)L(y).Therefore,xandywillnotbetheshortestpathtow(e)theamendmentchanges.36 山东科技大学本科毕业设计（论文）附录2中文译文在介绍最大流问题时，我们列举了一个最大物资输送流问题。如果这个问题的已知条件还包括每条边运送单位物资的费用，那么怎样运送，才能得到最大运输量，并且输送费用最少,这便是所谓最小费用最大流问题。在最大流的有关定义的基础上，若每条有向边除权数c(e)（表示边容量）外还有另外一个权数w(e)（表示单位流所需费用），并且已求得该网络的最大流值为F，那么最小费用最大流问题，显然可用以下线性模型加以描述：minw(e)f(e)eE满足0f(e)c(e)，对一切eEf(e)f(e)，对一切vVf(x)F（最大流约束）（或f(y)F)解决最小费用最大流问题，一般有两条途径。一条途径是先用最大流算法算出最大流，然后根据边费用，检查是否有可能在流量平衡的前提下通过调整边流量，使总费用得以减少。只要有这个可能，就进行这样的调整。调整后，得到一个新的最大流。然后，在这个新流的基础上继续检查，调整。这样迭代下去，直至无调整可能，便得到最小费用最大流。这一思路的特点是保持问题的可行性（始终保持最大流），向最优推进。另一条解决途径和前面介绍的最大流算法思路相类似，一般首先给出零流作为初始流。这个流的费用为零，当然是最小费用的。然后寻找一条源点至汇点的增流链，但要求这条增流链必须是所有增流链中费用最小的一条。如果能找出增流链，则在增流链上增流，得出新流。将这个流做为初始流看待，继续寻找增流链增流。这样迭代下去，直至找不出增流链，这时的流即为37 山东科技大学本科毕业设计（论文）最小费用最大流。这一算法思路的特点是保持解的最优性（每次得到的新流都是费用最小的流），而逐渐向可行解近（直至最大流时才是一个可行解）。由于第二种算法和已介绍的最大流算法接近，且算法中寻找最小费用增流链，可以转化为一个寻求源点至汇点的最短路径问题，所以这里介绍这一算法。在这一算法中，为了寻求最小费用的增流链，对每一当前流，需建立伴随这一网络流的增流网络。例如图1网络G是具有最小费用的流，边旁参数为c(e),f(e),v(e)，而图2即为该网络流的增流网络G′。增流网络的顶点和原网络相同。按以下原则建立增流网络的边：若G中边(u,v)流量未饱，即f(u,v)e(u,v)，则G"中建边(u,v)，赋权w(u,v)"w(u,v)；若G中边(u,v)已有流量，即f(u,v)0，则G"中建边(u,v)，赋权w(u,v)"w(u,v)。建立增流网络后，即可在此网络上求源点至汇点的最短路径，以此决定增流路径，然后在原网络上循此路径增流。这里，运用的仍然是最大流算法的增流原理，唯必须选定最小费用的增流链增流。计算中有一个问题需要解决。这就是增流网络G"中有负权边，因而不能直接应用标号法来寻找x至y的最短路径，采用其它计算有负权边的网络最短路径的方法来寻找x至y的最短路径，将大大降低计算效率。为了仍然采用标号法计算最短路径，在每次建立增流网络求得最短路径后,可将网络G的权w(e)做一次修正，使再建的增流网络不会出现负权边，并保证最短路径不至于因此而改变。下面介绍这种修改方法。当流值为零，第一次建增流网络求最短路径时，因无负权边，当然可以采用标号法进行计算。为了使以后建立增流网络时不出现负权边，采取的办法是将G中有流边f(e)0的权w(e)修正为0。为此，每次在增流网络上求得最短路径38 山东科技大学本科毕业设计（论文）后，以下式计算G中新的边权w""(u,v):w""(u,v)L(u)L(v)w(u,v)(*)式中L(u),L(v)--计算G"的x至y最短路径时u和v的标号值。第一次求最短径时如果(u,v)是增流路径上的边，则据最短路径算法一定有L(v)L(u)w"(u,v)L(u)w(u,v),代入(*)式必有w(u,v)0.。如果(u,v)不是增流路径上的边，则一定有：L(v)L(u)w(u,v)，代入(*)式则有(u,v)。可见第一次修正w(e),后，对任一边，皆有w(e)0，且有流的边（增流链上的边），一定有w(e）0。以后每次迭代计算若f(u,v)0，增流网络需建立(v,u)边，边权数w"(u,v)w(u,v)0，即不会再出现负权边。此外，每次迭代计算用(*)式修正一切w(e)，不难证明对每一条x至y的路径而言，其路径长度都同样增加L(x)L(y)。因此，x至y的最短路径不会因对w(e)的修正而发生变化。39'