《系统优化算法课程设计论文-最小费用最大流算法设计与实现》由会员分享，可在线阅读，更多相关《系统优化算法课程设计论文-最小费用最大流算法设计与实现（25页珍藏版）》请在金锄头文库上搜索。
1、课程设计（论文）课程名称： 系统优化算法设计与实现 题 目： 最小费用最大流算法设计与实现 院 （系）： 管理学院 专业班级： 信管 1302 姓 名： 王程 学 号： 130404026 指导教师： 黄光球 2015 年 7 月 18 日西安建筑科技大学课程设计（论文）任务书专业班级： 信管1302 学生姓名： 王程 指导教师（签名）： 一、课程设计（论文）题目最小费用最大流算法设计与实现二、本次课程设计（论文）应达到的目的系统优算法设计与实现课程设计是实践教学环节的重要组成部分，其目的是通过课程设计加深学生对系统优算法设计与实现基本知识掌握和基本编程技能的培养，提高综合运用知识解决实际问题
2、的能力；本次要求学生通过掌握系统优算法设计与实现的程序设计方法，以提高学生独立分析问题、解决问题的能力，逐步增强实际工程训练。三、本次课程设计（论文）任务的主要内容和要求设计内容：网络最大流问题，只考虑了流的数量，没有考虑流的费用。实际上许多问题还要考虑流的最小费用问题。在网络G=（V,E,C）中，每条边（v i，v j）除了已给容量c ij外，还给出了单位流量的费用d ij （d ij =0） ，记G=（V,E,C，d） 。求G的一个可行流f=f ij，使得流量W(f)=v，且总费用最小。(,)ijijvEff特别地，当要求f为最大流时，此问题即为最小费用最大流问题。最小费用最大流问题的常用
3、算法有两种：（1）原始算法；（2）对偶算法。本文将使用对偶算法来解决最小费用最大流问题，即先找一个流量为W(f（0） )Dk+costkj) 第 3 页 共 20 页 Dj=Dk+costkj; pj=k+1; /其中 Dn最后保存各点的最短路径长度，pj中保存最短路径； 2在与最短路相应的可增广链 上做流量调整,使用函数 modify()应用递归来计算所能增加流量的最大值,并在增广链上添加流量。void modify() pre=pn-1; i=n-1; min=cpre-1i-flowpre-1i; while(pre!=0) i=pre-1; pre=ppre-1; if(mincpre
4、-1i-flowpre-1i) min=cpre-1i-flowpre-1i; if(pre=1) pre=0;第 4 页 共 20 页令 (,)- ,ijijijijijfvf若 是 可 增 广 链 上 的 前 向 边若 是 可 增 广 链 上 的 后 向 边若 不 在 可 增 广 链 上其中 (1)(1)=mn,mnkkijijijcff3对网络 ，有可行流 f，保持原网络各点，每条边用(,)GVECd两条方向相反的有向边代替，各边的权 按如下规则进行调整：ijl（1）当边 ，令 (,)ijv ijijijij fcl当当（其中+的意义是：这条边已饱和，不能在增大流量，否则要花费更高的代价
5、，实际无法实现，因此权为+的边可从网络中去掉。在实际编程中可用一个较大的数如 100 来代替。 ）（2）当边 为原来 中边 的反向边，令(,)jivG(,)ijv 0ijijjidfl当 当（这里+的意义是此边流量已减少到 0，不能再减少，权为+的边也可以去掉。同样可以用一个较大的数如 100 来代替。 ）4当边上出现负权边时，采用逐次逼近法来求得从 Vs 到 Vt 的最短路，即最小费用流的可增广链。2.4 原代码#include stdio.h#include stdlib.h#include dos.h第 5 页 共 20 页#include math.h #define max 100#
6、define n 5 /根据不同问题可修改大小 #define stream 11 /根据不同问题可修改 int ptn=0,0,0,0,0; /原点到各点的路长(用于逐次逼近法中) int pn=0,0,0,0,0; int c1010,flow1010,scost1010,cost1010,D10,a,b;int maxflow; /设置最大流量 int mincost=0; /-计算 Vs-Vt 最短路径模块-/ void Dijkstra() /求源点 Vs 到其余顶点的最短路径及其长度;得到一条增广链 int sn; /Dn最后保存各点的最短路径长度 int i,j,k,vl,pre
7、; int min; int inf=2000;for(a=0;aDk+costkj) Dj=Dk+costkj; pj=k+1; /此时所有顶点都已扩充到红点集 S 中 printf(Vs 到 Vt 的最短路径为:n); for(i=0;icpre-1i-flowpre-1i) min=cpre-1i-flowpre-1i; if(pre=1) pre=0; if(min+maxflow)stream) min=stream-maxflow; pre=pn-1; /在增广链上添加流量 i=n-1; flowpre-1i+=min; while(pre!=0) 第 10 页 共 20 页 i=
8、pre-1; pre=ppre-1; flowpre-1i+=min; if(pre=1) pre=0;/*printf(流量矩阵：n); for(i=0;iflowij) costij=costpreij; if(cij!=max & cij=flowij) | (cij=max & flowij=max) costij=max; if(ij) if(cij!=max & cijflowij) | (cij=max & flowji0) costij=costpreji; 第 12 页 共 20 页if(cij!=max & cij=flowij) | (cij=max & flowji=0
9、) costij=max; if(i=j) costij=0; /* printf(费用矩阵：n); for(i=0;i(ptj+costji) min=ptj+costji; ptfi=min; for(i=0;in;i+) pti=ptfi; if(pfi!=pti) 第 14 页 共 20 页flag=0; /两次迭代的值不同,继续 while(flag=0); j=n-1; for(i=0;ij;i+) /找出最短路径走向 if(pti+costij=ptj) pj=i+1; /pj中的下标从 1 开始 if(pj=1) break; j=i; i=-1; for(i=0;in;i+)
10、 Di=pti; for(i=0;in;i+)if(i=n-1)printf(%d,i+1);j=pi;while(j!=0)第 15 页 共 20 页printf(-%d,j);j=pj-1;printf(n); /-END approach()-/ void main() int i,j; Dijkstra();while(1) modify(); /调整流量矩阵 maxflow=0; for(j=0;jn;j+) if(flow0j!=max) maxflow+=flow0j; if(maxflow=stream)break;modifycost();approach(); /采用逐次逼
11、近法得到一条增广链 第 16 页 共 20 页printf(最终流量矩阵：n); for(i=0;in;i+) for(j=0;jn;j+) printf(%d ,flowij); printf(n); printf(最终费用矩阵：n); for(i=0;in;i+) for(j=0;jn;j+)printf(%d ,costij); printf(n); for(i=0;in;i+)for(j=0;jn;j+)if(flowij!=100 & scostij!=100)mincost+=flowij*scostij;第 17 页 共 20 页printf(最大流为：%dn,stream);p
12、rintf(最小费用为：%dn,mincost); 3 实验研究小结3.1 使用说明详述3.1.1 本部分功能操作注意事项在初始化每条边上的容量限制、流量和费用时，当两个点不直接连通时用 100 来代替无穷大，当题目所给数字本来就大时，也可用更大的数如 1000 来答题无穷大，当起始点和终点相同时，容量、流量和费用均用 0 来表示。在输入数据时，依次输入容量限制 、边上的ijc流量 和费用 ，三个数据之间用逗号隔开，然后再空格输入ijf(cos)ijijdt下一边上的数。3.1.2 本部分功能与其他系统的关系最小费用最大流是一类网络优化问题, 在现实生活中往往被系统管理者和决策者所重视。本文综合求最大流原理和求最短路原理,在VC+6.0 的软件开发环境下直接输入初始状态下就求出任何一个网络图的最小费用值,最大流值以及其他一些相关数据。该算法程序可以为我们减少大量计算,提高工作效率。3.2 测试案例详
