第7章网络-3最大流问题应用

第七章网络规划第七章网络规划第一节：现实中的网络规划问题第二节：图的基本概念

第三节：树

第四节：最大流问题

第五节：最短路径问题

第六节：最小费用最大流问题第七节：网络规划的应用一

引言在网络图中指定一个源节点和一个汇节点，源节点的供应量为f，汇节点的需求量为f，图中其他节点均为中转节点。图中各边（i，j）流量的下界Lij=0，上界cij>0（图7-13）。对于一个给定的图，各节点流入、流出的流量保持平衡，各边上的流量为非负且不超过相应边的流量上界，求通过图的最大流量f的问题就是网络最大流问题。现实中的许多系统都存在各种各样的流，如公路系统中的车辆流、水利系统中的水流、电力系统中的电流、生产系统中的产品流、金融系统中的货币流、服务系统中的顾客流、信息系统中的信息流等。23411342f2cij图7-12.最大流示意图sts’t’对有多个发点和多个收点的网络,可以另外虚设一个总发点和一个总收点,并将其分别与各发点、收点连起来（见图），就可以转换为只含一个发点和一个收点的网络。所以一般只研究具有一个发点和一个收点的网络5基本概念

一、网络流：是指在一定的条件下通过一个网络的某种流在各边上的流量的集合。

一定条件指的是：

（1）网络有一个始点s和终点t

。（2）流过网络的流量具有一定的方向，一般用有向网络N

=

(V，A)加以描述，各弧的方向就是流量通过的方向。

（3）对每一弧

(

i,j)

∈A，都赋予一个容量

r

(i,j)

=

rij或Cij

，表示容许通过该弧的最大流量。在一个网络

N

=

(V,A)

中，设以xij=

x(i,j)表示通过弧(i,j)∈A

的流量，则集合

X={

xij│(i

,j)∈A

}称为该网络的一个流。其流量记为

f

=

f

(X)

。

23411342f2cij第8章网络分析6

二、可行流

满足下面条件的流称为一个可行流：

(1)弧流量限制条件

0≤

xij≤rij

（Cij）(i,j)∈A

(2)

中间点平衡条件

xij

-

xji

=

0，i

≠

s,t

这意味着每个中间点的净贮流量为0，即每个中间点的流入量必须等于其流出量，二者必须平衡。ijjxjixij

xji

xij

max

f

=

f

(X)

f

i=s

0

i

≠

s,

t

-f

i=t0≤

xij

≤rij,(i,j)∈As.tjj

xij

-

xji

=7

三、最大流

流量最大的可行流称为最大流，记为X*

=

{xij*}，其流量记为f

*

=

f(X*).最大流问题的

LP模型8

可行流恒存在，如X0

={xij=

0│(i,j)∈A

}就是一个可行流，称为零流，其流量

f(X0)=

0。又如图所示也是一个可行流。s2143t(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(6,3)(7,7)(2,1)

13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)网络最大流问题可以用线性规划方法求解网络最大流问题可以用线性规划方法求解。例如图7-12的最大流问题，设xij为各弧的流量，f表示可行流的流量。则此最大流问题的线性规划形式为：

23411342f2cijïïïîïïïí죣=+--=+--=++-=-+=ijijcxfxxxxxxxxfxxtsfz040302010..max34243423132423121312节点节点节点节点10

设

X

=

{xij}是一可行流，

是从

s到

t的一条链。若

上各弧的流量满足下述条件：

设μ是网络N中的一条从s到t的链,则链μ上与链的方向一致的弧称为前向弧，其集合记为；链上与链的方向相反的弧称为后向弧，其集合记为-

。

={(s,2),(1,4),(3,t)}-

={(1,2),(3,4)}xij

<

rij

当(i,j)∈xij

>

0

当(i,

j)∈-

则称

为一条关于可行流X的增广链，记为(X)。四、链的前向弧与后向弧五、增广链非零流弧非饱和弧s2143t(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(6,3)(7,7)(2,1)11六、截集S②S中各点不须经由中的点而均连通S中的各点也不须经由S中的点而均连通S①S∪=V

s∈

SSSS∩

=

t∈SS则把始点在S中而终点在中的一切弧所构成的集合，称为一个分离s和t的截集，记为(S,)。七、截量r(

S,)=

∑rij(i,j)∈(S,S)S(S,)={a1,a3}SSSa1a2a3st12

定理3：增广链调整法

设

X={xij}是N=(V,A)中的一个可行流，

=

s12···k···t是关于

X

的一条增广链，r*

=

r(S*,)

=

4+7

=

11S*定理2：流量

—

截量定理基本原理八、最小截集在网络N中，容量最小的截集称为最小截集，记为(

S*,

S*)。S*(S*,)

=

{(1,3),(4,t)}S在网络N=(V,A)中，设

X={

x(u,)∣u,

∈V}是任一可行流，(S,)是任一截集，则S

f(X)≤r(S,)SSa1a2a3st13最大流问题令

1=

min{rij-xij}则

X'

={

x'

}也是N的一个可行流，且有ij

f

(

X'

=f(X)+

)再令ijx'

=xij+

,

当(i,j)∈xij

-

,

当(i,j)∈-

xij

,当(i,j)∈

=

min{1

,2}-

2

=

min{xij}s2143t(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(6,3)(7,7)(2,1)40241(xij+)+(xij-)==(xij+xij)=(3+1)+(2-1)

定理4：最大流的充要条件设X*

={

x*ij

}是网络N=(V,A)

的一个可行流，则X*

为最大流的充要条件是：网络

N

中不存在增广链

(X*)。

s2143t(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(6,3)(7,7)(2,1)40241定理5：最大流量—最小截量定理网络中从s到t的最大流的流量等于分离s和t的最小截集的截量。

即，若设X*为一最大流，（S*,S*)为一最小截集，则有f(X*)=r(S*，S*)SSa1a2a3stsv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)截集与可行流无关，而只与网络本身有关最小截量是个定值17求网络最大流的标号法

（福特-富尔克逊标号法）一、基本思想

从某一可行流X（如零流）出发，按一定规则找出一条增广链，并按定理3的方法（增广链调整法）调整

X,得到一个流量增大

的新可行流

X

‘。重复上述做法直到找不出增广链为止,这时就得到一个最大流，同时还得到一个最小截集。二、基本步骤

1°

给始点

s

标号(0，∞)

，则

s

已标号待检查；前源点当前最大可调整量第8章网络分析18最大流问题

2°

取一个已标号待检查的点

i，对所有与

i

相邻而未标号的点

j

依次判断、执行如下手续：

(1)

若关联

j

与

i

的弧为(i,j)，则当该弧上的流量

xij<

rij时,给

j标号(

i，b(j))，其中

b(j)=min{b(i)，rij-

xij

}

表示

(i,j)

弧上的流量的最大可调整量；而当xij

=

rij时,不给

j标号。

(2)

若关联

j

与

i的弧为

(j,i)，则当该弧上的流量

xji

>

0

时,给

j标号(

-i，b(j))，其中

b(j)=min{b(i)，xji

}而当xji=0

时,不给

j

标号；当所有与

i

相邻而未标号的点

j

都执行完上述手续后，就给点

i打√，表示对它已检查完毕。前向弧后向弧第8章网络分析198最大流问题

3°重复2°,可能出现两种结果：

(1)

终点

t

得到标号。则从t回溯标号点的第一个标号，就能找出一条由标号点和相应的弧连接而成的从

s

到

t

的增广链(X)，转

4°；

(2)

所有标号点均已打√（检查过），而t又未得标号。这说明不存在增广链，而当前的可行流即最大流，算出其流量，停止。

4°取调整量

=b(t)

(即终点t

的第二个标号),令

xij

:

=

xij

+，对一切

(i,j)

∈

xij

:

=

xij

-，对一切

(i,j)

∈

-

非增广链上的各弧流量xij

不变。

第8章网络分析20最大流问题5°删除网络中原有一切标号，返回1°；例s2143t(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(6,3)(7,7)(2,1)(0,

∞)(s，2)(s，2)(1，2)(-4，1)(3，1)调整量

=1s2143t(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(6,3)(7,7)(2,1)(0,

∞)(s，1)(s，2)(1，1)f(X*)

=4

+

7

=

11(S*,S*)

=

{

(1,3),(4,

t)

}2048三、举例sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)(0,)(s,2)(-v2,2)(v1,2)(-v3,1)(v4,1)例:用标号法求下图中s→t的最大流量,并找出该网络的最小割.ε(v2)=min{ε(s),(cs2-fs2)}=2ε(v1)=min{ε(v2),f12}=min{2,4}=2ε(v3)=min{ε(v1),(c13-f13)}=min{2,5}=2ε(v4)=min{ε(v3),f43}=min{2,1}=1ε(t)=min{ε(v4),(c4t-f4t)}=min{1,2}=1sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)V*(f)==９＋５－０＝１４sv2v4v3v1t7(6)8(8)9(5)5(3)2(0)9(9)6(0)10(9)5(5)(-v2,1)(0,)(v1,1)(s,1)KK4

2

第8章网络分析23最大流问题例

求网络的最大流与最小截集

12st2st32st3t31s1st3st321287

12122

4

13

3

2

95

3

11

=8

=2

=2

=2

=5

=18101221823242352461112s1235243813213tf(

X*

)

=

20

(

S*,S*)

={

(s,1),(s,2),(s,3)

}作业：求下图所示网络中的最大流，弧旁数为(1,1)v2v1v4v3vsvt(3,3)(5,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)

13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)作业：求下图所示网络中的最大流，弧旁数为

13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)5解866858924944010511427最大流：11+9=20最小割：5+6+9=20第8章网络分析27最大流问题例

分配问题A

B

CD√

√

甲乙

丙需求量√

√

√√

√1020

15

10加工件数

181918

55第8章网络分析28最大流问题

A

BCD甲：√

√

18乙：√

√

√19丙：

√√

18

102015

10甲乙丙ABCDSt18，18，18，19，18，19，18，19，18，19，15，10，10，20，101002019191158701880=10

11111080910117例：S公司是的产品的生产地：为A和B两地，生产出的产品发送到两个一级配送中心—C和D进行储存，然后由再送到运送到全国各大分销公司（E1,E2）进行销售。下表给出了每月各个产地的产量、每个零售店的需求量以及各地之间的运输能力。

到从运输能力产量CDA211825B352040

到从运输能力E1E2

C1530

D1825

需求量2045

第8章网络分析30最小费用最大流问题基本概念

一、最小费用流

(1)

运价

设X是网络N=(V,A)的一个可行流,定义实值函数c(i,

j

)

=

cij≥0，

∀(i,

j

)

∈A表示该弧输送单位流量的费用，简称运价；

(2)

可行流的费用c(X)=Σ

cijxij(i,

j)∈A(3)

最小费用流

在流量为

f

的一切可行流中，若X费用为最小，则称X为流量为

f

的最小费用流。第8章网络分析31最小费用最大流问题

二、最小费用增广链

(1)

增广链的费用设：(X

)——

可行流

X

的增广链

X’

——

沿着

(X

)以

=

1去调整

X

而得到的一个新可行流则增广链

(X

)的费用定义为：c(

)

=c(

X’

)-c(

X

)

由xij'=

xij–1,(i,

j

)∈-

xij+1,(i,

j

)∈

xij,(i,

j

)

∈第8章网络分析32最小费用最大流问题得故有c(

)=c(

X')

–c(X)

=

Σ

cij

xij'(i,

j)∈A

=

Σ

cij(xij′–

xij)(i,

j)∈A=

Σ

cij(xij'

–

xij)(i,

j)∈

+

Σ

cij(xij'

–

xij)(i,

j)∈-

=

Σ

cij(i,

j)∈–

Σ

cij(i,

j)∈-xij'

–

xij=

–

1,(i,

j

)∈-

1,

(i,

j

)∈

0

,

(i,

j

)

∈+

Σ

cij(xij'

–

xij)(i,

j)

∈

-

Σ

cij

xij(i,

j)∈A第8章网络分析33最小费用最大流问题即

Σ

cij(i,

j)∈–

Σ

cij(i,

j)∈-c(

)=

(2)

最小费用增广链在所有关于X的增广链中,若(X)的费用最小,则称(X)为关于X的最小费用增广链。

三、对偶网络

设X

=

{

xij

}

是网络N=(V,A)的一个可行流,则称按下述方法所构造的一个对应于N

和X

的新网络N’(

X）=(D’,w)为关于可行流X

的对偶网络:

(1)

N’的结点与

N

的结点完全一致；

(2)

根据

N

中的每一弧(i,

j)∈

A及其流量

xij,确定

N’

的弧及其权数如下：第8章网络分析34最小费用最大流问题ijcijijcij–

cijij–

cij

(ⅰ)

若

xij

=0(

零流弧

)，则保留原弧，令wij=cij

，即

(ⅱ)

若

0

<

xij

<

rij(

非零流、非饱和弧

)则保留原弧，并增加一条反向弧，令

wij=

cij，wji

=

–

cij，即

(ⅲ)

若xij

=

rij

(

饱和弧

)，则将原弧反向，令

wij=

–

cij，即第8章网络分析35最小费用最大流问题(a)中弧旁数字为：

cij，rij，xij

(b)中弧旁数字为：wij3,

7,

75,6,42,8,71,

4,

4s12t1,

6,

0(a)N及X图8-25-2-3-5-1s12t(b)N

(

X）′521如下图第8章网络分析368.5最小费用最大流问题

8.5.

2

对偶法

一、基本思想沿着最小费用增广链调整当前可行流。

对偶网络始点到终点的最短路就能给出最小费用增广链。二、基本步骤

1°取零流X0={xij(0)=0

}为初始流，令k=0。

2°构造关于最小费用流Xk={xij(k)}的对偶网络

N’(X),从中寻找始点s

到终点t的最短路。

3°若N’(

Xk)中不存在从

s到

t的最短路，则Xk就是最小费用最大流,

算出c(Xk)

，停止；否则，在原网络N中，对应于

N’(Xk）的最短路

来构成最小费用增广链

(Xk)。

4°沿着(Xk)调整当前流，得到新的最小费用流

Xk+1={xij(k+1)}

。

5°令k:=k+1，返2°。第8章网络分析37最小费用最大流问题例

在右图中，求最小费用最大流。

弧旁数字为：

cij，rij3,75,62,81,4s12t1,6解

取零流X0为初始流。3,7,

05,6,02,8,0

1,4,

0s12t1,6,

0(a)X03521s12t1(b)N’(

X0）

=4

第8章网络分析38最小费用最大流问题

=

43,7,

05,6,02,8,41,4,

4s12t1,6,

4(a)X1352-1s12t1(b)N’(

X1）-1-23,7,

45,6,02,8,8

1,4,

4s12t1,6,

4(a)X235-3-1s12t1(b)N’(

X2）-1-2

=

3第8章网络分析39最小费用最大流问题

X*=X3

，f*

=

11

，c(X*)=2(8)+5(3)+1(1)

+3(7