- 在线时间
- 791 小时
- 最后登录
- 2022-11-28
- 注册时间
- 2017-6-12
- 听众数
- 15
- 收听数
- 0
- 能力
- 120 分
- 体力
- 36450 点
- 威望
- 11 点
- 阅读权限
- 255
- 积分
- 13896
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 616
- 主题
- 542
- 精华
- 12
- 分享
- 0
- 好友
- 225
TA的每日心情 | 开心 2020-11-14 17:15 |
|---|
签到天数: 74 天 [LV.6]常住居民II
 群组: 2019美赛冲刺课程 群组: 站长地区赛培训 群组: 2019考研数学 桃子老师 群组: 2018教师培训(呼伦贝 群组: 2019考研数学 站长系列 |
1 最大流问题的数学描述% L* u2 J) E% x2 D% p; M
1.1 网络中的流 定义4 c9 \0 f0 c6 _2 \+ [
在以V 为节点集, A 为弧集的有向图G = (V, A) 上定义如下的权函数:
" Q% w+ j. P* c* J/ W6 b
# v2 J+ X! O( ?(i) L : A → R 为孤上的权函数,弧 (i, j)∈ A 对应的权 L(i, j) 记为 ,称为孤 (i, j) 的容量下界(lower bound);
2 C! f* S" g5 o- Z% ?+ s" Y% Y8 s6 Y; H1 y# k" L
(ii)U : A → R 为弧上的权函数,弧(i, j)∈ A对应的权U(i, j) 记为 ,称为孤 (i, j) 的容量上界或容量(capacity);
2 j3 [% ^& j- x5 L* [+ d* `3 y
(iii) D :V → R 为顶点上的权函数,节点i ∈V 对应的权 D(i) 记为 ,称为顶 点i 的供需量(supply/demand);
& U; T. D4 w, |% E- X& h7 O1 z8 `7 m, m; l/ y
此时所构成的网络称为流网络,可以记为 N = (V, A, L,U,D) 。 由于我们只讨论V, A 为有限集合的情况,所以对于弧上的权函数 L,U 和顶点上的 权函数 D ,可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示,因此 L,U, D 有时直接称为权向量,或简称权。由于给定有向图G = (V, A) 后,我们总是可 以在它的弧集合和顶点集合上定义各种权函数,所以流网络一般也直接简称为网络。
V' Z* k1 Q9 n: ~5 P' x: A* X: n
/ D) V9 R$ w, e+ q& ?" A在流网络中,弧(i, j) 的容量下界 和容量上界表示的物理意义分别是:通过该 弧发送某种“物质”时,必须发送的最小数量为 ,而发送的最大数量为 。顶点i ∈V 对应的供需量则表示该顶点从网络外部获得的“物质”数量( > 0时),或从该顶 点发送到网络外部的“物质”数量(< 0 时)。下面我们给出严格定义。
2 K. l5 M7 {7 @, @: ]9 }% |( s8 z* z1 G- E. F. |: m
可行流(feasible flow)+ D1 R& p+ |) p3 @+ N
' o; w; i7 ~2 z' f; R & q0 ^1 u8 R7 k; g) X3 _
) N* f7 ~" D1 T/ Z+ Q; S
& f# W/ O v' ?可见,当 di > 0时,表示有di 个单位的流量从网络外部流入该顶点,因此顶点i 称 为供应点(supply node)或源(source),有时也形象地称为起始点或发点等;当di < 0 时,表示有|di | 个单位的流量从该顶点流失到网络外部(或说被该顶点吸收),因此顶 点i 称为需求点(demand node)或汇(sink),有时也形象地称为终止点或收点等;当 di = 0时,顶点i 称为转运点(transshipment node)或平衡点、中间点等。此外,根据 (1)可知,对于可行网络,必有
O/ ^7 b8 n/ L. |7 Z4 y4 s% s9 S& o' V, ]; |/ L3 d* @# Y- [' r
7 O/ x9 R5 m) l! B- b* l2 d8 t P# f
; x) J B+ H+ h# M7 W7 W& e也就是说,所有节点上的供需量之和为 0 是网络中存在可行流的必要条件
5 X1 A9 J" g# ~) v! t: l+ c; O6 [0 a, L u! ?
" L+ ?0 G$ R( L& e; x
![]()
1 h" U! Q L7 z3 X- ?; D$ k0 ^% }# q4 k! [0 J9 J
1.2 最大流问题1 i9 _7 r, F# c% ]& U- Q
考虑如下流网络 N = (V, A,U,D):节点 s 为网络中唯一的源点,t 为唯一的汇点, 而其它节点为转运点。如果网络中存在可行流 f ,此时称流 f 的流量(或流值,flow value)为 (根据(3),它自然也等于 − ),通常记为v 或v( f ) ,即, b( l6 p* f# y6 H* L% H
( E3 r ]0 m8 U9 I
![]()
- A8 N6 X0 P: ~# l对这种单源单汇的网络,如果我们并不给定 和 (即流量不给定),则网络一 般记为 N = (s,t,V, A,U) 。最大流问题( maximum flow problem )就是在 N = (s,t,V, A,U) 中找到流值最大的可行流(即最大流)。我们将会看到,最大流问题 的许多算法也可以用来求解流量给定的网络中的可行流。也就是说,当我们解决了最大 流问题以后,对于在流量给定的网络中寻找可行流的问题,通常也就可以解决了。0 }3 ~2 ]; \, p7 ?. q0 E% O% T
& |7 z: I c6 t- w; Q6 ~. q/ c用线性规划描述最大流问题
7 a9 N, E! c0 g$ s7 }2 s5 P2 [因此,用线性规划的方法,最大流问题可以形式地描述如下:
5 W5 \- }" M7 a: k' ]. v; \2 d
, H L; t; [; H; Y0 {9 D9 ?* \: c![]()
# d- R. a- Z# _, d9 R6 b
) z, ]; ^2 }3 Q) s t定义】 如果一个矩阵 A 的任何子方阵的行列式的值都等于0,1或 −1,则称 A 是 全幺模的(totally unimodular TU,又译为全单位模的),或称 A 是全幺模矩阵。/ O5 d" q9 o5 [" ^, ]# n
3 n8 p0 Q9 y! O
整流定理6 H/ v x/ ?/ G2 u# h2 W8 q
【定理 7】(整流定理) 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量 均为正整数,则问题的最优解为整数解。 最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点,解决这个问 题的方法较之线性规划的一般方法要方便、直观得多。4 o1 \. S* @5 n" B& C1 F
2 g6 J$ `. ~+ |% k: m6 K4 p1.3 单源和单汇运输网络
( @% [2 p. n" w: f多源多汇网络 转化成单源单汇网络* n& b3 i3 I- [' m( y, k; w- ~/ g
实际问题往往是多源多汇网络,为了计算的规格化,可将多源多汇网络G 化成单 源单汇网络G' 。设 X 是G 的源,Y 是G 的汇,具体转化方法如下:4 n7 l3 Z8 O* x
3 q# ^; D* ]: K7 U( @7 L
(i)在原图G 中增加两个新的顶点 x 和 y ,令为新图G' 中之单源和单汇,则G 中 所有顶点V 成为G' 之中间顶点集。
0 U4 m. B& W* _+ [1 m$ d9 B& E( [: i$ ]9 E8 c
(ii)用一条容量为∞的弧把 x 连接到 X 中的每个顶点。7 s. C8 H) w8 [4 s
- S# ]- I0 D! Z9 q/ [# ?( l(iii)用一条容量为∞的弧把Y 中的每个顶点连接到 y 。 G 和G' 中的流以一个简单的方式相互对应。若 f 是G 中的流,则由! w3 N: [ k$ I7 y5 n1 h8 x
6 L& x- m. x% U* V
9 X4 Q* Z3 H! I* u# w3 Y w. v
! j# s. [- G- a) x! }2 最大流和最小割关系割的容量![]()
: x9 C9 {8 `" N8 z
. S4 [& k% I/ F# ^. Y ( F3 Y! a4 w3 c+ h7 }3 {$ H: e; l. d# u
4 N; e+ R4 G+ j2 h+ `则在这条可增广轨上每条前向弧的流都可以增加一个量δ ,而相应的后向弧的流可减 少δ ,这样就可使得网络的流量获得增加,同时可以使每条弧的流量不超过它的容量, 而且保持为正,也不影响其它弧的流量。总之,网络中 f 可增广轨的存在是有意义的, 因为这意味着 f 不是最大流。4 \- ]# R3 ?- W F6 F6 ^
: B) c( w% U1 n/ T1 D3 最大流的一种算法—标号法! K0 a3 L: u% S$ B$ }5 ]( N
标号法是由 Ford 和 Fulkerson 在 1957 年提出的。用标号法寻求网络中最大流的基 本思想是寻找可增广轨,使网络的流量得到增加,直到最大为止。即首先给出一个初始 流,这样的流是存在的,例如零流。如果存在关于它的可增广轨,那么调整该轨上每条 弧上的流量,就可以得到新的流。对于新的流,如果仍存在可增广轨,则用同样的方法 使流的值增大,继续这个过程,直到网络中不存在关于新得到流的可增广轨为止,则该 流就是所求的最大流。
. b7 q$ z' m) s; A0 \
, z, ?0 o+ W0 j: u这种方法分为以下两个过程:
* O" f' P2 n3 N' f) W9 m1 C1 ~2 O/ _5 \5 i+ w5 S, E) ^
A.标号过程:通过标号过程寻找一条可增广轨。# |$ i& |+ z! \6 m0 n6 P3 d
' O3 ?+ s$ x- [5 |1 g0 T# h
B.增流过程:沿着可增广轨增加网络的流量。; r/ b5 I9 ?' t9 a. G
) V3 p7 h9 Y% W x+ x% ^: R3 q; ~( X C这两个过程的步骤分述如下。
- h/ V' o& N; e1 y
# k- B- C' W6 W' N/ L8 U: s9 p) g% C(A)标号过程:
* G( q, Y2 V- h) F! Q& `$ N
4 S4 h; ^) d2 ]5 _ 0 H d$ v& u+ @
8 L8 w8 k$ l" H+ f(B)增流过程 6 U; s4 o/ O9 K; U% r9 d
: [) v- {- m" g8 D/ ^& B网络最大流 x 的求解步骤
. t- X% U0 Q+ w; g ?8 b8 y4 m求网络 N = (s,t,V, A,U) 中的最大流 x 的算法的程序设计具体步骤如下:0 W! y$ m& w7 M) @; S- l3 b* k- d/ t% z
+ c: l4 a: f y' E' v1 b8 O对每个节点 j ,其标号包括两部分信息 (pred( j),maxf(j))- s: A- ?( j9 g* r
& t1 _: k% T i ` S4 p
该节点在可能的增广路中的前一个节点 pred( j) ,以及沿该可能的增广路到该节点为止 可以增广的最大流量 maxf( j)。
+ C3 b' I3 {$ ?& c
4 ?+ v( K1 j+ W: }8 y1 B: O 3 q) M- y( y% r# o0 x* B! R7 U
$ E2 j0 R! z, E) I3 y. I并将 j 加入 LIST 中。 例 17 用 Ford-Fulkerson 算法计算如图 6 网络中的最大流,每条弧上的两个数字分 别表示容量和当前流量。 9 Z1 x+ F6 w9 c0 s; V) `4 D% j0 Y* f$ T
2 v) C6 W/ l3 E& V+ `* G& l- a' S- q1 t1 }$ J5 S; |
解 编写程序如下:
; A6 }6 ~ _2 F1 X/ P/ e6 A" y0 |+ w6 @$ L
clc,clear, H0 K/ x# w: u4 Q F$ A# l2 _
u(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;$ }7 J! s) C& ~( Y* K; D0 C
u(3,5)=1;u(4,3)=3;u(4,5)=3;
! L5 ]' t, {/ p( D. U; s* tf(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1;* }& }7 B. Z* b' S& V1 L+ }1 C
f(3,5)=1;f(4,3)=1;f(4,5)=0;
) f3 ?( A7 w/ A) H2 \n=length(u);list=[];maxf(n)=1;# L- C5 h, P: \# D) a
while maxf(n)>0
, p. q8 J1 f" B' n, fmaxf=zeros(1,n);pred=zeros(1,n);
' ]& a6 p7 E: H0 ^( O+ Glist=1;record=list;maxf(1)=inf;
0 I7 ~& V7 E- B' q8 O % list是未检查邻接点的标号点,record是已标号点. h; ^+ S( D7 c8 U& s" d6 B
while (~isempty(list))&(maxf(n)==0)
& ~1 _5 o# X ^0 D1 G- J6 R flag=list(1);list(1)=[];- F4 \1 y' z a' w) @
label1= find(u(flag, -f(flag, );
/ ]2 |: a* W% C label1=setdiff(label1,record);
' B5 s+ n* K. I4 r, p9 d list=union(list,label1);
6 a$ y3 j3 S m/ P0 P2 M) L pred(label1)=flag;
. ?7 s' V/ S. E1 |: W( M7 ? maxf(label1)=min(maxf(flag),u(flag,label1)...
3 u& [6 [5 J7 L; ]( a! w -f(flag,label1));
7 [3 J2 Z$ G$ k% q record=union(record,label1);; P1 q1 ~ a z3 F
label2=find(f(:,flag));
# D0 O6 V1 a7 E9 y' x+ ^* G label2=label2';
, {6 o+ z5 M x7 t1 K8 s# | label2=setdiff(label2,record);' P* T( D, @" S2 p/ _* q5 U
list=union(list,label2);
# L) k3 C$ S w3 i# S- E+ N2 P9 P pred(label2)=-flag;
5 V0 e5 w# A+ q5 L maxf(label2)=min(maxf(flag),f(label2,flag)); G z. F' ]+ s. N
record=union(record,label2);* r* J: P+ X( y8 C- T# ]/ B3 S
end
& ]; I( f. |& I& W9 r' X" C if maxf(n)>0- `% H) u) S/ j! W+ r" w- Z
v2=n; v1=pred(v2);
% H: ^. Z# d, j while v2~=1
, A; ~: M2 _4 L0 v if v1>0
) W- p+ Y m/ ]7 v/ M$ {/ K7 e f(v1,v2)=f(v1,v2)+maxf(n);" ]) j, }5 O9 t5 [
else
; k( @1 l. S, C v1=abs(v1);$ i; [& l% E: K0 o0 j
f(v2,v1)=f(v2,v1)-maxf(n);
6 _( Q0 A, ?- H. A% o end
+ |$ n2 I* z2 N M v2=v1; v1=pred(v2);* f: g1 V3 X# r/ T
end7 y* e' @& C( U4 P9 L2 m
end
! E% z+ G. I, u! `. I1 Kend
! B; A2 j# `6 `f
% c: M5 Z: m$ L& `5 o* P例18 现需要将城市 s 的石油通过管道运送到城市t ,中间有4个中转站 v1 ,v2 ,v3 和 v4 ,城市与中转站的连接以及管道的容量如图7所示,求从城市 s 到城市t 的最大流。" l7 d! d0 r( l/ D+ g
2 y* T2 c0 {' l2 O
$ L' F5 C; J) K' E8 Z" L
5 `7 X. ^" p7 q8 Z* K- U
' P6 o( ?$ r- U) ^3 ^# P
解 使用最大流的数学规划表达式,编写LINGO程序如下:
% G% V1 }! d! [, b5 D# m# U. a( _( h
model:
5 i6 g# F# p4 o/ M2 Y* r0 Asets:
" f' s& M8 }* ]% gnodes/s,1,2,3,4,t/;
( v& _5 S; B$ V9 Uarcs(nodes,nodes)/s 1,s 3,1 2,1 3,2 3,2 t,3 4,4 2,4 t/:c,f;$ n8 U& A5 }' G/ S! \2 w4 r$ I2 K! u& D
endsets: J& y: S' p* X! `
data:
+ V/ N5 K8 ?: [: V1 Nc=8 7 9 5 2 5 9 6 10;- E/ o8 c! {0 w2 r U0 k V
enddata
% M% L: D4 L+ F* Mn=@size(nodes); !顶点的个数;2 A$ u3 u' I' e d7 w
max=flow;* V9 u7 H. [! m, f+ j" \9 A4 R
@for(nodes(i)|i #ne#1 #and# i #ne# n:6 }) k C3 [1 a, P, Z& F. c& B
@sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i)+ c2 r! i+ l& ^4 @5 O2 V* S
@sum(arcs(i,j)|i #eq# 1:f(i,j))=flow;
6 e1 m u. e5 i+ l" G" h. F@sum(arcs(i,j)|j #eq# n:f(i,j))=flow;& Q; C, j6 z5 E+ D# ~- c
@for(arcs bnd(0,f,c));
7 c2 }" x3 ]+ {4 q$ S8 W% aend
& E$ \* z8 e8 s3 |+ \' N; s* x ~# J/ {; @; ]: y0 W
在上面的程序中,采用了稀疏集的编写方法。下面介绍的程序编写方法是利用赋权邻 接矩阵,这样可以不使用稀疏集的编写方法,更便于推广到复杂网络。
3 k& W! z8 D! |
6 y6 }% p' c/ ]! F% u( l2 wmodel:
5 F% V2 e- V4 M9 h) nsets:, p" Y3 C( `" v
nodes/s,1,2,3,4,t/;( ]0 _, F5 F( T6 l/ |' [
arcs(nodes,nodes):c,f;$ F- f: @4 `2 T+ o4 I G% {0 O
endsets9 h! X% N, F. Y! V5 f" \" _0 C
data:) I) r& J7 P0 {8 K1 X
c=0;0 S2 o/ O4 ?) G/ Y ?
@text('fdata.txt')=f;( c) C) m: H9 g _# {+ K- T/ G
enddata
/ _( U( w; Z; }/ Ocalc:
: I+ f: _0 `6 m% Q' W5 Ic(1,2)=8;c(1,4)=7;" b- [2 H4 L1 `* D3 ~" p+ @4 G
c(2,3)=9;c(2,4)=5;" _$ H( j2 A) i5 N% |! A
c(3,4)=2;c(3,6)=5;, ~- ?3 g! f+ O0 h
c(4,5)=9;c(5,3)=6;c(5,6)=10;6 {) P9 w- i+ }1 R6 q% f) l8 Z
endcalc$ W3 J- }8 B; E0 r4 Y
n=@size(nodes); !顶点的个数;7 Q7 l+ M" B& W# W9 ^3 S$ h) a4 o
max=flow;- ^# D$ l2 p& @1 M; s. u
@for(nodes(i)|i #ne#1 #and# i #ne# n:6 t L+ Y1 `7 Q/ C# I3 |5 d p) S# L
@sum(nodes(j):f(i,j))=@sum(nodes(j):f(j,i)));
4 K% }7 l0 ~# j- j3 `@sum(nodes(i):f(1,i))=flow;
3 J4 i% i4 I1 W; O+ D, T; y@sum(nodes(i):f(i,n))=flow;) Y" ^3 w, d5 a3 q0 ^
@for(arcs bnd(0,f,c));
8 v' m1 f- }; F' s0 jend& }5 a: S0 ?% U6 p+ D4 ^
3 k6 C k, `2 h& S: Z* a
————————————————
( y' d7 r2 T& ]3 F0 ?6 ]! v: S版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
; o2 v) \' u4 g; r. ~! S4 l原文链接:https://blog.csdn.net/qq_29831163/article/details/897863130 K+ x) V8 I7 S
1 o& T9 P1 X' F3 a$ {# C v
: [0 F# C; [& B% ~# A
|
zan
|