災(zāi)情巡視的最短路數(shù)學(xué)建模

1、災(zāi)情巡視路線的數(shù)學(xué)模型摘 要本文研究的是根據(jù)某縣的鄉(xiāng)（鎮(zhèn)）、村公路網(wǎng)示意圖，如何在不同條件下制定出最佳災(zāi)情巡視方案的問(wèn)題。針對(duì)問(wèn)題一：首先將公路網(wǎng)轉(zhuǎn)化為一張無(wú)向賦權(quán)圖并構(gòu)造其鄰接矩陣，然后根據(jù)Dijkstra算法求出任意兩點(diǎn)間的最短距離及O點(diǎn)到其余頂點(diǎn)的最短路，最短路構(gòu)成了一棵以O(shè)為樹(shù)根的最小生成樹(shù)，將干枝分為三組，每組各頂點(diǎn)間的最短路構(gòu)成一個(gè)完備加權(quán)圖，再建立混合整數(shù)規(guī)劃模型求其最佳H圈。再逐步調(diào)整，使三組中路程較長(zhǎng)者減小，最后得到三個(gè)組路程分別為204.9km、208.8km和205.3km，最長(zhǎng)路程為208.8km，路程均衡度為1.9%，總路程為619km。針對(duì)問(wèn)題二:依題意至少需要4組

2、，根據(jù)問(wèn)題一中得到的最小生成樹(shù)將頂點(diǎn)分為4組，利用問(wèn)題一中的算法，求出每組的最佳H圈，然后逐步調(diào)整，使四組中用時(shí)較長(zhǎng)者減小，最后得到四個(gè)組所用時(shí)間分別為21.9h、22.41h、22.12h和21.66h，最長(zhǎng)時(shí)間為22.41h，時(shí)間均衡度為3.3%。針對(duì)問(wèn)題三:根據(jù)O點(diǎn)到最遠(yuǎn)點(diǎn)的距離確定時(shí)間上界，然后根據(jù)時(shí)間上界和到O點(diǎn)的距離由遠(yuǎn)及近確定最優(yōu)巡視路線，得最優(yōu)方案為分23組，巡視時(shí)間為6.43h，具體路徑見(jiàn)問(wèn)題三解答。針對(duì)問(wèn)題四：以問(wèn)題二中所得結(jié)果為例，固定T，t和V中的兩個(gè)量，改變一個(gè)量，求巡視時(shí)間與該變量間的關(guān)系，巡視時(shí)間與T，t和V的曲線圖見(jiàn)解答四。關(guān)鍵詞：Dijkstra算法、最小生成

3、樹(shù)、加權(quán)完備圖、最佳H圈、整數(shù)規(guī)劃1.問(wèn)題重述1.1問(wèn)題背景 今年夏天該縣遭受水災(zāi)。為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門(mén)負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。1.2需要解決的問(wèn)題 問(wèn)題一:若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線。 問(wèn)題二:假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車(chē)行駛速度V=35公里/小時(shí)。要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下你認(rèn)為最佳的巡視路線。 問(wèn)題三:在上述關(guān)于T , t和V的假定下，如果巡視人員足夠多，完成巡視的最短時(shí)間

4、是多少；給出在這種最短時(shí)間完成巡視的要求下，你認(rèn)為最佳的巡視路線。 問(wèn)題四:若巡視組數(shù)已定(如三組），要求盡快完成巡視，討論T，t和V改變對(duì)最佳巡視路線的影響。2.模型的假設(shè)假設(shè)一:各組在巡視過(guò)程中，路途通暢，無(wú)任何延誤時(shí)間。假設(shè)二:各組行駛車(chē)速都相同，并且勻速行駛。假設(shè)三:非本組巡視的鄉(xiāng)（鎮(zhèn)）或村只是路過(guò)，不作停留。3.符號(hào)的說(shuō)明符號(hào)符號(hào)說(shuō)明T在鄉(xiāng)(鎮(zhèn))的停留時(shí)間t在村的停留時(shí)間V汽車(chē)的速度wij兩相鄰點(diǎn)i和j的距離dij點(diǎn)i和點(diǎn)j的最短距離Zk第k組的最佳H圈的路程L第一問(wèn)三個(gè)組中路程最大者路程均衡度sjk第k組的巡視時(shí)間sj幾個(gè)組巡視時(shí)間的最大者，即完成巡視任務(wù)所需時(shí)間4.問(wèn)題分析針對(duì)問(wèn)

5、題一:問(wèn)題一是多個(gè)推銷(xiāo)員問(wèn)題，我們首先考慮對(duì)鄉(xiāng)(鎮(zhèn)）、村這些點(diǎn)進(jìn)行分組，然后安排三組人進(jìn)行巡視，將多個(gè)推銷(xiāo)員問(wèn)題轉(zhuǎn)化為單個(gè)推銷(xiāo)員問(wèn)題。首先根據(jù)公路網(wǎng)圖建立一個(gè)鄰接矩陣儲(chǔ)存相鄰頂點(diǎn)間的距離，然后根據(jù)所得的鄰接矩陣用Dijkstra算法求出任意兩個(gè)頂點(diǎn)間的最短距離及O點(diǎn)到其余頂點(diǎn)間的最短路，再根據(jù)O點(diǎn)到其余頂點(diǎn)的最短路用Matlab畫(huà)出以O(shè)為樹(shù)根的最小生成樹(shù)(程序見(jiàn)附錄一)，由最小生成樹(shù)的樹(shù)枝將頂點(diǎn)分為三組，根據(jù)每組各點(diǎn)間的最短距離，構(gòu)造一個(gè)完備加權(quán)圖，即在一個(gè)完備加權(quán)圖里面求最佳H圈，為T(mén)SP問(wèn)題。再建立一個(gè)整數(shù)規(guī)劃模型表示TSP問(wèn)題，求解得出最佳H圈的路程和其對(duì)應(yīng)的路徑，最后逐步調(diào)整，是三組中

6、巡視路程最長(zhǎng)的減小，可得到一個(gè)近似最優(yōu)解。針對(duì)問(wèn)題二，首先根據(jù)單個(gè)組的最小巡視路程和在各個(gè)停留點(diǎn)所需的總的停留時(shí)間計(jì)算出至少應(yīng)分4個(gè)組，考慮到該圖中鄉(xiāng)(鎮(zhèn))和村分布均勻，故首先將52個(gè)要巡視的頂點(diǎn)平分為4組，然后如問(wèn)題一求出每個(gè)組的最佳H圈的路程，根據(jù)改組的最佳H圈的路程和停留的時(shí)間可算出其巡視時(shí)間，然后逐步調(diào)整，使四個(gè)組中巡視時(shí)間最大的減小，可得到一個(gè)近似最優(yōu)解。針對(duì)問(wèn)題三，在巡視人員充足的前提下，設(shè)計(jì)最佳巡視路線。先根據(jù)問(wèn)題一中 得到的O點(diǎn)到最遠(yuǎn)點(diǎn)的距離確定巡視時(shí)間上界，然后再不超過(guò)時(shí)間上界的前提下，由遠(yuǎn)及近設(shè)計(jì)巡視路線，使巡視時(shí)間盡可能接近時(shí)間上界。針對(duì)問(wèn)題四，可以第二問(wèn)的結(jié)果為例進(jìn)行分

7、析，固定T,t和V中的兩個(gè)量，改變一個(gè)量，繪制出完成巡視任務(wù)所需時(shí)間隨各個(gè)量得變化曲線圖，觀察其對(duì)完成巡視任務(wù)所需時(shí)間的影響，并進(jìn)行分析。5.數(shù)據(jù)分析首先根據(jù)題目所給公路網(wǎng)圖建立一個(gè)鄰接矩陣，然后根據(jù)鄰接矩陣用Dijkstra算法算出O點(diǎn)到其余頂點(diǎn)間的最短路，根據(jù)最短路可用Matlab函數(shù)畫(huà)出以O(shè)為樹(shù)根的最小生成樹(shù)(程序見(jiàn)附錄一)，如下圖，將樹(shù)枝從左至右依次編號(hào)為、，6.問(wèn)題一的解答 6.1模型一的建立 問(wèn)題一是多個(gè)推銷(xiāo)員問(wèn)題，可以轉(zhuǎn)化為最佳H圈問(wèn)題，再建立整數(shù)規(guī)劃模型求解最佳H圈的路程及路徑。首先根據(jù)鄰接舉證用Dijkstra算法求出任意兩點(diǎn)間的最短距離及O點(diǎn)到其余頂點(diǎn)間的最短路，根據(jù)最短路

8、畫(huà)出以O(shè)為樹(shù)根的最小生成樹(shù)。Dijkstra算法如下：Dijkstra算法：求G中從頂點(diǎn)u0到其預(yù)定點(diǎn)的最短路。S：具有永久標(biāo)號(hào)的頂點(diǎn)集。對(duì)每一個(gè)頂點(diǎn)，定義兩個(gè)標(biāo)記(l(v),z(v),其中：L(v):表示從頂點(diǎn)u0到v的一條路的權(quán)。Z(v):v的父親點(diǎn)，用以確定最短路的路線。算法的過(guò)程就是在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終的l(v)為從頂點(diǎn)u0到v的最短路的權(quán)。輸入為帶權(quán)鄰接矩陣W。用上述算法求出的l(v)就是u0到v的最短路的權(quán)，從v的父親點(diǎn)標(biāo)記z(v)追溯到u0，就得到u0到v的最短路的路線。如上圖，可看出從O出發(fā)的共有六個(gè)干枝，將這六個(gè)干枝進(jìn)行分組，分組時(shí)遵循以下三個(gè)準(zhǔn)則。準(zhǔn)則一:盡量使長(zhǎng)

9、的干枝和短的干枝分為一組。準(zhǔn)則二:盡量把相鄰干枝上的點(diǎn)分為一組。準(zhǔn)則三:盡量使使同一枝干及其分支上的點(diǎn)分為一組根據(jù)該原則確定一個(gè)分組形式：(),(),()。然后分別求每個(gè)組的最佳H圈。為求最佳H圈，應(yīng)首先由給定的圖G=(V,E)構(gòu)造一個(gè)以V為頂點(diǎn)集的完備圖,的每條邊(x,y)的權(quán)等于頂點(diǎn)x與y在途中最短路的權(quán)，即，這樣就把在G中尋找最佳推銷(xiāo)員回路問(wèn)題轉(zhuǎn)化為在完備加權(quán)圖G中尋找最佳H圈，即TSP問(wèn)題，我們將其轉(zhuǎn)化為混合整數(shù)規(guī)劃模型，建立了模型一。 確定目標(biāo)函數(shù).3建立整數(shù)規(guī)劃模型尋找最佳H圈 首先引入0-1整數(shù)變量:，則目標(biāo)函數(shù)為: 確定約束條件巡視i后必須要有一個(gè)即將巡視的確切鄉(xiāng)(鎮(zhèn))或村；巡

10、視j前必須要有一個(gè)剛剛巡視過(guò)的確切鄉(xiāng)(鎮(zhèn))或村。用下面的兩組約束分別實(shí)現(xiàn)上面的兩個(gè)條件。 到此得到一個(gè)指派問(wèn)題的整數(shù)規(guī)劃模型，但這兩個(gè)條件對(duì)于TSP來(lái)說(shuō)并不充分，只是必要條件。因此要在原模型的基礎(chǔ)上附加充分的條件以避免產(chǎn)生子巡回的方法。把額外變量附加到問(wèn)題中，可把這些變量看作是連續(xù)的（這些變量在最優(yōu)解中取整數(shù)值）?，F(xiàn)附加下面形式的約束條件 綜上所述，有以下約束條件: 綜上所述，得到問(wèn)題一的最優(yōu)化模型 6.2模型一的求解由以上模型得到調(diào)整前和經(jīng)過(guò)兩次調(diào)整后的結(jié)果，整理如下表： (單位：km) 第1組第2組第3組總路程均衡度最長(zhǎng)路程調(diào)整前237.5191.1125.5554.147.2%237.5

11、第一次調(diào)整216.5191.1188.7596.312.8%216.5第二次調(diào)整204.9208.8205.36191.9%208.8 得到的第二次調(diào)整后的路線及各組路程，總路程，均衡度整理如下表： (單位：km)組別路線(用紅色標(biāo)記的點(diǎn)為停留點(diǎn))路程總路程均衡度最長(zhǎng)路程1O-2-5-6-7-E-11-G-13-14-H-12-F-10-F-9-E-8-E-7-6-5-2-O204.96191.9%208.82O-M-N-25-20-L-19-J-18-I-15-I-16-17-22-K-21-23-24-27-26-P-O208.83O-2-3-D-4-D-3-C-B-34-35-32-30

12、-Q-28-Q-29-R-31-33-A-1-O205.37.問(wèn)題二的解答7.1模型二的建立 由題知，有17個(gè)鄉(xiāng)鎮(zhèn)，35個(gè)村，巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車(chē)行駛速度V=35公里/小時(shí)，所以，總停留時(shí)間為(小時(shí)),計(jì)算得出單個(gè)組的巡視時(shí)最小H圈的路程為508.2km，為設(shè)有x個(gè)分組，則有，得x3.43，故取x=4，即分四組進(jìn)行巡視， 分組時(shí)遵循以下四項(xiàng)準(zhǔn)則:準(zhǔn)則一:盡量使長(zhǎng)的干枝和短的干枝分為一組。準(zhǔn)則二:盡量讓各組的停留時(shí)間相同。準(zhǔn)則三:盡量把相鄰干枝上的點(diǎn)分為一組。準(zhǔn)則四:盡量將同一干枝上的點(diǎn)分在一組，且能形成環(huán)路。確定目標(biāo)函數(shù)完成巡視的時(shí)間取決于四個(gè)

13、組中最長(zhǎng)的巡視時(shí)間，故目標(biāo)函數(shù)為 min sj=（max（sjk）,k=1,2,32,4確定約束條件 sjk24,k=1,2,3,47.13綜上所述，得到問(wèn)題二的最優(yōu)化模型min（max（sjk）,k=1,2,32,4 sjk24,k=1,2,3,47.2模型二的求解由以上模型求得調(diào)整前和調(diào)整后的結(jié)果整理如下表：第一組第二組第三組第四組總路程(km)時(shí)間均衡度最長(zhǎng)時(shí)間（h）調(diào)整前鄉(xiāng)鎮(zhèn)的停留點(diǎn)個(gè)數(shù)5354663.612.30%23.12村的停留點(diǎn)數(shù)81089路程(km)136.5149.7179.2198.2巡視所用時(shí)間(h)21.920.27723.1222.663調(diào)整后鄉(xiāng)鎮(zhèn)的停留數(shù)54446

14、68.23.33%22.409村的停留數(shù)81098路程(km)136.5154.3179.2198.2巡視所需時(shí)間（h）21.922.40922.1221.663 所得調(diào)整后的四組路線，巡視時(shí)間等整理如下表： 組別路線(用紅色標(biāo)記的點(diǎn)為停留點(diǎn))路程（km)停留時(shí)間（h）行駛時(shí)間（h）巡視時(shí)間(h）1O-1-A-33-31-R-29-Q-30-32-35-34-B-C-O136.5183.9021.92O-M-25-21-K-17-16-17-22-23-24-N-26-27-28-P-O154.3184.4122.413O-M-25-20-L-19-J-18-I-15-14-13-G-11-E

15、-7-6-5-2-O179.2175.1222.124O-2-3-D-4-8-E-9-F-12-H-12-F-10-F-9-E-7-6-5-2-O198.2165.6621.668.問(wèn)題三的解答8.1從O點(diǎn)巡視H點(diǎn)的最短時(shí)間是所有最短時(shí)間中最長(zhǎng)的，其距離為77.5km，算出時(shí)間為小時(shí)，因此，T=2h，t=1h，V=35km/h時(shí)，若巡視人員足夠多，完成巡視的最短時(shí)間為6.43小時(shí)。在最短時(shí)間的限制下，完成巡視的最佳路線應(yīng)滿足以下條件：（1）每個(gè)組巡視的總時(shí)間不能超過(guò)最短時(shí)間小時(shí)，（2）所有的點(diǎn)都必須訪問(wèn)到，不能漏點(diǎn)，（3）所需巡視組數(shù)要盡量小。在尋求最優(yōu)路線時(shí)，從距離O點(diǎn)較遠(yuǎn)的點(diǎn)開(kāi)始搜索比較容

16、易，因?yàn)榈竭@些點(diǎn)的路線比較少。具體方法如下：第一步：依據(jù)最小生成樹(shù)算出從O點(diǎn)到每一點(diǎn)的最短距離。第二步：找出其中最大的一個(gè)，算出從O點(diǎn)到最短路巡視所需時(shí)間ti，并求 。第三步：若，則這一組只能訪問(wèn)這一點(diǎn)；若，則在余下的點(diǎn)中找出 距離O點(diǎn)最遠(yuǎn)的點(diǎn)，根據(jù)條件看這一組能否巡視這一點(diǎn)。第四步：若能巡視則算出，轉(zhuǎn)到第三步。第五步：若不能，則依次判斷次遠(yuǎn)點(diǎn)、第三遠(yuǎn)點(diǎn)滿足總巡視時(shí)間不超過(guò)， 就讓這組巡視這一點(diǎn)，直到，然后再?gòu)牡诙介_(kāi)始。通過(guò)以上方法找到最優(yōu)解是23組，如下表：8.2模型三的求解路線(用紅色標(biāo)記的點(diǎn)為停留點(diǎn))時(shí)間第1組O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-

17、06小時(shí)26分第2組O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-06小時(shí)9分第3組O-M-25-21-K-18-I-15-I-18-K-17-16-17-K-21-25-M-06小時(shí)19分第4組O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O5小時(shí)51分第5組O-2-5-6-7-E-9-F-10-F-9-E-8-E-7-6-5-2-O6小時(shí)13分第6組O-2-5-6-7-E-11-G-11-E-7-6-5-2-O5小時(shí)35分第7組O-M-25-21-K-18-I-18-K-21-25-M-O5小時(shí)29分第8組O-2-5-6-7-E-11-E-7

18、-6-5-2-O6小時(shí)12分第9組O-2-5-6-L-E-9-F-9-E-7-6-5-2-O6小時(shí)9分第10組O-2-5-6-L-19-J-19-L-6-5-2-O6小時(shí)6分第10組O-M-25-21-K-17-16-17-K-21-25-M-O6小時(shí)3分第12組O-M-25-21-K-18-K-21-25-20-25-M-O6小時(shí)13分第13組O-P-26-N-23-22-23-N-24-N-26-P-O5小時(shí)12分第14組O-2-5-6-7-E-8-E-7-6-5-2-3-D-4-D-3-2-O6小時(shí)0分第15組O-2-5-6-L-6-5-2-O-M-O6小時(shí)17分第16組O-1-A-34

19、-35-34-A-33-A-1-O5小時(shí)29分第17組O-R-29-Q-30-Q-29-R-O6小時(shí)2分第18組O-M-25-M-O-P-26-N-26-P-O6小時(shí)3分第19組O-R-31-32-31-R-O5小時(shí)44分第20組O-P-26-27-26-P-28-P-O5小時(shí)40分第21組O-2-3-D-3-2-O-C-O5小時(shí)25分第22組O-1-A-1-B-1-O6小時(shí)9分第23組O-2-3-2-5-2-O-M-O-P-26-N-23-N-26-P-O5小時(shí)51分 9.問(wèn)題四的解答9.1模型四的建立根據(jù)題意，假設(shè)巡視組數(shù)定為四組，以問(wèn)題二中的分組方案為例，固定T，t和V中的兩個(gè)量，改變其

20、中一個(gè)量，求巡視時(shí)間與該變量間的關(guān)系，通過(guò)MATLAB求解得到如下巡視時(shí)間隨三個(gè)變量的變化而變化的圖(程序見(jiàn)附錄一):圖中三個(gè)紅色的點(diǎn)位于一條直線上，分別代表T=2小時(shí)，t=1小時(shí)，V=35千米/小時(shí)時(shí)，對(duì)應(yīng)問(wèn)題二的巡視時(shí)間22.409h，即為問(wèn)題二的解。顯然，由下圖得出以下結(jié)論： (1)當(dāng)固定t、V時(shí)，巡視時(shí)間隨T的增大而增大(2)當(dāng)固定T、V時(shí)，巡視時(shí)間隨t的增大而增大，且隨t增大得比隨T增大地快(3)當(dāng)固定T、t時(shí)，巡視時(shí)間隨V的增大而減小更進(jìn)一步分析，可看出，當(dāng)V低于20km/h后，巡視時(shí)間急劇增加，當(dāng)V高于50km/h后，再增加對(duì)減小巡視時(shí)間作用很小，故從效率和安全兩個(gè)角度綜合考慮，

21、汽車(chē)速度V應(yīng)不低于20km/h，應(yīng)不高于50km/h11.模型的模型的評(píng)價(jià)、改進(jìn)及推廣11.1模型評(píng)價(jià)模型優(yōu)點(diǎn)：(1) 用均衡度量化分組的均衡性。(2) 綜合多種算法的思想進(jìn)行求解，使所得模型在災(zāi)情巡視方面有科學(xué)的指導(dǎo)意義。模型缺點(diǎn)：第三問(wèn)用經(jīng)驗(yàn)來(lái)調(diào)整的，如果可以通過(guò)編程求解則更好。11.2模型改進(jìn) 由于實(shí)際情況中，各個(gè)鄉(xiāng)（鎮(zhèn)）、村的受災(zāi)情況不同，故應(yīng)根據(jù)受災(zāi)的嚴(yán)重程度來(lái)分配巡視時(shí)的停留時(shí)間，可先將每個(gè)巡視點(diǎn)的受災(zāi)程度量化，建立T，t關(guān)于受災(zāi)程度的函數(shù)，然后分組巡視，求最佳巡視路線。11.3模型推廣所建模型還可用于公安執(zhí)勤人員的最優(yōu)巡回路線、流水作業(yè)、生產(chǎn)線的順序問(wèn)題以及老師任課班級(jí)負(fù)荷分配等

22、問(wèn)題。12.參考文獻(xiàn)1 趙靜,但琦,數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn),北京:高等教育出版社,2008.2 薛定宇，陳陽(yáng)泉，高等應(yīng)用數(shù)學(xué)問(wèn)題的MATLAB求解，北京：清華大學(xué)出版社，2008.13.附錄附錄一：Matlab程序%dijkstra.mfunction d,path=dijkstra(b,s,t)n,m=size(b);ix=(b=0);visited(1:n)=0;dist(1:n)=inf;parent(1:n)=0;dist(s)=0;d=inf;for i=1:(n-1) ix=(visited=0);vec(1:n)=inf;vec(ix)=dist(ix); a,u=min(vec);

23、visited(u)=1; for v=1:n if (b(u,v)+dist(u)1 zdjl(m,n) p=dijkstra(b,m,n); path(n,1:length(p)=p; end endendjl_path=1:53 zdjl(:,1) pathzdjl%畫(huà)最小生成樹(shù)的程序a1=1;b1=4;w1=11.5;a2=1 20 21 5 20 23 24 13 37 11 31 24 25 6 6 29 6 27 7 7 30;b2=20 21 5 22 23 24 13 37 11 31 32 25 6 26 29 8 27 7 28 30 9;w2=9.2 4.8 8.2 1

24、2.7 8.3 9.7 11.8 7.2 8.1 9.8 8.6 7.3 7.2 8.0 14.2 6.8 7.8 5.6 10.8 12.2 10.2;a3=1 14 43 43 39 12 35 12 36 10;b3=14 43 38 39 12 35 34 36 10 33;w3=19.8 12.0 6.5 7.8 4.1 9.8 6.8 9.2 8.2 8.8;a4=1 16 16 44 44 15 15 41 ;b4=16 46 44 45 15 42 41 40;w4=10.1 12.1 10.5 7.9 10.5 13.2 7.9 10.0;a5=1 18 47 17 18 4

25、9;b5=18 47 17 48 49 50;w5=7.9 7.9 7.2 7.7 9.2 8.1;a6=1 19 19 2 2 52;b6=19 3 2 51 52 53;w6=6.0 7.9 10.3 7.4 11.5 8.2;R=sparse(a1 a2 a3 a4 a5 a6,b1 b2 b3 b4 b5 b6,w1 w2 w3 w4 w5 w6);R(53,53)=0;h=view(biograph(R,ShowWeights,on);%第一問(wèn)程序zdjl_12=zdjl(1 4 5 6 7 8 9 11 13 20:32 37,1 4 5 6 7 8 9 11 13 20:32 3

26、7);zdjl_34=zdjl(1 10 12 14 15 16 33:36 38:46,1 10 12 14 15 16 33:36 38:46);zdjl_56=zdjl(1 2 3 17 18 19 47:53,1 2 3 17 18 19 47:53);zdjl_12_1=zdjl(1 6 7 8 9 11 13 20 23:32 37,1 6 7 8 9 11 13 20 23:32 37);zdjl_56_1=zdjl(1 2 3 4 5 17 18 19 21 22 47:53,1 2 3 4 5 17 18 19 21 22 47:53);zdjl_12_tzh=zdjl(1

27、6 7 8 9 20 23:32,1 6 7 8 9 20 23:32);zdjl_34_tzh=zdjl(1 10 11 12 13 14 15 16 33:37 38:45,1 10 11 12 13 14 15 16 33:37 38:45);zdjl_56_tzh=zdjl(1 2 3 4 5 17 18 19 21 22 46:53,1 2 3 4 5 17 18 19 21 22 46:53);%第二問(wèn)程序zdjl_1=zdjl(1 2 3 4 17 18 19 47:53,1 2 3 4 17 18 19 47:53);zdjl_2=zdjl(1 12 15 16 34 35 3

28、9:46,1 12 15 16 34 35 39:46);zdjl_3=zdjl(1 8 10 11 13 14 24 29 31 32 33 36 37 38,1 8 10 11 13 14 24 29 31 32 33 36 37 38);zdjl_4=zdjl(1 5 6 7 9 20:23 25:28 30,1 5 6 7 9 20:23 25:28 30);zdjl_1_tzh=zdjl(1 2 3 4 17 18 19 47:53,1 2 3 4 17 18 19 47:53);zdjl_2_tzh=zdjl(1 12 14 15 16 34 35 39:46,1 12 14 15

29、 16 34 35 39:46);zdjl_3_tzh=zdjl(1 8 10 11 13 23 24 29 31 32 33 36 37 38,1 8 10 11 13 23 24 29 31 32 33 36 37 38);zdjl_4_tzh=zdjl(1 5 6 7 9 20:22 25:28 30,1 5 6 7 9 20:22 25:28 30);%第三問(wèn)程序jl index=sort(zdjl(:,1);jl_index=jl indexsj=2*77.5/35+2;2*72.7/35+1+1;(69.9+8.8+11.8+60.3)/35+1+1;(67.3+12.2+5.6+

30、49.5)/35+1+1; (65.9+10.8+5.6+7.8+8.0+49.7)/35+1+1;2*62.7/35+2;2*61.1/35+2;2*55.9/35+1+1+1; 2*55.1/35+2+1;2*54.3/35+1+2;2*53.5/35+1+2;(52.9+9.2+4.1+7.9+38.3)/35+1+1+1;(49+10.0+8.9+44.3)/35+1+1; (41.7+8+12.3+8.1+34.9)/35+2+1;(39+11.8+9.5+19.8)/35+2+2;(36+8.2+11.5+7.4+23.7)/35+1+1+1;2*35.7/35+1+2+1;(31.8+8.8+10.5+20.6)/35+1+2+1; (30.2+8.1+9.2+12.9)/35+1+1+2;(28.4+7.9+12.1+10.1)/35+1+1+2;(22.