|
求解最小生成树的方法虽然很多,但是利用LINGO建立相应的整数规划模型是一种新的尝试。这对于处理非标准的MST问题非常方便。我们主要参考了文[7]。
1 y- ~7 z: | n# H6 E2 m* @) K v T0 T在图论中,称无圈的连通图为树。在一个连通图G中,称包含图G全部顶点的树为图G的生成树。生成树上各边的权之和称为该生成树的权。连通图G的权最小的生成树称为图G的最小生成树。
: w# k V, M' M' L) r& P许多实际问题都可以归结为最小生成树。例如,如何修筑一些公路把若干个城镇连接起来;如何架设通讯网络将若干个地区连接起来;如何修筑水渠将水源和若干块待灌溉的土地连接起来等等。为了说明问题,以下面的问题作为范例。 + I& A% ^ `8 C. G' r9 G! x9 Z
范例:假设某电话公司计划在六个村庄架设电话线,各村庄之间的距离如图所示。试求出使电话线总长度最小的架线方案。 / F6 [& ~- F: e% h h& {. G& r
+ B7 S$ n- c, X# X+ Y
# Y2 ?/ z# X& |+ L" M& x! V
b) w) v# P( y+ Z, H( {. E0 z7 T" x" g+ v0 M( j5 E& O- J
! u" Z7 q( \0 v6 y3 X6 O
5 `) o- I/ `+ E: M8 x, f0 n8 q1 ^' A: U' f9 I. G; p
' Q1 A, t$ ?7 u$ W9 [6 g1 U* S
8 W$ \3 k% r# R. ]; Y5 K0 Q( H|
3 o4 |' ]/ j U, h: {) Z" J$ w9 O V1 | $ g# Q# c/ U8 _1 N
| % E/ v% L% k2 s2 q
! R+ D! S+ T+ t e
5 ^5 b" I3 P/ L; {. Q$ P7 l
: u. d1 \) k$ ~& @6 Y# o1 Q8 _6 v
# u) _: b7 v2 I' I; @8 u h1 e4 M& f2 R3 X
2 B& ~8 F7 k1 U: R6 t( s0 ^1 ?2 x. v1 y- l; I# {, I) r" }
" T# Y6 z( P9 ^, j& l" z; X| # i2 V# [8 F" a2 J, ~9 o7 X# e
V2 |
7 b. g: C. G5 f2 A | 0 Z! y3 W% S: F W7 [9 Z$ E; V9 `
7 E1 `% d& S; A& m% H' T
# L7 R; z6 A6 q
$ s) @& N2 f- Q' h
* v. ^0 g/ @7 ?3 b2 D5 D$ I/ c1 X) a: z3 K9 f& O$ a# \: x* ?; f* F
& ^ _( |& E5 Z1 o
; Y7 B1 ~0 N3 v7 W4 M$ V! C! c! v1 k" q- K g2 M
|
; K* q2 I2 R2 ?1 A6 T2 j" b0 E1 E' h V3 |
' g3 \- l/ G( g | ( [% ~. N( Q8 N6 W( g9 I) s
7 a5 o- H/ M: j1 y. `/ x" Q0 B/ u& P/ Z
) b0 y5 ]7 E+ K7 N( t" N/ `$ b! ]
, h, V6 y( _" h0 U5 P
* A8 p. G1 g& p2 F$ R b9 h& i5 r) E+ e5 R* n- ?* c
) g2 q! z& A( N2 B9 y$ X2 O/ H9 V4 t. u0 x
|
6 Q5 i$ s( g6 G. w V4 |
; F7 n5 O$ W& @. z. Y, H" A" j |
* d0 Q5 ?( R- N* }! U- j6 {- F3 H$ O( m
5 x5 d7 \* o. f3 }" F3 p; |8 I) g, O! G
1 K9 T1 D' X5 f E2 B8 T# o4 G# y
. ~2 x _% x8 \, h7 @, E4 ~+ f" t" a# H
" ^% H% M6 U( g/ t
|
7 B# Z! [4 S7 ?3 o# W V5 | 4 K; e5 A$ B, s+ ~" S
| 4 p! S) h9 n( a% x- |' m- ^
; P0 b1 {# c' X, [
7 u# G, H5 s5 M f
- f' G" I: P4 r8 p2 z7 f
5 }% ]$ Q" q( e$ D" Y9 P8 Y" E4 h* W1 E+ r3 |
$ H% B+ T0 a4 I1 G: o' a8 B0 {
# P% \, R8 z/ r
2 T0 ~: H; x" C; z|
4 ?1 _0 D! v6 j8 ^2 H V6 | * d1 E% h6 D Z/ _/ M7 u: ^, Y
| % l2 R! A T6 w
% F8 r8 f ?. j- u# P( k' [9 v. D
5 M8 o( N h3 V* j5 u1 o0 d
2 X7 V: h- t7 s) w# ]* A7 n
3 n% ^; G$ F0 T0 W
1 v5 w) p# B2 g* }+ c P" {' q( d" z; S$ g& c8 g- U: n
" I/ j' T6 ?7 |# z" V! o" z7 _: L, s5 P3 E) T6 v) u) q! w9 T) t
|
! E7 v1 e/ ]! c# d ]7 ^7 D) j 1 | 7 k0 V! u1 L! V% ?5 x
| / n2 _6 f5 X) N }
/ Q, r) i& t' H
" y2 ~3 D' ^# V
+ Y4 M- r) h% J1 ?" o
6 f2 w8 a* E; U5 Z a }) m7 c6 R! L4 K3 s3 Z( M' i
" l( L3 g! a; P8 }! L3 |3 x* f. i/ ^
: Y- c) W% `! @- J
1 z1 h$ X. G0 H; P2 k t" e4 ^| , N$ ?8 c' L9 A% n6 k, V
1 | ; V" u5 O7 y1 E# ]. |) _. M) {
|
! b7 N' f# B- d/ a: Q
8 c. t( M5 d$ U0 g: ?; c/ ?* T1 M4 M- j2 v4 [
. P; I; a1 b, l; b6 J
4 n3 Z$ Y4 e: r& T+ M8 s5 t' } { W5 H( b, W
' F1 u" L P& F m$ d) ^: Y$ o' Y: r' g
4 y3 d# _; x I, x `- s; U6 q- n|
, @4 o; R. \* b. d& z3 E9 w2 J 2 | 0 {( i1 L: H8 C
|
4 Y. `( L: i, L% K& K h9 G, _( Y
; V# x7 V9 v1 g9 v. W
3 r- @' x) ]4 K) d( j; L3 a4 J4 E6 g
/ H f7 ~# M( E' I# w0 i" B. W" b: l5 M3 k* W* X8 z0 d
! b+ _1 Y# O5 y/ ?6 H" q m$ }. v- X4 O( Q# ]7 m
: P. n( }0 } I* B; p) A3 L* N| % u, a4 d+ }: z3 c4 X6 J' n* X$ ~
2 |
; u* z' ^, ?6 ?: G! N5 u | / F% ^+ O" m5 d. Y2 a, o$ s) C
6 i6 \: v! p8 W& \% E
$ ^- g( x) x+ A+ W4 t9 s" h9 u K- \6 L. Y/ y" R; _
5 P" S$ Y/ I9 z7 k1 O$ f( w- `+ q# B$ t# b8 N- j* o* h2 X! b
" P) X& ~+ G5 n/ G0 M. @3 ?+ W1 c1 r c6 L$ M1 K$ u
5 G! X0 B( |, T3 o9 s7 [) @+ a, |
| ' I/ o5 O! o2 `+ m+ L
2 | 4 o0 k9 m! v c9 s
| L' I2 ~% X2 b
# c4 R1 _2 L! S1 W4 X& r! ~
/ G/ b8 m1 N8 W# q, ^) Z
( m/ \! Q2 f: z" p
2 y9 x( l. s/ Q) B$ i1 H* z2 d8 [
, T3 m, F+ ]* V; v& ^+ g; I5 L v( r) S
E# I5 N* A2 ^7 p% ^8 g) _& \5 W* s& G* ]* c0 y0 z2 m
|
, d/ n8 U* B7 x4 c5 l) M% } 3 | 2 B3 k6 l# j; Q B# i2 Y! `
| 4 c9 c& Z3 v3 w" D5 w9 t& t
8 g& d- N2 w& W4 x) U
4 d2 M& w+ r: n; z y6 d, a$ z* |6 T
5 g9 D! K: X& M1 K% U
( ?* w) P6 i9 z; }# P. E G" f: e5 B
: D. f7 A4 v3 d" _. p; \3 K
2 g% U- A' E+ I* z( n! C7 K. a0 C+ @* o9 E% s
|
. G8 b# N( [; H) ?6 y& p. x3 W 3 |
2 S6 k" e5 R* {7 S | s! b' | x2 h3 i! v+ ?7 {) L
+ ?; n7 s5 I& B! m L( I, x$ ?
0 Z4 Y+ q% F0 ~4 j- }/ w0 A
, d$ I2 E+ K5 _5 r* G* z
3 z( H- K4 v* F& ~7 r0 V7 ]
, r8 o# ~$ F( z+ G/ D8 s6 |
5 K6 W( \6 y9 j$ {, x
p- G- V9 V. `3 Z/ F( C9 Z2 U
" Q* r7 J6 z1 n4 V6 `% L' u0 A| - W! C: K& g& h) [ e2 k
3 |
) z8 ]% i& u! I7 | | & y$ m3 C, a' a- m* Z; F. V( E
0 C6 m* D0 [0 |) `' x
- O5 a' }3 n8 P: ]8 T6 z4 M
7 @5 k* {) O4 u! L' ^9 l# b7 `7 W; `6 ^% a( D0 T6 d( S( }
) K0 {! u$ `% Z2 E
) U7 K( K' Q; t0 O, x6 `; s4 U- R' m1 y7 N
9 {( S T- c! {) I0 F' g4 v
|
6 C8 v/ ~. I# Q5 ~2 ] 4 |
3 {1 \( N# R( ^4 w | r2 [- i! o: L) h) S
/ z8 \5 F' Y+ U- C( o! g! V' D6 J! ? u# X6 @( o, R; j
0 m' R) C7 q' R* U# `7 P1 Q- b# A; r
# x s: K& [( \: p7 x, f% K) l# v# N$ T) w1 c. a4 A1 v g
- ^$ U, {+ q: E! t" i) c
6 m6 X3 N3 r' ~) q' o+ m" G; A" L0 n6 ]& i: p4 S
| $ r' C/ U$ z' w8 z( a7 }# g
5 |
B8 c( @3 W- M- p. G* T4 z+ \ | val>val>val>val>val>val>val>val>val>val>val>val>为了便于计算机求解,特作如下规定:(1)节点V1表示树根;(2)当两个节点之间没有线路时,规定两个节点之间的距离为M(较大的值)。 7 r; b5 _" R: B, ^
MST的整数规划模型如下:
/ s, ^' i/ c L% _8 c% x
/ O0 g* W2 R) f. u' z
8 ~: g2 z/ ]# Q F( Y
2 B, o2 k- K/ q2 Q5 m. B: E0 Q% s3 s. X % L9 T. ]+ v4 M4 c4 \8 a
0 z1 h4 J& s4 [
4 i/ ?: T6 C1 I6 q/ Z7 U, x
例7.7 分配问题(指派问题,Assignment Problem)
2 j# W$ Q" d; m1 g这是个给n个人分配n项工作以获得某个最高总效果的问题。第i个人完成第j项工作需要平均时间 。要求给每个人分配一项工作,并要求分配完这些工作,以使完成全部任务的总时间为最小。该问题可表示如下: 2 m w/ P& z/ \: `3 H$ W
! C) A u3 \7 H9 v& X: s 显然,此问题可看作是运输问题的特殊情况。可将此问题看作具有n个源和n个汇的问题,每个源有1单位的可获量,而每个汇有1单位的需要量。从表面看,这问题要求用整数规划以保证 能取0或1。然而,幸运的是,此问题是运输问题的特例,因此即使不限制 取0或1,最优解也将取0或1。如果把婚姻看作分配问题,丹茨证明,整数性质证明一夫一妻会带来最美满幸福的生活!显然,分配问题可以作为线性规划问题来求解,尽管模型可能很大。例如,给100人分配100项工作将使所得的模型具有10000个变量。这时,如采用专门算法效果会更好。时间复杂度为 的匈牙利算法便是好选择,这是由Kuhu(1955)提出的。 2 s9 D$ R0 G" F, K8 `. q! {
model: / |+ q1 w3 W; f& o9 _: A/ O
!7个工人,7个工作的分配问题; 9 k* V, y, t4 t c1 M: M# _* F4 x
sets: + W- A: V7 o) K3 n0 O( D
workers/w1..w7/;
. @. B) J6 F8 k' g! t+ |) b' O5 P: ~ jobs/j1..j7/; . @' |. |+ H t$ l) d. l" Z
links(workers,jobs): cost,volume; / J$ k6 A. j5 v& K) @6 m7 i5 Q
endsets
8 P/ O( C, b9 a, @" v a: r6 n3 j !目标函数;
[+ r! x- c* y8 m L+ p* ` min=@sum(links: cost*volume);
$ D1 h3 j3 m. }8 v !每个工人只能有一份工作;
6 Z4 L0 k9 `' V @for(workers(I): 4 l" v- E" g* i4 e
@sum(jobs(J): volume(I,J))=1; 0 E: p" _8 q- T, A+ g9 o9 J' X
);
8 @8 k# q! n% i( `+ \6 {( t1 f !每份工作只能有一个工人; $ L3 @0 n4 q+ A
@for(jobs(J):
+ R& x R) C4 I# S @sum(workers(I): volume(I,J))=1;
' b7 q& k& p$ Z. P );
. f4 p* w- t7 o9 p6 Xdata:
0 m! X& u' E$ _7 j cost= 6 2 6 7 4 2 5
/ W+ D4 }/ q8 Z+ w 4 9 5 3 8 5 8
& Z6 }) ?# n; Y% o* g& w+ H 5 2 1 9 7 4 3 / F7 L1 q* z2 m6 y" X& z% I K
7 6 7 3 9 2 7 : L1 u" D3 Z+ c |+ l
2 3 9 5 7 2 6
6 }. K% T0 t R 5 5 2 2 8 11 4
: T. w; q! U! w6 k1 F6 G: A 9 2 3 12 4 5 10;
3 o/ Z- V" w8 S/ b0 B! Qenddata " V6 T+ u" b# c5 R
end |