全國數(shù)學(xué)建模優(yōu)秀論文

1、承諾書我們仔細閱讀了中國人學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng) 上咨詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的，如果引用別人的成果或其他公開的 資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在止文引用處和參 考文獻中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如冇違反競賽規(guī) 則的行為，我們將受到嚴(yán)肅處理。我們授權(quán)全國大學(xué)生數(shù)學(xué)建模競賽組委會，可將我們的論文以任何形式進行公開展 示（包括進行網(wǎng)上公示，在書籍、期刊和其他媒體進行正式或非

2、正式發(fā)表等）。我們參賽選擇的題號是（從a/b/c/d中選擇一項填寫）：衛(wèi)我們的參賽報名號為（如果賽區(qū)設(shè)置報名號的話人 j2019所屈學(xué)校（請?zhí)顚懲暾娜簠①愱爢T（打卬并簽名）：1.2. 3. 指導(dǎo)教師或指導(dǎo)教師組負責(zé)人（打印并簽名）：日期：2013年9月16_日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）:編號專用頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）:賽區(qū)評閱記錄（可供賽區(qū)評閱吋使用）:評閱人評分rrorooro備 注oooooo全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）:送貨路線設(shè)計問題摘要木文針對送貨路線優(yōu)化設(shè)計問題進行研究，建立了求

3、最小ham訂ton圈模型。借助 mat lab, lingo, vc6. 0軟件，利用c語言、floyd算法、窮舉法、最遠送貨點優(yōu)先法、 最近送貨優(yōu)先法求解，較好的實現(xiàn)了送貨路線的設(shè)計優(yōu)化。首先,針對將30號貨物以最快時間送達問題，將此問題簡化為tsp問題，即尋 找一個最小hamilton圈。利用floyd算法求出任意兩點間距離，借助matalb、lingo 軟件求解最小的hamilton圈，求出最優(yōu)路線如下：0>2621>17>14>16>23 >32>35>38>36>38>43>42>49>42>4

4、5>4>34>31>27>39 >27>31>24> 19> 13> 18>0。其次，在問題一的基礎(chǔ)上，考慮到送達點的時間的要求，我們按照送貨時間的限制, 將送達點分四個階段，在每個階段內(nèi)利用窮舉法求解每一階段的最佳路徑，并判斷其總 的送貨時間是否滿足指定的時間。最終求出最優(yōu)路線如下： 0->18->13->19->24->31->27->27->39->27->31->31->34->40->45->45->45->42

5、->49-> 42->43->43->38->36->38->35->32->32->32->23->23->16->14->17->21->26->26->0o最后，針對將100件貨物以最快時間送達的問題，選擇一條最優(yōu)的路徑，我們分別 采用最遠送貨點優(yōu)先法和最近送貨點優(yōu)先兩種方法，分別得出兩種方案，最后將兩種方 案進行比較，方案一優(yōu)于方案二，因此，在考慮載重量及載重休積情況下，完成100件 送貨任務(wù)，我們選擇最遠送貨點優(yōu)先法，即方案一。關(guān)鍵詞：送貨路線優(yōu)化設(shè)計 最小hami

6、lton圈floyd算法 最遠送貨點優(yōu)先mat lab 軟件一、問題重述現(xiàn)今社會網(wǎng)絡(luò)越來越普及，網(wǎng)購已成為一種常見的消費方式，隨z物流行業(yè)也漸漸 興盛，每個送貨員需要以最快的速度及時將貨物送達，而且他們往往一人送多個地方， 要設(shè)計方案使其耗時最少。現(xiàn)有一快遞公司，庫房在圖1中的o點，一送貨員需將貨物送至城市內(nèi)多處，請設(shè) 計送貨方案，使所用時間最少。該地形圖的示意圖見圖1,各點連通信息見表3,假定 送貨員只能沿這些連通線路行走，而不能走其它任何路線。各件貨物的相關(guān)信息見表1, 50個位置點的處標(biāo)見表2。假定送貨員最大載重50公斤，所帶貨物最大體積1立方米。送貨員的平均速度為 24公里/小時。假定

7、每件貨物交接花費3分鐘，為簡化起見，同一地點冇多件貨物也簡 單按照每件3分鐘交接計算?，F(xiàn)在送貨員要將100件貨物送到50個地點。我們對以下問題做出研究。1. 若將130號貨物送到指定地點并返冋。設(shè)計最快完成路線與方式。給出結(jié)果。要 求標(biāo)出送貨線路。2. 假定該送貨員從早上8點上班開始送貨，要將130號貨物的送達時間不能超過指 定時間，請設(shè)計最快完成路線與方式。要求標(biāo)出送貨線路。3. 若不需要考慮所有貨物送達時間限制（包括前30件貨物），現(xiàn)在要將100件貨物全部 送到指定地點并返回。設(shè)計最快完成路線與方式。要求標(biāo)出送貨線路，給出送完所有快 件的時間。由于受重量和休積限制，送貨員可屮途返回取貨。可

8、不考慮中午休息時間。二、問題分析2. 1問題一由附表1可以得到30個包裹的總重量不超過（m3° = £>m）50kg,且總體積 /=130（v30 = £ v（）超過1加，則送貨員可一次攜帶30個包裹送貨到指定地點并返回。對于問題一，耍求送貨員以最快的方式將130貨物送達指定的地點并返回。因此, 可以將問題簡化為tsp （旅行商）進行求解（本題可以重復(fù)經(jīng)過某頂點），因此最佳運 送方案等價于找出一個遍歷所有目的頂點并返冋出發(fā)點的最短路線，送達的頂點間的最 短路徑及距離，即尋找一個最小的hamilton圈。2.2問題二問題二中耍求將130號貨物的送達時間不能超過

9、指定時間，考慮到所到的點的時間 的要求是否滿足題意即采用多次分區(qū)域的假設(shè)模型從而找出最優(yōu)的解。由題口所給的附表1可知，根據(jù)指定時間的先后，分四個階段去送貨（劃分見附錄 2）。從而最佳運送方案是找出每個階段的起點到終點以（距離下一個區(qū)域最近的點） 的最短路徑，即尋找出每個階段的最短路徑。應(yīng)用局部全排列窮舉法求解每一塊的最佳 路徑。2.2問題三在不考慮送貨吋間限制的情況下，將體積與重量兩個因素考慮在內(nèi)，允許送貨員可以往返取貨，要求送貨員以最快的方式將貨物送達指定地點并返冋。由于所有100個包 #100 <=100裹物體的總重量是mkx)=$> = 14%g，總體積為皿=£&g

10、t; = 2.曲，送貨員的最大載貨 1=1 1=1量為50kg,最大載貨體積為1加彳，所以送貨員會往返三次取貨，因此可以將所有的送 貨地點分為三塊。對于所有送貨地點的分塊，可以采用2種方案尋找離始發(fā)點最遠 的點，逐次加入次遠點，直至達到送貨員的最大載貨量；尋找離始發(fā)點最近的點，逐次 加入次近點，直至達到送貨員的最大載貨量。三、基本假設(shè)和符號說明3. 1基本假設(shè)1假設(shè)送貨員的行進速度與所送貨物的重量無關(guān)，速度均為24公里/小時；2. 假設(shè)送貨員只能沿如圖路線圖行駛，不能走其他的任何路線。且在聯(lián)通路線中，送 貨員可自由選擇；3. 假設(shè)送貨員保持24km/h,不考慮堵車及發(fā)生意外的情況；4. 送貨員

11、在送貨期間無塞車現(xiàn)象，即業(yè)務(wù)員送快遞途中不受任何外界因素影響；送貨的每一條路、每個地點可以重復(fù)經(jīng)過。3. 2符號說明符號符號說明i，j送貨點的標(biāo)號jfw30個包裹的總重量jfwo100個包裹的總重量fn30個包裹的總體積fw>100個包裹的總體積w從0開始回到0的總路線t從o開始冋到o的總路線四、模型的建立與求解4.1模型準(zhǔn)備1)根據(jù)已知點的坐標(biāo)和連接情況，使用matlab做出齊點位置如圖所示:160001400012000100008000600040002000°!圖1送貨地點示意圖2）根據(jù)已知各點坐標(biāo)，利用c語言編程求得圖屮相鄰連通點間的距離如下表（附 錄一）3）利用fl

12、oyd算法求出任意兩個頂點vi,vj之間的距離（附錄一）:4. 2問題一模型的建立與求解4.2. 1模型的建立30m 30 = / m i由附表1可以得到30個包裹的總重量不超過（ 臺 ）50kg,且總體積30（-）不超過1加3,則送貨員可一次攜帶30個包裹送貨到指定地點并返冋。30個包裹的送達地點總共有22個,分別為：13 14 16 17 18 21 23 24 26 27 31 32 34 36 38 3940 42 43 45 49；4. 2. 2模型的求解利用vc6.0編程，先計算岀相鄰頂點（vi, vj） z間的距離（附錄一），并賦為邊的 權(quán)值，然后floyd算法求出任意兩點間最短

13、路徑（附錄二）。構(gòu)造連接各頂點的哈密爾頓 圈（附錄三），求出最優(yōu)解送貨路線如下：0>26>21 > 17> 14> 16>23>32>35>38>36>38>43>42>49>42>45>40>34>31 >27>39>27>31 >24> 19> 13> 18>0 如圖所示：從而，得到最短送貨路線的總長d=54707.47m4. 3問題二模型的建立與求解4.3.1模型的建立曲于考慮到送貨時間運輸限制，我們優(yōu)先考慮送貨時間。根據(jù)

14、指定時間的先后，分 四個階段去送貨，應(yīng)用局部全排列窮舉法求解每一-塊的最佳路徑。即以送貨時間對所冇 貨物進行分塊，并在每一塊內(nèi)部采用局部全排列窮舉法求取路徑，并判斷其總的送貨時 間是否滿足指定的時間。4. 3. 2模型的求解基本步驟如下：(1) 第一時間段為8:009:00之間送到的站點為：13、18、39、27、24、27,不計 重復(fù)站點，總共有5個站點，利用窮舉法比較次得到最佳路徑為:18->13->24->27->39, 考慮交貨吋間在內(nèi)總吋間為57.1分。(2) 第二時間段為9:009:30之間送到的站點為:31、31、34、40、45、45、45, 不計重復(fù)站

15、點，總共有4個站點，利用窮舉法比較次得到最佳路徑為：31->34->40->45, 考慮交貨時間在內(nèi)總時間為46.05分。(3) 第三時間段為9:3010:15之間送到的站點為:42、49、43、43、38,不計重復(fù) 站點，總共有4個站點，利用窮舉法比較次得到最佳路徑為：42->49->43->43->3&考慮 交貨時間在內(nèi)總時間為39.58分。(4) 第四時間段為10:1512:00之間送到的站點為：36、32、23、16、14、17、21、 26,不計重復(fù)站點，總共有8個站點，利用窮舉法比較次得到最佳路徑為：36->32->23

16、-> 16-> 14-> 17->21 ->26,考慮交貨時間在內(nèi)總時間為81.97分。 按照時間分段得到站點分塊表，如下表所示：表1站點分塊表第時間段貨物號送達地 點重量體積時間最佳路 徑時間（含 交貨時 間）/分1132.50.03169:001857.12180.50.03549:001313392.560.05959:002419272.450.05459:002720242.930.0529:002722272.250.00189:0039第時間段3311.180.02689:303146.0511451.10.02879:303114452.280.0

17、5019:303421310.80.01089:304024342.80.01039:304525402.140.01559:304526450.680.06829:3045第三吋間段10381.330.031910:154239.5812430.950.022810:154915422.850.01910:154316431.70.078210:154327491.350.014410:1538第 四 時 冋 段4261.560.03512:003685.455212.150.037712:00326141.720.0112:00327171.380.010912:00328231.40.0

18、42612:00239320.70.048112:002317320.250.051212:001618361.790.018412:001423261.570.02112:001728320.520.00212:002129232.910.058712:002630161.20.042912:0026因此，由以上時間段得到的路徑各時間分段路線圖，如下:綜上得到最佳路徑為：0->18->13->19->24->31->27->27->39->27->31->31->34->40->45->45->4

19、5->42- >49->42->43->43->38->36->38->35->32->32->32->23->23->16->14->17->21->26->26 ->0 4. 4問題三模型的建立與求解4. 3.1模型的建立在考慮送貨員所載貨物重量及體積限制，不考慮送貨時間限制的前提下，設(shè)計將貨 物最快送到指定地點的往返路線。由于所有物體的總重量是148公斤，總體積為2.98立方 米，送貨員的最大載貨量為50公斤，最大載貨體積為1立方米，所以送貨員會往返三次 取貨，因

20、此最少要將所有的送貨地點分為三塊。本題我們采用兩種分塊方案，分別為最 遠送貨點優(yōu)先法和最近送貨點優(yōu)先法；4. 3. 2模型的求解(1) 最遠送貨點優(yōu)先法尋找離始發(fā)點o點最遠的點，以此點為中心尋找周圍離其最近的點，直至達到送貨 員的最大載貨量和最大載貨體積，在剩余點鐘再以距離o的次遠點為屮心尋找其周圍的 點，直至達到送貨員的最大載貨量和最大載貨體積，直到所有貨物運送結(jié)束為止。有題目數(shù)據(jù)計算可得，距離0點最遠點為2號點，因此以2號點為中心的一組送貨點 分塊數(shù)據(jù)為：2、3、4、5、8、15、15、1、6、7、7、11、11、12、12、13、13、10、 10、18、18、20、20、22、25、2

21、5、25、29、30、28、9、33、33、14、14,共35個站 點，送貨員運送的總重量為48.54公斤，總體積為0.9857立方米，不計重復(fù)站點，共有23 個送貨點，將前12個站點作為一部分，后11個站點作為一部分，利用窮舉法得到其最佳 路徑為：18- >13->11->12-> 15->25->29->22->20->22->30->28->33->28->30->22-> 15->5->2->4 ->3->8-> 1 ->6-> 1 ->

22、7-> 10->9-> 14,其總吋間為 167.48分。除去此23個站點，由計算可知，距離o點最遠的點為48號點，以此點為中心的一組 送貨點數(shù)據(jù)為：48、44、46、46、46、41、41、50、47、40、40、37、37、34、34、19、 19、24、24、45、45、45、45、31、31、31、27、27、27、39、39,共31 個站點，送貨 員運送的總重量為50公斤，總體積為0.9573立方米，不計重復(fù)站點，共有15個送貨點， 將前11個站點作為一部分，后4個站點作為一部分，利用窮舉法得到其最佳路徑為：19- >24->31 ->34->

23、;40->47->40->37->41 ->46->48->44->50->45->36->27->39,其總時 間為141.82分。除去前兩部的站點后，經(jīng)計算的離o點最遠的站點時17號點，以此點為中心的一組 送貨點數(shù)據(jù)為：16、16、17、17、17、23、23、23、23、32、32、32、32、32、32、35、 38、38、38、36、36、36、21、21、43、43、43、42、42、49、49,共31 個站點，送貨 員運送的總重量為45.07公斤，總體積為0.9751立方米，不計重復(fù)站點，共冇11個送貨點,

24、利用窮舉法得到其最佳路徑為：17->23-> 16->23->32->35->38->43->42->49->42->43->38->36->21,其總時間為78.04 分。最后以26、26、26為一-組送回點數(shù)據(jù)，共3個站點，送貨員運送的總重量為4.39公斤, 總體積為0.0619立方米，不計重復(fù)只有1個站點，其總吋間為6.96分。綜合此四塊的數(shù)據(jù)可知，總的運送時間為394.3分。(2) 最近送貨點優(yōu)先法尋找離始發(fā)點最近的點，逐次加入次近點，直至達到送貨員的最大載貨量和最大載 貨體積，再在剩余點屮尋找距離o點

25、最近的點直至達到送貨員的最大載貨量和最大載貨 體積，直到所有貨物運送結(jié)束為止。由題目數(shù)據(jù)計算可得，距離o點最近點為26號點，因此以26號點為起始心的一組送 貨點分塊數(shù)據(jù)為:26、26、26、18、18、21、21、23、23、23、23、27、27、27、31、 31、31、34、34、36、36、36、39、39、24、24、17、17、17、17、11,共31 個站點， 送貨員運送的總重量為45.77公斤，總體積為0.936立方米，不計重復(fù)只有11個站點，利 用窮舉法得到其最佳路徑為：26->21 -> 17->23->36->27->39->31

26、 ->34->24-> 18,總時間為81.12分。除去此11個站點外，由計算可得，剩余點中離o點最近的點為25號點，以此點為起 始心的一組送貨點分塊數(shù)據(jù)為:25、25、25、37、37、42、42、43、43、43、50、1、 47、 3、 6、 15、 15、 29、 22、 30、 49、 49、 41、 41、 28、 20、 20、 44、 4、 4、 4、 4、 20, 總共有33個點，送貨員運送的總重量為44.55公斤，總體積為0.8004立方米，不計重復(fù)只 有20個站點，將前12個站點作為一部分，后8個站點作為一部分，利用窮舉法得到其最 佳路徑為：25->

27、;29->22->30->33->28->20-> 15->4->3-> 1 ->6->47->37->41 >44->50->49->42->43, 總時間為219.5分。除去此31個點外，由計算可得，剩余的點中距離o點最近的點為38號點，以此點為 起始點的一組分塊數(shù)據(jù)為：38、38、38、9、11、11、12、12、13、13、14、14、16、 16、 19、 19、 32、 32、 32、 32、 32、 32、 35、 40、 40、 45、 45、 45、 45、 45、 8

28、、 10、 10、7、7、15,總共冇35個點，送貨員運送的總重量為48.73公斤，總體積為0.9839立方 米，不計重復(fù)只有15個站點，將前10個站點作為一部分，后5個站點作為一部分，利用 窮舉法得到其最佳路徑為：19-> 13-> 11 -> 12->8->7-> 10->9-> 14-> 16->32->35->38->45->40,總時間為：125.35剩余點中，由計算可得2號點距離o點最近，依此點作為起始點的一組分塊數(shù)據(jù)為： 2、5、48、46、46、46,共6個站點，送貨員運送的總重量為8.95公斤

29、，總體積為0.2597 立方米，不計重復(fù)只有4個站點，利用窮舉法得到其最佳路徑為：2->5->48->46,總時間為:125.55 分。綜合此四塊的數(shù)據(jù)可知其總時間為：551.52分。綜上所述：有計算結(jié)果可知：應(yīng)用方案一所得總的送貨時間為：394.3分；應(yīng)用方案 二所得總的送貨時間為551.52分，方案一優(yōu)于方案二，因此，在考慮載重量及載重體積 情況卜：完成100件送貨任務(wù)的最優(yōu)路徑為：第一趟0-> 18->13->11->12-> 15->25->29->22->20->22->30->28->3

30、3->28->30->22-> 15->5->2->4 >3->8-> 1 ->6-> 1 ->7-> 10->9-> 14->18->0第二趟：0->26->31 -> 19->24->31 ->34->40->47->40->37->41 ->46->48->44->50->45->36->27->39-> 27->31->26->0第三趟：0-&

31、gt;21 -> 17->23-> 16->23->32->35->38->43->42->49->42->43->38->36->21 ->0 第四趟：0->26->26->26->0總時間為:394.3分。貝i垸成100件送貨任務(wù)的路線圖如下：1600014000120003210000n.40002000800012030eoco-*85圖4各分段路線圖第一趟0-> 18->13->11->12-> 15->25->29->

32、;22->20->22->30->28->33->28->30->22-> 15->5->2->4 >3->8-> 1 ->6-> 1 ->7-> 10->9-> 14-> 18->0笫二趟：0->26->31 -> 19->24->31 ->34->40->47->40->37->41 >46->48->44->50->45->36->27->

33、39-> 27->31->26->0 第三趟：0->21 -> 17->23-> 16->23->32->35->38->43->42->49->42->43->38->36->21 ->0 第四趟：0->26->26->26->0總時間為：394.3分。五、模型的評價5.1模型的優(yōu)缺點5.1.1模型的優(yōu)點問題一建立的單旅行商的模型，是被認(rèn)為解決這類型的通用算法。本模型將最快完 成任務(wù)，轉(zhuǎn)化為尋找最短路徑，借助lingo軟件得到最小hamilto

34、n圈，進而得到問題的 最優(yōu)解，這種方法有嚴(yán)格的理論基礎(chǔ)，并且更具普遍性。問題二在問題一的求解基礎(chǔ)上，添加了時間限制，要尋找到一條路線使得送貨員在 規(guī)定的時間內(nèi)，完成任務(wù)。我們根據(jù)題口所給定的運貨吋間將前30件貨物的運達地點分 為四塊，使得數(shù)據(jù)量減小，因此可以利用窮舉法將每一時間段的運送路徑精確地表示出 來，再根據(jù)每一吋間段首尾銜接的站點可以得到最終的最佳路徑。根據(jù)問題三己知的送貨員最人運載量及最人運載體積的限制條件，至少要將所有的 貨物分為三組，往返三次送達最終地點。根據(jù)分組方案的不同得到不同的結(jié)果。本題我 們分兩種方案，即最遠點優(yōu)先法和最近點優(yōu)先法進行計算，并通過比較得到結(jié)果，這樣 可使結(jié)果

35、更具說服力。5.1.2模型的缺點1.對于與詼tsp問題雖然我們用計算機模擬技術(shù)，得到了近似優(yōu)解，但跟實際存在 的最優(yōu)解直接仍然有一定差距。2對于求解問題中，對于一些問題我們基于一些假設(shè)，但是還是缺少證明，同時還 應(yīng)該加入-些數(shù)據(jù)修整的優(yōu)化方法。六、參考文獻【1】richard johnsonbaugh, marcus schaefer著,大學(xué)算法教程m,清華大學(xué)出版社 【2】黃厚生，求解tsp問題的新方法j,天津大學(xué)碩士學(xué)位論文3 譚永基.數(shù)學(xué)模型.上海：復(fù)旦大學(xué)出版社，20054 姜啟源，數(shù)學(xué)模型，北京：高等教育出版社，2004七、附錄附錄一:序號位置點1位置點2距離(m)序號位置點1位置點

36、2距離(in)1131916.284325191966.212182863.784425291885.9032207823.324527311067.754242292.644628331325.695381958.094729221097.866343536.414830281017.897422292.644930414997.6285155004.545031261537.039521252.945131342324.7510611294.315232351114.00117185917.945332231311.8712711968.255433463758.51138121756.7

37、75533281325.69149142681.355634401630.78159101945.515735381409.731610185909.555836453182.46171072059.375936272203.921811121417.686037402090.051912131456.796138361537.422012255756.576239271779.922112154805.806340341630.782213183113.466440453217.012313193455.706541442366.032413111669.566641372601.92251

38、4185342.186741462735.422614162607.68684243917.672714172195.726942491917.382814213296.737043382618.442915222860.987144482152.543015254235.407244504987.103116232097.647345503102.763217231774.517445422351.723318311780167546481494133419242258.647647402331.223520221498.937748442152.543621262191.747849503

39、568.823721362880.187949421917.383821171823.918050403043.493922301287.49810182182.034023171774.51820211796.944124311780.1683o261392.064225414154.59附錄二：求兩點間距離的源程序#include "stdio.h"#include "math.h"void main()int xl,x2,yl,y2,i;double d,m,n;for(i=0;i< 100;i+)printft輸入第一組坐標(biāo)，屮間用空格門；

40、 scanf(,%d%d,&xl,&yl);printfc*輸入第二組坐標(biāo),中間用空格:”); scanf(”d%d”,&x2,&y2); m=pow(x2-xl,2); n=pow(y2-yl,2); d=sqrt(m+n);printfc'%.2fan,d);附錄三：找出包括o點在內(nèi)的22個點之間任意兩點之間的最短距離的matlab源代碼如下: clear;clc;lianjie=l 31 82 20243834425 15526 17 187 18 129 149 1010 1810 711 1212 1312 2512 1513 1813 191

41、3 1114 1814 1614 17142115 2215 2516 2317 23183119 2420 2221 2621 3621 1722 3023 1724 3125 4125 1925 2927 3128 3329 2230 2830 4131 2631 3432 3532 2333 4633 2834 4035 3836 4536 2737 4038 3639 2740 3440 4541 4441 3741 4642 4342 4943 3844 4844 5045 5045 4246 4847 4048 4449 5049 4250 4051 1851 2151 26;zu

42、obiao=|9185 5001445 5607270 5703735 6702620 99510080 143510025 22807160 252513845 268011935 30507850 35456585 41857630 520013405 53252125 597515365 704514165 73858825 80755855 8165780 835512770 85602200 883514765 90557790 93304435 952510860 963510385 10500565 97652580 98651565 99559395 1010014835 10

43、3651250 109007280 1106515305 1137512390 114156410 1151013915 116109510 120508345 123004930 1365013265 1414514180 142153030 1506010915 142352330 145007735 14550885 1488011575 151608010 1532511000 8250;d,d22=juli(zuobiao,lianjie);其中的d,d22=juli(zuobiao,lianjie)函數(shù) matlab 源代碼如下：%計算任意兩點間的最短距離與達到最短距離的路徑表示%

44、zuobiao為已知各頂點的坐標(biāo)，lianjie表示圖中相鄰兩點間有連接的點的序號 %d表示任意兩點間最短路徑%d1表示第一問小30件貨物所要到達的指定地點之間的任意兩點之間的最短距離function d d1 =juli(zuobiao,lianjie)%計算任意相鄰的兩點間的距離a,b=size(zuobiao);for i=l:afor j=i :ajuli(i,j)=sqrt(zuobiao(i, 1 )-zuobiao(j, 1 )a2+(zuobiao(i,2)-zuobiao(j,2)a2);endend%計算在lianjie情況下，所應(yīng)該知道的口j到達點的距離c,d=size(

45、iianjie);e=zeros(a);for i=l:ce(lianjie(i, 1 ),lianjie(i,2)= 1;e(lianjie(i,2),lianjie(i, 1 )= 1;endf,g=find(e-=l);h=length(f)；for i=l:h j=l;juli(f(i),g(j)=inf;endp,o=size(juli);for i=l:pjuli(i,i)=0;end%運用floyd算法計算任意兩點間的最短距離a=juli;n=size(a,l);d=a;path=zeros(n,n);for i=l:nfor j=l:nif d(i,j)=infpath(i,j

46、)=j;endendendfor k=l:nfor i=l:nfor j=l:nifd(i,k)+d(k,j)vd(i,j)d(i,j)=d(i,k)+d(k,j);path(i,j)=path(i,k);endendendendx=13 18 31 26 21 14 17 23 32 38 45 43 39 42 36 27 24 34 40 49 1651;y=sort(x);dl=d(y,y);利用所求得的任意兩點間的最短距離，利用lingo求解最短的hamilton圈的源代碼如2model:sets:city/1.22/:u;link (city,city):dist,x;endset

47、sdata:dist=0 8455.6 11063 8916.3 3113.5 7092.4 10691 5714.3 6687.5 6284.95217.2 12003 7541.9 8488.8 10026 8064.8 9172.7 13562 1264511671 15534 5295.58455.6 0 2607.7 2195.7 5342.2 3296.7 3970.2 8805.6 5488.5 8093.37025.5 5282.1 9350.2 6176.9 7714.3 9873.2 10981 11250 103339359.4 13222 5093.711063 260

48、7.7 0 3872.2 7949.9 5696.1 2097.6 11205 7887.8 9674.69424.8 3409.5 11750 7470.7 5933.2 11454 13380 9469.4 8551.710653 11441 74938916.3 2195.7 3872.2 0 5802.9 1823.9 1774.5 7332.8 4015.7 6620.45552.7 3086.4 7877.4 4704.1 5610.1 8400.4 9508.2 9146.2 8228.67886.5 11118 3620.93113.5 5342.2 7949.9 5802.9

49、 0 3979 7577.4 3883.8 3574.1 3171.42103.7 8889.3 4428.4 5375.4 6912.8 4951.4 6059.2 10449 9531.28557.8 12420 21827092.4 3296.7 5696.1 1823.9 3979 0 3598.4 5508.9 2191.7 4796.53728.8 4910.3 6053.5 2880.2 4417.6 6576.4 7684.3 7953.7 70366062.6 9925.1 1796.910691 3970.2 2097.6 1774.5 7577.4 3598.4 0 91

50、07.3 5790.2 7576.97327.2 1311.9 9651.9 5373 3835.6 9356.9 11283 7371.7 64548555.5 9343.1 5395.45714.3 8805.6 11205 7332.8 3883.8 5508.9 9107.3 0 3317.2 2847.91780.1 9113 4104.9 5051.8 6589.2 4627.8 5735.7 10125 9207.78234.3 12097 4709.26687.5 5488.5 7887.8 4015.7 3574.1 2191.7 5790.2 3317.2 0 2604.8

51、1537 7102 3861.8 4808.7 6346.1 4384.7 5492.6 9882.2 8964.67991.2 11854 1392.16284.9 8093.3 9674.6 6620.4 3171.4 4796.5 7576.9 2847.9 2604.8 01067.8 6265.1 3392.5 2203.9 3741.3 1779.9 5023.3 7277.5 6359.85386.4 9248.8 3996.85217.2 7025.5 9424.8 5552.7 2103.7 3728.8 7327.2 1780.1 1537 1067.80 7332.8 2324.7 3271.7 4809.1 2847.7 3955.5 8345.2 7427.5 6454.110317 2929.112003 5282.1 3409.5 3086.4 8889.3 4910.3 1311.9 9113 7102 6265.17332.8 0 9657.6 4061.1 2523.7 8045 10461 6059.8 5142.2 7243.68031.2 6707.27541.9 9350.2 11750 7877.4 442