发布时间 : 星期二 文章信息与计算科学毕业论文最大流问题及应用更新完毕开始阅读
目录
第一章 绪论 ................................................................................................................. 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
山东科技大学本科毕业设计（论文）
第一章 绪论
1.1 最大流问题的研究内容及背景
最大流问题也就是是指网络分析问题的一类，它是在指定的条件下,要求通过网络的物流、能量流、信息流等流量为最大的问题。比如交通运输网络中的人流、车流、物流,供水网络中的水流、金融系统中的现金流通信系统中的信息流等等，都属于最大流问题。
图论是组合数 学的—个分支与其他的数学分支如群论、矩阵论、概率论、拓扑学、数值分析有着密切的联系而且其应用十分广泛，是近年来较为活跃的数学分支之一。它的产生和 发展历经了二百多年的历史，瑞士数学家欧拉(L．Euler)在1736年解决了当时颇为有名的一个数学难题，即哥尼斯城堡七桥问题，从而使他成了图论和拓扑学的创始人。早期的图论与数学游戏有密切的联系，如哈密尔顿 的周游世界问题、迷宫问题、博奕问题以及棋盘上马的行走路线之类的难题等吸引了许多学者。20世纪后，图论的应用渗透到许多其他学科领域，如物理、化学、信息学、运筹学、博奕论、计算机网络、社会学以及集合论、矩阵论等。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，使图论成为数学领域中发展最快的分支之一，也成为现代研究最大流问题的一个重要工具。
1.2 最大流问题的发展状况
最大流问题是早期的线性网络最优化的一个例子。最早研究这类问题的是美国学者希奇柯克（Hitchcock），1941年他在研究生产组织和铁路运
1
山东科技大学本科毕业设计（论文）
输方面的线性规划问题时提出运输问题的基本模 型；后来柯普曼（Koopmans）在1947年独立地提出运输问题并详细地对此问题加以讨论；从上世纪40年代早期开始，康脱洛维奇（Kantorovich）围绕着运输问题作了大量的研究，因此运输问题又称为希奇柯克问题或康脱洛维奇问题。与 一般线性规划问题不同，它的约束方程组的系数矩阵具有特殊的结构，这就需要采用不同的甚至更为简便的求解方法来解决这种在实际工作中经常遇到的问题。运输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题。后来把这种解决线性网络最优化的方法与最大流问题相结合，同时推动了最大流问题的发展。
最大流问题就是就是在一个有向连通图中，指定一点为发点，另一点 为收点，其余的点为中间点，在所有的点 都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流。本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题，提高生产的有效性和生产设备的有效利用率。
最大流问题应用极为广泛，很多生活中的问题都可转化为最大流问题，其难点是从实际中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。
1.3 选题的意义
在日常生活和生产中我们时常遇到一些网络图。如交通图、旅游线路图、管道系统图等。在优化理论 中所谓图就是上述各类图的抽象和概括，用图来描述我们的研究对象，以及这些对象之间的相互联系。例如旅游管理、网络通信、交通运输、金融系统等问题都可以用网络图来描述。
最大流问题就是就是在一个有向连通图中，指定一点为发点，另一点
2
山东科技大学本科毕业设计（论文）
为收点，其余的点为中间点，在所有的点 都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流。本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题，提高生产的有效性和生产设备的有效利用率。
最大流问题应用极为广泛，很多生活中的问题都可转化为最大流问题，其难点是从实际中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。
3