最大流问题实验报告.docxVIP

最大流问题实验报告 　　实验7最大流问题的编程实现　　专业班级学号姓名报告日期.　　实验类型：●验证性实验○综合性实验○设计性实验　　实验目的：熟练最大流问题的求解算法。　　实验内容：最大流问题的求解算法。　　实验原理：先给定初始可行流，然后找出可扩充路，调整可扩充路上的流量，使可行流增大，不断重复上述过程，直到不存在可扩充路为止。　　实验步骤　　1要求上机实验前先编写出程序代码　　2编辑录入程序　　3调试程序并记录调试过程中出现的问题及修改程序的过程　　4经反复调试后，运行程序并验证程序运行是否正确。　　5记录运行时的输入和输出。　　预习编写程序代码：　　实验报告：根据实验情况和结果撰写并递交实验报告。　　实验总结：　　参考程序　　求最大流　　V28　　4V46　　V16　　V63V335V5　　n=6;　　C=[;;;;;];　　[f,wf,No]=maxflow(n,C)　　f=　　　　　　　　　　　　　　wf=　　13　　No=　　　　由运行结果知，最大流量为13.　　程序代码　　function[f,wf,No]=maxflow(n,C)　　%利用Ford--Fulkerson标号法求最大流算法的MATLAB程序代码　　%f%显示最大流　　%wf%显示最大流量　　%No%显示标号,由此可得最小割　　%n节点个数　　%C%弧容量　　for(i=1:n)　　for(j=1:n)　　f(i,j)=0;　　end;　　end%取初始可行流f为零流　　for(i=1:n)　　No(i)=0;　　d(i)=0;　　end%No,d记录标号　　while(1)　　No(1)=n+1;　　d(1)=Inf;%给发点vs标号　　while(1)　　pd=1;%标号过程　　for(i=1:n)　　if(No(i))%选择一个已标号的点vi　　for(j=1:n)　　if(No(j)==0f(i,j)d(i))　　d(j)=d(i);　　end　　elseif(No(j)==0f(j,i)0)%对于未给标号的点vj,当vjvi为非零流弧时No(j)=-i;　　d(j)=f(j,i);　　pd=0;　　if(d(j)d(i))　　d(j)=d(i);　　end;　　end;　　end;　　end;　　end　　if(No(n)|pd)　　break;　　end;　　end%若收点vt得到标号或者无法标号,终止标号过程　　if(pd)　　break;　　end%vt未得到标号,f已是最大流,算法终止dvt=d(n);　　t=n;%进入调整过程,dvt表示调整量while(1)　　if(No(t)0)　　f(No(t),t)=f(No(t),t)+dvt;%前向弧调整elseif(No(t)添加或扩大反方向的容量，大小就是刚才减去的容量。一直到没有路为止。此时辅助图上的正向流就是最大流。　　增广路方法可以解决最大流问题，然而它有一个不可避免的缺陷，就是在极端情况下每次只能将流扩大1　　，这样会造成性能上的很大问题。　　实验步骤　　1要求上机实验前先编写出程序代码　　2编辑录入程序　　3调试程序并记录调试过程中出现的问题及修改程序的过程　　4经反复调试后，运行程序并验证程序运行是否正确。　　5记录运行时的输入和输出。　　预习编写程序代码：　　实验报告：根据实验情况和结果撰写并递交实验报告。　　实验总结：　　参考程序　　例：解决如下问题：　　①使用lingo求解，调用如下模型，程序代码如下：　　model:　　sets:　　point/v1,v2,v3,v4,v5,v6/;　　route(point,point)/v1v2,v1v3,v2v3,v2v4,v2v5,v3v4,v3v5,v4v6,v5v4,v5v6/:transport,capacity;　　endsets　　data:　　capacity=17;　　enddata　　max=z;　　z=@sum(point(j)|@in(route,@index(point,v1),j):transport(1,j));　　@for(point(i)|i#ne#@index(point,v1)#and#i#ne#@index(point,v6):@sum(point(j)|@in(route,i,j):transport(i,j))=@sum(point(j)|@in(route,j,i):transport(j,i)));　　@for(route:transport最大流问题实验