最小生成树模型与实验.doc

最小生成树模型与实验
第六章最小生成树模型与实验
最优化模型与实验
156
第 页
第155页
第六章最小生成树模型与实验
最优化模型与实验
156
第 页
第155页
证：tance of links
on the network to connect all the nodes is the
classic problem called minimal spanning tree (MST);
第六章最小生成树模型与实验
最优化模型与实验
156
第 页
第159页
SETS:
CITY / 1.. 5/: U; ! U( I) = level of city I;
! U( 1) = 0;
LINK( CITY, CITY):
DIST, ! The distance matrix;
X; ! X( I, J) = 1 if we use link I, J;
ENDSETS
DATA: ! Distance matrix need not be symmetric;
! However, city 1 is base of the tree;
!to: A B C D E;
DIST = 0 1 3 4 6 !from A;
1 0 2 3 5 !from B;
3 2 0 1 3 !from C;
第六章最小生成树模型与实验
最优化模型与实验
156
第 页
第159页
4 3 1 0 2 !from D;
6 5 3 2 0;!from E;
ENDDATA
! The model size: Warning, may be slow for N >= 8;
N = ***@SIZE( CITY);
! Minimize total distance of the links;
MIN = ***@SUM( LINK: DIST * X);
! For city K, except the base, ... ;
***@FOR( CITY( K)| K #GT# 1:
! It must be entered;
***@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
第六章最小生成树模型与实验
最优化模型与实验
156
第 页
第160页
! If there are 2 disjoint tours from 1 city to
another, we can remove a link without breaking
connections. Note: These are not very powerful
for large problems;
***@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:
U( J) >= U( K) + X ( K, J) -
( N - 2) * ( 1 - X( K, J)) +
( N - 3) * X( J, K); );
);
! There must be an arc out of city 1;
***@SUM( CITY( J)| J #GT# 1: X( 1, J)) >= 1;
! Make the X's 0/1;
***@FOR( LINK: ***@BIN( X); );
第六章最小生成树模型与实验
最优化模型与实验
156
第 页
第161页
! The level of a city except the base is at least
1 but no more than N-1, and is 1 if it links to
the base;
***@FOR( CITY( K)| K #GT# 1:
***@BND( 1, U( K), 99