【文章內容簡介】
mize 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。 ! 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 X39。s 0/1。 @FOR( LINK: @BIN( X)。 )。 ! The level of a city except the base is at least 1 but no more than N1, and is 1 if it links to the base。 @FOR( CITY( K)| K GT 1: @BND( 1, U( K), 999999)。 U( K) = N 1 ( N 2) * X( 1, K)。 )。END使用Solve求解獲得如下結果:, X(1,2)=1, X(2,3)=1, X(3,4)=1,X(4,5)=1, 其它X(I,J)=0。最優(yōu)值。167。 最小生成樹的應用與LINGO軟件求解 使用最小生成樹程序應用求解下面具體例子。例6 已知五個城市Atlanta, Chicago, Cincinnati, Houston 和 。 求解連接五個城市網(wǎng)絡的最小生成樹。 距離 kmATLCHICINHOULAATL07024548422396CHI702032410932136CIN454324011372180HOU8421093113701616LA2396213621081616 0 使用LINGO軟件編制此題的程序如下:MODEL:!Given the number of nodes and the distance between them, finding the shortest total distance of links on the network to connect all the nodes is the classic problem called minimal spanning tree (MST). This model finds the (MST) connecting Atlanta, Chicago, Cincinnati, Houston, and L