系统优化算法课程设计论文-最小费用最大流算法设计与实现

《系统优化算法课程设计论文-最小费用最大流算法设计与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计（论文）课程名称：系统优化算法设计与实现题目：最小费用最大流算法设计与实现院（系）：管理学院专业班级：信管1302姓名：王程学号：130404026指导教师：黄光球2015年7月18日西安建筑科技大学课程设计（论文）任务书专业班级：信管1302学生姓名：王程指导教师（签名）：一、课程设计（论文）题目最小费用最大流算法设计与实现二、本次课程设计（论文）应达到的目的《系统优算法设计与实现》课程设计是实践教学环节的重要组成部分，其目的是通过课程设计加深学生对系统优算法设计与实现基本知识掌握和基

2、本编程技能的培养，提高综合运用知识解决实际问题的能力；本次要求学生通过掌握系统优算法设计与实现的程序设计方法，以提高学生独立分析问题、解决问题的能力，逐步增强实际工程训练。三、本次课程设计（论文）任务的主要内容和要求设计内容：网络最大流问题，只考虑了流的数量，没有考虑流的费用。实际上许多问题还要考虑流的最小费用问题。在网络G=（V,E,C）中，每条边（vi，vj）除了已给容量cij外，还给出了单位流量的费用dij（dij>=0），记G=（V,E,C，d）。求G的一个可行流f={fij}，使得流量

3、W(f)=v，且总费用最小。特别地，当要求f为最大流时，此问题即为最小费用最大流问题。最小费用最大流问题的常用算法有两种：（1）原始算法；（2）对偶算法。本文将使用对偶算法来解决最小费用最大流问题，即先找一个流量为W(f（0）)

4、代码。2．提交设计说明书。3.接受现场检验。四、应收集的资料及主要参考文献：应收集的资料：本次设计应该收集和题目背景的有关资料。主要参考文献：1.胡运权.《运筹学》.清华大学出版社，20122.谭浩强，《C程序设计》，清华大学出版社，20103.韩明亮，求最小费用最大流问题的一种方法[J]，中国民航学院学报,20004.张远福,谭毓澄,余剑敏，制造网络的一个最小费用最大流算法[J].江西师范大学学报(自然科学版).20075.寇玮华,董雪,吕林剑，交通运输网络中两个结点间有流量约束的最小费用最大

5、流算法[J]，兰州交通大学学报.2009五、审核批准意见教研室主任（签字）设计总说明摘要：在现实生活中，关于系统网络的研究就有不少。许多系统网络就包含了流量的问题，如何实现网络最大流往往是我们一直关注并研究的重点。但在经济活动中或是涉及“流”的问题时，我们考虑的还有“费用”的因素，“最小费用最大流问题”就往往被系统管理者和决策者所重视。最小费用最大流是一类网络优化问题,它与最大流的区别在于,它不仅要考虑流量问题,还要考虑费用因素,其优化的目标是流量最大且费用最小。本文综合求最大流原理和求最短路原

6、理,在直接输入初始状态下就求出任何一个网络图的最小费用值,最大流值以及其他一些相关数据。该算法程序可以为我们减少大量计算,提高工作效率,因此被大量使用研究。关键字：发点、汇点、最短路径、最大流、增广路径、Dijkstra算法、逐次逼近法目录1绪论11.1内容简介11.2本次课设目的11.3课设内容12最小费用最大流算法设计说明22.1程序设计过程详述22.2编程实现过程详述22.4原代码43实验研究小结173.1使用说明详述173.1.1本部分功能操作注意事项173.1.2本部分功能与其他系统的

7、关系173.2测试案例详述17参考文献201绪论1.1内容简介本文综合求最大流原理和求最短路原理,在直接输入初始状态下就求出任何一个网络图的最小费用值,最大流值以及其它一些相关数据。1.2本次课设目的（1）在G上，除了已给容量cij，还给了每一条弧的费用bij，编制程序，找到从发点Vs到收点Vt的最小费用最大流；（2）熟悉运用开发环境，基于VC++6.0的软件开发环境；（3）完成课程设计基本任务的设计及编码；（4）熟练掌握VC++6.0上的基本的调试方法。1.3课设内容在实际网络问题中，不仅要考

8、虑从Vs到Vt的流量最大，而且还要考虑可行流在网络传送过程中的费用问题，这就是网络的最小费用最大流问题。在最小费用最大流的实现中，其实大的来说就两个步骤：在图中寻找最短路径；路径调整。当然在这其中涉及到了流量的如何调整，以及图中边的方向变化。在寻找最短路径的增广链中，需要将从始点到终点的每一条增广链找到，直到没有增广链了程序才能停止。第20页共20页2最小费用最大流算法设计说明2.1程序设计过程详述解决这一类问题，最常见的方法便是运用Ford-Fulkerson算法的思想，即把各条弧上单位流量的