- 在线时间
- 791 小时
- 最后登录
- 2022-11-28
- 注册时间
- 2017-6-12
- 听众数
- 15
- 收听数
- 0
- 能力
- 120 分
- 体力
- 36448 点
- 威望
- 11 点
- 阅读权限
- 255
- 积分
- 13895
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 616
- 主题
- 542
- 精华
- 12
- 分享
- 0
- 好友
- 225
TA的每日心情 | 开心 2020-11-14 17:15 |
|---|
签到天数: 74 天 [LV.6]常住居民II
 群组: 2019美赛冲刺课程 群组: 站长地区赛培训 群组: 2019考研数学 桃子老师 群组: 2018教师培训(呼伦贝 群组: 2019考研数学 站长系列 |
1 最大流问题的数学描述
" ?5 h% @' f7 `2 ?7 o p5 j1.1 网络中的流 定义# `9 [5 O5 S, z* q- p# C
在以V 为节点集, A 为弧集的有向图G = (V, A) 上定义如下的权函数:, l2 B; ^% b+ f4 t$ _
1 ^/ X5 I0 Z: e: x, R(i) L : A → R 为孤上的权函数,弧 (i, j)∈ A 对应的权 L(i, j) 记为 ,称为孤 (i, j) 的容量下界(lower bound);& Y9 f: F* U( t# m8 f
$ }6 A" D2 |" C5 W" M# y
(ii)U : A → R 为弧上的权函数,弧(i, j)∈ A对应的权U(i, j) 记为 ,称为孤 (i, j) 的容量上界或容量(capacity);
2 D* w6 C' B2 U( w% U: x
* i) W* n' G g( \+ l7 H. p(iii) D :V → R 为顶点上的权函数,节点i ∈V 对应的权 D(i) 记为 ,称为顶 点i 的供需量(supply/demand);8 t0 E! v6 s) X2 Z- l# M% c3 D
7 U' g( e P+ V- ?! E& F5 f
此时所构成的网络称为流网络,可以记为 N = (V, A, L,U,D) 。 由于我们只讨论V, A 为有限集合的情况,所以对于弧上的权函数 L,U 和顶点上的 权函数 D ,可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示,因此 L,U, D 有时直接称为权向量,或简称权。由于给定有向图G = (V, A) 后,我们总是可 以在它的弧集合和顶点集合上定义各种权函数,所以流网络一般也直接简称为网络。
" a( e1 v, i8 m6 b: R, J/ m) [
* G1 g8 s/ U( C% N6 F: i' E' ]! d在流网络中,弧(i, j) 的容量下界 和容量上界表示的物理意义分别是:通过该 弧发送某种“物质”时,必须发送的最小数量为 ,而发送的最大数量为 。顶点i ∈V 对应的供需量则表示该顶点从网络外部获得的“物质”数量( > 0时),或从该顶 点发送到网络外部的“物质”数量(< 0 时)。下面我们给出严格定义。: |% d: h, i3 o! _! K
% X; }5 [" I% q0 D5 L4 g8 n8 M可行流(feasible flow)- [/ o9 l* \* H& ?2 h6 F
) I. T3 q0 w; E" b: u
![]()
& v. {) E8 g* I; f3 A1 c, I1 g# ^4 z" J6 R4 ?7 P$ R% F
- G: t8 s$ g6 o( j1 Y
可见,当 di > 0时,表示有di 个单位的流量从网络外部流入该顶点,因此顶点i 称 为供应点(supply node)或源(source),有时也形象地称为起始点或发点等;当di < 0 时,表示有|di | 个单位的流量从该顶点流失到网络外部(或说被该顶点吸收),因此顶 点i 称为需求点(demand node)或汇(sink),有时也形象地称为终止点或收点等;当 di = 0时,顶点i 称为转运点(transshipment node)或平衡点、中间点等。此外,根据 (1)可知,对于可行网络,必有6 O* q" g ? q% a/ j
( a. E9 w( X2 h3 M, E: @' p2 l
+ Y/ ?. G" d# q$ i
! m+ k/ j' }+ {4 p+ R! G- [
也就是说,所有节点上的供需量之和为 0 是网络中存在可行流的必要条件4 v/ ^9 ?4 q2 f% K9 h
" X' t( O, N- p![]()
( Z* I! O- M6 h![]()
8 y, _! y1 p' v: P6 { n# o- N3 `/ `. f
1.2 最大流问题; C6 ~! j: v) K1 P+ h) _
考虑如下流网络 N = (V, A,U,D):节点 s 为网络中唯一的源点,t 为唯一的汇点, 而其它节点为转运点。如果网络中存在可行流 f ,此时称流 f 的流量(或流值,flow value)为 (根据(3),它自然也等于 − ),通常记为v 或v( f ) ,即2 I* Z% Z! q) W# @$ W) I* X% R' {" v
8 t; h7 g: L- y9 p, f
3 p9 r; s. Y4 q6 S) R9 v
对这种单源单汇的网络,如果我们并不给定 和 (即流量不给定),则网络一 般记为 N = (s,t,V, A,U) 。最大流问题( maximum flow problem )就是在 N = (s,t,V, A,U) 中找到流值最大的可行流(即最大流)。我们将会看到,最大流问题 的许多算法也可以用来求解流量给定的网络中的可行流。也就是说,当我们解决了最大 流问题以后,对于在流量给定的网络中寻找可行流的问题,通常也就可以解决了。
& |1 [6 C" J9 Q0 Q6 K) h( k5 Q6 a8 D' e8 N" ]
用线性规划描述最大流问题3 X" w3 O9 j- _) a- K4 M5 l6 q
因此,用线性规划的方法,最大流问题可以形式地描述如下:
/ |5 k* ~, e0 _1 b* i; l" V! A% T3 _
, s9 S( u1 l& [- A: G; H
2 T# } U( ?0 R& v定义】 如果一个矩阵 A 的任何子方阵的行列式的值都等于0,1或 −1,则称 A 是 全幺模的(totally unimodular TU,又译为全单位模的),或称 A 是全幺模矩阵。
- h3 p g/ u5 l9 ?% M0 ~% T5 ^/ }3 o, I5 F; a5 N" u* {9 w4 U
整流定理! O1 r5 j9 M& o$ K6 {+ {
【定理 7】(整流定理) 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量 均为正整数,则问题的最优解为整数解。 最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点,解决这个问 题的方法较之线性规划的一般方法要方便、直观得多。
* I: t- g- y% C! t0 ?. D0 [( X( g, q( Y& o. r
1.3 单源和单汇运输网络 l3 X, D2 K7 N7 Q
多源多汇网络 转化成单源单汇网络
2 N6 s5 e! g, f) s* S$ A' @$ c实际问题往往是多源多汇网络,为了计算的规格化,可将多源多汇网络G 化成单 源单汇网络G' 。设 X 是G 的源,Y 是G 的汇,具体转化方法如下:
! J9 ^" e$ C6 g3 T4 t2 f I" B! T2 P
( h- \2 B5 z4 K) {2 u# y(i)在原图G 中增加两个新的顶点 x 和 y ,令为新图G' 中之单源和单汇,则G 中 所有顶点V 成为G' 之中间顶点集。0 y0 b) {8 L1 x, _7 D
' E; I- w/ r. g
(ii)用一条容量为∞的弧把 x 连接到 X 中的每个顶点。
5 V: u: W2 e7 T/ z" d, s5 O! W% n( M3 }8 y/ R
(iii)用一条容量为∞的弧把Y 中的每个顶点连接到 y 。 G 和G' 中的流以一个简单的方式相互对应。若 f 是G 中的流,则由
; j. v' p4 G7 q m$ ? l! s6 v6 a' j
![]()
. h( U5 _5 Y+ p+ j0 l2 |
# o/ K0 `- T! b2 最大流和最小割关系割的容量 ( a2 Z" c0 E9 |- @$ S
* c- a9 v9 E, p) _: g$ U2 b 5 ~( q4 j, N! T" J' B( X/ r; C- D
: H6 E; P8 T @* V: W$ \$ L2 I, p
则在这条可增广轨上每条前向弧的流都可以增加一个量δ ,而相应的后向弧的流可减 少δ ,这样就可使得网络的流量获得增加,同时可以使每条弧的流量不超过它的容量, 而且保持为正,也不影响其它弧的流量。总之,网络中 f 可增广轨的存在是有意义的, 因为这意味着 f 不是最大流。" O+ H O8 k" G* r: X) t
5 a6 J0 T* V6 N3 最大流的一种算法—标号法9 p% D; g2 O* O% z
标号法是由 Ford 和 Fulkerson 在 1957 年提出的。用标号法寻求网络中最大流的基 本思想是寻找可增广轨,使网络的流量得到增加,直到最大为止。即首先给出一个初始 流,这样的流是存在的,例如零流。如果存在关于它的可增广轨,那么调整该轨上每条 弧上的流量,就可以得到新的流。对于新的流,如果仍存在可增广轨,则用同样的方法 使流的值增大,继续这个过程,直到网络中不存在关于新得到流的可增广轨为止,则该 流就是所求的最大流。: p- j8 h* Q6 Q8 Z. [5 `6 [
. T& s# f" N1 E6 n! M K& r这种方法分为以下两个过程:
& g8 b6 A W3 E8 d, ~4 ]) z c, `7 T) w2 z' E1 C
A.标号过程:通过标号过程寻找一条可增广轨。
2 r/ }1 {7 J* Y: }& G6 A9 h8 f7 ]* E- f: f* H; ~( @4 I
B.增流过程:沿着可增广轨增加网络的流量。5 w1 o" H7 z# j2 W
( k. N9 D3 r5 Q3 @这两个过程的步骤分述如下。& e3 g: Z, L' M' f! |
8 x! r; y# G! Y* H
(A)标号过程:
- m- C! i) u# Y; j' e) \- h% H
8 i2 s% L0 I/ c" i * z. L q" s' s1 u; g) z! d. e
5 o4 l# e" E* ?/ t' R(B)增流过程 , }* [5 H) l. Y1 t6 c/ z4 z) l# O. {
7 {0 V4 g5 o8 ^+ ~ x; F
网络最大流 x 的求解步骤. c7 S4 G) x V3 Y9 A6 j& ~
求网络 N = (s,t,V, A,U) 中的最大流 x 的算法的程序设计具体步骤如下:
9 h! B% T* W5 P" | [
1 N+ O! E y, R* i' H对每个节点 j ,其标号包括两部分信息 (pred( j),maxf(j)); A; r$ D, V% e9 i
6 s2 @4 p! [6 N9 f
该节点在可能的增广路中的前一个节点 pred( j) ,以及沿该可能的增广路到该节点为止 可以增广的最大流量 maxf( j)。
! ]9 L* I, x4 i1 U* x$ `
5 C( K9 ~% t! N1 Q9 S* J/ C0 r. ^5 B 4 X- |) n E' i3 s( V, b$ ?
+ J4 C0 S* b; C% y9 Z% j0 t
并将 j 加入 LIST 中。 例 17 用 Ford-Fulkerson 算法计算如图 6 网络中的最大流,每条弧上的两个数字分 别表示容量和当前流量。 " f- t1 d( y& |; p
* G' V7 k9 a# T+ ~8 H+ e1 Y* L& t
3 N% M) k; \$ L9 d; i7 k6 k) E- S解 编写程序如下:
% s) u5 e$ L. [! H: [3 t
( x3 t' m0 O9 ]$ o+ G" \clc,clear. N5 W/ V2 t; N9 I+ `2 J
u(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;
* T- a( |$ b6 I) uu(3,5)=1;u(4,3)=3;u(4,5)=3;5 {4 x5 t$ f# @ ~+ B0 n
f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1;# q" b. @& p- T& Z& v9 `9 u% ~: X
f(3,5)=1;f(4,3)=1;f(4,5)=0;
( p/ r H) d1 w. g. In=length(u);list=[];maxf(n)=1;5 D+ Y2 A8 X7 Q' q+ `2 C8 n
while maxf(n)>0* n/ w7 k; H5 f4 q; _! @; n
maxf=zeros(1,n);pred=zeros(1,n);8 e6 n7 R' X* G$ w/ x$ c8 k! J5 U
list=1;record=list;maxf(1)=inf;4 z3 N8 ]* k3 x8 [
% list是未检查邻接点的标号点,record是已标号点7 F, W! z) D( e2 z
while (~isempty(list))&(maxf(n)==0)
4 m- I) S# d; C" |+ E9 C flag=list(1);list(1)=[];
5 Z& V% t8 Q- S2 q* Y9 a7 L7 l label1= find(u(flag, -f(flag, );- W8 M- {" m+ Y E! w9 z( c5 b
label1=setdiff(label1,record);3 p, z* @: X; E8 z' R) j
list=union(list,label1);8 f+ o! C. ^" `5 `1 }
pred(label1)=flag;
* t% X2 F+ v% F( t' D maxf(label1)=min(maxf(flag),u(flag,label1)...
`8 ?. X! _8 z/ Z2 \ -f(flag,label1));- K. u; h" q; X: F
record=union(record,label1);
' Y0 L3 u. X6 k: B3 n' h label2=find(f(:,flag));3 {% z6 G5 ]- D3 v" H# B6 w5 l9 o
label2=label2';
4 @" A8 |* S0 t2 s4 a label2=setdiff(label2,record);
8 }; `- x+ L) Z: e list=union(list,label2);$ j# X# P# [# Z" | l
pred(label2)=-flag;0 f2 E9 I4 e! f2 R2 m1 ^
maxf(label2)=min(maxf(flag),f(label2,flag));
( R. }( x5 ~* w6 g, |- n) ] record=union(record,label2);. i: G) [% Y! ]4 p
end7 l, c7 m( E5 H; C+ K, f
if maxf(n)>0# z' n) d+ M; q/ M# m+ h1 ~3 `" ~
v2=n; v1=pred(v2);
7 G# K9 R6 E' y4 V7 k! C while v2~=1
+ a7 A2 r3 z4 I( a- k N) p if v1>0
+ U* f3 u! J) x+ I3 \9 P% l- ]% e1 J f(v1,v2)=f(v1,v2)+maxf(n);
t" X8 C8 m3 L6 D( X" M+ _ else
6 L* i! N0 L8 A4 I3 @4 W v1=abs(v1);4 I S3 N9 L! Z; r; O
f(v2,v1)=f(v2,v1)-maxf(n);+ {2 C T' c2 h( d; D
end
/ C! \: _! c% U9 I) r v2=v1; v1=pred(v2);$ a+ N* a! F5 h1 ?$ p6 Y. x" r
end
8 b" w6 I$ X+ {, [! @+ G end {& H% q0 ~6 O7 Q- @
end) t L8 [ M7 I" \& ?
f
1 d. F* `* K6 c% `5 a例18 现需要将城市 s 的石油通过管道运送到城市t ,中间有4个中转站 v1 ,v2 ,v3 和 v4 ,城市与中转站的连接以及管道的容量如图7所示,求从城市 s 到城市t 的最大流。8 @, Z! W4 [" p4 B
3 w% ~3 o- U8 f( T' z8 a$ \/ V9 P- g% l! V& q
![]()
& j; K8 t6 W% `7 H. X
. p$ L2 K% t' L4 a) I9 _解 使用最大流的数学规划表达式,编写LINGO程序如下:
7 L0 U1 w$ h1 ?* y4 ]% A' p6 {
% Q3 D/ p p& \0 I/ u2 n/ r* nmodel:/ H: f+ ?4 H( V7 c1 w1 n
sets:
/ @7 r8 A% D" V$ C& Onodes/s,1,2,3,4,t/;
6 |% f0 i0 p3 w* p4 r7 U* Carcs(nodes,nodes)/s 1,s 3,1 2,1 3,2 3,2 t,3 4,4 2,4 t/:c,f;/ W1 k+ F' }7 [3 G% N/ ~, H( T
endsets
! S! W% r+ L* Q! Jdata:
" V }5 B; a- h" |' `# Kc=8 7 9 5 2 5 9 6 10;
0 _% J; N! s% [! Yenddata4 ]- Z" o, {+ C
n=@size(nodes); !顶点的个数;" N) V& h; T8 y' b8 `& U
max=flow;2 E1 `( W( ]# o; d
@for(nodes(i)|i #ne#1 #and# i #ne# n:
6 p& R, o* u" P- _' w @sum(arcs(i,j):f(i,j))=@sum(arcs(j,i):f(j,i)
C- ?7 b1 z9 I% x! [# f0 h@sum(arcs(i,j)|i #eq# 1:f(i,j))=flow;
% [' H2 V; c* \, B, O3 ~3 m: L@sum(arcs(i,j)|j #eq# n:f(i,j))=flow;0 f) M- M; b+ z) Q& Q3 |
@for(arcs bnd(0,f,c));
, h9 C2 b) u4 v1 x! h. f4 Q7 Lend
: P1 |% p" k$ V* d* m V' ]( P
u. @, o2 t' V3 |) z: H) y- ]在上面的程序中,采用了稀疏集的编写方法。下面介绍的程序编写方法是利用赋权邻 接矩阵,这样可以不使用稀疏集的编写方法,更便于推广到复杂网络。
r1 r. k: r# x- C8 [7 G
v: X4 Q9 F0 G2 C/ Zmodel:! {1 k8 W N7 R8 z4 u
sets:' m: H; ]$ C: U G
nodes/s,1,2,3,4,t/;
5 w" R1 {; G, R0 X. M# Jarcs(nodes,nodes):c,f;* O8 q" R. _0 C* R4 X5 s
endsets
3 c& T) b/ s( kdata:' e3 r0 l/ T0 g5 X
c=0;
7 a ?$ q M& J" F" O3 m2 v@text('fdata.txt')=f;
/ u& _. A1 _% C" ]enddata" W3 ?. }" r$ h% @# E
calc:
& S1 E1 {( `6 V* G9 Vc(1,2)=8;c(1,4)=7;
% |* H( s/ \6 l# i8 s( c pc(2,3)=9;c(2,4)=5;6 d$ a- u+ p7 Q' n
c(3,4)=2;c(3,6)=5;, p. f* n: }- O' ?( Z( _6 h8 E
c(4,5)=9;c(5,3)=6;c(5,6)=10;
# c: C! p) ^% Z8 J a, m* s4 R7 jendcalc
% Q! I" Y! L3 O6 W+ v$ J6 sn=@size(nodes); !顶点的个数;( B' R# c. W* h' S- I0 N
max=flow;
7 E9 Z7 O$ x/ {9 r6 o3 F7 T/ Z' x5 _@for(nodes(i)|i #ne#1 #and# i #ne# n:
W# w) g- J1 S7 _. g6 ] @sum(nodes(j):f(i,j))=@sum(nodes(j):f(j,i)));0 c N3 D5 n# C1 ~
@sum(nodes(i):f(1,i))=flow;. L9 f8 p) l+ Q2 Q& K4 c# i" }
@sum(nodes(i):f(i,n))=flow; Z& L$ H, r/ T) h8 d7 J! @
@for(arcs bnd(0,f,c));
. C# y5 ^- L8 V9 Oend
( S9 L/ L3 D- z8 w+ G# C
( H$ e2 U9 _ V9 p————————————————
+ l4 d7 M* V4 X版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
/ B5 K! d, L7 \1 I; r: b+ q原文链接:https://blog.csdn.net/qq_29831163/article/details/89786313
* k- _: n) v2 F3 a. b7 n
@+ p9 y0 ] g/ b7 [+ R
9 _ [ i* q& @/ }8 z g7 e# G' s |
zan
|