在线时间 791 小时 最后登录 2022-11-28 注册时间 2017-6-12 听众数 15 收听数 0 能力 120 分 体力 36352 点 威望 11 点 阅读权限 255 积分 13866 相册 0 日志 0 记录 1 帖子 616 主题 542 精华 12 分享 0 好友 225
TA的每日心情 开心 2020-11-14 17:15
签到天数: 74 天
[LV.6]常住居民II
群组 : 2019美赛冲刺课程
群组 : 站长地区赛培训
群组 : 2019考研数学 桃子老师
群组 : 2018教师培训(呼伦贝
群组 : 2019考研数学 站长系列
1 最大流问题的数学描述- g6 ~. O, O l) C: B% m/ U z
1.1 网络中的流 定义" L$ Q7 Y8 w( y) `
在以V 为节点集, A 为弧集的有向图G = (V, A) 上定义如下的权函数:. d5 s4 J/ |) w2 A1 H
8 m8 k% x' q/ w
(i) L : A → R 为孤上的权函数,弧 (i, j)∈ A 对应的权 L(i, j) 记为 ,称为孤 (i, j) 的容量下界(lower bound);
" i; ^( F! A! p7 \7 m7 i! W
# h1 i7 d- C( P- H) a4 I (ii)U : A → R 为弧上的权函数,弧(i, j)∈ A对应的权U(i, j) 记为 ,称为孤 (i, j) 的容量上界或容量(capacity);) b+ s3 M/ n% q3 y9 M4 @* Y) r
3 B* ^$ S; p w* R! y. y+ {7 ^( T6 _ (iii) D :V → R 为顶点上的权函数,节点i ∈V 对应的权 D(i) 记为 ,称为顶 点i 的供需量(supply/demand);6 `* d$ P& S* E
! b: J4 `9 @ O* W0 R) a4 A5 T 此时所构成的网络称为流网络,可以记为 N = (V, A, L,U,D) 。 由于我们只讨论V, A 为有限集合的情况,所以对于弧上的权函数 L,U 和顶点上的 权函数 D ,可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示,因此 L,U, D 有时直接称为权向量,或简称权。由于给定有向图G = (V, A) 后,我们总是可 以在它的弧集合和顶点集合上定义各种权函数,所以流网络一般也直接简称为网络。
8 m- P# P# u S6 P- t
. f6 W' E5 y3 }% ? 在流网络中,弧(i, j) 的容量下界 和容量上界表示的物理意义分别是:通过该 弧发送某种“物质”时,必须发送的最小数量为 ,而发送的最大数量为 。顶点i ∈V 对应的供需量则表示该顶点从网络外部获得的“物质”数量( > 0时),或从该顶 点发送到网络外部的“物质”数量(< 0 时)。下面我们给出严格定义。
9 ?0 M. @/ Z8 T5 x6 _0 { # P5 Q, O! C% c- `2 ^
可行流(feasible flow)
- G& k5 g% [- q8 _0 i) D0 ~( m
$ {! X8 F- x% p: B8 ]' K 2 M7 a; U9 ~- r5 b/ s) a( i6 A- e
" @5 o9 J) m( `7 b/ y! h
) f H, i, k0 H) v 可见,当 di > 0时,表示有di 个单位的流量从网络外部流入该顶点,因此顶点i 称 为供应点(supply node)或源(source),有时也形象地称为起始点或发点等;当di < 0 时,表示有|di | 个单位的流量从该顶点流失到网络外部(或说被该顶点吸收),因此顶 点i 称为需求点(demand node)或汇(sink),有时也形象地称为终止点或收点等;当 di = 0时,顶点i 称为转运点(transshipment node)或平衡点、中间点等。此外,根据 (1)可知,对于可行网络,必有4 B2 m4 i z; i1 U
5 \3 B& u ~# o- q( y 3 G3 w4 H+ n* U& K$ D( b. u! K
7 _4 k9 i8 D+ K9 |) J
也就是说,所有节点上的供需量之和为 0 是网络中存在可行流的必要条件
1 y2 m, s. P. V+ p* f; c" s 5 M$ ^% f7 r. G4 q# n R
4 z, l+ W( \" E! h) p, T
! t: \( F9 F( [" f" z- ~
! A/ v- \ e. _3 } 1.2 最大流问题' F: n( h- R- q8 w0 U
考虑如下流网络 N = (V, A,U,D):节点 s 为网络中唯一的源点,t 为唯一的汇点, 而其它节点为转运点。如果网络中存在可行流 f ,此时称流 f 的流量(或流值,flow value)为 (根据(3),它自然也等于 − ),通常记为v 或v( f ) ,即- x6 m$ G# Y9 a" H7 o! `
, K) k6 n0 U/ e: F; _7 }2 U1 W8 {
, e; P& V! g" s, E) Y; b) Y 对这种单源单汇的网络,如果我们并不给定 和 (即流量不给定),则网络一 般记为 N = (s,t,V, A,U) 。最大流问题( maximum flow problem )就是在 N = (s,t,V, A,U) 中找到流值最大的可行流(即最大流)。我们将会看到,最大流问题 的许多算法也可以用来求解流量给定的网络中的可行流。也就是说,当我们解决了最大 流问题以后,对于在流量给定的网络中寻找可行流的问题,通常也就可以解决了。0 z( T# Y# Q; Y
6 D& V7 C6 E% F$ m% R
用线性规划描述最大流问题
1 ~) ]5 x/ @5 f7 `3 z 因此,用线性规划的方法,最大流问题可以形式地描述如下:2 A! H6 I. ]4 ?
3 Y% G ^- i: O
, o) J1 {# k* N% V7 T$ l
4 @) |$ I2 S6 Q5 o- Q; K( i
定义】 如果一个矩阵 A 的任何子方阵的行列式的值都等于0,1或 −1,则称 A 是 全幺模的(totally unimodular TU,又译为全单位模的),或称 A 是全幺模矩阵。& Q# W/ t1 X& W+ R
6 Y' }1 L9 @ j/ L( f3 a+ T
整流定理0 ~) r" V' w4 n) y
【定理 7】(整流定理) 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量 均为正整数,则问题的最优解为整数解。 最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点,解决这个问 题的方法较之线性规划的一般方法要方便、直观得多。/ `$ S8 r) E% D1 L
1 T0 v$ [) @* Z% x 1.3 单源和单汇运输网络
! z9 ^4 H2 L+ a! G* g( D 多源多汇网络 转化成单源单汇网络
/ y+ ~; M2 | i* S) C 实际问题往往是多源多汇网络,为了计算的规格化,可将多源多汇网络G 化成单 源单汇网络G' 。设 X 是G 的源,Y 是G 的汇,具体转化方法如下:- u- X. A9 {; b8 s
! c( K% b+ |. O/ W3 N
(i)在原图G 中增加两个新的顶点 x 和 y ,令为新图G' 中之单源和单汇,则G 中 所有顶点V 成为G' 之中间顶点集。 X- _' y; h, {+ @8 H) ?7 [
; H& `, s+ q1 K, P& m (ii)用一条容量为∞的弧把 x 连接到 X 中的每个顶点。
5 d. |+ B9 G, G
* |; a6 {2 h M" t! u (iii)用一条容量为∞的弧把Y 中的每个顶点连接到 y 。 G 和G' 中的流以一个简单的方式相互对应。若 f 是G 中的流,则由
( b) K; V0 G3 S8 S/ O, f
1 ~7 S/ D2 A& f- }; | 2 R: ?8 M& S0 a% x9 M
8 O! L; r+ G9 q$ j: T7 h& N& D* H 2 最大流和最小割关系 割的容量 * r$ Y" q/ |; U2 W# b
8 I5 m( \% p, i" V Z
3 v6 A* g# G$ n' l! t; ~( \1 Q7 p
% P: F; _+ X+ W4 e3 r 则在这条可增广轨上每条前向弧的流都可以增加一个量δ ,而相应的后向弧的流可减 少δ ,这样就可使得网络的流量获得增加,同时可以使每条弧的流量不超过它的容量, 而且保持为正,也不影响其它弧的流量。总之,网络中 f 可增广轨的存在是有意义的, 因为这意味着 f 不是最大流。$ q: {& V( y# ^% D
$ D* ~" o; O, \5 m% s! C* ? E 3 最大流的一种算法—标号法1 N! d2 m' I) _: M; F9 _8 O
标号法是由 Ford 和 Fulkerson 在 1957 年提出的。用标号法寻求网络中最大流的基 本思想是寻找可增广轨,使网络的流量得到增加,直到最大为止。即首先给出一个初始 流,这样的流是存在的,例如零流。如果存在关于它的可增广轨,那么调整该轨上每条 弧上的流量,就可以得到新的流。对于新的流,如果仍存在可增广轨,则用同样的方法 使流的值增大,继续这个过程,直到网络中不存在关于新得到流的可增广轨为止,则该 流就是所求的最大流。
/ y3 g" i9 u* {1 m/ P" u, V& D , T- n. e! L& z0 E
这种方法分为以下两个过程:2 ]3 [+ e& k+ s: R5 |
! H8 ?! {& d' @0 t B
A.标号过程:通过标号过程寻找一条可增广轨。7 O8 s A8 d5 P( B" V% x
! U+ `" ~: ], h) G' z5 m
B.增流过程:沿着可增广轨增加网络的流量。: T4 K8 X3 t' I' U) Y
9 q1 p; h& @, X% O
这两个过程的步骤分述如下。" {3 W, o! J- C% B; F. d$ h
5 o' Y- } a# d* @3 _( j (A)标号过程:3 p, H' ~4 w6 e& q
# t$ W1 u9 u! n( V" e2 }( \ ! N5 }/ @4 Y8 y9 h) Y: h0 P' ?" M
0 b0 }$ b, G9 h. }! `
(B)增流过程 5 t& \1 @2 x- N6 Y
! X( j0 p) n) W8 Z q( t% _: `
网络最大流 x 的求解步骤
0 |6 U1 z- i/ u1 W9 P2 ~ 求网络 N = (s,t,V, A,U) 中的最大流 x 的算法的程序设计具体步骤如下:$ e( ]3 n; a' }* v0 c3 t, e
/ A( G5 l. W9 u) Q# e 对每个节点 j ,其标号包括两部分信息 (pred( j),maxf(j))
4 @( m# V# L. u! u
0 V* c# w0 T* x" t. W. @1 W 该节点在可能的增广路中的前一个节点 pred( j) ,以及沿该可能的增广路到该节点为止 可以增广的最大流量 maxf( j)。
2 ~, s4 X" i/ a1 C+ E- g 3 g5 R. Z. ]9 u
3 C6 Q, X$ }6 ? S: R
) y7 J' |; w5 ?# B+ g
并将 j 加入 LIST 中。
例 17 用 Ford-Fulkerson 算法计算如图 6 网络中的最大流,每条弧上的两个数字分 别表示容量和当前流量。
5 r7 u$ H$ r9 n% I. A* F( K& o
! y3 U% \, ]7 q( c) ?; x
0 _1 J/ s* g4 \( L z
解 编写程序如下:
* j! e8 `" s1 G0 r$ |1 i; E
% c. K! b- G) R' W clc,clear0 {* ]" @! f9 Q) o; o
u(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;
/ I. ]/ x2 ~3 @4 {9 y u(3,5)=1;u(4,3)=3;u(4,5)=3;
# s- i4 Q( _1 }% @6 C! {, y f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1;
6 c. r6 |0 r/ a3 O f(3,5)=1;f(4,3)=1;f(4,5)=0;
: N' U- Y( L. m. a0 x$ j) x n=length(u);list=[];maxf(n)=1;
: h& O. d+ l3 t while maxf(n)>0
1 `+ ?. d# @, H+ @" Y' |' D5 ` maxf=zeros(1,n);pred=zeros(1,n);
4 {- B2 U8 W/ z7 [+ v/ ~" M list=1;record=list;maxf(1)=inf;
7 H3 \4 W8 \2 H; |6 O4 B % list是未检查邻接点的标号点,record是已标号点
6 Y$ U! G9 }. m. I/ T; N* D while (~isempty(list))&(maxf(n)==0); J! o$ E( F d/ q+ Q1 Q
flag=list(1);list(1)=[];+ [0 l: }: Q! ?2 E. N4 Q# _* s& w2 b
label1= find(u(flag, -f(flag, );* n" g% Q4 h/ s
label1=setdiff(label1,record);
2 ^3 e4 c P7 _8 ]# c4 h4 m list=union(list,label1);
1 {: B* p$ n$ z7 Q! `+ w7 K u pred(label1)=flag;; d. i8 Q. m/ |
maxf(label1)=min(maxf(flag),u(flag,label1)...
9 G! d. |' U& s2 [, k7 m8 C7 J' L -f(flag,label1));
) H* W- c+ A7 `. W7 ~) ~ record=union(record,label1);
$ Y1 v8 ]/ ^/ Q+ z. G label2=find(f(:,flag));, r( z# D0 W6 I: Y7 b3 d; t
label2=label2';
: q! o5 m, `% Q; A C/ j4 K label2=setdiff(label2,record);
+ K2 R7 C$ w9 O z4 [: z list=union(list,label2);
8 W2 j5 W3 x, ^. e pred(label2)=-flag;
# Y& D; n8 c% i+ X8 W8 N maxf(label2)=min(maxf(flag),f(label2,flag));7 d+ O) Z, K9 j. c, c
record=union(record,label2);
5 n: t0 w; b9 m |6 `0 p end
& z, A! ^" [ I if maxf(n)>0
5 J/ b3 R& W( T% |& h$ [& k v2=n; v1=pred(v2);
8 s/ w" X+ s0 W4 V1 w while v2~=1
0 p# O8 ^" ~4 K. L& i0 B# i& V! b if v1>0
) r; [5 G% I9 w f(v1,v2)=f(v1,v2)+maxf(n);
4 d6 X7 a6 V2 R1 w else
. R' d: [6 {2 k, w8 Y: P. c v1=abs(v1);
5 m4 W+ v; g; m6 }8 ^, W f(v2,v1)=f(v2,v1)-maxf(n);
; \0 ] f T) r C, B end
3 v$ }9 h: e" r/ P" E$ {" @ v2=v1; v1=pred(v2);' a; l6 o! y5 a& S0 y' |6 s( {
end8 f" v6 `7 b' }) x. k/ I
end
- }2 A# I- r+ ?" g7 y$ Q9 z end$ o0 k4 J& y; a$ t/ y, Z
f 8 [5 ~- `" j+ R9 a _
例18 现需要将城市 s 的石油通过管道运送到城市t ,中间有4个中转站 v1 ,v2 ,v3 和 v4 ,城市与中转站的连接以及管道的容量如图7所示,求从城市 s 到城市t 的最大流。 Q, d8 T N8 V# e% }
# C1 }6 [" @2 k/ v9 S4 O2 y- ?
3 c: X; }4 N9 o9 _
4 I+ v; K5 I' e( ]% Y! {; T2 M * Y$ S% q9 \5 a! H
解 使用最大流的数学规划表达式,编写LINGO程序如下:
e7 N/ s* a1 H' c) r* W; j
, V# p2 D- t/ C3 \) m- A6 Q( k y6 r model:! q$ P! V% _1 U2 C% M; |/ L
sets:6 M2 v. O% I! l) D. B6 }
nodes/s,1,2,3,4,t/;
( T5 _* x& k7 a" Q arcs(nodes,nodes)/s 1,s 3,1 2,1 3,2 3,2 t,3 4,4 2,4 t/:c,f;$ n9 T+ O# h7 S, r( L# d7 E* D
endsets2 |9 U) w' Z) c, O; V- ?
data: z1 I# o) C/ o, u6 U: a
c=8 7 9 5 2 5 9 6 10;
0 H3 ` t/ z) S% O enddata. ?8 N, j9 ~( Y; d; x
n=@size(nodes); !顶点的个数;& K$ C) m1 y3 e- j
max=flow; H3 v& F6 t. @$ ]( o- Y
@for(nodes(i)|i #ne#1 #and# i #ne# n:
0 d) T/ z. k1 Y8 e8 f @sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i); b) M% y4 L3 S' @% [/ C+ H5 W
@sum(arcs(i,j)|i #eq# 1:f(i,j))=flow;1 e) O0 J6 `# ~; ?% b
@sum(arcs(i,j)|j #eq# n:f(i,j))=flow;- [4 k2 F; ~7 u' P! |
@for(arcs bnd(0,f,c));
0 l5 r' @+ S6 z9 d end
0 _7 i' v/ \7 e) ^ 3 q# o1 c6 f. ^( A$ U- p
在上面的程序中,采用了稀疏集的编写方法。下面介绍的程序编写方法是利用赋权邻 接矩阵,这样可以不使用稀疏集的编写方法,更便于推广到复杂网络。
2 u/ l5 j& e3 \& v+ [ l) X2 N. p
- ]$ V, Z( F8 A6 w0 t. d; O model:( U3 n# x; C. ]' x0 o
sets:
! E# o! s# I9 f nodes/s,1,2,3,4,t/;
* X/ _5 X9 p! x" K- @% Y arcs(nodes,nodes):c,f;$ L. O3 t6 w2 p# G8 R2 j" Y
endsets" H9 K6 h t$ j# N6 j0 y
data:6 Q1 A. \' ?+ v
c=0;7 h2 s, s g3 @& k: j( e( b+ \
@text('fdata.txt')=f;4 T) F1 I% \- d# P3 ~$ }
enddata
7 j0 f" n" J( R4 ]) d8 v0 g- q. m calc:/ k( |7 M6 q8 h$ H
c(1,2)=8;c(1,4)=7;1 m( p3 c5 S2 g( E& }
c(2,3)=9;c(2,4)=5;
, Q1 D8 G: g1 r% R# O h6 J" D. y/ x c(3,4)=2;c(3,6)=5;9 o; \. A1 K7 w) S! }8 J% d
c(4,5)=9;c(5,3)=6;c(5,6)=10;
1 y9 _+ F4 K6 }2 f F endcalc0 s+ s' M* Q, D6 m% E6 T
n=@size(nodes); !顶点的个数;' J3 J1 V7 ]8 w1 [8 M ? b# r- w
max=flow; s/ V) \0 I8 ~
@for(nodes(i)|i #ne#1 #and# i #ne# n: p- R5 B* b+ A0 ]& |
@sum(nodes(j):f(i,j))=@sum(nodes(j):f(j,i)));
+ O% d0 ^+ X. q @sum(nodes(i):f(1,i))=flow;( ?( G) i! S7 y! Y; D
@sum(nodes(i):f(i,n))=flow;* f4 X, x+ }/ X, c( a' W( D/ b0 @
@for(arcs bnd(0,f,c));# \7 Z" Z% \1 H" y, R/ o
end
& }+ X, O+ A. g5 j( I& S1 O+ {& m
2 A' m9 F& l7 S0 @, q% v* X' F ————————————————
N( a8 J+ o" m) U 版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
4 k$ _ o6 o& |4 C. | 原文链接:https://blog.csdn.net/qq_29831163/article/details/89786313
1 m/ S b5 L3 I; S1 r) W+ A 5 s; e0 U2 `- H4 p5 n' g
' @$ d. [. E$ m2 ~3 a5 p1 x6 m/ l
zan