- 在线时间
- 791 小时
- 最后登录
- 2022-11-28
- 注册时间
- 2017-6-12
- 听众数
- 15
- 收听数
- 0
- 能力
- 120 分
- 体力
- 35383 点
- 威望
- 11 点
- 阅读权限
- 255
- 积分
- 13558
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 621
- 主题
- 542
- 精华
- 10
- 分享
- 0
- 好友
- 225
TA的每日心情 | 开心 2020-11-14 17:15 |
---|
签到天数: 74 天 [LV.6]常住居民II
群组: 2019美赛冲刺课程 群组: 站长地区赛培训 群组: 2019考研数学 桃子老师 群组: 2018教师培训(呼伦贝 群组: 2019考研数学 站长系列 |
1 最大流问题的数学描述
, t" p4 s- s3 I$ M1.1 网络中的流 定义/ h' Y4 U- t7 B6 h, V* A
在以V 为节点集, A 为弧集的有向图G = (V, A) 上定义如下的权函数:( B. b/ O; k7 X6 y. Q# H3 H
5 u9 I* n+ V6 n
(i) L : A → R 为孤上的权函数,弧 (i, j)∈ A 对应的权 L(i, j) 记为 ,称为孤 (i, j) 的容量下界(lower bound);
& X7 g, b: V' D; }
* |7 w3 a4 O) [ [" D(ii)U : A → R 为弧上的权函数,弧(i, j)∈ A对应的权U(i, j) 记为 ,称为孤 (i, j) 的容量上界或容量(capacity);
9 M* a, j, K% X8 t% z# P8 ]1 h" }( u7 d! v+ r F- A, _3 E
(iii) D :V → R 为顶点上的权函数,节点i ∈V 对应的权 D(i) 记为 ,称为顶 点i 的供需量(supply/demand);$ @8 v+ l7 X- B9 M0 {# {5 f9 S; j! X
Q' o: L4 y. J, Y8 C n( ?此时所构成的网络称为流网络,可以记为 N = (V, A, L,U,D) 。 由于我们只讨论V, A 为有限集合的情况,所以对于弧上的权函数 L,U 和顶点上的 权函数 D ,可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示,因此 L,U, D 有时直接称为权向量,或简称权。由于给定有向图G = (V, A) 后,我们总是可 以在它的弧集合和顶点集合上定义各种权函数,所以流网络一般也直接简称为网络。
2 b; x: t8 i4 w# m; j; w8 \
. s: l* n2 P+ _; {2 O7 A" k7 i在流网络中,弧(i, j) 的容量下界 和容量上界表示的物理意义分别是:通过该 弧发送某种“物质”时,必须发送的最小数量为 ,而发送的最大数量为 。顶点i ∈V 对应的供需量则表示该顶点从网络外部获得的“物质”数量( > 0时),或从该顶 点发送到网络外部的“物质”数量(< 0 时)。下面我们给出严格定义。& D" y* l X" {; X' m
2 f0 k# J% B( c- l, x/ V可行流(feasible flow)
) m9 O. {- D4 U" Y7 |0 P: M" J6 d6 Q6 W9 g" d( B* e
; Y. w5 S7 h7 b5 J9 d: D
; x8 N) y! M8 N0 } w$ a! p$ B3 p, a
' T& S! Y2 y3 [0 M# R1 |可见,当 di > 0时,表示有di 个单位的流量从网络外部流入该顶点,因此顶点i 称 为供应点(supply node)或源(source),有时也形象地称为起始点或发点等;当di < 0 时,表示有|di | 个单位的流量从该顶点流失到网络外部(或说被该顶点吸收),因此顶 点i 称为需求点(demand node)或汇(sink),有时也形象地称为终止点或收点等;当 di = 0时,顶点i 称为转运点(transshipment node)或平衡点、中间点等。此外,根据 (1)可知,对于可行网络,必有7 W# k: d, @' u' V; d
2 X: R# g# T! M
9 Q: I& R( k9 D7 E2 k7 {9 y9 z4 G
( \/ I: H) J! n$ v `7 A5 v3 O7 _7 _
也就是说,所有节点上的供需量之和为 0 是网络中存在可行流的必要条件
& P& u. z6 B+ E# I6 s
& B& z; n7 o3 r( q/ Y$ W
- L. x$ S3 m; S# Z6 r5 b3 D. w' C9 x9 C4 m
' Q$ p$ |" O5 U1.2 最大流问题% W8 ]! Y X3 _) M/ i& a8 z
考虑如下流网络 N = (V, A,U,D):节点 s 为网络中唯一的源点,t 为唯一的汇点, 而其它节点为转运点。如果网络中存在可行流 f ,此时称流 f 的流量(或流值,flow value)为 (根据(3),它自然也等于 − ),通常记为v 或v( f ) ,即. H4 r5 N' P. Q. c( v/ Q% A
: {/ L- n! _% i) y5 j
. h" F0 T' ?, r对这种单源单汇的网络,如果我们并不给定 和 (即流量不给定),则网络一 般记为 N = (s,t,V, A,U) 。最大流问题( maximum flow problem )就是在 N = (s,t,V, A,U) 中找到流值最大的可行流(即最大流)。我们将会看到,最大流问题 的许多算法也可以用来求解流量给定的网络中的可行流。也就是说,当我们解决了最大 流问题以后,对于在流量给定的网络中寻找可行流的问题,通常也就可以解决了。
2 k8 Y# ]0 L. V% {7 Q" i/ \; |+ o" t* H/ S
用线性规划描述最大流问题, C# ?# j' U. `5 \8 E. O
因此,用线性规划的方法,最大流问题可以形式地描述如下:* C. P# F+ L* W1 U
/ \- ]/ i& ^7 G m
: v# Z, H9 V! P' F- U
+ M3 k5 c( `9 k0 ?1 w定义】 如果一个矩阵 A 的任何子方阵的行列式的值都等于0,1或 −1,则称 A 是 全幺模的(totally unimodular TU,又译为全单位模的),或称 A 是全幺模矩阵。' G( [/ @4 \! a8 s2 N+ F' o$ I
3 c3 T+ w& T9 Z. n9 u$ J+ c
整流定理
5 E5 w+ N7 ]: o3 G& D【定理 7】(整流定理) 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量 均为正整数,则问题的最优解为整数解。 最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点,解决这个问 题的方法较之线性规划的一般方法要方便、直观得多。1 U3 X5 H5 P6 u+ ~5 f" Q
9 V/ |3 O/ ]# @; L8 Q& o' ^' K
1.3 单源和单汇运输网络5 g0 v0 X- w' ~# h P
多源多汇网络 转化成单源单汇网络' b6 m+ M: @/ X2 H- O1 t
实际问题往往是多源多汇网络,为了计算的规格化,可将多源多汇网络G 化成单 源单汇网络G' 。设 X 是G 的源,Y 是G 的汇,具体转化方法如下:
; |- L6 _/ A3 G# h# @+ p. ~8 T
& C! O$ A$ |, H( r; p0 W' y(i)在原图G 中增加两个新的顶点 x 和 y ,令为新图G' 中之单源和单汇,则G 中 所有顶点V 成为G' 之中间顶点集。) k4 y$ p, ~/ J; R1 o8 E
8 {% j2 \; |% A8 }
(ii)用一条容量为∞的弧把 x 连接到 X 中的每个顶点。1 F0 s1 y z1 a0 }$ \7 U" f
$ X& g- A W& p$ D& z; e( ~9 m, j* n( L(iii)用一条容量为∞的弧把Y 中的每个顶点连接到 y 。 G 和G' 中的流以一个简单的方式相互对应。若 f 是G 中的流,则由2 V3 n5 D# B4 @; y$ l5 x
+ o: J: i- d" x9 `9 @9 s1 {) z# o/ u/ l
$ c0 ]7 V! k+ @" z" d" Y2 最大流和最小割关系割的容量9 I' c% ?% G! E9 o
$ C! o8 _! v9 K' U. E( h0 k( z2 T5 ]+ ?& Z3 l
* A% L- M- s! ]0 q- j则在这条可增广轨上每条前向弧的流都可以增加一个量δ ,而相应的后向弧的流可减 少δ ,这样就可使得网络的流量获得增加,同时可以使每条弧的流量不超过它的容量, 而且保持为正,也不影响其它弧的流量。总之,网络中 f 可增广轨的存在是有意义的, 因为这意味着 f 不是最大流。% `/ h, Y1 ^2 S N1 V* |2 d3 @
! M9 ^5 {+ O9 @3 最大流的一种算法—标号法0 t( ?. c# u6 F6 a+ s. O
标号法是由 Ford 和 Fulkerson 在 1957 年提出的。用标号法寻求网络中最大流的基 本思想是寻找可增广轨,使网络的流量得到增加,直到最大为止。即首先给出一个初始 流,这样的流是存在的,例如零流。如果存在关于它的可增广轨,那么调整该轨上每条 弧上的流量,就可以得到新的流。对于新的流,如果仍存在可增广轨,则用同样的方法 使流的值增大,继续这个过程,直到网络中不存在关于新得到流的可增广轨为止,则该 流就是所求的最大流。
+ a" S$ A: Z/ L0 A. \/ y
) [$ u$ H7 Q8 { m% b5 T7 E! J6 K这种方法分为以下两个过程:
q/ |: c- E K( j/ e5 Q6 x* R
" S6 B. b8 Y, O7 aA.标号过程:通过标号过程寻找一条可增广轨。
5 P0 {5 `- s- n; Z4 ?5 m% Z7 ^
5 t: |8 A! o. y( J& W- OB.增流过程:沿着可增广轨增加网络的流量。. b; D) k0 |/ Q( ~8 }# v
* Z2 j+ \+ B6 h* L' n2 S& ]
这两个过程的步骤分述如下。, J) K+ P* y" l8 a/ q, y$ [+ S
" E' E* A/ c2 y* ^# X3 \' J
(A)标号过程:
+ w: e. L" A5 h4 n# Z! b. E, }# l- i" I
& x' B' s9 ^5 g5 r- B: k
( ]3 k: `/ r% W+ H(B)增流过程
- g h+ ^& z% \7 n( h$ h& Y
; L3 ^+ `7 _6 g& s网络最大流 x 的求解步骤& o j, o, b3 K. G: q" p1 e
求网络 N = (s,t,V, A,U) 中的最大流 x 的算法的程序设计具体步骤如下:
0 j1 l9 b9 q2 N9 k+ h7 y5 ]9 d3 e. d) u
对每个节点 j ,其标号包括两部分信息 (pred( j),maxf(j))
# Z7 ?& Q \3 G8 _& M! d% Z
. Z0 p, X/ I+ e o该节点在可能的增广路中的前一个节点 pred( j) ,以及沿该可能的增广路到该节点为止 可以增广的最大流量 maxf( j)。
9 l4 [5 Z: {% w; [+ U& g+ Z: i( o& }8 I m2 y
' @8 s$ o; |4 s9 K
/ \" R3 r$ Y3 r8 Q- U并将 j 加入 LIST 中。 例 17 用 Ford-Fulkerson 算法计算如图 6 网络中的最大流,每条弧上的两个数字分 别表示容量和当前流量。
" _( f9 ?4 U" g, }: D' j: T, H* Y2 U5 _& d/ t2 M- I, ~1 B' ]7 {
0 }! t0 e2 g/ e( ] I# ^
解 编写程序如下:: t+ R) c. }3 z$ z5 D
4 ~+ S) V) _4 lclc,clear
4 u: _3 p3 f) ? xu(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;0 ~3 I" {2 P: u
u(3,5)=1;u(4,3)=3;u(4,5)=3;4 O1 L0 v( i/ _0 k4 h1 M
f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1;
8 O: X: { a& Q i4 nf(3,5)=1;f(4,3)=1;f(4,5)=0;. ?5 h s: }) I2 f! o! n
n=length(u);list=[];maxf(n)=1;
7 c+ H( H, \6 [( @% f& F# C1 X) Y& Dwhile maxf(n)>0+ a" y% I. ?$ C1 S5 b* }
maxf=zeros(1,n);pred=zeros(1,n);
& a, a7 U! k! Zlist=1;record=list;maxf(1)=inf;
. t K* i# ]* D % list是未检查邻接点的标号点,record是已标号点
( S$ G7 m' k/ Z; F) w1 o4 kwhile (~isempty(list))&(maxf(n)==0)
9 c8 v6 \) q+ J0 M1 C flag=list(1);list(1)=[];5 U) r7 n- \' Q) s+ i9 T2 H, K7 X
label1= find(u(flag,-f(flag,);( ?- q. q) O9 E: k
label1=setdiff(label1,record);* p2 @2 U4 M% H: r( A9 G
list=union(list,label1);' S) R! E* D5 Z/ G6 U
pred(label1)=flag;) _- O& E% M& {1 ~, O3 `$ P1 r
maxf(label1)=min(maxf(flag),u(flag,label1)... ]2 n; U; V/ v5 p" {0 b M4 ]( n! M
-f(flag,label1));
- I O" s8 P) L, o) h& f record=union(record,label1);& H4 _- j. c: ^- x+ K
label2=find(f(:,flag));- ~. x: ?( e, l2 B8 |* j
label2=label2';0 s: i$ b+ X/ Q1 z" E1 Q
label2=setdiff(label2,record);$ \- q1 Q9 k' \! [ ~0 v1 {
list=union(list,label2);
% y2 o; V! {% _% ?) H" X- U" o pred(label2)=-flag;7 T. P* }: \0 {
maxf(label2)=min(maxf(flag),f(label2,flag));/ ^. m/ v/ ~$ H+ p: ^' S8 Z
record=union(record,label2);
5 _/ O9 V7 ~! y: H$ L' x) B8 U end
7 T1 A$ @, w" Q: o if maxf(n)>0* g' F6 W) e# i3 H9 L# @
v2=n; v1=pred(v2);, M4 b' d. J8 F
while v2~=11 l1 Q$ S' b8 D$ C& h. n' Q
if v1>0
* V( _4 c4 Q4 M4 l f(v1,v2)=f(v1,v2)+maxf(n);
+ {$ f' y0 {: z" _" G else
7 T" x& {$ _/ [$ \& L: S v1=abs(v1);6 l8 p) t; ?' t" r
f(v2,v1)=f(v2,v1)-maxf(n);; X3 f/ ?4 s* D1 s3 o/ R+ D7 I
end9 ]3 H3 h% t3 h5 C9 m) k
v2=v1; v1=pred(v2);7 i N5 i+ u1 _8 O6 m
end) U* h1 T0 G- F' c Z
end
R4 B3 ~2 I9 R: j4 r% I7 fend
7 A0 Q) G5 e5 P) Z; r1 H: Rf
/ E5 k( M4 a! f& a5 Z7 u1 o- s例18 现需要将城市 s 的石油通过管道运送到城市t ,中间有4个中转站 v1 ,v2 ,v3 和 v4 ,城市与中转站的连接以及管道的容量如图7所示,求从城市 s 到城市t 的最大流。
5 \4 g- g, _0 M$ \# T9 ?% C, A* Y) F- k& ]4 D, j) E2 s ]
/ C' \. S M* b9 ^4 o
, c7 ?* B; j- J5 p9 P b
; w: g! h+ p% J+ v0 W6 M- B解 使用最大流的数学规划表达式,编写LINGO程序如下:
1 y$ P8 i5 N/ P$ N* G
" _% O8 |/ b: [& Vmodel:
( P' Y8 ]; u: bsets:
! U2 k' M5 ~3 s& N1 Hnodes/s,1,2,3,4,t/;, S) I2 o# L! E3 X/ T0 r
arcs(nodes,nodes)/s 1,s 3,1 2,1 3,2 3,2 t,3 4,4 2,4 t/:c,f;' @$ a5 R2 w8 V# @( _3 M! x
endsets
+ V: C/ _; ~; h# O4 f& f9 adata:
4 m7 A# c7 x, s' Dc=8 7 9 5 2 5 9 6 10;
; j5 J$ n" e5 W8 w! f- aenddata$ ?- M; m7 X4 r- @* Z. _
n=@size(nodes); !顶点的个数;
% p: }/ G( T* u8 B. \. Nmax=flow;
$ T9 Q" v- A H4 R/ ~4 `@for(nodes(i)|i #ne#1 #and# i #ne# n:* e6 G* Y. J& |9 S, p
@sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i)! A( `. H3 Q( Z
@sum(arcs(i,j)|i #eq# 1:f(i,j))=flow;
' `& K3 p0 h) q& z2 H- o4 e* V6 G( P@sum(arcs(i,j)|j #eq# n:f(i,j))=flow;. F! Y0 }3 C9 B) c- v
@for(arcsbnd(0,f,c));
& r) I' @' H" C E1 t3 E# {end ! K. X7 w8 N$ B0 j; x$ n- H5 _
8 H4 Z* { o- Y7 P, D
在上面的程序中,采用了稀疏集的编写方法。下面介绍的程序编写方法是利用赋权邻 接矩阵,这样可以不使用稀疏集的编写方法,更便于推广到复杂网络。
1 K% a8 I5 t5 j! Y) s* A
: @. x. `# g' Cmodel:
( B. e2 G: _1 D, F8 ^' Osets: Y- q+ R7 [6 y5 u* V" t
nodes/s,1,2,3,4,t/;
' B9 |/ L- O1 b: _4 h8 farcs(nodes,nodes):c,f;
: Y) j: [4 V4 s3 k) sendsets' Q! A" C I) B0 x) g+ a2 I
data:
6 k/ X9 z8 ]. X6 tc=0;3 R U& [, t$ Y" T: @) Y
@text('fdata.txt')=f;8 a7 H( d) n. h
enddata
1 Z& U/ |% ~* x `calc:! J, C0 E8 z4 f1 S& M P
c(1,2)=8;c(1,4)=7;5 C+ W+ `. j7 p1 d
c(2,3)=9;c(2,4)=5;
: o6 [* {' X; O/ ^. O. Uc(3,4)=2;c(3,6)=5;2 h4 O K G- F! R2 Q1 p# m7 h
c(4,5)=9;c(5,3)=6;c(5,6)=10;
% w9 M) X* L& z! B( f7 nendcalc/ s+ @) C, R6 u% _* ?% z& y' K% T
n=@size(nodes); !顶点的个数; \/ |1 K$ t# Z8 C' ~3 r
max=flow;8 F) f+ N+ O. V3 X- ^6 S
@for(nodes(i)|i #ne#1 #and# i #ne# n:
1 O2 Y! ^: ^6 Y: ^) ^$ c" L @sum(nodes(j):f(i,j))=@sum(nodes(j):f(j,i)));( ?- }+ T, P" }" f( E' j l
@sum(nodes(i):f(1,i))=flow;$ u# G9 X6 U g! ^( G" m( M! P$ [$ x
@sum(nodes(i):f(i,n))=flow;% J5 s( G. q/ v, d4 [
@for(arcsbnd(0,f,c));
' {1 F! b. N4 C2 aend
9 f) }+ Z( ?/ V o" Z* X0 Z' p
: h7 C( y3 u/ B————————————————
3 X1 C" p# ~& I# p版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
. P2 F# P0 M% j# \% f( C1 G. d) a原文链接:https://blog.csdn.net/qq_29831163/article/details/89786313' V* H3 L Q! B/ c% R! k
. S, W$ l. Y6 Z4 k- D- X) n( J }6 ^1 b- x8 m* r
|
zan
|