|
求解最小生成树的方法虽然很多,但是利用LINGO建立相应的整数规划模型是一种新的尝试。这对于处理非标准的MST问题非常方便。我们主要参考了文[7]。 ( w! J+ A5 e. l# E( p
在图论中,称无圈的连通图为树。在一个连通图G中,称包含图G全部顶点的树为图G的生成树。生成树上各边的权之和称为该生成树的权。连通图G的权最小的生成树称为图G的最小生成树。
- e2 O+ d( g, H" y许多实际问题都可以归结为最小生成树。例如,如何修筑一些公路把若干个城镇连接起来;如何架设通讯网络将若干个地区连接起来;如何修筑水渠将水源和若干块待灌溉的土地连接起来等等。为了说明问题,以下面的问题作为范例。
8 K7 r, g1 o; I0 A4 T范例:假设某电话公司计划在六个村庄架设电话线,各村庄之间的距离如图所示。试求出使电话线总长度最小的架线方案。
/ D; W! x- a" Q* h2 z; f0 p( b" ]) `. K
6 O* D' g8 I! V
: U# m: Y( l3 n9 o8 E$ `, W3 z/ a3 h6 W0 p' R! K1 M N# r- \
* t4 A* T' D8 Y4 G4 [ Q
& H* h: l+ v% @3 L% D- _4 w" q8 R( R7 A: E. X! `4 p- K
( j3 u0 i: G1 p% }, {3 m+ ^! I1 g
* x" E4 K8 a1 Z% _
| 9 Y- a) n; l7 \2 g, x
V1 | + a+ m! K+ B, [4 w8 @$ F
|
& I5 g* n ?1 S0 r* L; t, x4 `" b1 i8 {! S @- v: M+ Q
! d; Y! Q1 ?. f
+ q( I$ h* M7 _3 E% z4 f
: ]* ~7 ` i2 }0 C$ y5 _
6 W2 c- v* f4 U5 z, N7 k* @! I0 v( R: A5 N5 e. B9 Y( v: d1 K
4 \/ B3 I+ Z- w# M; x1 q0 Y& ?$ B5 y0 A; ^' ] D
| $ r7 m' b7 M) M" A
V2 | + ]- Z# p0 E; u+ V7 i0 c: F
| , R5 @' L% b; m# W" V/ n
8 |1 r& \; _! h6 f, X/ C1 i: j6 p6 a& u! }: @( y* ?
: l) e4 p J& h6 x8 p l5 s: X
7 Z, y3 E9 r+ \# U2 g. W; E4 o7 R& t
! w9 ]5 ^; Q1 s. k
* {' T8 w V' c4 Z% O* X- l
. @6 }2 N. Z% ~- f& y& |" y Y| 8 ?8 b- y* |4 q" `1 ?; \& y5 m$ U
V3 | 1 C V% s% ^# `2 t; k
| 4 |: r" _4 e4 F2 d U
4 n' |; o' x( e- A, `: d
$ Z( T% P0 _) X$ a
) Z U* ^6 a9 C ~
! q1 I; Y |, k j0 u" T+ y; P& F; C
7 l5 O# z* I, L9 ?3 h
* _& h0 a( G5 {! d6 [. j, C
( q4 [7 m+ h3 o0 u" Y' X% S|
5 t, h+ N" y7 t' H/ v" A6 V V4 | 4 C4 r3 H1 Q& g/ f
| ; _# P' F, {* y, _
2 b' D2 c7 O% v' O" o1 R6 K. A
- ?$ X% w, H3 |- _- [
; m6 `# p) E1 c9 V7 E6 G! N- U2 U+ U& _5 Z, p) |1 C$ ~1 O1 `
( O- J; M$ A+ o& e
/ s. k/ q! f4 Z" `+ i) c) a F) R- G% j0 [1 d) J H0 ?
" c' s5 b$ x6 [! I' J9 G|
( U7 }' g: M/ I7 `/ A q# ^ V5 |
3 z0 p& ?7 Z3 l+ \$ B- L | 2 l" N' u3 U7 R0 r; p: u u
0 v% z( D6 \8 _* g/ }/ n2 }
- Q( U) E" g( s% i' z- l. M% n3 O7 K$ C0 d4 x! B
- Q+ F, |& ?) X6 K/ S8 @+ W' o" D& C
$ q, K" K5 z# @2 c; K, {- G( V6 T7 X$ t T
" d* W) X2 z& D1 J) `|
. m0 ]2 J$ F x6 ~: x5 c3 r9 X V6 |
0 ^- p& e6 f: {0 |# ~! l! a |
* e- c! n1 w* _. H! I0 Z D3 x' V3 E! u7 Z; {7 i+ Q+ X
: P. ^4 J; J: K# L6 Y3 O) A. B# i
3 d d* p% s9 r& s- F3 x( N$ u' I9 s2 l
/ W$ ]7 W9 @/ P* R) f
& R) K/ p) u, [; w/ P6 f! r4 a3 {- c
/ k( O l0 q9 \' ~| ) f/ }. q3 Y' f8 a9 B
1 |
- w7 X) P* U2 ?- X. e7 T: p' m |
0 R' l2 R7 i5 [4 M k3 b3 x1 [$ [+ j) F# L5 l& s1 J J2 X
. ^2 P6 [6 Z e0 z" j0 R) K
0 _% x2 P9 c+ s; p' r6 t- J
+ @9 j9 g# L1 h0 d& v: C
( A" o+ b! w2 I5 g& H1 a$ L6 U8 m& r; O' Z
) b% U. h3 W2 }& G) Y5 K- {
/ _- W9 Z9 z1 _) E
| ; @9 D1 t: j( A
1 | 8 B+ O& k! m5 _% u" A" b" U9 H: f
| " J6 s d; G% Y
% @) V6 J" F; c. D9 V
9 q5 z0 G g2 w" d
1 V' Q% Q1 G/ Z3 p
' ]5 W2 w0 U' F' \7 d6 L. U
6 r8 E" e; D& t
) x3 o# R& ]' _5 ~$ B- a
$ ^% T( i; G0 t9 Q o( [- o; L# g# O- [
|
8 }# u/ T* k* i7 _) M9 Y 2 |
) N1 a9 m. j! Z( F8 `% \" { | ( m" R; ^. G/ g8 D# U0 `8 B
5 `- F7 o6 b }! F
; i+ a: g3 f) C% u0 H
! n' c* x5 L6 R5 x
k; k. v3 _0 D, f3 M9 @1 I
. u* _# i- \. u4 U* m9 ?( p3 ^
; F% o' N1 Y3 Y- H/ h. v
0 p% o# X6 R1 y% m4 e
, a+ L" H# D: R1 J: B, a
| * K! }2 {* z& n4 q
2 |
; y0 ` ^, o" t5 {& t |
7 ?* z+ s6 v% q1 N5 _- k' x/ k
3 _. p6 D; h1 Y$ I6 K1 ]0 y
5 m7 N' A' |4 w Y2 v5 Q- d# i; W* l
0 G3 K$ C. L' g& I1 m5 [5 y3 v0 V- _5 q/ S$ E- |9 \
/ I/ a8 d& U" D1 C: H9 |5 v4 `- a8 S; \, T
' q( J2 o* T' x: x2 f* n* ?/ T3 g$ E( n% G
|
/ N8 g1 s. k8 q( ^. }+ O1 G; t 2 | ) p2 l0 X6 p: L" x9 u8 \$ Q% t
|
5 R2 l7 L& ]6 ~% E8 J3 a) @2 k7 r3 k0 h8 [+ B/ i" z
, t) z4 Y! W6 Q6 _8 p2 c8 |4 f2 u- n# e! v+ y
3 }% L% F2 T& d* [) e
7 {" K% ^+ {7 x. w
; q4 w( d5 M8 E
. q+ U% a+ S9 F
9 Y1 Q" Y: N3 E% D# k/ k| 8 U$ G8 }/ S0 e0 S7 d9 B! ]
3 |
, D' Y& ?& h" @$ ?2 b; y/ N | : b4 q+ |3 {8 t' m+ O: F
) G4 K; }% Y+ g, y0 n# Q8 Y5 ~3 l' E6 ~- L! S
2 v* |; |" U; S
. V9 Z, @1 g' s; [3 {
9 G6 k3 Z" Y8 {
/ s* C/ ~% d5 E. i* S1 V, `( J8 s! N5 J0 i1 p; F
0 E' ? N: |1 q7 N
| # f% x$ ?# w( v! ?
3 |
1 F5 `1 Y. y* a8 R R$ w" { | 1 o" D8 `! ~6 X( e& J! ?
. T2 l* a. C* E! c7 u% r' ~ L4 {! V. A& P
& A6 C" P0 ?3 W/ s; l# `
% g; ^& H* g* U M+ {
) A1 {9 a- D, y
& B2 R: Q/ g6 q& v
6 _+ V& J0 E$ G- `# o7 X O
6 y7 E$ a, D. {+ {" ~| 4 L3 l/ l4 b3 v5 m% |
3 | 2 n# x/ ~3 R9 v- i' _; z3 @* a; |
|
" B; P1 D' y7 j8 I7 b
: d" B3 {4 r1 [* T) ` {9 ?! i" |
! G4 a' n- T0 E% K( L$ [* `6 N
5 C, b( U( Y- ]/ p3 I# _5 P) y! z! h, S
6 a3 g4 h3 M2 r- k+ @; @% T: O$ X
! J, w% ]) C' k8 T; m$ ?, R) n! a
e! k% A# `4 h/ H2 C3 W( b
; U# y' G* s* B+ j|
( e; z# }# X9 P- @- ? 4 | 8 f5 M) u2 L, S, Z* [1 ? }* S
| ; t3 b5 y2 I0 J! I
. d7 L7 t- ~# B# w3 N
_+ q+ O/ V& T. j+ I+ |
1 T% e/ s- {5 P) L& z( B/ Y
3 m' I1 U2 M7 }' v; z
' e J/ D! \5 s
- J; ?8 }2 k2 V0 }- U9 A
3 _5 ?2 g: F/ @' n9 A' Z
) e+ _% B+ |5 ^) ^% e. J. ?| 2 Y. F* S6 m8 i: \* H
5 | : S* x0 T+ S% E( _3 Y& q! m
| val>val>val>val>val>val>val>val>val>val>val>val>为了便于计算机求解,特作如下规定:(1)节点V1表示树根;(2)当两个节点之间没有线路时,规定两个节点之间的距离为M(较大的值)。
/ P& U7 B }; ]6 j MST的整数规划模型如下:
; V; n1 n/ A6 Z: |
6 h7 |9 ` t& B5 s. T9 k3 Q8 i1 E' c
0 ]1 O" i" i+ ?& l
# r9 f4 M$ H" I& `; a # V" L- F9 f- X: i5 e
% u' L% i" S/ S; c! F0 v 2 M+ B0 }3 u- G/ s. Q% J4 F
例7.7 分配问题(指派问题,Assignment Problem) 3 G4 S$ u" V1 v' M& y% n) ~
这是个给n个人分配n项工作以获得某个最高总效果的问题。第i个人完成第j项工作需要平均时间 。要求给每个人分配一项工作,并要求分配完这些工作,以使完成全部任务的总时间为最小。该问题可表示如下: " e/ h6 W7 @( v: J4 {
7 {( I5 g7 X) O; F) f
显然,此问题可看作是运输问题的特殊情况。可将此问题看作具有n个源和n个汇的问题,每个源有1单位的可获量,而每个汇有1单位的需要量。从表面看,这问题要求用整数规划以保证 能取0或1。然而,幸运的是,此问题是运输问题的特例,因此即使不限制 取0或1,最优解也将取0或1。如果把婚姻看作分配问题,丹茨证明,整数性质证明一夫一妻会带来最美满幸福的生活!显然,分配问题可以作为线性规划问题来求解,尽管模型可能很大。例如,给100人分配100项工作将使所得的模型具有10000个变量。这时,如采用专门算法效果会更好。时间复杂度为 的匈牙利算法便是好选择,这是由Kuhu(1955)提出的。
6 K% @1 d0 m4 G' }; N* Rmodel: % S; i0 T& e( X8 f' m* i& m5 Z
!7个工人,7个工作的分配问题;
, `9 m- m2 K+ A. p# e% @! s9 a! Xsets:
' j# y ?3 D- o0 C) G V7 |- }% E4 m workers/w1..w7/; 1 Y+ M7 E/ g4 o& Y5 ?
jobs/j1..j7/;
* _: K' v1 z; E+ @7 y6 ] links(workers,jobs): cost,volume; }0 f+ g) r) s2 Q
endsets
+ P' S* _+ `( a1 S7 _% b" x !目标函数;
" `# K; ]2 g2 W& X min=@sum(links: cost*volume); ) a- F" X, d7 |0 q
!每个工人只能有一份工作;
$ p& a# Y; Q4 C) s4 [* a @for(workers(I): & l K% r; L, M/ m1 F7 s
@sum(jobs(J): volume(I,J))=1;
# c5 e' }( u3 W/ E8 N ); : z9 T. f0 K" E: C/ N) U
!每份工作只能有一个工人;
0 a$ q6 ^. ?4 J& F @for(jobs(J): , ?+ p4 B/ ^; \. U- U- v
@sum(workers(I): volume(I,J))=1; $ A! C: I1 d2 n3 U
); 4 A$ [5 |& Q' [6 _, r: ^
data:
. s6 l5 X* Z: K" T3 M5 B; { cost= 6 2 6 7 4 2 5 & s8 p. G* b$ R B+ Q0 c
4 9 5 3 8 5 8 , h2 K* V8 O1 K
5 2 1 9 7 4 3
3 Y9 u) v( r/ o' M0 ^ 7 6 7 3 9 2 7 / Q' `0 q8 e$ F9 Q3 R: R, @
2 3 9 5 7 2 6 * v" c) l+ k8 e
5 5 2 2 8 11 4 3 ^% I* Y$ Z8 y* \# z
9 2 3 12 4 5 10;
- b+ ?1 w" \% i# g" g0 Q; r- A. _enddata
$ }! ~# P/ W9 }8 P. y' cend |