- 在线时间
- 791 小时
- 最后登录
- 2022-11-28
- 注册时间
- 2017-6-12
- 听众数
- 15
- 收听数
- 0
- 能力
- 120 分
- 体力
- 36312 点
- 威望
- 11 点
- 阅读权限
- 255
- 积分
- 13854
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 616
- 主题
- 542
- 精华
- 12
- 分享
- 0
- 好友
- 225
TA的每日心情 | 开心 2020-11-14 17:15 |
|---|
签到天数: 74 天 [LV.6]常住居民II
 群组: 2019美赛冲刺课程 群组: 站长地区赛培训 群组: 2019考研数学 桃子老师 群组: 2018教师培训(呼伦贝 群组: 2019考研数学 站长系列 |
1 最大流问题的数学描述
# l+ b- P. l! g: j, r1.1 网络中的流 定义
: ~) |( t2 T' W q1 _在以V 为节点集, A 为弧集的有向图G = (V, A) 上定义如下的权函数:
0 X1 M5 u/ t X* ?5 W Q( O8 O* d1 y) K# \
(i) L : A → R 为孤上的权函数,弧 (i, j)∈ A 对应的权 L(i, j) 记为 ,称为孤 (i, j) 的容量下界(lower bound);
/ X' J8 G0 j& d) h& h* Z0 c X5 f# X' P
(ii)U : A → R 为弧上的权函数,弧(i, j)∈ A对应的权U(i, j) 记为 ,称为孤 (i, j) 的容量上界或容量(capacity);+ w; U) P$ g0 ]( Y) h
9 @0 M* \1 e2 T T& E
(iii) D :V → R 为顶点上的权函数,节点i ∈V 对应的权 D(i) 记为 ,称为顶 点i 的供需量(supply/demand);
3 R! w2 v2 X- F6 [0 t* P% e |% |7 E
此时所构成的网络称为流网络,可以记为 N = (V, A, L,U,D) 。 由于我们只讨论V, A 为有限集合的情况,所以对于弧上的权函数 L,U 和顶点上的 权函数 D ,可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示,因此 L,U, D 有时直接称为权向量,或简称权。由于给定有向图G = (V, A) 后,我们总是可 以在它的弧集合和顶点集合上定义各种权函数,所以流网络一般也直接简称为网络。
( }% \, y9 ]4 k
$ _( Y& C9 \$ t' V在流网络中,弧(i, j) 的容量下界 和容量上界表示的物理意义分别是:通过该 弧发送某种“物质”时,必须发送的最小数量为 ,而发送的最大数量为 。顶点i ∈V 对应的供需量则表示该顶点从网络外部获得的“物质”数量( > 0时),或从该顶 点发送到网络外部的“物质”数量(< 0 时)。下面我们给出严格定义。
7 J& N: {5 K* H4 \; `8 F7 x$ |% d& ]" M! b! n" B- I
可行流(feasible flow)
; w# p8 S9 n" C. M* b! U* A$ \* `( l8 s! j; C2 Q. A# Z& M
![]()
/ F+ ~- s0 U3 c6 K0 d2 S7 d4 n) P- d, W8 \8 t+ d; q, ]
1 |4 Q; v0 u6 G, \5 c
可见,当 di > 0时,表示有di 个单位的流量从网络外部流入该顶点,因此顶点i 称 为供应点(supply node)或源(source),有时也形象地称为起始点或发点等;当di < 0 时,表示有|di | 个单位的流量从该顶点流失到网络外部(或说被该顶点吸收),因此顶 点i 称为需求点(demand node)或汇(sink),有时也形象地称为终止点或收点等;当 di = 0时,顶点i 称为转运点(transshipment node)或平衡点、中间点等。此外,根据 (1)可知,对于可行网络,必有' y, v3 K. w- \' [4 I
/ H) P) p; T3 T9 ~![]()
4 Y$ |& \: e# o' }* h. j/ [% L+ ^9 |1 |' V U# F1 t
也就是说,所有节点上的供需量之和为 0 是网络中存在可行流的必要条件
4 u3 \7 v! Q w9 \8 V+ [5 o, G' g
( `3 T/ U9 c& U6 B 6 P3 z& L1 f ?& s* \% |
5 t; |9 O% o$ `5 G& }0 ]' q8 e9 g- T
1 H" ?- N E. s0 q7 s. T
1.2 最大流问题6 Y4 \% G; O) b. y) a
考虑如下流网络 N = (V, A,U,D):节点 s 为网络中唯一的源点,t 为唯一的汇点, 而其它节点为转运点。如果网络中存在可行流 f ,此时称流 f 的流量(或流值,flow value)为 (根据(3),它自然也等于 − ),通常记为v 或v( f ) ,即
# g5 w+ E! b) E9 q6 Z( o' e1 M, s$ d1 W$ f# p
![]()
; Y5 ^) m0 f; p& Q+ @, q2 e对这种单源单汇的网络,如果我们并不给定 和 (即流量不给定),则网络一 般记为 N = (s,t,V, A,U) 。最大流问题( maximum flow problem )就是在 N = (s,t,V, A,U) 中找到流值最大的可行流(即最大流)。我们将会看到,最大流问题 的许多算法也可以用来求解流量给定的网络中的可行流。也就是说,当我们解决了最大 流问题以后,对于在流量给定的网络中寻找可行流的问题,通常也就可以解决了。) T& o% t$ o) u7 F
4 _/ E9 E# X. d; b5 i用线性规划描述最大流问题
9 S; G7 j5 A s {+ o/ W) L7 x因此,用线性规划的方法,最大流问题可以形式地描述如下:
( q! H3 |# Q% j1 L- Z4 `. x5 h: q# E% D8 [5 `# O
![]()
$ L# o0 f, W' Z) |* j, a3 M* V
+ R+ G3 {5 y* j* |. a定义】 如果一个矩阵 A 的任何子方阵的行列式的值都等于0,1或 −1,则称 A 是 全幺模的(totally unimodular TU,又译为全单位模的),或称 A 是全幺模矩阵。
$ |2 W _- Y9 m8 C9 O
% R$ z: |' K& [! {+ J: ^! c" \( w整流定理
, }& n2 i2 ~& T# G" o2 Y& {3 d' M# U【定理 7】(整流定理) 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量 均为正整数,则问题的最优解为整数解。 最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点,解决这个问 题的方法较之线性规划的一般方法要方便、直观得多。
1 r- q: E8 C" }5 r
4 Y9 b6 ~3 r3 d0 V+ m1.3 单源和单汇运输网络9 U6 c1 N8 ]( o! _
多源多汇网络 转化成单源单汇网络 K7 @. ~$ G2 U& d
实际问题往往是多源多汇网络,为了计算的规格化,可将多源多汇网络G 化成单 源单汇网络G' 。设 X 是G 的源,Y 是G 的汇,具体转化方法如下:
8 y$ Y+ [! ?; k2 z
% Y+ l t: b6 w5 V D# T! U(i)在原图G 中增加两个新的顶点 x 和 y ,令为新图G' 中之单源和单汇,则G 中 所有顶点V 成为G' 之中间顶点集。
H5 X" ~- m" @ \- F% H
, w1 L. I: _" \4 }8 E9 }(ii)用一条容量为∞的弧把 x 连接到 X 中的每个顶点。
7 r/ V% u$ h7 D) h6 w8 T! W
- {! {4 d: {) F8 l/ y(iii)用一条容量为∞的弧把Y 中的每个顶点连接到 y 。 G 和G' 中的流以一个简单的方式相互对应。若 f 是G 中的流,则由; e# Q2 [9 B. `+ M
- G% m5 g5 ~$ a/ a' P7 ?* j6 h/ N ( i9 i# @5 P' o7 a2 C5 i/ A; T
, y( M$ X5 X) t
2 最大流和最小割关系割的容量![]()
% T* G4 f y0 f8 x! L3 u- h& ~; w' H( N0 A( C0 n
( u3 L1 w3 k& p/ m" ]
- x* U0 H8 D' Y) H则在这条可增广轨上每条前向弧的流都可以增加一个量δ ,而相应的后向弧的流可减 少δ ,这样就可使得网络的流量获得增加,同时可以使每条弧的流量不超过它的容量, 而且保持为正,也不影响其它弧的流量。总之,网络中 f 可增广轨的存在是有意义的, 因为这意味着 f 不是最大流。
) x/ _9 P* v& g6 [4 m# c# r+ y: }0 w/ U: G/ d. A
3 最大流的一种算法—标号法4 K+ |- h* p6 {
标号法是由 Ford 和 Fulkerson 在 1957 年提出的。用标号法寻求网络中最大流的基 本思想是寻找可增广轨,使网络的流量得到增加,直到最大为止。即首先给出一个初始 流,这样的流是存在的,例如零流。如果存在关于它的可增广轨,那么调整该轨上每条 弧上的流量,就可以得到新的流。对于新的流,如果仍存在可增广轨,则用同样的方法 使流的值增大,继续这个过程,直到网络中不存在关于新得到流的可增广轨为止,则该 流就是所求的最大流。' _6 y4 Z: P) [/ I. d5 y+ a
' @" `# z1 M+ P# H
这种方法分为以下两个过程:* ?* a' h; p- A' I5 {# e
& `1 `8 [2 v. {3 k7 N) [% jA.标号过程:通过标号过程寻找一条可增广轨。5 t+ a# l0 T. h; {" ]8 M" f
! t& D5 R; ?5 Y, S
B.增流过程:沿着可增广轨增加网络的流量。
3 t4 C, d& O9 p' I3 s7 S+ d- N, |1 P4 v! M7 ]) S. g6 r
这两个过程的步骤分述如下。
6 B* n. F* k5 |! F& d7 p
; F4 R6 x N3 w9 P( X(A)标号过程:/ a( A* A j0 W! v: @- z
0 v5 l2 [: r1 V) L' S9 S# \
![]()
- V7 _5 s$ ~/ O; G2 g/ a/ v$ M0 b) R `
(B)增流过程 8 A* U' s5 T9 V" _8 P
. r Y0 j: e! [/ `1 p( D, T
网络最大流 x 的求解步骤/ P6 l. l4 ]& D
求网络 N = (s,t,V, A,U) 中的最大流 x 的算法的程序设计具体步骤如下:
$ k9 V0 h+ c+ L' `5 ?% ~7 w# c; N0 l# W8 F9 m
对每个节点 j ,其标号包括两部分信息 (pred( j),maxf(j)). \. c. |, [, t
z+ T7 r' x3 \6 q' c4 ~3 M" ?: f- ]
该节点在可能的增广路中的前一个节点 pred( j) ,以及沿该可能的增广路到该节点为止 可以增广的最大流量 maxf( j)。 L) k0 E. Y& ~8 b6 n! Q
! G+ L0 I1 B: [* x8 {
![]()
( P6 l9 u* t- z- d4 ]# G" |! ^* I3 j! Z
并将 j 加入 LIST 中。 例 17 用 Ford-Fulkerson 算法计算如图 6 网络中的最大流,每条弧上的两个数字分 别表示容量和当前流量。 ![]()
- c. b: t# _- N p, U9 H2 h
; `) c/ F. e' L% [- Z J, I
( `$ r# h7 m) i8 ~5 T) I解 编写程序如下:" K3 _8 T, q! H. p; `0 `
4 J" t: ]1 U- r( x
clc,clear1 M! r$ m% J9 a+ K$ s
u(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;
% W1 n: H) p6 h( Z4 q, mu(3,5)=1;u(4,3)=3;u(4,5)=3;4 L$ E! O3 d7 H0 p7 c( _
f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1;
$ E% y2 B% @0 d5 ff(3,5)=1;f(4,3)=1;f(4,5)=0;
* l0 M# r( {. Z, S' An=length(u);list=[];maxf(n)=1;
& Z5 B( d! ?2 \4 u$ V0 {8 M0 H0 B' T/ ^while maxf(n)>06 o- ^ g4 G8 G0 I
maxf=zeros(1,n);pred=zeros(1,n);
0 ?" _" y" |) m3 Dlist=1;record=list;maxf(1)=inf;
- y9 ^: _' F. C" }2 h ^. r % list是未检查邻接点的标号点,record是已标号点 \( p' M2 j9 s$ u& U m; a m1 M
while (~isempty(list))&(maxf(n)==0)
. L! r! i1 x3 J5 _/ N3 O" G+ ? flag=list(1);list(1)=[];/ y+ q, |5 [) V& ]# N0 K
label1= find(u(flag, -f(flag, );
! d' C0 c. ^: J5 s. c w) j label1=setdiff(label1,record);
- w4 m( b# s& o# G1 P list=union(list,label1); c. a, d4 M! L" ^) p% N5 i! H
pred(label1)=flag;- _3 y( X$ B3 q, ^ c: F
maxf(label1)=min(maxf(flag),u(flag,label1)...! r$ V4 r$ g# Y
-f(flag,label1)); u0 K' f, L1 V$ |
record=union(record,label1);
+ `; V# z' j7 @+ [ label2=find(f(:,flag));
7 T U# Z) c, w1 x' v# L label2=label2';
8 f! o- K* C! g% X8 ?3 | label2=setdiff(label2,record);
4 @# m# Q5 h, _ list=union(list,label2);
8 p2 c/ u& R3 N; c pred(label2)=-flag;
* v. e- ^+ U, D+ e maxf(label2)=min(maxf(flag),f(label2,flag));
7 V! C; G7 I( {9 x& p record=union(record,label2);
& T m& h( _( a1 n3 ?( B end6 T. m7 A9 X* l/ ~
if maxf(n)>0
9 p" k- S5 q$ S& v' _ v2=n; v1=pred(v2);
7 C6 t* e9 |7 y k while v2~=1
5 t. ~% d, j F; U4 i7 k if v1>0
+ `3 U! C+ v+ \7 W$ ~4 F f(v1,v2)=f(v1,v2)+maxf(n);
3 F" L* B! a6 n; i8 a else% t: |, b7 o) C6 x7 r
v1=abs(v1);
9 x6 O, S& x1 g f(v2,v1)=f(v2,v1)-maxf(n);
# ?9 T% M4 C) }& X) h end* c# o* s4 @* b7 G& I/ v: o3 `2 M
v2=v1; v1=pred(v2);# Y- B3 a3 C$ R$ j
end
( Z: q1 ]+ M- w! C3 O) M end0 z6 u: O$ A t! |2 [
end
* j$ G4 n; Y9 u% R# }7 if
2 d/ ~& @, C# v% U0 I例18 现需要将城市 s 的石油通过管道运送到城市t ,中间有4个中转站 v1 ,v2 ,v3 和 v4 ,城市与中转站的连接以及管道的容量如图7所示,求从城市 s 到城市t 的最大流。
" g4 _# b, E$ Z2 l. ^; Z/ ]$ @, r1 q6 f& ], F. s- s
! N3 e- E8 c7 z1 r( j4 Y* J6 ~![]()
7 R$ ^& W4 O0 P) F, X1 a; R1 d
( T- z/ B/ i0 D0 S! V g" F# N8 P解 使用最大流的数学规划表达式,编写LINGO程序如下:
# v2 |! o; g, m; W1 v* i8 V7 R3 p. P
model:
9 @6 d, H7 Z% X+ x6 Gsets:1 `8 Y8 q0 I1 u1 ^# f& m: B, [
nodes/s,1,2,3,4,t/;8 v/ w; Y0 V7 D
arcs(nodes,nodes)/s 1,s 3,1 2,1 3,2 3,2 t,3 4,4 2,4 t/:c,f;
$ g# Q/ E& O2 t2 q u. ~endsets4 N- K- W% ?; W& x# W1 m
data:
, {' n9 T1 U' l; Y* Bc=8 7 9 5 2 5 9 6 10;
3 R5 d7 i( c. e1 s( ]) j( b, U9 ], }enddata0 \- b: \0 L3 w- f1 G% F
n=@size(nodes); !顶点的个数;
8 c$ @3 l( P5 B; G2 L! F7 imax=flow;
3 s' v R, x* Z' a- H@for(nodes(i)|i #ne#1 #and# i #ne# n:
& C, R i1 P& }/ F: n6 I @sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i): h6 Q. B$ k2 c' `4 b9 ~
@sum(arcs(i,j)|i #eq# 1:f(i,j))=flow;2 b$ R9 V: R2 F5 p2 ~9 e8 Q
@sum(arcs(i,j)|j #eq# n:f(i,j))=flow;
; x6 B4 o. [" w! }: C* ~$ P$ ]. C v" `@for(arcs bnd(0,f,c));
3 m$ E) [$ i; E* _end
# m* }% P! r$ f0 l
7 U- s: U& R# v! {8 ^: X在上面的程序中,采用了稀疏集的编写方法。下面介绍的程序编写方法是利用赋权邻 接矩阵,这样可以不使用稀疏集的编写方法,更便于推广到复杂网络。
- C3 q$ a- C# V) P" G4 N1 r( B( d `! g, O" T. k8 g
model:6 }6 R$ r: ~9 J
sets:
0 D5 i/ s* |! L# K% y. c! `nodes/s,1,2,3,4,t/;$ I" N* y/ e" K" o- e+ z0 z% y
arcs(nodes,nodes):c,f;( w" p# W2 p" k- r2 y0 d* k, X
endsets
& H, r) y4 q0 ]) J xdata:
1 {1 b8 I0 P3 Q/ M4 cc=0;
! V" \2 q# S9 l/ ]@text('fdata.txt')=f;
. u8 }* r5 I5 f* ]enddata
4 u! L( {- V/ ?3 n3 Y2 q% S# `calc:
0 x }# O* x |4 ]c(1,2)=8;c(1,4)=7;* Y% H5 u; q9 y
c(2,3)=9;c(2,4)=5;5 ^$ ~ J" S1 C( C3 j; A
c(3,4)=2;c(3,6)=5;/ `/ _/ V* g( U5 W
c(4,5)=9;c(5,3)=6;c(5,6)=10;. Q! ?% }2 t; ]+ D2 |, O2 {) j
endcalc
, b2 C7 B) R* }' G4 zn=@size(nodes); !顶点的个数;
! U. i' h/ {2 o( O7 a' fmax=flow;1 O0 c. r- ^$ R5 h: r
@for(nodes(i)|i #ne#1 #and# i #ne# n:) W' W5 i& Q5 k- J
@sum(nodes(j):f(i,j))=@sum(nodes(j):f(j,i)));9 y3 V- v U* U7 x/ n
@sum(nodes(i):f(1,i))=flow; x$ `5 X# h9 R) v) |4 z
@sum(nodes(i):f(i,n))=flow;; w) u2 g5 N2 [0 h- @ U- ~. H
@for(arcs bnd(0,f,c));
4 p* V- @+ j- U: Aend
: \# Z. U# w$ @- S$ }
7 ^0 ?2 h1 D5 O7 R5 S& @————————————————
S5 N/ K2 T% f7 f6 y版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
Y, X/ x' y ]9 t2 y/ V% v原文链接:https://blog.csdn.net/qq_29831163/article/details/89786313( \+ v& Z2 M1 E: q2 J' \& L
. g+ H* J8 `" b$ C) P0 l0 t1 b/ ]" S3 w! |6 U8 m N( Z
|
zan
|