1. 研究目的与意义
最大流问题是指在一定条件下，要求流过网络的物流、能量流、信息流等流量为最大的问题。最大流问题已有40多年的研究历史，在这段时期，人们建立了最大流问题较为完善的理论，同时开发了大量的算法。如Ford和Fulkson增截轨算法、重标号算法等等，这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用。 近年来，随着计算机科学技术和网络的快速发展，网络最大流问题得到了更深入的研究。最大流问题作为特殊的线性规划问题远比一般线性规划问题容易解决，发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决。因此，关于网络最大流问题的研究具有十分重要的理论意义和实用价值。 |
2. 研究内容和预期目标
求最大流的标号法，标号法思想是：先找一个可行流。对于一个可行流，经过标号过程得到从发点vs到收点vt的增广链；经过调整过程沿增广链增加可行流的流量，得新的可行流。重复这一过程，直到可行流无增广链，得到最大流。
标号过程:
(1)给vs标号(-, ∞)，vs成为已标号未检查的点，其余都是未标号点。
3. 国内外研究现状
最大流的应用一直是十分有意义的研究工作。网络流问题的研究者和具体问题的工程师从不同的角度充实着这方面的研究。无论从线性规划还是从组合优化角度来看， 最大流问题都是一个已经研究得比较深入的问题，存在大量优秀的算法。许多研究者也已开发出大量的代码。因此，对许多实际应用问题，如果能找到它和最大流问题的联系， 可以使问题得到十分有效的解决。发现实际应用问题和最大流问题的联系是非常重要的工作。另一方面，事实上，许多应用问题所对应的最大流问题都有比较明显的特征，但充分利用这些特征，设计面向应用问题的算法并不多。
4. 计划与进度安排
2022-12-1--2022-12-31 开题阶段 撰写、提交、修改开题报告、指导周记
2022-1-19--2022-3-19初稿阶段 撰写、提交论文初稿、中期检查
2022-4-21--2022-5-6 论文修改阶段 反复修改论文并提交修改稿（二稿、三稿）、提交外文文献及译稿，指导周记
5. 参考文献
[1]张宪超，陈国良，万颖瑜．网络最大流问题研究进展[J]．计算机研究与进展，2003，40(9)：1281-1292
[2]钱颂迪.运筹学[ M] .北京:清华大学出版社, 2003.
[3] 夏冬晴． 最大流算法的改良［J］． 邵阳学院学报: 自然科学版， 2004( 6) : 12 － 13．
以上是毕业论文开题报告，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
