|
求解最小生成树的方法虽然很多,但是利用LINGO建立相应的整数规划模型是一种新的尝试。这对于处理非标准的MST问题非常方便。我们主要参考了文[7]。
$ s: S& d1 | ~8 q9 t在图论中,称无圈的连通图为树。在一个连通图G中,称包含图G全部顶点的树为图G的生成树。生成树上各边的权之和称为该生成树的权。连通图G的权最小的生成树称为图G的最小生成树。
9 Y0 F5 |+ \" m5 M/ a9 z( S! p许多实际问题都可以归结为最小生成树。例如,如何修筑一些公路把若干个城镇连接起来;如何架设通讯网络将若干个地区连接起来;如何修筑水渠将水源和若干块待灌溉的土地连接起来等等。为了说明问题,以下面的问题作为范例。 6 X8 p: f( N; ?3 w3 |. j
范例:假设某电话公司计划在六个村庄架设电话线,各村庄之间的距离如图所示。试求出使电话线总长度最小的架线方案。
5 U) B) p. v* a
4 T! t1 x5 q2 K- \ Z" |- H D% q' ~! w F7 e+ S# d
- |( f8 e6 x" M- N- ^
7 r; C9 Q/ `: E- z+ S& s6 c
2 x0 ?% }* m9 _2 u/ `
# o9 f4 ]6 E/ B( M; u A: N# ?# z3 w7 N/ J% U1 K; W+ h" j' n) q
7 Z* m- p! q9 i2 Z$ J& i% O: P( C! c) L# Z S( v" M5 X0 D0 X; B6 ]
|
p5 b# P. Q- t7 R2 c# g1 t1 G V1 |
! i" E; p/ I& L8 \8 V- y |
" o8 x8 q0 w( `# e' m/ a9 V, }; Y3 {
: N) f1 g5 u# @# [" q" K2 }/ b$ F; f' Y
& `' z& I* Z+ Q; c8 t% l# e+ r! a8 E7 R) E) k
1 P$ K& D5 N% |% U
1 W9 \+ R* }5 G: U: ~6 S* v) L
& H* R$ Z9 e4 \' @; C) |& ]
. o! d4 f2 X) m1 I, o| , |' Z! p. A3 `4 S- |+ t% K. `
V2 | ! Y4 |- _" D# R. ^4 }
|
) N) a7 m) _/ x5 p' m8 a' V$ Y; b* H# _6 g% J+ w1 c
6 E% h& ?2 F- h, C2 y, q( @+ l8 a! o
6 Y. M+ d& ], ^0 j2 C x* ~: b0 d4 |, i4 [3 G8 c3 G1 _
) S5 R5 g5 w; `4 k/ v
9 W/ b6 r& p. k' X* \+ H: X/ Z8 ^* b9 x& f/ r
| 8 b' X3 e5 j- J) q% B9 G
V3 | * t z) e. f$ a+ h% D/ R% `
|
& B8 [2 F% }7 S- x7 E) C( Q- P+ {2 W7 B7 ^1 w7 z5 Q5 N" B
, r+ J8 C& M" j! e7 d9 u- Q
* q3 V3 ?( p4 B( ^
, S9 m5 J) @* X4 M# P& J& a: F# ^9 }6 A" Y
& \, x& }4 @) o7 Q2 a3 @( i( b. ]
e) e2 K0 r7 l% E# f! L
( |4 Q" p5 W5 q% k|
$ p2 w& i& N2 M, X5 n( B) K V4 |
& Z% F4 E# d3 |" `2 ?+ ~8 R | 2 x/ ?0 O; e: {+ S+ H) T5 Y+ {. I
3 P4 z! W! l( M9 h5 L- N/ x h& E& N! s& p7 K+ L5 J6 R) V
0 b# }2 h t# F X5 B
- P3 q9 C6 N2 U: [/ c5 B9 \5 |2 U0 [# T/ w' I1 T M
* ^: W$ ^% y4 F/ v; C- F
& w( W/ V/ P7 j# v
R% A' Z9 C7 j6 Z9 P| 5 d0 G* a) A, b0 p( ~- s
V5 |
; r6 ]% d" u1 |6 ` |
: H: u: |0 j- `# o" B& m: J
: b% ]" \, Q% d( W1 R! ^; c6 G
! ^+ [2 t7 H2 P) \8 M: R' j6 c
) z6 b2 [; }+ |: }7 r- Q0 u3 O1 r7 o
& F$ u) P( F, y. r* a
5 L O3 E; A4 Y n4 p; d0 q( P0 J' z* E& {0 P$ u; L% K9 f0 c
3 x' b6 B4 I5 F|
1 P7 b! @+ x7 l, _ V6 |
" S3 e& V1 C5 u* D; e' A | 3 V8 H: _7 l' `7 {
8 q0 @9 V8 N9 [) j3 Z! Y0 B3 j% B
' j3 F9 [! U9 Q. e% j
! t% H- I4 _, ]0 @9 r6 D2 \' F' Y7 k& C) Z1 h
z6 ~- f7 q! G- K
& r' ?# I8 b* @6 ~1 q6 ^. W5 N8 ?4 s9 i V5 Y
7 g$ N9 i) l% u% ^4 j% r! V7 a. F|
' L/ G$ \0 x* K. { 1 |
. `1 C& I$ F' a8 K" O" L | 4 i6 S1 g; \1 n& f. j( ^2 a
) l) [ K. s3 q& o
7 u- ^% u7 m* D- C' U- [7 e1 ?
' g( d) s( V$ g& {; u( L
& B2 [) ], k4 ~% G) w' x
5 c$ r4 L) q0 r/ `1 S$ ?& w: K, [5 _- S5 X2 w# Q
% Q' L% u; f L1 s
9 X5 W; w8 W0 r. o1 l, v
|
& k: i4 }. R* T) O 1 | ! E3 N6 O$ ^; I4 O3 d% ~
| 1 s& S* V+ |. w2 d" V
) \6 C! d9 o9 P7 ?
5 ~: v* F: m8 a( L* D/ v% E' n3 p; M) r( n
' K, ` b9 R- K
( c7 y( |8 W& D' h0 N
' g3 c* ~5 f/ d* H5 m, U% J; K5 Y: D
' H4 x* P4 f" Q6 v/ h
| 9 D) h* T5 @3 }7 J j
2 |
A4 @+ m6 n' I/ w( x- A |
+ t- g/ D5 }6 n8 F/ j6 j8 c0 X, P" Z% i/ E% r
~' L( @! z5 V! k9 J6 Q
3 x6 ^" y1 ] r }% e) e! M! M5 q/ G3 ~
& z5 L, ?# R w% G* F& _& {
4 U. t' G& c7 u7 S* d5 {2 N4 F# f. w' c# z8 w3 b
; k6 U% Z2 O* k7 Q
|
7 v9 i+ d7 W; w, U" \ 2 | ' `' { E/ J& a5 w8 q4 {
| ) m! v% v) {# Z) L2 {
3 e1 E& q; y& A$ Z5 D5 [' R* |9 z8 K/ d N$ b3 U
& s2 c: D, {" y' U: Q
( D( i; \- a5 w' V/ s \% u! ]& L" O. k, x; W
; F+ S& a4 Z8 ?1 [, G3 ]4 k$ f' \/ ?
% {4 ~7 x$ \7 o+ H% p% u7 X; {1 a/ y
| . c- Y* ]: K/ U9 _# S0 _) i
2 | " k8 G! C$ C/ y. w8 b! I
|
8 Z7 v, X8 ]2 }1 S* K$ Y& v; F$ v% j: O
5 g8 [0 l* Z1 j0 b) Q: q+ f1 X# K/ g' _% B" c+ p
. P2 S T. z) Y. p% K( G
y0 P0 H3 z: y% u6 J" V1 W
. M1 {1 O5 a! m3 b) U0 z
8 c4 v2 W; r. h) C
3 C( l& h; l. A$ R- i| ! r. E! B/ e/ _& O1 v
3 | . w1 f$ M* z0 I/ \7 n! w: ?
| 2 v" ~, ]# `3 e2 N. N3 y# b
* ?& Y4 I( l( m( r/ N+ r! z/ c* ^
! L! V6 ]% k8 G; W6 d* [
- c$ }- b- k" ]9 [" I. @) `3 |9 i% q1 ^6 z0 e5 G' P
2 L. ]/ w# ?: q
+ {4 x: F/ h9 l* H
6 |5 X/ L( m* W/ `3 o& M
5 G r7 e# c: C& f- ?6 B* \|
& y7 Z* k8 Q( @+ O 3 |
! M9 ~+ H& C6 i' Z/ i% F* P |
& s, Y! H3 K% o6 }0 c3 i; `0 e7 L" @4 R) t' [" A7 D5 @ {
% {; b$ Y+ h* |1 S( E4 Y* p) n% J- D% r4 l8 i& T: H/ r' H5 ]7 x
B+ U6 N* D& O$ k* j2 s* u, l% D: l- x- [: y
& a) U! Y: o/ _
+ N; [0 k h: I# F
' H0 G: W8 R f0 @' ]6 z| + w4 [/ s) Q- c( G. a
3 | & q5 {$ F+ ~9 \+ V, I, I- z7 n9 l
|
; Y+ l: W# H7 b( `, Q7 M1 ~" H6 l+ i- ?- u& b/ e* i
0 j, W3 T9 F4 H: K; t+ P# u% s* E0 N0 K
+ b. }4 s9 t1 J8 h7 B- A
" Q$ ~6 S! u% \: j; `
, u- ^* h9 S6 t7 D* V
% H. \) G1 {% A" p$ K
! O, x+ C+ H% q* }4 C, y| $ J x- j. t3 d" a2 A3 m- i
4 |
- W/ h. ]7 p# R: M% \' T9 Z" {" ^ |
& J. j3 i7 T1 E' M8 ~* K; W! e6 u7 @3 n3 O5 A
1 e' U d$ d2 i1 b
- J' K% [( K7 j5 M7 v( a
3 d5 p! i1 j+ O' B/ W
+ f* \; Q& A8 t
# x- w9 @3 S( }- W8 ]- U$ `- q9 Q8 }
' P5 y" F; m* s1 w6 ]9 O6 \
| % G4 \2 X& B8 ]5 G% @- f x- c
5 | + t. | M$ U9 h0 _$ k( H
| val>val>val>val>val>val>val>val>val>val>val>val>为了便于计算机求解,特作如下规定:(1)节点V1表示树根;(2)当两个节点之间没有线路时,规定两个节点之间的距离为M(较大的值)。 - O- x$ n6 j, {) I p+ D
MST的整数规划模型如下: ' [, I7 ?2 N$ H _/ e# ]3 i
f: R' X& J8 t; U0 m6 x! l3 s) ~
: _" K: |, t0 d* F6 a( V( ?( ~2 k
) ]: Y+ j, V. E1 R
% @) [0 M Q# ]1 B+ [6 x' Q
8 p3 [" Z S+ i8 v3 M $ I1 N* h l+ F* u
例7.7 分配问题(指派问题,Assignment Problem) - k7 ?5 `9 p: o. Q1 x( j' z
这是个给n个人分配n项工作以获得某个最高总效果的问题。第i个人完成第j项工作需要平均时间 。要求给每个人分配一项工作,并要求分配完这些工作,以使完成全部任务的总时间为最小。该问题可表示如下:
% m9 v4 N6 U' @/ N- Z ( c4 Y( ?$ Y8 n! c) P) a
显然,此问题可看作是运输问题的特殊情况。可将此问题看作具有n个源和n个汇的问题,每个源有1单位的可获量,而每个汇有1单位的需要量。从表面看,这问题要求用整数规划以保证 能取0或1。然而,幸运的是,此问题是运输问题的特例,因此即使不限制 取0或1,最优解也将取0或1。如果把婚姻看作分配问题,丹茨证明,整数性质证明一夫一妻会带来最美满幸福的生活!显然,分配问题可以作为线性规划问题来求解,尽管模型可能很大。例如,给100人分配100项工作将使所得的模型具有10000个变量。这时,如采用专门算法效果会更好。时间复杂度为 的匈牙利算法便是好选择,这是由Kuhu(1955)提出的。
# X+ r' Z7 j' v9 r8 a/ Tmodel:
9 E. A, y7 o+ j" S2 Y8 K' ~" D !7个工人,7个工作的分配问题;
2 n0 o& J+ G# H2 M( T/ Zsets:
@9 j, s" T( ]" H; W: W# [+ T2 v workers/w1..w7/; 1 o5 [" a2 L. s# x* B3 P4 N1 b1 n
jobs/j1..j7/; , G; G) ?9 h' d8 h2 f1 u/ i
links(workers,jobs): cost,volume;
# k3 c# Z3 X% T h! O' m0 d; }% ^endsets
/ M- ~% Y$ V2 @: t !目标函数; 4 N5 r& w* h; |7 H# q( X, {
min=@sum(links: cost*volume); 5 g2 c- M0 y: W$ s3 G" N3 @6 S
!每个工人只能有一份工作;
1 P2 [4 h: J$ D- u1 p/ P7 z @for(workers(I): 6 j1 `( b* H h; j
@sum(jobs(J): volume(I,J))=1; & O9 t/ _+ i8 [( x2 I
);
: Q' t# i" U5 B) u1 O5 p !每份工作只能有一个工人;
' q& S3 s3 [) @( ^2 W. ]; i @for(jobs(J): # U, b6 v7 b: J1 G. B: a5 M) w
@sum(workers(I): volume(I,J))=1;
) @. R% K8 i( }$ U6 S, b );
" S: @ q! C$ R0 G; o* Kdata: 7 M* n9 ?; p- b6 i/ k8 L5 M& L
cost= 6 2 6 7 4 2 5
$ K$ K1 v% C! Q 4 9 5 3 8 5 8
' p5 ?' S; u7 k. r. s) E4 j9 `8 ] 5 2 1 9 7 4 3
$ s/ X' N! g' f- @9 v6 |2 D 7 6 7 3 9 2 7
Q; e2 K# }! }$ Y% l* y# P/ n 2 3 9 5 7 2 6
0 }1 t; K# S" P4 E8 ]- m 5 5 2 2 8 11 4 , A/ H. u( G6 K! a5 y5 I4 \4 e% Z
9 2 3 12 4 5 10;
8 F9 [" U9 _' e, A5 L! B; P8 S4 Jenddata
& O) R9 Q. y7 P! }end |