【数学建模算法】(13)图的应用：最大流算法（下）

作者: 热爱学习的高老板 | 来源:发表于2019-08-15 15:56 被阅读0次

3.最大流的一种算法——标号法

标号法是由 Ford 和 Fulkerson 在 1957 年提出的。用标号法寻求网络中最大流的基本思想是寻找可增广轨，使网络的流量得到增加，直到最大为止。即首先给出一个初始流，这样的流是存在的，例如零流。如果存在关于它的可增广轨，那么调整该轨上每条弧上的流量，就可以得到新的流。对于新的流，如果仍存在可增广轨，则用同样的方法使流的值增大，继续这个过程，直到网络中不存在关于新得到流的可增广轨为止，则该流就是所求的最大流。

这个方法分为以下两个过程：
A.标号过程：通过标号过程寻找一条可増广轨。
B.增流过程：沿着可増广轨增加网络的流量。

3.1.标号过程

1.给发点标号为 $\left(s^{+}, \infty\right)$ 。

2.若顶点 $x$ 已标号，则对 $x$ 所有未标号的邻接顶点 $y$ 按如下规则标号：

（1）若 $(x, y) \in A$ ，且 $f_{x y}<u_{x y}$ 时，令 $\delta_{y}=\min \left\{u_{x y}-f_{x y}, \delta_{x}\right\}$ ，则给顶点 $y$ 标号为 $\left(x^{+}, \delta_{y}\right)$ ，若 $f_{x y}=u_{x y}$ ，则不给顶点 $y$ 标号。

笔者认为这一步的意思是对流量未达到容量的流进行标号。

(2) $(y, x) \in A$ ，且 $f_{y x}>0$ ，令 $\delta_{y}=\min \left\{f_{y x}, \delta_{x}\right\}$ 则给 $y$ 标号为 $\left(x^{-}, \delta_{y}\right)$ ，若 $f_{y x}=0$ ，则不给 $y$ 标号。

力求让反向流量都为0。

3.不断重复步骤(2)直到收点 $t$ 被标号，或不再有顶点可以标号为止。当 $t$ 被标号时，表明存在一条从 $s$ 到 $t$ 的可増广轨，则转向下面的增流过程。如果 $t$ 点不能被标号，且不存在其他可以标号的顶点时，表明不存在从 $s$ 到 $t$ 的増广轨，算法结束，此时所得的流就是最大流。

只要标过号的顶点，都有待优化的流，都要放到下面的增流过程中进行优化。

3.2.增流过程

1.令 $u=t$ 。

从起点开始

2.若 $u$ 的标号 $\left(v^{+}, \delta_{t}\right)$ ，则 $f_{w}=f_{w}+\delta_{i}$

正向流，流量加满

若 $u$ 的标号 $\left(v^{-}, \delta_{t}\right)$ ，则
$f_{u v}=f_{u v}-\delta_{t}$

反向流，流量清空

3.若 $u=s$ ，则去掉全部标号，并回到标号过程。否则令 $u=v$ ，并回到增流过程2。

如果到了终点，则这条轨调整完成，返回标下一条轨，若没到终点，则以下一个起点开始继续增流。

3.3.程序设计具体步骤

对于每个节点，标号包括两部分信息
$(\text { pred }(j), \max f(j))$
该节点在可能的增广路中的一个节点 $\operatorname{pred}(j)$ ，以及沿该可能的增广路到该节点为止。可以增广的最大流量 $\max \mathrm{f}(j)$ 。

1.置初始可行流 $x$ （如零流）；对节点 $t$ 标号，即令 $\max \mathrm{f}(t)=$ 任意正值（如1）。
2.若 $\max \mathrm{f}(t)>0$ ，继续下一步；否则停止，已经得到最大流，结束。
3.取消所有节点 $j \in V$ 的标号，即令 $\max \mathrm{f}(j)=0$ ， $\operatorname{pred}(j)=0$ ；令LIST $=\{s\}$ ，对节点 $s$ 标号，即令 $\max \mathrm{f}(s)=$ 充分大的正值。
4.如果LIST $\neq \Phi$ 且 $\max \mathrm{f}(t)=0$ 继续下一步，否则：

(1)如果 $t$ 已有标号（即 $\max \mathrm{f}(t)>0$ ），则找到了一条增増广路，沿该増广路对流 $x$ 进行増广（增广的流量即是 $\max \mathrm{f}(t)$ ，増广路可以根据pred方便地回溯得到），转到2。
(2)如果 $t$ 没有标号（即 $\mathrm{LIST}=\Phi$ 且 $\max \mathrm{f}(t)=0$ ），则停止，已得到最大流。

5.从 $LIST$ 中移走一个节点 $i$ ;寻找从节点 $i$ 出发的所有可能的増广弧；
(1)对非饱和前向弧 $(i,j)$ ，若节点 $j$ 没有标号（即 $\operatorname{pred}(j)=0$ ），对 $j$ 进行标号，即令
$\max \mathrm{f}(j)=\min \left\{\max \mathrm{f}(i), u_{i j}-x_{i j}\right\}, \quad \operatorname{pred}(j)=i$
并将 $j$ 加入 $LIST$ 中。
(2)对非空后向弧 $(j,i)$ ，若节点 $j$ 没有标号（即 $\operatorname{pred}(j)=0$ ），对 $j$ 进行标号，即令
$\max \mathrm{f}(j)=\min \left\{\max \mathrm{f}(i), x_{i j}\right\}, \quad \operatorname{pred}(j)=-i$
并将 $j$ 加入 $LIST$ 中。

3.4.举例

例1 计算最大流，弧上两个数字分别代表容量和当前流量。

例1题图

编写Matlab程序：

clc,clear
u(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;
u(3,5)=1;u(4,3)=3;u(4,5)=3;
f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1;
f(3,5)=1;f(4,3)=1;f(4,5)=0;
n=length(u);list=[];maxf(n)=1;
while maxf(n)>0
    maxf=zeros(1,n);pred=zeros(1,n);
    list=1;record=list;maxf(1)=inf;
    %list是未检查邻接点的标号点，record是已标号点
    while (~isempty(list))&(maxf(n)==0)
        flag=list(1);list(1)=[];
        label1= find(u(flag,:)-f(flag,:));
        label1=setdiff(label1,record);
        list=union(list,label1);
        pred(label1)=flag;
        maxf(label1)=min(maxf(flag),u(flag,label1)...
        -f(flag,label1));
        record=union(record,label1);
        label2=find(f(:,flag));
        label2=label2';
        label2=setdiff(label2,record);
        list=union(list,label2);
        pred(label2)=-flag;
        maxf(label2)=min(maxf(flag),f(label2,flag));
        record=union(record,label2);
    end
        if maxf(n)>0
            v2=n; v1=pred(v2);
            while v2~=1
            if v1>0
                f(v1,v2)=f(v1,v2)+maxf(n);
            else
                v1=abs(v1);
                f(v2,v1)=f(v2,v1)-maxf(n);
            end
        v2=v1; v1=pred(v2);
            end
    end
end
f

当然，最大流问题也可以从线性规划的角度解决：

例2 现需要将城市 $s$ 的石油通过管道运送到城市 $t$ ，中间有4个中转站 $v_{1}, v_{2}, v_{3}$ 和 $v_{4}$ ，城市与中转站的连接以及管道的容量如图所示，求从城市 $s$ 到 $t$ 的最大流。

例2图

提供两个版本的Lingo程序：

model:
sets:
nodes/s,1,2,3,4,t/;
arcs(nodes,nodes)/s 1,s 3,1 2,1 3,2 3,2 t,3 4,4 2,4 t/:c,f;
endsets
data:
c=8 7 9 5 2 5 9 6 10;
enddata
n=@size(nodes); !顶点的个数;
max=flow;
@for(nodes(i)|i #ne#1 #and# i #ne# n:
@sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i)));
@sum(arcs(i,j)|i #eq# 1:f(i,j))=flow;
@sum(arcs(i,j)|j #eq# n:f(i,j))=flow;
@for(arcs:@bnd(0,f,c));
end

model:
sets:
nodes/s,1,2,3,4,t/;
arcs(nodes,nodes):c,f;
endsets
data:
c=0;
@text('fdata.txt')=f;
enddata
calc:
c(1,2)=8;c(1,4)=7;
c(2,3)=9;c(2,4)=5;
c(3,4)=2;c(3,6)=5;
c(4,5)=9;c(5,3)=6;c(5,6)=10;
endcalc
n=@size(nodes); !顶点的个数;
max=flow;
@for(nodes(i)|i #ne#1 #and# i #ne# n:
@sum(nodes(j):f(i,j))=@sum(nodes(j):f(j,i)));
@sum(nodes(i):f(1,i))=flow;
@sum(nodes(i):f(i,n))=flow;
@for(arcs:@bnd(0,f,c));
end

【数学建模算法】(13)图的应用：最大流算法（下）

3.最大流的一种算法——标号法

3.1.标号过程

3.2.增流过程

3.3.程序设计具体步骤

3.4.举例

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读