题，它是指在定的条件下,要求流过网络的物流能量流信息流等流量为最大的问题。比如交通运输网络中的人流车流物流供水网络中的水流金融系统中的现金流通信系统中的信息流等等，都属于最大流问题参见文献。在对最大流问题进行研究的过程中，人们建立了最大流问题较为完善的理论，同时开发了大量的算法，如标号法修正算法算法等等，这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用。近年来，随着计算机科学技术和网络的快速发展，网络最大流问题得到了更深入的研究，并极大地推动了最大流问题的研究进展参见文献。以图论理论基础来研究最大流问题是运筹学中的种重要方法。在自然界和人类社会的实际生活中，用图形来描述些对象或事物之间具有种特定关系常常感到特别方便，例如用工艺流程图来描述项工程中各工序之间的先后关系用网络图来描述通讯系统各小通讯站之间信息传递关系用交通图来描述地区内各城市之间的铁路连接关系等等参见文献。图论是组合数学的个分支，与其他的数学分支如群论矩阵论概率论拓扑学数值分析有着密切的联系，其应用十分广泛，是近年来较为活跃的数学分支之参见文献。它的产生和发展历经了二百多年的历史，瑞士数学家欧拉在年解决了当时颇为有名的个数学难题，即哥尼斯城堡七桥问题，从而使他成了图论和拓扑学的创始人参见文献。早期的图论与数学游戏有密切的联系，如哈密尔顿的周游世界问题迷宫问题博奕问题以及棋盘上马的行走路线之类的难题等吸引了许多学者。世纪后，图论的应用渗透到许多其他学科领域，如物理化学信息学运筹学博奕论计算机网络社会学以及集合论矩阵论等。从世纪年代以后，由于计算机的迅速发展，有力地推动了图论的发展，使图论成为数学领域中发展最快的分支之，也成为现代研究最大流问题的个重要工具。最大流问题的发展状况第章前言最大流问题是早期的线性网络最优化的个例子。最早研究这类问题的是美国学者希奇柯克，年他在研究生产组织和铁路运输方面的线性规划问题时提出运输问题的基本模型后来柯普曼在年地提出运输问题并详细地对此问题加以讨论从上世纪年代早期开始，康脱洛维奇围绕着运输问题作了大量的研究，因此运输问题又称为希奇柯克问题或康脱洛维奇问题。与般线性规划问题不同，它的约束方程组的系数矩阵具有特殊的结构，这就需要采用不同的甚至更为简便的求解方法来解决这种在实际工作中经常遇到的问题。运输问题不仅代表了物资合理调运车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题。后来把这种解决线性网络最优化的方法与最大流问题相结合，同时推动了最大流问题的研究与进展。国外学者从算法角度考虑，对于最大流问题的求解提出了很多可行的解法，如表上作业法图上求解法以及应用计算机实现的启发式多种算法等，其基本上可以总结如下表上作业法是解决般最大流问题最常用的解法，因其求解工作均在运输表上进行而得名。它是种迭代算法，迭代步骤为先按种规则找出个初始解再对现行解作最优性判别若该解不是最优解，就在表上对它进行调整改进，从而得出个新解，再重复判别改进的过程，直至得到最大流问题的最优解为止。最短路线法。当已知物资从出发地运往目的地，可有多条运输路线供选择，这时可构造费用网络图，用求最短路线的方法，选择最优的运输方案，需画出各种运输路线的线路图及图上每条边或弧上的距离或费用也可以用邻接矩阵表示，然后用标号法或邻接矩阵法求最优运输路线。国内学者对于最大流问题的研究主要可以分为三个角度是在国外算法的基础上，对最大流问题算法的改进研究二是从目标函数的角度，在最大流问题中有时要同时考虑成本最小运输过程中货物损坏率最低以及单位运价变化的调整等多个目标从约束函数的角度，有研究供给量和需求量在个区间变化的不确定型运输问题有时间窗口的运输问题等。选题的意义在日常生活和生产中我们时常遇到些网络图。如交通图旅游线路图管道系第章前言统图等。在优化理论中所谓图就是上述各类图的抽象和概括，用图来描述我们的研究对象，以及这些对象之间的相互联系。例如旅游管理网络通信交通运输金融系统等问题都可以用网络图来描述。最大流问题就是就是在个有向连通图中，指定点为发点，另点为收点，其余的点为中间点，在所有的点都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流车在两站之间的运行时间即可控制货车的开出时间，其实不然，此问题是在追赶问题的基础上求最多可开出的货车辆数，我们把该问题转化成为最大流问题，应用标号法解决了这问题。通过对算法的分析求解制定出了货车运行的最大数量并列出货车运行时间表，可见最大流算法的有效性和实用性。第五章结论第五章结论本课题主要以图论的知识为理论基础，来讨论最大流问题。最大流问题是类应用极为广泛的问题，世纪年代福特富克逊建立的网络流理论，是网络应用的重要组成部分。最大流问题的核心依据是最大流最小割定理，在这个定理的基础上，解决最大流问题的几种算法有标号法修正算法算法等本论文分别介绍了这几种算法，并举实例说明各个算法具体的解题过程，各算法的优劣各不相同，标号法是最原始的算法，由和提出，和针对该算法增广路径选取的任意性这缺点对它做了修正算法产生了修正算法，而算法则兼取前两种算法的优点，是这三种算法中最有效的算法。最大流问题是网络流问题的个重要的内容，研究最大流问题并将其应用到工业工程商业农业，运输业等领域可给我们的生活带来很大方便。在很多情况下，实际遇到的问题可能是很复杂的，甚至是无从下手，不过通过分析建立模型，如果可以建立成个网络图，转化成为最大流问题，就会找到相应的解决方法。由此，最大流问题在现实生活中是非常重要的。参考文献参考文献熊义杰运筹学教程天津国防工业出版社，徐俊明图论及其应用合肥中国科学技术大学出版社，卢开澄图论及其应用北京清华大学出版社，吴育华，杜纲管理科学基础天津天津大学出版社，谢政，李建平网络算法与复杂性理论北京国防科技大学出版社，刁在筠，郑汉鼎，刘家壮，刘桂真运筹学第版北京高等教育出版社，田丰，马仲蕃图与网络流理论北京科学出版社，卜月华，吴建专图论及其应用南京东南大学出版社,王树禾图论及其算法合肥中国科学技术大学出版社，戴奇图论及其应用北京水利电力出版社，展丙军运筹学哈尔滨哈尔滨地图出版社，运筹学教材编写组运筹学第版北京清华大学出版社，胡运权运筹学教程北京清华大学出版社，谢金星，邢文顺网络优化北京清华大学出版社，李向东运筹学管理科学基础北京北京理工大学出版社，李建中,骆吉洲译图论导引北京机械工业出版社，王朝瑞图论北京北京工业学院出版社，谢凡荣运输网络中求最小费用最大流的个算法运筹与管理韩明亮求解最小费用最大流问题的种方法中国民航学院学报指导老师简介指导老师简介张中旭，男，岁，山东人。年毕业于云南大学数学与统计学院运筹学与控制论专业，获理学硕士学位，现西南林业大学理学院数学系任教，主讲高等数学，概率论与数理统计运筹学组合数学等课程。致谢致谢本科毕业论文即将完成，回顾大学四年的学习生涯，我得到了众多老师的教诲，同学的支持和帮助，再次对他她们表示中心的感谢。首先感谢我的导师张中旭老师，她生活中待人热情诚恳，给予我无微不至的关怀和照顾工作中她治学严谨，思维活跃，在研究课题阅读文献论文写作上给予我许多指导和帮助，使我对数学的认识有了很大的提高，我将铭记恩师的教诲关心和帮助。还要感谢大学四年来所有的老师，为我们打下数学专业知识的基础，在论文的写作过程中，感谢班内同学的帮助，他们在我完成论文的过程中，给我提了很多宝贵的建议，正是因为有了你们的支持和鼓励。此次毕业设计才会顺利完成。感谢父母对我二十多年来辛勤的养育,并让我获取了定的知识并最终走向社会,为社会贡献自己,感谢所有给予我帮助和锻炼的人，祝愿他们合家欢乐，身体健康,最后，衷心感谢所有老师对我的栽培支持和鼓励，感谢所有朋友的关心和帮助。向在百忙中抽出时间对此论文进行评审并提出宝贵意见的各位专家表示衷心地感谢,衷心祝愿母校西南林业大学基础部的明天更加美好,最大流问题及其应用西南林业大学理学院，中国云南昆明，摘要网络流问题是运筹学的重要研究课题。最大流问题是网络流问题的个重要的内容，应用极为广泛。研究最大流问题并将其应用到工业工程商业农业，运输业等领域可给我们的生活带来很大方便。本论文讨论最大流问题，综述图论的历史背景基本概念和基本知识阐述网络的基本概念介绍最大流问题的核心依据最大流最小割定理综述解决最大流问题的几种算法标号法修正算法算法，并比较各算法在解决不同问题中的优劣。为了更加明确的展现最大流问题在生产生活中的应用，本文例举了个实际生活中的问题铁路货运列车的最优调度来突出研究最大流问题的重要意义，此实例需要求解的是在定的限制条件下，设计出个在昼夜间能通过段铁路的最多的货运列车数量并列出每辆列车开出的时刻表。在此实例中，通过从实际问题中抽象出网络图，将实际问题转化为最大流问题并应用图的性质和标号法的算法依据，最终解决了问题。本文采用理论与实例相结合，重在应用理论依据解决实际问题，具有较强的实践性，突出的是应用。关键词图网络流最大流,目录第章前言前言最大流问题的研究内容及背景最大流问题的发展状况选题的意义第二章预备知识图论网络的基本概念最大流问题核心依据最大流最小割定理第三章最大流问题的几种算法标号法算法标号法算法思想标号法的具体步骤修正算法算法增量网络与分层增量网络算法的基本思想及具体步骤第四章最大流问题的应用铁路货运列车的最优调度问题叙述问题分析问题求解问题总结第五章结论参考文献指导老师简介致谢第章前言第章前言前言最大流问题的研究内容及背景最大流问题是类网络分析问题，它是指在定的条件下,要求流过网络的物流能量流信息流等流量为最大的问题。比如交通运输网络中的人流车流物流供水网络中的水流金融系统中的现金流通信系统中的信息流等等，都属于最大流问题参见文献。在对最大流问题进行研究的过程中，人们建立了最大流问题较为完善的理论，同时开发了大量的算法，如标号法修正算法算法等等，这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用。近年来，随着计算机科学技术和网络的快速发展，网络最大流问题得到了更深入的研究，并极大地推动了最大流问题的研究进展参见文献。以图论