1、1 毕业论文（设计）任务书 数学与应用数学 网络最大流问题算法研究 一 目的 : 近年来网络流问题在实践中的应用越来越广泛 , 其中网络最大流算法问题更是得到了许多学者的青睐 , 研究成果更是层出不穷 , 算法结构也是越来越趋向成熟 , 其中的 Ford-Fulkerson 标号算法是很多算法的基础 , 本文主要介绍标号算法的标号 步骤和应用 实例 , 也简要介绍了现有的几个优秀算法 . 最 后给出了一个新算法的实例 . 本文的主要目的是让 对基础的 最大流算法 -标号算法 进行总结和分析 , 给出的 matlab 程序 实现 可以让 我们更好 了解 标号算法的 标 号过程 , 在实践中我们通
2、过比较算法的时间复杂度来比较算法的优秀与否 , 这离不开程序的帮助 . 本文的最终目的是在着重介绍标号算法的基础上深刻认识最大流问题的理论基础 , 并根据基础开发出新的算法 . 二任务 : 对网络最大流算法有深刻了解 , 并着重掌握标号算法在实践中的应用 . 三计划进度 : 准备工作 : 1根据指导老师研究方向 , 公布论文题目 , 选择确定指导老师 ; 2确定论文题目 , 查找相关资料 ; 3寒假期间阅读资料 . 工作步骤 : 第 一 周 : 寒假回学校 , 学生分别向指导教师汇报期间材料收集、阅读情况 . 第 二 周 : 学生阅读文献、翻译英文资料 . 第 三 周 : 上交英文翻译 , 指
3、导教师指导学生撰写文献综述 . 第 四 周 : 上交文献综述 . 第 五 周 第 六 周 : 学生开始动笔撰写论文 , 指导教师随时检查学生的工作情况 , 随时 解答学生在工作中出现的问题 . 第 七 周 : 学生上交论文初稿 . 第 八 周 : 指导教师帮助学生修改初稿 , 反复修改毕业论文 . 第 九 周 : 整理论文资料 , 论文定稿 . 第十周 : 学生准备答辩 . 2 四措施 : 在老师指导下 , 通过到图书馆、上网等查阅收集资料 , 参考相关内容 . 五预期结果 : 1 了解了网络最大问题的起源和发展 . 2 通过资料 , 了解到很多网络最大流算法新算法 . 3 基本掌握网络最大流
4、算法中的标号算法 , 并对的算法的复杂度进行比较 , 了解更多算法的优劣 . 参考资料 : 1 廖敏 . 运筹学基础与应用 M. 南京 : 南京大学出版社 , 2009: 190-197. 2 弗雷德里克 S希利尔 , 杰拉尔德 J利伯曼（胡运权等译） . 运筹学导论 M. 北京 :清华大学出版社 , 2007 : 375-381. 3 L R Ford, D R Fulkerson. Maximum flow through a network. Canadian Journal of Math, 1956, 8(5): 399-404. 4 王志强 . 网络最大流的新算法 D. 陕西 :
5、宝鸡文理学院 , 2009. 5 张 宪超 , 陈国良 , 万颖瑜 等 . 网络最大流问题研究进展 J. 计算机研究与发展学报 , 2003, 40(9): 1281-1292. 6 A.V. Goldberg and R.E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 1988, 35: 921-940. 7 赵可培 . 运筹学 M. 第二版 . 上海 : 上海财经出版社 , 2008: 243-249. 8 R. K. Ahuja and J.B. Orlin. A fast and si
6、mple algorithm for the maximum flow problem. Oper. Res. 1989, 37: 748-759. 9 Maria Grazia Scutella. A note on the parametric maximum flow problem and some related reoptimization issues. Ann Oper Res, 2007, 150: 231-244. 10 Robert E. TARJAN. Algorithms for maximum network flow. Mathematical Programming Study, 1986, 26: 1-11.
