|
求解最小生成树的方法虽然很多,但是利用LINGO建立相应的整数规划模型是一种新的尝试。这对于处理非标准的MST问题非常方便。我们主要参考了文[7]。 + z8 a O" V0 r9 } _, p
在图论中,称无圈的连通图为树。在一个连通图G中,称包含图G全部顶点的树为图G的生成树。生成树上各边的权之和称为该生成树的权。连通图G的权最小的生成树称为图G的最小生成树。
8 A: u/ j# ]7 W( Q2 b# [3 I' _许多实际问题都可以归结为最小生成树。例如,如何修筑一些公路把若干个城镇连接起来;如何架设通讯网络将若干个地区连接起来;如何修筑水渠将水源和若干块待灌溉的土地连接起来等等。为了说明问题,以下面的问题作为范例。
" q( J$ M- B: u, i0 B2 q4 J范例:假设某电话公司计划在六个村庄架设电话线,各村庄之间的距离如图所示。试求出使电话线总长度最小的架线方案。
7 }, e* {! S& s _9 @4 i0 W0 P+ z8 P/ v' a6 e% h: D
- ]. H+ w/ T7 w8 j
- m( X8 T5 Q% G5 B" I3 i/ Z4 A$ P& Z7 c
: q/ i* j7 n2 O; c' L( a- n6 ^: x9 |. z7 @1 K
$ l! ^: D+ T: h3 G2 ~/ j4 Q) u J2 X
: k" f/ {# m( b$ Y
|
1 `* k- P% o$ J0 M V1 | 3 w1 @0 I9 _; o. N% V0 x
|
$ B& R% n8 H, E# k5 N9 ?3 H0 e8 J3 \
. k( g2 d4 d9 ?. x0 d5 {& ^& L( A6 c
' a; i- a P' l9 [3 v) O
, W3 H% a8 Z0 w( B1 u" l, X! ^/ f$ t7 P# g# V9 {" x5 |; d
2 [. y5 k/ }& J, s
# {/ Z- d/ q5 h, X! o$ C* e1 ?3 a# z" t
|
) F4 [$ c- \' ^) l. O V2 |
9 D U1 P8 O+ q$ H1 Z' E" x6 n |
* T. `" H6 v. y1 W9 z7 h7 G2 n3 c2 I |5 y9 M' _
$ {; K7 n% b. Y( _+ W( O& e) |2 C1 q/ J9 i- x5 A/ _1 {. U- F7 `- B: j V
6 `1 o" @& c0 S1 Y. S7 d8 |; t$ n9 |) r$ K6 C
9 C1 m5 u @/ { ^0 v ^& [) w3 {& w2 _) E) N3 l
, m# g9 d h( c. P6 q2 {
|
9 K1 e8 E, H( l. p/ a V3 | " D- q0 \/ b+ n1 J/ G4 v& p, _
|
1 t/ E0 r( f& _4 `
/ g% t7 Q c) I$ J6 _& G, e$ f A! [
U9 N" P, c0 i3 p+ N1 M7 |7 G" e" Q7 z5 _
8 ~, t* x+ {2 H& [+ q% N
5 I# `# h4 a. P) Q2 t
+ v+ P) R9 [% X
& d4 v3 |( w, c e+ o. ~
s% S0 ^/ K1 d3 ^|
% m7 u* |# G# W# h& X V4 |
' N4 g0 y; V: [* c | ) C6 i2 G l' }
% M( d- @* O; p# d+ g
7 i* {# ^4 n* {2 e; `$ [0 r
1 J" x6 P: l2 N5 D7 ~: l) [
0 j7 y2 z3 b+ l2 _
& A; M& d% o/ l/ W# C4 G
$ |. j7 B5 @1 q: ^, h$ Z+ C" v0 S0 M5 B' h) Z- }! C
8 c$ c# U! A, c t; s
| $ G6 E+ m& f9 H& K5 A, T1 [1 H5 r2 \: e
V5 | 4 I7 t& n4 D( v7 j( O
| 7 P7 q8 ]0 ~- p2 A$ L) Q6 ~
1 Y2 e l( i. {( m9 C9 M* ]
3 s- g& t @: j2 u& r
% G9 S5 q2 v9 ]1 a! c, X9 {. x# v
3 U+ ?+ z% b% `) c( k& X: U/ A2 C& x
& Z+ y( x/ E9 K* A) v# R
. s! D# r, Q9 T% W5 C3 b| 7 ~6 \1 ?4 w, f' t- f5 \
V6 |
2 K) u) H, Z: m! `+ G" ^ | 1 w- [, N* W5 K& d, j8 B7 \6 c [
3 F/ p0 {. U+ `1 w7 U' f6 h4 `
( @5 d4 U4 F! T7 a/ f' r! ]5 B7 C: O1 ?3 m
& b6 v0 g. r: G$ U" I$ j
' N+ I4 X. { }0 N
- |- c4 f! ]3 W) `& ^
5 I2 |$ {* K2 z7 T/ m M; k; S7 P6 u8 a) m% @, K
| & @# O, D5 a% s# }+ v' B: n
1 | ' J9 j5 l9 C: {
| ' p9 n8 Z, K+ \
1 B7 e! Y/ ~2 v$ `
& W+ f8 a* G8 ]
1 m5 x& a, s" @3 e$ w/ m8 z9 _* d% m3 y2 B1 I5 E
( j6 |9 Y4 e4 C5 h
1 h- [6 V# m4 j7 r. J6 G/ e
, ~: a9 X6 n4 Q- ~4 M' L8 a
\4 @- d7 O* \! e( G|
+ J* M; ?8 Y( C7 D- q: h- Q 1 |
+ N, B. A. w- f9 B* f# u2 t- o | , X: z3 C! e& j/ R& V
6 r5 A1 j& R4 ~& t m7 f8 V' _% T. Y1 J0 _9 J0 Z) i
4 t9 \ b- m8 u
1 J! @- I* S2 y B+ I% |
8 }! _% N# L( y% L. H/ |
6 S3 Y; d) P5 K2 I+ q/ h, [- A* F! W; a! ~# Q9 p
% B0 T& Y( |+ L, I& `6 g- i|
9 ~2 N3 F2 U+ F* m5 d1 d# R 2 | : U+ w! H; O- Z# }" E b
| % I7 I6 ]: Z6 E/ U9 `4 p4 o
; s. n: [: W% X/ N( d1 a
$ Y- N* h5 X1 |0 y
. i! b: |7 `# @, Z Z E8 H& R- X2 q* m& V9 o w% \0 B y+ w* K1 V
& l/ j8 j, L/ X% |' U: p0 V! ~- m5 P2 \3 T, k% G- |& w5 K
$ Q* L/ m% U7 D4 I- `9 H
& i- m5 {. Q/ v% e2 h1 D
| 8 J' s1 |# b7 s: O
2 | ( Y, R# I) F ]! a' |+ z1 h8 T( X- E j
|
2 h8 R( `0 ~! k9 w
" M7 V" U( q5 Y$ d# g+ C' e1 \- D' T& k
; j1 X' Y5 x, W+ X2 C
, \1 a" ^# R8 K& N W, \
. l/ E5 y: H& [3 z% I& o" y; v# y; f+ G' M& ] [4 A
4 l* _5 h) j( n5 D& _
# e3 S/ F/ R8 |9 k/ R|
2 l) ]+ a3 _ w$ \6 N; A8 K 2 |
1 ` j" e1 t5 \% f" j* n |
A$ @& k0 m7 o$ D2 A. }) P1 q: Y& s. q2 X% @
/ k1 N6 p9 q5 F6 i, s3 z) t+ A2 v' e# e* b
3 v$ y$ B1 [, l, v, W
, a. G" J& j$ W5 f# Z1 ^ h
, x- A" Z1 M1 F- I! D7 ?2 D% k& J- Y3 y
8 e& Z, }, o& |/ A: o+ u
| ! m' b& _$ j1 J8 }; [" H. P
3 | " ?1 f* v1 p; U& S1 c: W
|
1 R$ p* x) F+ z0 V0 S2 ^. p. K) d$ {2 Y& T) }3 U Q" E1 H% E) U+ _8 @
4 ]- s; t$ f' T3 O3 v* M2 N g1 L0 z
1 W# ~2 i7 L4 `# K
1 ~5 p1 X& N6 L. k5 m
/ ?! I& t. {$ Z- J3 H& R# K' ]) y" h8 H* _/ r: F- P
: H. M e3 X% ~
8 k3 U& J. \( ]1 }/ L0 q2 s| 1 }3 f. l" \( t, ?: Q2 @ u5 Y
3 |
) v) _, j% @6 p | # Y E2 d* {/ ?( @2 W9 ?
7 s1 H ?% T, ~; k: a/ u4 [% n, K2 V: `; Q. r
9 g p1 x9 O% K' [+ u4 ]4 r
3 H0 Q+ U* |) \' E+ R2 \) l$ Q; @& N) D T+ a: Y4 s9 `0 w2 W/ b
# i) w7 S' ^$ V1 C
" o# g+ V1 E) k- d
4 H5 I' S7 o7 V! b2 E# `|
; [+ N* i$ k. B' w2 X 3 |
6 A- `& Y5 p& i( x: @# A$ o0 R | 4 D/ C9 Y6 q4 P+ o: P/ F* U; Y" [
' L! u2 [7 t4 {! |5 @$ F, n1 o! s; x; | U
' { l; s- l" {& r, }9 S7 y, m; \& G/ i: y
- E. m7 l4 L. K$ O j2 M% ?
: S( d0 W+ \$ Y# \2 S* T" u+ M' _5 P
2 \: V* |: u1 `; |1 H& m
| * w# N+ |- z) s& k& K. V X- O8 e3 J
4 | 9 `- D$ T0 y3 `6 V B: x" B
|
8 F& l$ t9 x/ H4 U# T8 o, y) U$ x7 K2 g( K
$ n/ b0 Q$ m- o" j$ B( b" M. m1 z- `8 o4 z
\! i+ K. }) U7 I M) h
- b! r; X: \, s8 T/ _; `/ G& y2 x
[" j' e( E$ k' G
2 i5 m) `6 ?& b
| 6 @' @9 D) p7 v' G# B" @
5 | ( G- L, s9 e8 s- a* p! N( Q
| val>val>val>val>val>val>val>val>val>val>val>val>为了便于计算机求解,特作如下规定:(1)节点V1表示树根;(2)当两个节点之间没有线路时,规定两个节点之间的距离为M(较大的值)。
3 b) O* x1 s0 y: A7 D MST的整数规划模型如下:
3 c" f# P5 l7 ]6 G; a 9 k3 B; R, r7 y
. ?* Q* Y# a: T8 O, o
* n M0 L. g5 m - K' |/ c. `1 ?8 Y8 p
+ X% X4 _) ^) Z( g z
. ]% H# G+ Y3 M
例7.7 分配问题(指派问题,Assignment Problem)
6 ~+ F: k% d% e( Y这是个给n个人分配n项工作以获得某个最高总效果的问题。第i个人完成第j项工作需要平均时间 。要求给每个人分配一项工作,并要求分配完这些工作,以使完成全部任务的总时间为最小。该问题可表示如下:
7 F) y$ v- o) Q- H : f9 W$ _4 L$ O) I+ K1 Y; V
显然,此问题可看作是运输问题的特殊情况。可将此问题看作具有n个源和n个汇的问题,每个源有1单位的可获量,而每个汇有1单位的需要量。从表面看,这问题要求用整数规划以保证 能取0或1。然而,幸运的是,此问题是运输问题的特例,因此即使不限制 取0或1,最优解也将取0或1。如果把婚姻看作分配问题,丹茨证明,整数性质证明一夫一妻会带来最美满幸福的生活!显然,分配问题可以作为线性规划问题来求解,尽管模型可能很大。例如,给100人分配100项工作将使所得的模型具有10000个变量。这时,如采用专门算法效果会更好。时间复杂度为 的匈牙利算法便是好选择,这是由Kuhu(1955)提出的。
/ P. t7 T& ?( M6 _+ w, emodel:
* q- [8 V. ~# K4 k: V !7个工人,7个工作的分配问题;
. |5 M' Y( K3 K2 e9 _sets: 3 g; N& J) v3 ^( b6 v
workers/w1..w7/; 7 C- e2 h+ o2 s3 f0 x1 }" X6 E' U
jobs/j1..j7/; ) \8 J8 n8 K- H3 ^2 [6 G% h0 _
links(workers,jobs): cost,volume;
% ] x- u4 A4 m( mendsets
1 n+ G+ m! v* R7 L !目标函数;
* p7 Y, z; g1 | E- l2 a min=@sum(links: cost*volume);
( a$ s/ a' ^7 f- o, J !每个工人只能有一份工作; ( U4 ?! }4 e, B' f2 ?* H* b% h6 K
@for(workers(I):
9 d* T) T& a6 z3 h3 R# A @sum(jobs(J): volume(I,J))=1; 3 p% |( @) c" i
);
0 G& U1 t) J0 x# ~/ Y) [3 k !每份工作只能有一个工人;
2 p5 j) d- z% @8 h% f9 B* i @for(jobs(J): % h! h' ? ~( z2 \! A. B7 P
@sum(workers(I): volume(I,J))=1; N) n7 \7 K0 s' @
); - Q, k, S2 |* k1 X1 {. @1 W" p8 H, g
data: 5 o: _1 K* K0 a! r$ ~9 Q$ L
cost= 6 2 6 7 4 2 5
5 U# W9 J7 e$ c& Z6 D 4 9 5 3 8 5 8
9 l; l* x. A+ V m2 x 5 2 1 9 7 4 3 x. l% R( k: o. d& r
7 6 7 3 9 2 7
- [( G; g7 N: ?; t: m% }# v5 v+ Q 2 3 9 5 7 2 6 * R( F5 I( m" `% X" G; a8 |
5 5 2 2 8 11 4
' E5 `# \0 |/ W$ W! T7 Z+ Q; ^ 9 2 3 12 4 5 10;
/ b+ [* j v) H: n4 {enddata
+ G1 \2 N Z! p3 O, F- ~$ u) U, Y0 Aend |