2022年网络最大流问题 .pdf

《2022年网络最大流问题 .pdf》由会员分享，可在线阅读，更多相关《2022年网络最大流问题 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1、网络与流设一个赋权有向图D=（V,A）,在 V中指定一个发点vs和一个收点 vt(本题中，1V和7V分别是发点和收点)其它的点叫做中间点。对于 D中的每一个弧（vi,vj）A,（i，j1，2，3，4，5，6，7）都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，A，C）。弧的容量：是对网络上的每条弧(vi,vj)都给出一个最大的通过能力，记为c(vi,vj)或简写为 cij。2流：加在网络各条弧上的一组负载量f(vi,vj)：加在弧(vi,vj)上的负载量，简记为fij，为非负数网络上的流：名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页

2、，共 5 页 -是指定义在弧集合上的一个函数f=f(vi,vj),其中 f(vi,vj)称为弧（vi,vj)上的流量，流也可看作一个双下标变量。3.弧的流量 f(vi,vj)：表示弧(vi,vj)上每单位时间内的实际通过能力弧的容量 c(vi,vj)：表示弧（vi,vj)上每单位时间内的最大通过能力对于实际的网络系统上的流，有几个显著的特点：(1)发点的净流出量和收点的净流入量必相等。(2)每一个中间点的流入量与流出量的代数和等于零。(3)每一个弧上的流量不能超过它的最大通过能力（即容量）.4.可行流与最大流称满足下列条件的流为可行流：（1）容量限制条件：对于每一个弧（vi,vj）A，有 0f

3、(vi,vj)c(vi,vj)（简记为 0 fij cij）（2）平衡条件1，对出发点1V有，11jjffVf2.对于收点7V有，77jjffVf式子中 V(f)称为可行流 f 的流量,即发点的净输出量（或收点的净输入量）。3.对于中间点:流入量=流出量。即对每个 i(i1,7)有 f(vi,vj)-f(vj,vi)=0(i1，7)(简记为 fij-fji=0(i1，7)即总流量=发点的净输出量=收点的净输入量；容量网络的可行流总是存在的，如当所有弧的流均取零，即对所有的i,j,有 f(vi,vj)=0 就是一个可行流。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -5

4、.网络最大量：就是要求一个流 fij,使其流量 v(f)达到最大,并且满足 0fij cij；求网络的最大流，即是指满足容量限制条件和平衡条件的条件下，使v(f)值达到最大.这是一个线性规划模型的问题：()101,7()7ijjiv fiffiv fi名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 5 页 -Lingo程序如下：model:!这是一个最大流问题;sets:point/v1.v7/;links(point,point):cost,volume;endsetsmax=vf;!起点1流出的和终点 7流入的量等于最大流量;sum(point(J):volume(1,J)-

5、sum(point(J):volume(J,1)=vf;sum(point(J):volume(7,J)-sum(point(J):volume(J,7)=-vf;!其他中间点的流入流出量相等;for(point(I)|I#ne#1#and#I#ne#7:sum(point(J):volume(I,J)-sum(point(J):volume(J,I)=0);for(links(I,J):volume(I,J)cost(I,J);!约束条件，不超过最大流量;data:cost=0 20 14 0 0 0 0 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 5 页 -0 0 0 15 12 0 0 0 0 0 10 0 13 0 0 0 0 0 8 0 9 0 0 0 0 0 8 10 0 0 0 0 0 0 12 0 0 0 0 0 0 0;enddataend 程序运行结果如下：名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -