课程设计论文-王程130404026

课程设计（论文）课程名称：系统优化算法设计与实现题目：最小费用最大流算法设计与实现院（系）：管理学院专业班级：信管1302姓名：王程学号：130404026指导教师：黄光球2015年7月18日西安建筑科技大学课程设计（论文）任务书专业班级：信管1302学生姓名：王程指导教师（签名）：一、课程设计（论文）题目最小费用最大流算法设计与实现二、本次课程设计（论文）应达到的目的《系统优算法设计与实现》课程设计是实践教学环节的重要组成部分，其目的是通过课程设计加深学生对系统优算法设计与实现基本知识掌握和基本编程技能的培养，提高综合运用知识解决实际问题的能力；本次要求学生通过掌握系统优算法设计与实现的程序设计方法，以提高学生独立分析问题、解决问题的能力，逐步增强实际工程训练。三、本次课程设计（论文）任务的主要内容和要求设计内容：网络最大流问题，只考虑了流的数量，没有考虑流的费用。实际上许多问题还要考虑流的最小费用问题。在网络G=（V,E,C）中，每条边（vi，vj）除了已给容量cij外，还给出了单位流量的费用dij（dij=0），记G=（V,E,C，d）。求G的一个可行流f={fij}，使得流量W(f)=v，且总费用最小。(,)()ijijijvvEdfdf特别地，当要求f为最大流时，此问题即为最小费用最大流问题。最小费用最大流问题的常用算法有两种：（1）原始算法；（2）对偶算法。本文将使用对偶算法来解决最小费用最大流问题，即先找一个流量为W(f（0）)v的最小费用流（可用零流作为初始流），然后寻找从vs到vt的可增广链，用最大流方法将f（0）调整到f（1）,使f（1）流量为W(f（0）)+θ，且保证f（1）是在W(f（0）)+θ流量下的最小费用流，不断进行到W(f（0）)=v为止。要求：1．提交正确的和完整的程序设计代码。2．提交设计说明书。3.接受现场检验。四、应收集的资料及主要参考文献：应收集的资料：本次设计应该收集和题目背景的有关资料。主要参考文献：1.胡运权.《运筹学》.清华大学出版社，20122.谭浩强，《C程序设计》，清华大学出版社，20103.韩明亮，求最小费用最大流问题的一种方法[J]，中国民航学院学报,20004.张远福,谭毓澄,余剑敏，制造网络的一个最小费用最大流算法[J].江西师范大学学报(自然科学版).20075.寇玮华,董雪,吕林剑，交通运输网络中两个结点间有流量约束的最小费用最大流算法[J]，兰州交通大学学报.2009五、审核批准意见教研室主任（签字）设计总说明摘要：在现实生活中，关于系统网络的研究就有不少。许多系统网络就包含了流量的问题，如何实现网络最大流往往是我们一直关注并研究的重点。但在经济活动中或是涉及“流”的问题时，我们考虑的还有“费用”的因素，“最小费用最大流问题”就往往被系统管理者和决策者所重视。最小费用最大流是一类网络优化问题,它与最大流的区别在于,它不仅要考虑流量问题,还要考虑费用因素,其优化的目标是流量最大且费用最小。本文综合求最大流原理和求最短路原理,在直接输入初始状态下就求出任何一个网络图的最小费用值,最大流值以及其他一些相关数据。该算法程序可以为我们减少大量计算,提高工作效率,因此被大量使用研究。关键字：发点、汇点、最短路径、最大流、增广路径、Dijkstra算法、逐次逼近法目录1绪论......................................................11.1内容简介................................................11.2本次课设目的............................................11.3课设内容................................................12最小费用最大流算法设计说明................................22.1程序设计过程详述........................................22.2编程实现过程详述........................................22.4原代码..................................................43实验研究小结.............................................173.1使用说明详述...........................................173.1.1本部分功能操作注意事项.............................173.1.2本部分功能与其他系统的关系.........................173.2测试案例详述..........................................17参考文献...................................................20第1页共20页1绪论1.1内容简介本文综合求最大流原理和求最短路原理,在直接输入初始状态下就求出任何一个网络图的最小费用值,最大流值以及其它一些相关数据。1.2本次课设目的（1）在G上，除了已给容量cij，还给了每一条弧的费用bij，编制程序，找到从发点Vs到收点Vt的最小费用最大流；（2）熟悉运用开发环境，基于VC++6.0的软件开发环境；（3）完成课程设计基本任务的设计及编码；（4）熟练掌握VC++6.0上的基本的调试方法。1.3课设内容在实际网络问题中，不仅要考虑从Vs到Vt的流量最大，而且还要考虑可行流在网络传送过程中的费用问题，这就是网络的最小费用最大流问题。在最小费用最大流的实现中，其实大的来说就两个步骤：在图中寻找最短路径；路径调整。当然在这其中涉及到了流量的如何调整，以及图中边的方向变化。在寻找最短路径的增广链中，需要将从始点到终点的每一条增广链找到，直到没有增广链了程序才能停止。第2页共20页2最小费用最大流算法设计说明2.1程序设计过程详述解决这一类问题，最常见的方法便是运用Ford-Fulkerson算法的思想，即把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自Vs至Vt的最短路；再将这条最短路作为可扩充路，用求解最大流问题的方法将其上的流量增至最大可能值；而这条最短路上的流量增加后，其上各条弧的单位流量的费用要重新确定，如此多次迭代，最终得到最小费用最大流。具体设计过程如下：（1）取零流为初始可行流，即(0){0}f；（2）若有(1)kf)，流量为(1)()kWfv，构造长度网络(1)()kLf；（3）在长度网络(1)()kLf中求从Vs到Vt的最短路。若不存在最短路，则(1)kf已为最大流，不存在流量等于的流，停止；否则转（4）；（4）在原网络G中与这条最短路相应的可增广链μ上对(1)kf进行调整，做()(1)kkff，其中(1)(1)=minmin(),minkkijijijcff。此时()kf的流量为(1)()kWf，若(1)()kWfv则停止，否则令f(k)代替(1)kf返回（2）。2.2编程实现过程详述1．首次用Dijkstra算法求最短路，即最小费用流。voidDijkstra(){…for(j=0;jn;j++){if((!s[j])&&(D[j]D[k]+cost[k][j]))第3页共20页{D[j]=D[k]+cost[k][j];p[j]=k+1;}}…}//其中D[n]最后保存各点的最短路径长度，p[j]中保存最短路径；2．在与最短路相应的可增广链μ上做流量调整,使用函数modify()应用递归来计算所能增加流量的最大值,并在增广链上添加流量。voidmodify(){…pre=p[n-1];i=n-1;min=c[pre-1][i]-flow[pre-1][i];while(pre!=0){i=pre-1;pre=p[pre-1];if(minc[pre-1][i]-flow[pre-1][i])min=c[pre-1][i]-flow[pre-1][i];if(pre==1)pre=0;}…第4页共20页}令'(,)-(,)(,)ijijijijijijijfvvffvvfvv若是可增广链上的前向边若是可增广链上的后向边若不在可增广链上其中(1)(1)=minmin(),minkkijijijcff3．对网络(,,,)GVECd，有可行流f，保持原网络各点，每条边用两条方向相反的有向边代替，各边的权ijl按如下规则进行调整：（1）当边(,)ijvvE，令ijijijijijijdfclfc当当（其中+∞的意义是：这条边已饱和，不能在增大流量，否则要花费更高的代价，实际无法实现，因此权为+∞的边可从网络中去掉。在实际编程中可用一个较大的数如100来代替。）（2）当边(,)jivv为原来G中边(,)ijvv的反向边，令00ijijjiijdflf当当（这里+∞的意义是此边流量已减少到0，不能再减少，权为+∞的边也可以去掉。同样可以用一个较大的数如100来代替。）4．当边上出现负权边时，采用逐次逼近法来求得从Vs到Vt的最短路，即最小费用流的可增广链。2.4原代码#includestdio.h#includestdlib.h#includedos.h#includemath.h第5页共20页#definemax100#definen5//根据不同问题可修改大小#definestream11//根据不同问题可修改intpt[n]={0,0,0,0,0};//原点到各点的路长(用于逐次逼近法中)intp[n]={0,0,0,0,0};intc[10][10],flow[10][10],scost[10][10],cost[10][10],D[10],a,b;intmaxflow;//设置最大流量intmincost=0;//------------------计算Vs--Vt最短路径模块----------------//voidDijkstra()//求源点Vs到其余顶点的最短路径及其长度;得到一条增广链{ints[n];//D[n]最后保存各点的最短路径长度inti,j,k,vl,pre;intmin;intinf=2000;for(a=0;an;a++){for(b=0;bn;b++){scanf(%7d,%7d,%7d,&c[a][b],&flow[a][b],&scost[a][b]);}}第6页共20页for(a=0;an;a++){for(b=0;bn;b++){cost[a][b]=scost[a][b];}}vl=0;//求V0到Vn的增广链for(i=0;in;i++){D[i]=cost[vl][i];//置初始距离值if((D[i]!=max)&&(D[i]!=0)){p[i]=1;}elsep[i]=0;}for(i=0;in;i++){s[i]=0;s[vl]=1;D[vl]=0;}for(i=0;in;i++){第7页共20页min=inf;for(j=0;jn;j++){if((!s[j])&&(D[j]min)){min=D[j];k=j;}}s[k]=1;if(min==max)break;for(j=0;jn;j++){if((!s[j])&&(D[j]D[k]+cost[k][j])){D[j]=D[k]+cost[k][j];p[j]=k+1;}}}//此时所有顶点都已扩充到红点集S中printf(Vs到Vt的最短路径为:\n);for(i=0;in;i++){if(i=n-1){printf(%d,i+1);第8页共20页pre=