|
求解最小生成树的方法虽然很多,但是利用LINGO建立相应的整数规划模型是一种新的尝试。这对于处理非标准的MST问题非常方便。我们主要参考了文[7]。 - `9 b5 a$ d2 z7 d, b
在图论中,称无圈的连通图为树。在一个连通图G中,称包含图G全部顶点的树为图G的生成树。生成树上各边的权之和称为该生成树的权。连通图G的权最小的生成树称为图G的最小生成树。 / v/ G/ b* ~4 B/ H! O3 I$ y/ v7 r' ~6 u0 \
许多实际问题都可以归结为最小生成树。例如,如何修筑一些公路把若干个城镇连接起来;如何架设通讯网络将若干个地区连接起来;如何修筑水渠将水源和若干块待灌溉的土地连接起来等等。为了说明问题,以下面的问题作为范例。 ) P. @* @4 J0 E. ?# d- |$ k$ |
范例:假设某电话公司计划在六个村庄架设电话线,各村庄之间的距离如图所示。试求出使电话线总长度最小的架线方案。 * i2 w: b3 F0 v7 h/ _
# z# K# S Z$ A
) Q5 n4 E# T2 ?$ _ w0 d2 i
9 }6 _1 y6 e8 z- `# d
9 o- H. ]0 v+ Y7 S/ T- z) V9 f
! p- \) f) X0 D7 @1 l* g, D* m# O2 u3 z. j( o" V; |
# i+ V. K0 ]" w
* G3 h# V# l) h3 Q: K+ P& {8 [4 Q8 ~) r; Y3 x8 S# P
| 3 u4 x; J% R4 H! [( ?8 t
V1 |
3 d: R, z$ b+ ^# v( j M |
+ K' d! |& c% S4 Z5 ?9 Q: s7 G( s# H$ f, z5 `* R' ~5 L
! p/ \# T/ C. H7 U6 \, K# w0 t. D/ y/ n
# E+ b4 _# P# u4 d! M
, D% y! C6 M' B X( o. `7 S9 b Y1 n* [6 A% H d# `: P9 ?
' l/ P' _2 o: t3 N* q0 \7 [; L2 u5 _/ W4 s7 c2 @, N
| 0 l( Q7 A5 C/ O0 L) F
V2 |
, c& Z; t7 P2 x) ]2 m |
+ M' r* ]& s3 }. y' J1 ?2 A% o0 |0 v( ~" i3 Q4 W8 V
* |( X* d7 D* q9 b% [
& V e: r$ @9 v c3 _
* z% \+ i' D3 P4 S1 ]1 ~2 Z5 G- D+ c) k- Q
6 x; g8 a/ X( J+ P' @
- ^1 ?$ y0 T& |% a
m. r7 ]. P8 P7 N1 J1 E. q| , n, `( i( G8 n
V3 |
: h; M' G( }" _9 N" M6 X0 g | ! E0 Q# e! E( e% a& N9 V4 n
0 K0 I/ [1 M% A9 D
9 ~4 o: m5 m, {8 `4 J
" ^5 K2 U# ]0 q- B. t
7 p) X D: b2 C3 k' w, i
9 a/ R$ y+ }9 h- [3 a _
: I" \ A1 Q* L9 Q' q; X
* u* X1 p4 y8 ~# i3 d( f7 C) Z* m. \% m( S& T
|
5 ^; a: Y3 L! o, H# x w2 H V4 |
" T7 j) d7 |) C3 p$ j | 0 _) T( Q* \- c$ g
5 t. H$ T* w- E5 o# d2 N
+ q) c0 O! i8 K7 r |
3 ~1 A6 H8 G1 c5 y; K- I* H) t) v( R5 I* d
, h& i: `" q' s7 M) y
# I! f B0 C+ u5 d8 n* S1 r# r2 T; G4 t9 {5 U, p" j! y$ ?8 `
5 P' O; ~) g" w0 E& S2 @* W5 c3 }| 1 S; E$ I6 R# h: y- v
V5 | {) l- v# P+ Q/ L3 f" @; k! R
| ' f7 L/ w& Z2 |, d S+ g
9 L0 X2 S7 l( x3 p
* J6 l$ B8 }& Q' u: v% h
' Q6 F& m% M( E0 ^1 ?2 A
) S# @0 w7 T7 r: _9 b5 e
4 @/ w. l. b9 B; z( i% L* j
6 N7 j4 I7 d' P7 B1 o8 b
M) l: e- K8 h( H X6 ~: `/ a( C2 d1 q4 s0 T
|
) v; b+ K V1 Y6 O V6 |
+ `) p* o h5 ^& B* B8 t L | 0 a# Y. o2 X& F! J! U7 o
+ P3 v, k3 j' a/ Z o$ ?8 l! I
) i. f2 A- E3 F3 H e! A" K* S
# u" t B$ |8 L+ V% O$ u
) |% J; t0 x, c. y+ K4 \
. m) H2 S- p7 A7 y# Z
: ` k) |( r) U6 o3 K- J, _. r& Y) |$ {. ?9 `- z% n# D7 l
, @' n3 a k* N, Y( u9 a1 X|
# c3 c6 K) K% Q; ?; s1 Z' N7 q: Y 1 | 2 @: `2 E% O3 e7 V5 E4 h9 h% d
|
7 j6 {7 t! ?& ~2 F
" p' Y2 M; J$ M$ l6 w) ]* Y+ Q6 ~2 x' l/ j
1 p/ {' ~0 A1 u+ w
8 n7 [3 [; b m* i/ w, R( c- u8 Z5 C
w* _! ~0 B3 S+ ~$ W3 y) K& }; x5 C
6 E3 c N4 V- S6 x6 h$ M| . G8 _) _8 x; l Y9 r* G' c
1 | / D% w/ A$ T# u
|
9 i* O: E4 Y) D) X# w, I8 ?8 R' _% w" w5 O& {
' C4 O6 m( e9 t' e( Z+ S3 k8 |
2 K! N1 m& f3 ~/ }) d$ _9 u0 ]; I ~7 ]. @ n j& D8 B1 G
0 s2 ?5 X( z/ i. a% a5 u w! R8 y) E7 B7 I
8 F2 m) Q( f) Q" Q+ x( S/ ]
+ {$ W& S$ g/ C7 Y8 Y# \6 C' S4 {| 2 D3 g5 f8 l) e: O: |, h0 u
2 |
$ q' Z2 B, ~, n" |" X |
7 \" h& Z- R$ g% Z7 T, Q* h3 f* x% L% d1 b% U
?9 a. q2 U7 ^% }
% g. }* z2 o: h' R+ u5 m$ c$ J$ H+ ^" |; V5 g7 S( r
5 [! s7 e( i4 S' @, U
: ~* u* a4 l) ^: A0 ^
( x) p* Y# Z, N' D
0 ^ B' H' u9 ?2 a$ R|
3 o+ O7 V! }& x& D1 k: Q5 i 2 |
3 B6 D8 ?7 S4 k2 p7 K |
$ H6 N. i+ e3 s& D" E
" R) B {- d+ f; j7 ~ u& W: ?4 j; i, L, y& C
" t, R8 C5 L6 {, I
7 v0 E: P m( L4 L) X- F3 ?# |* P: o5 B* b" o5 j$ l* B
& q! ]5 u1 J5 t$ a: {
+ A2 N5 b% s" j" c' p I* O
: u4 H4 V, M3 z' y| ! B( } K" `2 v% {
2 | ' @4 P7 W3 R" L( y$ `
| , B( K& _ ?! Z# C( p, V" C
4 ]' ?& N8 o) D, l: s! I' u
3 \( J* `5 Y, ?" q7 V+ i
' l7 y" H* {# G. d" F. J: d6 U9 J! j) O/ n8 ?: X0 d" f7 t$ E
- m; J0 V+ a* }0 K/ J
: {! h; w0 |2 R/ R+ }" g& w
$ l* b# }, O0 V
, e0 }# |- K% L# E( n5 [| / B+ L) F6 Z# I: _1 v* E& p4 _% k
3 | - [2 J' T2 b% I* h, }
|
& W3 n( S6 S( U- J8 e2 }; w, a! }. y3 [5 D: K! Q
0 l2 ?2 X( \% t- |5 s$ l
4 j; a6 H; Y. s7 k g
5 r: {5 n4 | r) l/ @" c7 `: O
% e; e* i" w' Q% R8 V$ `; ^; E
7 B% q) P8 d. F( |! E1 K
' T* w K& E( L) m, H+ @$ {
! X2 Z9 o( N$ v u% n
| M; v; Z( {$ k+ z1 e8 W
3 |
0 b; t4 ^9 O) t3 m/ {0 n$ a | / C. [) m3 `4 z3 F! m
' j9 K7 ?& z3 {4 ]8 \4 E) C$ J1 |
# q" {/ ?8 Y. K5 d: R
. q' r9 v+ G3 p
. K' ^' o9 \0 G: Q# y6 Q) S
9 {5 x( p+ J) }% U# Q/ \* @- A- l0 E/ J6 t' t
! G8 v; r6 G% j r4 i) r7 O s/ Z/ T* c! K
| ' y5 \$ C, N- V" ?6 }% N7 U! v
3 | & y1 Z- S; g7 ?
|
- }& H% |. |5 T" c
' Z6 v/ \8 ]* k! Z% r( {+ X, z; B6 p' `' q, E C4 ]
) f0 S1 ?, J5 P1 A. I' v! }
. G$ k% \ X, g6 f
: W/ l8 v1 r) {2 s9 @; o
5 i/ @0 t3 j# Z
! [% X" g5 `, \
+ C, U, P4 R0 D- O
| h" C$ m1 _% D% [3 i8 ]/ ]
4 | . P8 N x: l' P1 X# f$ k
| " A; B: E- r( E0 `; x8 ~/ l
# I6 j* r0 w6 f/ ~3 l
. s/ q( _/ b7 _: u1 m
0 O: ~5 E/ _5 u% E
/ I! z9 @5 S0 g+ n0 D `, m$ L! F. O% T9 ]( G& P
* n4 I8 P* W: Z' \& q- f/ m, T" k
7 T. }: r i1 g/ y- M
$ L3 G9 M6 P$ f# t* E|
( c8 L- J4 N; I: r1 J1 E% p 5 | 0 b5 M, C+ v; r/ ]% Q
| val>val>val>val>val>val>val>val>val>val>val>val>为了便于计算机求解,特作如下规定:(1)节点V1表示树根;(2)当两个节点之间没有线路时,规定两个节点之间的距离为M(较大的值)。
8 N; k( H0 k U N MST的整数规划模型如下:
5 k/ t- j! ^& g8 ^9 M
. r# j( S0 K/ e3 Y. ~, T! j0 ~- S 9 L; t3 r1 M) }6 N+ [1 c4 ^5 o- x; w
1 R k6 Z9 K: Z; k9 @ ; ?& |- B& T& v' D% K
* w* c) o ~/ [3 e' E - e( y4 a1 o. g" F# E
例7.7 分配问题(指派问题,Assignment Problem)
' y* }6 ~& h. c. {- R2 A这是个给n个人分配n项工作以获得某个最高总效果的问题。第i个人完成第j项工作需要平均时间 。要求给每个人分配一项工作,并要求分配完这些工作,以使完成全部任务的总时间为最小。该问题可表示如下:
2 W5 C% V) o6 L. T' d 3 A1 g6 B& A% g [: f. ~1 r" y: k
显然,此问题可看作是运输问题的特殊情况。可将此问题看作具有n个源和n个汇的问题,每个源有1单位的可获量,而每个汇有1单位的需要量。从表面看,这问题要求用整数规划以保证 能取0或1。然而,幸运的是,此问题是运输问题的特例,因此即使不限制 取0或1,最优解也将取0或1。如果把婚姻看作分配问题,丹茨证明,整数性质证明一夫一妻会带来最美满幸福的生活!显然,分配问题可以作为线性规划问题来求解,尽管模型可能很大。例如,给100人分配100项工作将使所得的模型具有10000个变量。这时,如采用专门算法效果会更好。时间复杂度为 的匈牙利算法便是好选择,这是由Kuhu(1955)提出的。
* ^4 Q- F# ?( s$ xmodel:
, x/ j, b* m+ ~. m4 f !7个工人,7个工作的分配问题;
- r4 _' R0 G7 t T6 R, p1 \sets: 2 ~! _4 B/ o2 u* V
workers/w1..w7/;
) _: T: X$ w& j" @+ j9 x jobs/j1..j7/; $ j$ D/ {( Y V9 A6 Z. u+ a# k9 _
links(workers,jobs): cost,volume;
+ ^0 s; W- L6 S& pendsets
' I l5 Z! L. L- g# s !目标函数; + [3 _2 a+ v( o( ]' T
min=@sum(links: cost*volume); 5 a6 i2 ]1 {0 l6 r
!每个工人只能有一份工作;
2 w6 O" G, f7 ~4 q+ f; S5 S @for(workers(I): 3 b, o( n' i% h M& g# I
@sum(jobs(J): volume(I,J))=1; 6 y" [) }, e: Q7 e8 @* N4 }
);
$ {! {; I7 i0 W* U$ @' `( Y( d; g !每份工作只能有一个工人;
2 v$ U: y2 Y% ]7 d @for(jobs(J):
2 G2 Y/ O- q6 k' n% A3 ?) Y0 z @sum(workers(I): volume(I,J))=1; 7 Y( w& {" Q/ u# e6 ^9 C% ]' H
); # J& V1 H; K8 W- ]4 \' ]- c
data: 8 Z" U/ D/ Q% h5 e8 x
cost= 6 2 6 7 4 2 5 / z" x) {' b, R6 E/ }& \. m9 b
4 9 5 3 8 5 8
/ f* @4 n/ ?! v 5 2 1 9 7 4 3 ! f+ N: l( S6 q0 N, h5 J
7 6 7 3 9 2 7 2 E( y9 H0 w- M, S
2 3 9 5 7 2 6 3 c" Z+ e( |: w8 p$ s6 z8 Z; }
5 5 2 2 8 11 4
8 N% C0 T9 `7 d4 _7 y 9 2 3 12 4 5 10;
5 n- K9 F. _2 n. c$ i9 Z4 E D1 Lenddata
& O) R4 Q4 s* Z. z0 U8 Hend |