LINGO在圖論中的應(yīng)用

第2章LINGO在圖論和網(wǎng)絡(luò)模型中的應(yīng)用 圖是一種直觀形象地描述已知信息的方式 它使事物之間的關(guān)系簡潔明了 是分析問題的有用工具 很多實際問題可以用圖來描述 一 圖的基本概念 圖論是以圖為研究對象的數(shù)學(xué)分支 在圖論中 圖由一些點和點之間的連線所組成 稱圖中的點為頂點 節(jié)點 稱連接頂點的沒有方向的線段為邊 稱有方向的線段為弧 所有線段都沒有方向的圖稱為無向圖 所有線段都有方向的圖稱為有向圖 既有邊也有弧的圖稱為混合圖 點與邊相連接稱為關(guān)聯(lián) 與邊e關(guān)聯(lián)的頂點稱為該邊的端點 與同一條邊關(guān)聯(lián)的兩個頂點稱為相鄰頂點 與同一個頂點關(guān)聯(lián)的邊稱為相鄰邊 具有相同頂點的邊稱為平行邊 兩個端點重合的邊稱為環(huán) 在無向圖中 沒有環(huán)和平行邊的圖稱為簡單圖 任意一對頂點都有一條邊相連的簡單圖稱為完全圖 任意兩個頂點之間有且只有一條弧相連的有向圖稱為競賽圖 在圖中 兩個頂點u和v之間由頂點和邊構(gòu)成的交錯序列 使u和v相通 稱為鏈 通道 沒有重復(fù)邊的通道稱為跡 起點與終點重合的通道稱為閉通道 不重合的稱為開通道 沒有重復(fù)頂點 必然邊也不重復(fù) 的開通道稱為路 起點與終點重合的路稱為圈 回路 如果頂點u和v之間存在通道 稱u和v是連通的 任意兩個頂點都連通的圖稱為連通圖 無圈的連通圖稱為樹 如果一棵樹T包含了圖G的所有頂點 稱T為G的生成樹 如果圖G的每條邊e都對應(yīng)一個實數(shù)C e 稱C e 為該邊e的權(quán) 稱圖G為賦權(quán)圖 通常稱賦權(quán)的有向圖為網(wǎng)絡(luò) 二 最短路問題 1 動態(tài)規(guī)劃法 1 問題的描述給定N個點Pi i 1 2 n 組成集合 Pi 集合中任一點Pi到另一點Pj的距離用Wij表示 如果Pi到Pj沒有弧聯(lián)結(jié) 無通路 則規(guī)定Wij 又規(guī)定 Wii 0 i 1 2 n 指定一個終點PN 要求從Pi點出發(fā)到PN的最短路線 可以用動態(tài)規(guī)劃的方法來求最短路問題 下面舉例說明其算法原理 2 算法原理舉例 圖中A B G表示7個城市 連線表示城市之間有道路相通 連線旁的數(shù)字表示道路的長度Wij 現(xiàn)要從城市A到G找出一條最短路線 該問題有三個階段 第一階段從A到B或C 第二階段到D E或F 第三階段到終點G 我們從終點向前倒過來找 A G F E D C B 2 4 1 2 3 1 3 3 1 3 4 第三階段 從D E F到G的最短路分別為1 3 4 記為f D 1 f E 3 f F 4 第二階段 與D E F有連線的出發(fā)點為B和C 從B出發(fā)分別經(jīng)過D E F 至終點G的里程分別為 WBD f D 3 1 4WBE f E 3 3 6WBF f F 1 4 5故B到G的最短路是上述三者的最小值 4 可以寫成f B min WBj f j 4 j是上一步考察過的三個點D E F 同理f C min WCj f j 而WCD f D 2 1 3WCE f E 3 3 6WCF f F 1 4 5故F C 3 第一階段 出發(fā)點只有一個A 從A出發(fā)分別經(jīng)過B C 至終點G的里程分別為 WAB f B 2 4 6WAC f C 4 3 7故A到G的最短路是上述兩者的最小值6 可以寫成f A min WAj f j 6 j是上一步考察過的兩個點B C 現(xiàn)在已經(jīng)到了起點 結(jié)束運算 從A到G的最短路為6 上述算法可以簡寫成N是終點 1是起點 j是與i相聯(lián) 上一步考察過 且與終點相通 f j 為已知的點 編寫LINGO程序如下 model sets cities A B C D E F G FL 定義7個城市 roads cities cities A BA CB DB EB FC DC EC FD GE GF G W P 定義哪些城市之間有路相聯(lián) W為里程 P用來存放最短路的路徑 endsets data W 24331231134 enddataN SIZE CITIES FL N 0 終點的F值為0 for cities i i lt N FL i min roads i j W i j FL j 遞推計算各城市F值 顯然 如果P i j 1 則點i到點n的最短路徑的第一步是i j 否則就不是 由此 我們就可方便的確定出最短路徑 for roads i j P i j if FL i eq W i j FL j 1 0 end 部分計算結(jié)果 FL A 6FL B 4FL C 3FL D 1FL E 3FL F 4FL G 0最短路線為ABDG以上計算程序是通用程序 對其它圖 只需在此程序基礎(chǔ)上對數(shù)據(jù)作一些修改即可 程序中的語句roads cities cities A BA CB DB EB FC DC EC FD GE GF G W P 定義的集合稱為稀疏集合 本例中cities有7個成員 但是并非每個城市到其它6個城市都有路相通 只有部分城市之間有路 故定義衍生集合roads時用列舉法列出有路相通的每對城市 2 0 1規(guī)劃法用0 1規(guī)劃法也能求解最短路問題 其思路如下 設(shè)起點為1 終點為n 引入0 1型決策變量Xij 如果弧 i j 在最短路上 則Xij 1 否則Xij 0 對于除了起點1和終點n以外的任意一個頂點i 如果 說明從i出發(fā)的所有弧中必然有一條弧在最短路上 也就是說最短路經(jīng)過該頂點 此時所有從其它頂點到達該頂點的弧中必然也有一條弧在最短路上 因而必有 如果 說明最短路不經(jīng)過頂點i 故必有兩種情況可以合并寫成 對于起點1 則必然滿足 對于終點n 則必有 目標(biāo)函數(shù)是最短路上的各條弧的長度之和 總里程 最小 于是最短路問題可以用如下0 1規(guī)劃來描述 式中表示全體邊的集合 對于上例 編寫LINGO程序如下 model sets cities A B C D E F G 定義7個城市 roads cities cities A BA CB DB EB FC DC EC FD GE GF G W X 定義哪些城市之間有路相聯(lián) W為里程 X為0 1型決策變量 endsetsdata W 24331231134 enddata N SIZE CITIES MIN SUM roads W X FOR cities i i GT 1 AND i LT N SUM roads i j X i j SUM roads j i X j i SUM roads i j i EQ 1 X i j 1 SUM roads i j j EQ N X i j 1 end 計算結(jié)果與動態(tài)規(guī)劃法相同 程序中的最后一個約束方程可以去掉 因為有了前面兩個約束條件 共n 1個約束方程 可以導(dǎo)出最后一個約束方程 即終點的約束方程與前面n 1個約束方程線性相關(guān) 保留該約束方程 LINGO求解時也不會產(chǎn)生任何問題 因為LINGO會自動刪除多余的方程 該方法與前面的方法相比 靈活性稍差 它一次只能求出指定起點到指定終點的最短路 如果更改起點 則必須改動程序然后重新求解 三 旅行售貨商模型 旅行售貨商問題 又稱貨郎擔(dān)問題 TravelingSalesmanProblem簡稱TSP模型 是運籌學(xué)的一個著名命題 模型 有一個推銷商 從某個城市出發(fā) 要遍訪若干城市各一次且僅一次 最后返回出發(fā)城市 已知從城市i到j(luò)的旅費為Cij 問他應(yīng)按怎樣的次序訪問這些城市 使得總旅費最少 稱能到每個城市一次且僅一次的路線為一個巡回 圈 TSP是典型的組合優(yōu)化問題 也是公認(rèn)的NP完全難題 不算出發(fā)地 n個城市有 n 1 種排列方法 每一種旅行路線是排列中的一種 當(dāng)n變大時 計算量呈指數(shù)增長 窮舉法所費時間是難以承受的 為此 多年以來有許多人研究了一些近似算法 我們把TSP問題轉(zhuǎn)化為0 1規(guī)劃 然后用LINGO來求解 1 方法一 判斷各邊是否包含在旅行路線中引入0 1整數(shù)變量xij 且i j xij 1表示路線從i到j(luò) 即邊i j在旅行路線中 而xij 0則表示不走i j路線目標(biāo)函數(shù)首先必須滿足約束條件 對每個城市訪問一次且僅一次 從城市i出發(fā)一次 到其它城市去 表示為 引入0 1整數(shù)變量xij 且i j xij 1表示路線從i到j(luò) xij 0則表示不走i j路線目標(biāo)函數(shù)首先必須滿足約束條件 對每個城市訪問一次且僅一次 從城市i出發(fā)一次 到其它城市去 表示為從某個城市到達j一次且僅一次 表示為 以上建立的模型類似于指派問題的模型 對TSP問題只是必要條件 并不充分 例如 用圖示路線連接六個城市 滿足以上兩個約束條件 但這樣的路線出現(xiàn)了兩個子回路 兩者之間不通 不構(gòu)成整體巡回路線 為此需要考慮增加充分的約束條件以避免產(chǎn)生子巡回 下面介紹一種方法 增加變量ui i 2 3 n 它的大小可以取整數(shù) 例如從起點出發(fā)所達到的城市u 2 依此類推 附加約束條件 ui uj nxij n 1 i 1 n j 2 n 且i j 下面證明 1 任何含子巡回的路線都必然不滿足該約束條件 不管ui如何取值 2 全部不含子巡回的整體巡回路線都可以滿足該約束條件 只要ui取適當(dāng)值 用反證法證明 1 假設(shè)存在子巡回 則至少有兩個子巡回 那么 必然 至少有一個子巡回中不含起點城市1 如上圖中的4 5 6 4 則必有u4 u5 n n 1 u5 u6 n n 1 u6 u4 n n 1 把這三個不等式加起來得到n n 1 不可能 故假設(shè)不能成立 而對整體巡回 因為附加約束中j 2 不包含起點城市1 故不會發(fā)生矛盾 對于整體巡回路線 只要ui取適當(dāng)值 都可以滿足該約束條件 對于總巡回上的邊 xij 1 ui可取訪問城市i的順序數(shù) 則必有ui uj 1 約束條件ui uj nxij n 1變成 1 n n 1 必然成立 對于非總巡回上的邊 因為xij 0 約束條件ui uj nxij n 1變成 1 n 1 肯定成立 綜上所述 該約束條件只限止子巡回 不影響其它 于是TSP問題轉(zhuǎn)化成了一個混合整數(shù)線性規(guī)劃問題 TSP問題可以表示為規(guī)劃 TSP問題的LINGO模型 旅行售貨員問題 model sets city 1 6 u 定義6個城市 link city city dist 距離矩陣 x 決策變量 endsetsn size city data 距離矩陣 dist 070245484223961196702032410932136764454324011372180798842109311370161618572396213621801616029001196764798185729000 這里可改為你要解決的問題的數(shù)據(jù) enddata 目標(biāo)函數(shù) min sum link dist x FOR city K 進入城市K sum city I I ne K x I K 1 離開城市K sum city J J ne K x K J 1 保證不出現(xiàn)子圈 for city I I gt 1 for city J J gt 1 and I ne J u I u J n x I J n 1 限制u的范圍以加速模型的求解 保證所加限制并不排除掉TSP問題的最優(yōu)解 for city I u I n 1 for link bin x 定義X為0 1變量 end 計算結(jié)果 目標(biāo)函數(shù)值 6610路線 1 3 6 2 5 4 1 2 方法二 對城市排序 找出最優(yōu)排序在現(xiàn)實中的城市交通圖中 有些城市之間有直接道路 有些則沒有 如果兩點之間沒有直接的通路 則兩點之間的距離取最短路 經(jīng)過其它點 即用任意兩點之間的最短路Cij作為圖的距離矩陣 于是該圖可以看成是一個完全圖 即任意一對頂點都有一條邊相連的圖 此時形式上的環(huán)形巡回路線實際上個別點有可能不止經(jīng)過一次 設(shè)某個城市為旅行的出發(fā)地和終點 相當(dāng)于總部所在地 旅行者從該城市出發(fā)到其它n個城市各一次且僅一次 最后回到出發(fā)地 我們把行進路線分成n步 每一步到一個城市 第n 1步返回出發(fā)地 于是一條旅行路線就相當(dāng)于n個城市的一種排列 n個城市共有n 種排列方式 排序不同則總里程 或費用 可能不同 總里程 或總費用 最小的排序就是我們要尋找的最優(yōu)路線 引入0 1型決策變量Xkj 下標(biāo)k表示旅行的步數(shù) 下標(biāo)j表示到達哪一個城市 Xkj 1表示旅行者第k個目的地 到達點 是城市j Xkj 0則表示否 用lj表示總部到各城市的距離 用Cij表示城市i與城市j之間的最短路 從出發(fā)地到第1個點的路程為從最后一個點返回出發(fā)地的里程為 假設(shè)在第k步郵車達到城市i 在第k 1步達到支局j 即Xki Xk 1 j 1 則走過的里程為 Cij Xki Xk 1 j從第1點到第n點走過的總里程為目標(biāo)函數(shù)為 約束條件有以下2條 1 每一步到達一個城市 即 2 每一個城市必須到一次且只需一次 即 綜上所述 可以把TSP問題轉(zhuǎn)化成如下非線性0 1規(guī)劃 以上規(guī)劃種允許包含其它約束條件 用LINGO可以求解該規(guī)劃 舉例如下 某縣郵局和10個鄉(xiāng)鎮(zhèn)支局組成該縣的郵政運輸網(wǎng)絡(luò) 已知縣局到各支局的距離和支局之間的距離矩陣 數(shù)據(jù)在程序中 用一輛郵車完成郵件運輸任務(wù) 郵車從縣局出發(fā)到各支局去一次且只需一次 最后回到縣局 求總路程最短的行駛路線 編寫LINGO程序如下 MODEL SETS CITY 1 10 JL STEP 1 10 LINE STEP CITY X LINKS CITY CITY C ENDSETS DATA JL 71 56 27 30 28 26 15 9 30 27 C 0 15 44 47 64 83 86 75 93 9815 0 29 32 49 68 71 60 78 8344 29 0 20 37 53 42 31 49 5447 32 20 0 17 36 42 39 60 5764 49 37 17 0 19 37 37 58 5583 68 53 36 19 0 18 35 56 4786 71 42 42 37 18 0 24 38 2975 60 31 39 37 35 24 0 21 2693 78 49 60 58 56 38 21 0 2998 83 54 57 55 47 29 26 29 0 ENDDATA FOR LINE BIN X M1 SIZE STEP FOR CITY I SUM STEP N X N I 1 FOR STEP N SUM CITY I X N I 1 L1 SUM CITY I X 1 I X M1 I JL I LX SUM STEP N N LT M1 SUM LINKS I J C I J X N I X N 1 J MIN L1 LX END 在程序運行前需要對LINGO的參數(shù)作必要的設(shè)置 對于非線性規(guī)劃 LINGO提供兩種求解方法 一種是 GlobalSolver 稱為全局優(yōu)化求解器 另一種是 MultistartSolver 稱為多起點算法 全局優(yōu)化求解器優(yōu)點是確保找到全局最優(yōu)解 缺點是有時需要較長運行時間 多起點算法的優(yōu)點是節(jié)省運行時間 但不能保證找到的解就是全局最優(yōu)解 多設(shè)置起點數(shù)往往找到的解就是全局最優(yōu)解 點擊菜單 Options 再打開全局優(yōu)化求解器 GlobalSolver 選項 可以選或不選 GlobalSolver 當(dāng)選擇多起點算法 MultistartSolver 時 需要設(shè)置起點數(shù) 若選擇 SolverDecides 表示由LINGO決定 對以上程序 我們選擇 GlobalSolver 點擊菜單 Options 在全局優(yōu)化求解器 GlobalSolver 選項框內(nèi)打 再點擊 確定 運行以上程序 費時4分多鐘 得到最優(yōu)解 目標(biāo)函數(shù)值 總路程 260公里郵車的行駛路線為 縣局 8 9 10 7 6 5 4 1 2 3 縣局 3 多旅行商問題在現(xiàn)實中問題中 有時候不是由一人走遍所有點 而是由幾個人分工合作 每個人只到其中部分城市 每個點都有人來過一次且只需一次 事先不指定誰到哪些點 求出使總路程最小的旅行規(guī)劃 每個人的行走路線 例如郵路規(guī)劃中 為了在允許的時間內(nèi)完成郵件運輸任務(wù) 縣局的郵車往往不止1輛 而是用若干輛郵車分工運輸 只要保證每個支局有郵車來過即可 為了節(jié)省行駛費用 需要規(guī)劃幾輛郵車的最佳路線 這就是多旅行商問題 多旅行商問題的提法如下 有n 1個城市 相互間的路程 或旅行費用 為已知 有k個旅行商都從總部所在城市出發(fā) 赴其它城市旅行推銷 分工遍歷其余n個城市 即每個城市各有任意一名旅行商來過一次且僅一次 最后都回到出發(fā)地 目標(biāo)是總路程最短或總費用最省 多旅行商問題在物流配送 郵路優(yōu)化等方面具有較高的實用價值 而在現(xiàn)實問題中 研究對象往往不是單純的旅行商問題 而要考慮各種約束條件 例如時間約束 載重量約束等等 研究這一類帶約束條件的多旅行商問題具有很強的現(xiàn)實意義 在現(xiàn)實的多旅行商問題中 往往帶有約束條件 例如時間約束 載重量約束等等 帶約束條件的多旅行商問題具有廣泛現(xiàn)實意義 且是極具挑戰(zhàn)性的難題 我們?nèi)匀话阉D(zhuǎn)化為0 1非線性規(guī)劃并編成LINGO程序來求解 實例某縣郵政局管轄16個支局 已知縣局到各支局的距離以及16個支局之間的距離矩陣 寄達各支局和各支局收寄的郵件 袋 如下表所示 縣郵局和各支局分布圖 每一輛郵車最多裝載65袋郵件 郵車的運行成本為3元 公里 試用最少郵車 并規(guī)劃郵車的行駛路線使總費用最省 分析 首先考慮最少郵車數(shù)量 由題目所給表中數(shù)據(jù) 寄達16個支局的郵件總數(shù)為176袋 從各支局收寄的郵件總數(shù)為170袋 每一輛郵車最多容納65袋郵件 至少需要176 65 2 7輛郵車 由于郵車數(shù)量為整數(shù) 故最少需要3輛郵車 如果3輛郵車能夠完成郵件運輸任務(wù) 則3輛車就是郵車數(shù)量的最優(yōu)解 運輸費用與行駛里程成正比 總里程最短對應(yīng)總費用最省 把16個支局放在一起作為一個整體考慮 找出3條郵路 每條郵路都從縣局出發(fā) 到若干支局進行卸裝 最后回到縣局 各郵車路過的支局?jǐn)?shù)量未知 合理安排各郵車的行駛路線 由3輛郵車分別承包運輸 在滿足運載量約束前提下 把3條巡回路線的總里程最小作為優(yōu)化的目標(biāo) 該問題相當(dāng)于附帶約束條件的多旅行商模型 引入0 1型決策變量Xkj Ykj Zkj 分別表示3輛郵車第k步到達支局j 下標(biāo)k表示郵車行走的步數(shù) 下標(biāo)j表示到達哪一個支局 當(dāng)決策變量Xkj Ykj Zkj等于1時分別表示某郵車第k個裝卸點是支局j 等于0時表示否 設(shè)各郵車管轄的支局?jǐn)?shù)量分別為m1 m2 m3 則m1 m2 m3 16 約束條件有以下3條 1 任何一輛車在任何一步到達一個支局 即 2 任何一個支局必須有一輛郵車到達一次且只需要一次 即 3 在郵車行進的任何路段上 裝載的郵件不超過65袋 設(shè)寄達各支局的郵件量為Pj 各支局收寄的郵件量為Qj 裝載量是動態(tài)變化的 以第1輛郵車為例 出發(fā)時的裝載量為 到第1個支局卸裝以后 裝載量變?yōu)樵谛旭傔^程中 裝載量的遞推公式為約束條件為 綜上所述 建立多旅行商問題的0 1規(guī)劃模型如下 裝載量的計算公式為 編寫LINGO程序如下 MODEL SETS STATION 1 16 JL P Q STEPX 1 6 WX STEPY 1 5 WY STEPZ 1 5 WZ LINEX STEPX STATION X LINEY STEPY STATION Y LINEZ STEPZ STATION Z LINKS STATION STATION C ENDSETS DATA JL 27361711243144403020252121182736 P 10 15 6 9 13 6 11 4 13 17 11 2 11 21 13 14 Q 9 14 5 10 9 10 13 9 15 9 6 7 13 15 10 16 C 0312738515871675747524821415261310193327324564534761575248566327190142734474939294238382938443833140132033352515333232152430512727130921372626434545282938583234209013323235475252353342714547332113019303950656548444067644935373219011203154613425215753392526323011010204351241413474729152635392010018364114918 526142334347503120180234625142348573832455265544336230272233422152383245526561514146270394857414829152835483424142522390112052563824293344251491433481109616344303842402113182342572090 ENDDATA FOR LINEX BIN X FOR LINEY BIN Y FOR LINEZ BIN Z M1 SIZE STEPX M2 SIZE STEPY M3 SIZE STEPZ FOR STATION I SUM STEPX N X N I SUM STEPY N Y N I SUM STEPZ N Z N I 1 FOR STEPX N SUM STATION I X N I 1 FOR STEPY N SUM STATION I Y N I 1 FOR STEPZ N SUM STATION I Z N I 1 WX0 SUM STATION I P SUM STEPX N X N I WY0 SUM STATION I P SUM STEPY N Y N I WZ0 SUM STATION I P SUM STEPZ N Z N I WX 1 WX0 SUM STATION J P J Q J X 1 J WY 1 WY0 SUM STATION J P J Q J Y 1 J WZ 1 WZ0 SUM STATION J P J Q J Z 1 J FOR STEPX N N GE 2 WX N WX N 1 SUM STATION J P J Q J X N J FOR STEPY N N GE 2 WY N WY N 1 SUM STATION J P J Q J Y N J FOR STEPZ N N GE 2 WZ N WZ N 1 SUM STATION J P J Q J Z N J WX0 65 WY0 65 WZ0 65 FOR STEPX N WX N 65 FOR STEPY N WY N 65 FOR STEPZ N WZ N 65 L1 SUM STATION I X 1 I X M1 I JL I L2 SUM STATION I Y 1 I Y M2 I JL I L3 SUM STATION I Z 1 I Z M3 I JL I LX SUM STEPX N N LT M1 SUM LINKS I J C I J X N I X N 1 J LY SUM STEPY N N LT M2 SUM LINKS I J C I J Y N I Y N 1 J LZ SUM STEPZ N N LT M3 SUM LINKS I J C I J Z N I Z N 1 J MIN L1 L2 L3 LX LY LZ END 三輛郵車各自負責(zé)的支局?jǐn)?shù)量有若干種分配方法 例如有6 5 5 6 6 4 7 5 4等不同分組法 經(jīng)過試驗 以6 5 5方案最優(yōu) 目標(biāo)函數(shù)值 3條郵路的總里程 為343km 第一條郵路 縣局 10 9 8 7 5 6 縣局 總里程121km 沿途各段郵件的裝載量為64 56 58 63 65 61 65袋 注意 如果支局5和6的先后次序倒過來 即走7 6 5 縣局 則里程為106km 減少15km 但是在支局6卸裝以后 郵件達69袋 超過了裝載量約束 看來先到支局5 后到支局6是因為避免超載的原因 被迫繞路 整體上仍然保持最優(yōu) 第二條郵路 縣局 14 15 16 11 12 縣局 總里程105km 沿途各段郵件的裝載量為61 55 52 54 49 54袋 第三條郵路 縣局 13 1 2 3 4 縣局 總里程117km 沿途各段郵件的裝載量為51 53 52 51 50 51袋 三條郵路的圖形如圖所示 四 最小生成樹和最優(yōu)連線 問題的提出 要建造一個連接若干城市的通訊網(wǎng)絡(luò) 已知城市i與j之間架設(shè)通訊線路所需費用為cij 請設(shè)計一個既能使所有城市都能接通 又使總費用最小的的方案 在圖論中 連通并且無圈的無向圖稱為樹 設(shè)G是具有n個頂點的無向連通圖 則G是樹的充分必要條件是G有n 1條邊 若T是包含G的全部頂點的子圖 它又是樹 則稱T是G的生成樹 如果圖的邊有權(quán) 對應(yīng)于邊的實數(shù) 則權(quán)的和最小的生成樹稱為最小生成樹 最優(yōu)連線就是尋找圖的最小生成樹 MinimalSpanningTree 簡稱MST 許多實際問題都可以歸結(jié)為最小生成樹 例如 如何修筑一些公路把若干個城鎮(zhèn)連接起來 如何架設(shè)通訊網(wǎng)絡(luò)將若干個地區(qū)連接起來 如何修筑水渠將水源和若干塊待灌溉的土地連接起來等等 為了說明問題 以下面的問題作為范例 范例 假設(shè)某電力公司計劃在七個村莊架設(shè)電線 各村莊之間的距離如圖所示 試求出使電線總長度最小的架線方案 節(jié)點1表示樹根 點i到點j的距離用Cij表示 當(dāng)兩個節(jié)點之間沒有線路相通時 兩點之間距離用M 很大的實數(shù) 表示 引入0 1整數(shù)變量xij xij 1 且i j 表示從i到j(luò)的邊在樹中 xij 0則表示邊不在樹中 目標(biāo)函數(shù)約束條件 1 除樹根外每個點都有線路通到 且只需要一次 表示為 2 至少有一條線路從1出來 以上約束條件是必要條件 但不充分 類似于TSP問題 增加一個變量u 再附加約束條件 1 限制uj的取值范圍為 u1 0 1 uj n 1 j 2 3 n 用以下不等式可以達到目的 uj 1且uj n 1 n 2 x1j j 1 2 如果線路從j到k 則uk uj 1 且避免來回重復(fù)和圈 約束條件為 uj uk xkj n 2 1 xkj n 3 xjk 1 k n 2 j nj k 最優(yōu)連線 最小生成樹 轉(zhuǎn)化為混合整數(shù)規(guī)劃 編寫LINGO程序如下 MODEL sets city 1 7 u 定義7個城市 link city city dist x 距離矩陣和決策變量 endsetsn size city data dist是距離矩陣 dist 034710010010030324100100430100571007210002100610045201410010071001021001001006420 這里可改為你要解決的問題的數(shù)據(jù) enddata min sum link dist x 目標(biāo)函數(shù) U 1 0 for link bin x 定義X為0 1變量 FOR city K K GT 1 sum city I I ne K x I K 1 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 sum city J J GT 1 x 1 J 1 for city K K gt 1 U K 1 U K N 1 N 2 X 1 K end 計算結(jié)果 目標(biāo)函數(shù)值 最優(yōu)連線的長度 為13 最優(yōu)連線的構(gòu)成如圖所示 五 最大流問題 1 問題的描述設(shè)有一批物資 要從A市通過公路網(wǎng)絡(luò) 內(nèi)含一些中轉(zhuǎn)站 運往B市 已知每段公路的運輸能力有限制 流量限制 問應(yīng)如何安排運輸方案 才能使總運量最大 這就是網(wǎng)絡(luò)最大流問題 例 下圖是從發(fā)貨地 到目的地 的有向運輸網(wǎng)絡(luò) 稱點 為發(fā)點 源 點 為收點 匯 有向邊 弧 旁邊的數(shù)字是該弧的流量 運輸能力 限制 求 的最大流 2 數(shù)學(xué)模型 對每一條弧 頂點i到j(luò) 定義f i j 為該弧上從頂點i到頂點j的流量 用Cij表