【33页】毕业论文_最大流问题及其应用源文档 ㊣ 精品文档 值得下载

可给我们的生活带来很大方便。

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

为了更加明确的展现最大流问题在生产生活中的应用，本文例举了个实际生活中的问题铁路货运列车的最优调度来突出研究最大流问题的重要意义，此实例需要求解的是在定的限制条件下，设计出个在昼夜间能通过段铁路的最多的货运列车数量并列出每辆列车开出的时刻表。

在此实例中，通过从实际问题中抽象出网络图，将实际问题转化为最大流问题并应用图的性质和标号法的算法依据，最终解决了问题。

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

关键词图网络流最大流，第章前言前言最大流问题的研究内容及背景最大流问题的发展状况选题的意义第二章预备知识图论网络的基本概念最大流问题核心依据最大流最小割定理第三章最大流问题的几种算法标号法算法标号法算法思想标号法的具体步骤修正算法算法增量网络与分层增量网络算法的基本思想及具体步骤第四章最大流问题的应用铁路货运列车的最优调度问题叙述问题分析问题求解问题总结第五章结论参考文献指导老师简介致谢第章前言第章前言前言最大流问题的研究内容及背景最大流问题是类网络分析问题，它是指在定的条件下，要求流过网络的物流能量流信息流等流量为最大的问题。

比如交通运输网络中的人流车流物流供水网络中的水流金融系统中的现金流通信系统中的信息流等等，都属于最大流问题参见文献。

在对最大流问题进行研究的过程中，人们建立了最大流问题较为完善的理论，同时开发了大量的算法，如标号法修正算法算法等等，这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用。

近年来，随着计算机科学技术和网络的快速发展，网络最大流问题得到了更深入的研究，并极大地推动了最大流问题的研究进展参见文献。

以图论理论基础来研究最大流问题是运筹学中的种重要方法。

在自然界和人类社会的实际生活中，用图形来描述些对象或事物之间具有种特定关系常常感到特别方便，例如用工艺流程图来描述项工程中各工序之间的先后关系用网络图来描述通讯系统各小通讯站之间信息传递关系用交通图来描述地区内各城市之间的铁路连接关系等等参见文献。

图论是组合数学的个分支，与其他的数学分支如群论矩阵论概率论拓扑学数值分析有着密切的联系，其应用十分广泛，是近年来较为活跃的数学分支之参见文献。

它的产生和发展历经了二百多年的历史，瑞士数学家欧拉在年解决了当时颇为有名的个数学难题，即哥尼斯城堡七桥问题，从而使他成了图论和拓扑学的创始人参见文献。

早期的图论与数学游戏有密切的联系，如哈密尔顿的周游世界问题迷宫问题博奕问题以及棋盘上马的行走路线之类的难题等吸引了许多学者。

世纪后，图论的应用渗透到许多其他学科领域，如物理化学信息学运筹学博奕论计算机网络社会学以及集合论矩阵论等。

从世纪年代以后，由于计算机的迅速发展，有力地推动了图论的发展，使图论成为数学领域中发展最快的分支之，也成为现代研究最大流问题的个重要工具。

最大流问题的发展状况第章前言最大流问题是早期的线性网络最优化的个例子。

最早研究这类问题的是美国学者希奇柯克，年他在研究生产组织和铁路运输方面的线性规划问题时提出运输问题的基本模型后来柯普曼在年地提出运输问题并详细地对此问题加以讨论从上世纪年代早期开始，康脱洛维奇围绕着运输问题作了大量的研究，因此运输问题又称为希奇柯克问题或康脱洛维奇问题。

与般线性规划问题不同，它的约束方程组的系数矩阵具有特殊的结构，这就需要采用不同的甚至更为简便的求解方法来解决这种在实际工作中经常遇到的问题。

运输问题不仅代表了物资合理调运车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题。

后来把这种解决线性网络最优化的方法与最大流问题相结合，同时推动了最大流问题的研究与进展。

国外学者从算法角度考虑，对于最大流问题的求解提出了很多可行的解法，如表上作业法图上求解法以及应用计算机实现的启发式多种算法等，其基本上可以总结如下表上作业法是解决般最大流问题最常用的解法，因其求解工作均在运输表上进行而得名。

它是种迭代算法，迭代步骤为先按种规则找出个初始解再对现行解作最优性判别若该解不是最优解，就在表上对它进行调整改进，从而得出个新解，再重复判别改进的过程，直至得到最大流问题的最优解为止。

最短路线法。

当已知物资从出发地运往目的地，可有多条运输路线供选择，这时可构造费用网络图，用求最短路线的方法，选择最优的运输方案，需画出各种运输路线的线路图及图上每条边或弧上的距离或费用也可以用邻接矩阵表示，然后用标号法或邻接矩阵法求最优运输路线。

国内学者对于最大流问题的研究主要可以分为三个角度是在国外算法的基础上，对最大流问题算法的改进研究二是从目标函数的角度，在最大流问题中有时要同时考虑成本最小运输过程中货物损坏率最低以及单位运价变化的调整等多个目标从约束函数的角度，有研究供给量和需求量在个区间变化的不确定型运输问题有时间窗口的运输问题等。

选题的意义在日常生活和生产中我们时常遇到些网络图。

如交通图旅游线路图管道系第章前言统图等。

在优化理论中所谓图就是上述各类图的抽象和概括，用图来描述我们的研究对象，以及这些对象之间的相互联系。

例如旅游管理网络通信交通运输金融系统等问题都可以用网络图来描述。

最大流问题就是就是在个有向连通图中，指定点为发点，另点为收点，其余的点为中间点，在所有的点都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流。

本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题，提高生产的有效性和生产设备的有效利用率。

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

第二章预备知识第二章预备知识图论所谓图论，顾名思义是研究图的理论。

图论中的图是由许多实际问题经过抽象而得到，由点及点与点之间的连线构成，它可以反映些对象之间的关系。

图形中的点表示对象如工序选手通讯站等，两点之间的有向或无向连线表示对象之间具有种特定的关系如先后关系胜负关系传递关系连接关系等参见文献。

物质结构电路网络城市规划交通运输信息传递物资调配等都可以用点和线连接起来的图进行模拟。

这里所研究的图与平面几何中的图不同，这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的，相对位置如何，都是无关紧要的参见文献。

定义两点之间不带箭头的连线称为边，条连接，的边记为或表示边的集合。

定义两点之间带箭头的连线称为弧，条以为始点为终点的弧记为表示弧的集合。

定义由点和边构成的图为无向图，记为，由点和弧构成的图为有向图，记为，定义在无向图中，若存在个点边交错序列，满足，，则称之为条联结和的链，记为，，若，则称之为圈。

定义在有向图中，若存在个点弧交错序列，，弧的始点为，终点为，记为，，则称这条点弧的交错序列为从到的条路，记为，。

若路的第点和最后点相同，则称之为回路。

链与路中的点互不相同，则为初等链路，以后说到的链与路，均指初等链路。

定义如果对于个无向图的每条边，相应有个权数，则称这样的图为第二章预备知识赋权图，记为。

定义如果对于个有向图的每条弧，相应有个权数，称这样的图为网络，记为。

般在网络图中，每条弧的权，不是表示弧的长度而是表示弧的宽度，即代表距离费用通过能力容量等等。

例如，公路运输网络中路面的宽度或管道输送网络中管道的直径，它是单位时间内允许通过实体的数量。

所以将弧权称为弧的容量，网络称为容量网络参见文献。

定义在图中，若任何两个点之间至少有条链或条路，则称是连通图，否则，称为不连通图。

网络的基本概念假设要把起点的批流转物运送到终点去，在每弧上通过流转物的总量不能超过这条弧上的容量，问题是应该怎样安排运送，才能使从起点运送至终点的总量达到最大，这样的问题就称为网络上最大流问题，最大流问题是网络流问题中的个非常重要的研究内容参见文献，以下讨论的网络均为只有个发点和个收点的容量网络。

定义对任意容量网络中的弧，有流量，称集合为网络上的个流，称满足下列条件的流为可行流容量限制条件对中每条弧有平衡条件对中间点，有即中间点的物资的输入量与输出量相等。

对收发点，有即从点发出的物资总量等于点入的量，为网络流的总流量。

在容量网络中表示弧，的容量，令为通过弧，的流第二章预备知识量，显然有，流应遵守点守恒规则，即，称为守恒方程。

定义对任意容量网络，寻求可行流使得流量取得极大值，这个可行流便称为最大流。

定义在容量网络中，若为网络中从发点到收点的条路，给定向为从到，上的弧凡与同向称为前向弧。

凡与反向称为后向弧，其集合分别用和表示，是个可行流，如果满足则称为从到的关于的增广链。

定义在容量网络中，若有弧集为的子集，将分为两个子图其顶点集合分别记，分别属于满足，不连通为的真子集，而，仍连通，则称为的割集，记，。

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