最小生成樹模型與實驗-閱讀頁
2025-05-02 02:04本頁面
【正文】 ( N 3) * X( J, K)。 )。 SUM( CITY( J)| J GT 1: X( 1, J)) = 1。s 0/1。 )。 FOR( CITY( K)| K GT 1: BND( 1, U( K), 999999)。 )。最優(yōu)值。 最小生成樹的應用與LINGO軟件求解 使用最小生成樹程序應用求解下面具體例子。 求解連接五個城市網(wǎng)絡的最小生成樹。 SETS: CITY / 1.. 5/: U。 ! U( 1) = 0。 X。 ENDSETS DATA: ! Distance matrix need not be symmetric。 !to: Atl Chi Cin Hou LA 。 702 0 324 1093 2136 !from Chi。 842 1093 1137 0 1616 !from Hou。 !from LA。 N = SIZE( CITY)。 MIN = SUM( LINK: DIST * X)。 FOR( CITY( K)| K GT 1: ! It must be entered。 ! 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。 )。 ! There must be an arc out of city 1。 ! Make the X39。 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。 U( K) = N 1 ( N 2) * X( 1, K)。END使用Solve求解獲得如下結(jié)果：（）。即：連接五個城市最小的生成樹網(wǎng)絡為：Chicago→Houston→Atlanta→Cincinnati→LA。最優(yōu)值公里。 選址問題選址問題是指為一個或幾個服務設施在一定區(qū)域內(nèi)選定它的位置，使某一指標達到最優(yōu)值。在此只簡單介紹服務設施與服務對象都位于一個圖的頂點上的單服務設施問題。 某城市要建立一個消防站，為該市所屬的七個區(qū)服務（），問應設在哪個區(qū)，才能使它至最遠區(qū)的路徑最短。此點稱為圖的中心點。一般要考慮人口密度問題，要使全體被服務對象來往的平均路程最短。已知各礦點每天的產(chǎn)礦量（）。問應選在哪個礦點，才能使各礦點所產(chǎn)的礦運到選礦廠所在地的總運力（單位：千噸/km）最小。此點稱為圖 的重心或中位點。若購置新設備，就要支付一定的購置費用；若繼續(xù)使用，這需支付一定的維修費用。已知該種設備在每年年初的價格為：第一年第二年第三年第四年第五年1111121213使用不同時間設備所需維修費為：使用年限0112233445維修費5681118對此問題，構(gòu)造加權(quán)有向圖。（3） 問題轉(zhuǎn)化為頂點到的最短路問題。求得最短路的權(quán)為53。習題六 分別用破圈法和避圈法求下面各圖的最小生成樹并使用LINGO求解其
教學教案相關(guān)推薦
鄂ICP備17016276號-1