发布时间 : 星期四 文章信息与计算科学毕业论文最大流问题及应用更新完毕开始阅读
山东科技大学本科毕业设计（论文）
⑨vs(0,?) v11,1(vs,6) v11,2(v11,1,1) v11,3(v11,2,1)
v11,4(v11,3,1)
vt(v11,4,1) ??1 ⑩vs(0,?) v12,1(vs,1,6) v12,2(v12,1,1) v12,3(v12,2,1)
v12,4(v12,3,1)
vt(v12,4,1) ??1 以上10条增广链的调整量均为??1。用它对初始流（零流）进行调整后，结果如图4.1.3所示。若对现行流继续标号，则只有A站的12个状态节点获得标号，即标号中断，不能延伸达vt。故现行流即为最大流，其流量
v(f)?fs,(1,1)?fs,(2,1)?fs,(3,1)?fs,(5,1)?fs,(6,1)?fs,(7,1)?fs,(8,1)?fs,(10,1)?fs,(11,1)?fs,(12,1)?1?1?1?1?1?1?1?1?1?1?10
结论 在本问题所给条件下各车站一昼夜中能开出的最多货运列车数位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] Bondy JA, Mutry USR. Graph Theory with Applications. London and Basingstoke: MacMillan Press, 1976
[10] 王树禾. 图论及其算法. 合肥：中国科学技术大学出版社，1990 [11] 戴一奇. 图论及其应用. 北京：水利电力出版社，1988 [12] 展丙军．运筹学．哈尔滨：哈尔滨地图出版社，2005
[13] 《运筹学》教材编写组. 运筹学. 第3版. 北京: 清华大学出版社，2004 [14] 胡运权．运筹学教程．北京：清华大学出版社，2007 [15] 谢金星，邢文顺. 网络优化. 北京：清华大学出版社，2000 [16] 李向东. 运筹学：管理科学基础. 北京：北京理工大学出版社，1990 [17] 李建中, 骆吉洲(译). 图论导引. 北京：机械工业出版社，2006 [18] 王朝瑞. 图论. 北京：北京工业学院出版社，1987
31