运筹学-最大流问题的编程实现实验

实验7最大流问题的编程实现成绩专业班级学号姓名报告日期.实验类型：●验证性实验○综合性实验○设计性实验实验目的：熟练最大流问题的求解算法。实验内容：最大流问题的求解算法。实验原理：先给定初始可行流，然后找出可扩充路（增广链），调整可扩充路上的流量，使可行流增大，不断重复上述过程，直到不存在可扩充路为止。实验步骤1要求上机实验前先编写出程序代码2编辑录入程序3调试程序并记录调试过程中出现的问题及修改程序的过程4经反复调试后，运行程序并验证程序运行是否正确。5记录运行时的输入和输出。预习编写程序代码：实验报告：根据实验情况和结果撰写并递交实验报告。实验总结：参考程序求最大流n=6;C=[067000;003840;000350;0000010;0006014;000000];[f,wf,No]=maxflow(n,C)f=067000000600000340000009000004000000wf=13No=700000由运行结果知，最大流量为13.程序代码function[f,wf,No]=maxflow(n,C)%利用Ford--Fulkerson标号法求最大流算法的MATLAB程序代码%f%显示最大流V4V6V5V3V1673348561410V2%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))%选择一个已标号的点vifor(j=1:n)if(No(j)==0&f(i,j)C(i,j))%对于未给标号的点vj,当vivj为非饱和弧时No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;if(d(j)d(i))d(j)=d(i);endelseif(No(j)==0&f(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;endif(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)0)f(No(t),t)=f(No(t),t)-dvt;end%后向弧调整if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0;end;break;end%当t的标号为vs时,终止调整过程t=No(t);end;end;%继续调整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);endend