1、校車問題的分析報告摘要本文是解決如何有效的安排校車讓教師和工作人員盡量滿意的問題。根據老校區教師和工作人員所在區的分布以及各區的人數，針對如何設置乘車點使得各區距離乘車點最近，教師和工作人員最滿意，以及如何有效安排車輛等問題進行了深入分析，利用改進的Floyd 算法， 綜合評價方法建立了最短乘車距離模型 、 滿意度評價模型對問題做出了詳細合理的解答。針對問題一，考慮到需要求得每個區到達乘車點的最小距離，我們建立了最短乘車距離模型并通過改進后的Floyd 算法（見附件2）實現。首先運用Floyd算法思想得到各頂點之間的最短通路值，并得到最小距離矩陣，然后運用for 循環語句在各區中隨機抽取n 個

2、區作為乘車點并在最小距離矩陣中取出對應的數據即乘車點到達任意一個區的最小距離向量。將這n 個向量按位求最小值生成一個新向量A,對A向量各元素求和得到一個數 So最后將每次循環得到的 S 比較，最小值（So）即為問題一的解。最后得出：n=2時應該在第18區和31 區設立乘車點，其最短總距離為24492 米。 n=3 時應該在第15 區、 21 區和 31區建立乘車點，最短距離為19660 米。針對問題二，考慮到教師和工作人員的滿意度受到距離與人數兩個因素的影響， 即滿意度隨著距離的增加而減小，而人數的多少會放大或減小距離對滿意度的影響程度，從而建立了滿意度評價模型。由于影響滿意度的因素（人數、

3、距離）存在不同的單位所以我們分別對人數和距離做了無量綱化處理（見公式1、 2）并得到了滿意度評價函數（見公式3） 。最后在模型一的基礎上，結合滿意度評價函數建立了問題二的求解算法（見附件3） 。依據模型可知當求得的數值越小表示不滿意度越小即滿意度越高，最終求解得到了：n=2 時最優解為16 區和36 區不滿意度為0.4980 。 當 n=3 時最優解為15 區、 22 區和 32 區不滿意度為0.3720 。針對問題三，由于要求使用盡可能少的車輛讓教師和工作人員的滿意度盡量高， 所以我們把車輛數作為一個限制滿意度的條件。通過在問題二的基礎上把車輛數考慮進去得到了問題三的求解公式和算法（見附4）

4、 。 最終求解得到：當 n=3時最優解為至少需要54 輛車對應的區域分別為15、 22、 32。對應的車輛數為20 、 16 、 18 。針對問題四，我們通過對前三個問題的深入分析對校車安排問題提出了合理化的建議和措施。關鍵詞：最短乘車距離模型滿意度評價模型Floyd 算法一、問題重述如今越來越多的學校需要經常將老校區的教師和工作人員用校車送到新校區，如何實現以最少的車輛讓教師和工作人員盡量滿意是個十分重要的問題。現已知老校區的教師和工作人員分布在50 個區，以及各區的距離與各區人員分布情況。需要對以下問題進行研究：（ 1 ） 建立 n 個乘車點，要求使各區人員到最近乘車點的距離最小，該將校車

5、乘車點應建立在哪n 個點。 建立一般模型，并給出 n 2,3時的結果。（ 2） 若考慮每個區的乘車人數，為使教師和工作人員滿意度最大，該將校車乘車點應建立在哪n 個點。 建立一般模型，并給出 n 2,3時的結果。（ 3） 若建立 3 個乘車點，為使教師和工作人員盡量滿意，至少需要安排多少輛車？給出每個乘車點的位置和車輛數。設每輛車最多載客 47 人。（ 4） 關于校車安排問題，你還有什么好的建議和考慮。可以提高乘車人員的滿意度，又可節省運行成本。二、基本假設1 .假設乘客的滿意度只與小區到車站之間的距離以及車站乘車人數有關；2 .在問題一、二中，假設每位教師及工作人員只會到最近的車站乘車；3

6、.在問題一、二中，假設每位乘客到達車站后，都有校車乘坐；三、符號說明1. V1 , V2,Vk,Vn表小各個區；2. Ai, A2,八匕八門表示第k個區到其他區的最短距離的矩陣;3.S表示任意一種隨機取得的車站方式所得到的最短距離；4.So表示所有可能存在的組合方式構成車站的最短距離；-可編輯修改-5.Y滿意度評價函數四、模型的建立與求解4.1 最短乘車距離模型：4.1.1 問題分析：要求得使每個小區與車站距離最小， 可以用以下幾步來實現：(1)隨機選擇 n個小區作為車站 V1, V2, - Vk, - Vn ; (2)求得這n個車站到任意一個小區 的最小距離，并得到n個50階的行矩陣A1,

7、A2, - Ak/ An； (3)按位比較這n 個行向量，得到最終每個小區到達最近車站的最短距離A; (4)將A中每個元素加起來，得到S,即為最短距離。(5)將所有隨機可能性得出所有最終最短距 離,進行比較，得到它們中的最小值 So,即為結果。如圖1:隨機取得n個小 區作為車站V, VVk,Vn求得n個最小距 離行向量AA, A,An按位比較n個行 向量，得到最終 最小距離行向量將最小距離行向量 A各項相加，得到此 隨機車站的最小總 距離S將各種隨機情況得到 的最小總距離S比較, 得到最小總距離So,即 為結果圖1:最小距離模型建立的示意圖4.1.2 隨機選取n個小區作為乘車站點:我們運用n個

8、for循環語句對隨機選取n個小區作為乘車站點的所有情況進 行一次歷遍，以n=3為例，具體實現如算法1:fo門=1:48for j=2:49for k=3:50算法1算法1是用循環的方法，將i, j, k分別從1取到48 , 2取到49 , 3取到 50,這樣就能得到從50個小區中隨機選取三個作為乘車站點的所有可能，所選 取的站點即為：Vi, Vj, Vko4.1.3 求得這n乘車站點到各個小區的最短距離：1 .首先應得到由各個小區之間的距離組成的鄰接矩陣（見附件1）;2 .其次考慮到要計算任意兩點之間的最短距離，我們采用了 Floyd算法進行求算；Floyd算法的基本思想是：遞推產生一個矩陣序

9、列其中 4«.力表示從頂點匕到頂點刀的路徑上所經過的頂點序號不大于上的最短路徑長 度V r計算時用迭代公式；，4&J）= min（繪04/弦）+ 4T 化 J）.k是迭代次數,=1之,融. ¥最后，當七=。時，凡即是各頂點之間的最短通路值. J示例：Floyd算法的基本步驟如圖2所示問題，要求的任意兩點之間的又t短距離建立相鄰矩陣，見表 1 , 則從上面的表1開始，對于每兩個頂點u、v,在表1中存儲著一條路徑uv。 現在我們考察，試著把a加到u、v的路徑上能否，得到一條更短的路徑，即如 果u - a+a -v<u - v的話，能夠找到一條更短的路徑。圖2本來路

10、徑上源點或終點就有a的不必考慮。對角線上的也不必考慮，并 且Dba+Dac=6+11>Dbc=2,所以如果從 a繞，反而遠，又因為Dca+Dab=3+4<Dcb= 工,所以如果從a繞，更近，因此，由表 1 變成表2。從上面的表2開始，對于每兩個頂點u、v,在表2中存儲著一條路徑uv。 現在我們考察，試著把b加到u、v的路徑上能否，得到一條更短的路徑，即如 果u - b+b - v<uv的話，能夠找到一條更短的路徑。同樣地，本來路徑上源 點或終點就有b 的不必考慮。對角線上的也不必考慮， Dab+Dbc=6<Dac, 所以 如果從 b 繞， 更近，Dcb+Dba=7+6&

11、gt;Dca=3,所以如果從b繞，反而遠，因此表2中的數據應該變為表3。從上面的表2開始，對于每兩個頂點u、v,在表2中存儲。o著一條路徑u - Vo現在我們考察，試著把c加到u、v的路徑上能否，得到 一條更短的路徑，即如果 uc+cv<uV的話，能夠找到一條更短的路徑。 同樣地，本來路徑上源點或終點就有c的不必考慮。對角線上的也不必考慮，Dac+Dcb=6+7>Dab=4,所以如果從 c 繞，反而遠，Dbc+Dca=2+3<Dba=6,所以如果從c繞，更近，因此表 3應該變成表4中的數據。現在，已經把所有的頂點都試了一遍，算法結束。每兩個頂點之間的路徑如 表4所小。表1ab

12、ca,0411b602c3oo0-可編輯修改-abca0411B602c370a046b602c370表4abca046b502c370假設圖G權的鄰接矩陣為4,3來存放各邊長度,其中；，% = 01 =12,，門；a% = s Lj之間沒有邊，在程序中以各邊都不可能達到的充分大的數代高 % 二 % 卻4是LJ之間邊的長度，Lj = d 、在 對于無向圖，4是對稱矩陣，a. = a.QAo即為我們要得到的任意兩點之間的最小距離的矩陣，見算法 2:b=a+a'path=zeros(length(b);for k=1:50fo門=1:50for j=1:50if b(i,j)>b(i

13、,k)+b(k,j) b(i,j)=b(i,k)+b(k,j);path(i,j尸k;endendendendb,path算法2算法2即為Floyd算法的核心程序3 .得到n個乘車站點到各個小區的最短距離的行矩陣：在2中得到的b矩陣中提取出這n個小區對應的行的行向量，例如，選取 第一個小區作為乘車站點，則將 b矩陣中的第一行取出，作為行向量 Ai,其他的依此類推即可，由此可以得到各個乘車站點最短距離的行矩陣Ai, A2,Ak,An 。4.1.4 求得各個小區到這n 個乘車站點的最短距離S：因為得到的行矩陣Ai, A2,Ak,An的階數是相同的，因此，我們按位求最小值，得出另一個行矩陣 A,將A

14、中各個元素相加就可以得到各小區到達這n個乘車站點的最小距離S,算法見算法3:for a=i:50t=b(i,a) b(j,a) b(k,a);d(a,i)=min(t);end;f(u,i)=sum(d);f(u,2)=i;f(u,3)=j;f(u,4)=k; u=u+i;算法 34.1.5 得出最終結果S0：遍歷所有可能情況后，通過比較每種情況得出的S,得出其最小值，得到的So即為最小距離，取得最小距離時隨機選取的i， j， k 即為乘車站點的設置地點。具體的程序實現見程序i 。4.1.6 求解結果：n=2 時應該在第i8 區和 3i 區設立乘車點，其最短總距離為24492 米。n=3 時應

15、該在第i5 區、 2i 區和 3i 區建立乘車站，最短距離為i9660 米。4.2 滿意度評價模型：-可編輯修改-4.2.1問題分析:對距離以及人數兩個 指標進行無量綱化處 理，得到兩個指標的量 化數據。將已經無量綱化后的 指標參數相乘得到定 義的不滿意度指標。-可編輯修改-將得到后的綜合指標當 作第一問中的距離指 標，建立滿意度評價函 數，求解第二問中的變 化后的距離的最小值。如圖3,對于滿意度模型：我們對人數以及距離兩個指標進行無量綱化處 理，使其量化；對兩組無量綱化后的數據相乘，得到滿意度評價函數，即相乘 的結果越小，其滿意度越大，我們將其定義為不滿意度；再對所有小區進行歷 遍，選取n個

16、小區作為乘車站點，對其不滿意度進行比較；最后得出最小的 不滿意度即為本問的解4.2.2對指標進行無量綱化：1 .對人數進行無量綱化：我們采用每個小區人數除以總人數的方法來實現其無量綱化， Qj=Pj/P0 （公式 1）得到表5 :表5區域人數區域人數10.0259792260.006394920.0267786270.037569930.0167866280.007194240.0135891290.011590750.0151878300.02997660.0115907310.003996870.0067946320.034372580.0255795330.027977690.01558

17、75340.0223821100.0079936350.0259792110.0243805360.0103917120.018785370.0319744130.0263789380.0359712140.0083933390.018785150.0279776400.0159872160.0339728410.0227818170.0047962420.0159872180.0139888430.0275779190.0191847440.0267786200.0215827450.0079936210.0195843460.0071942220.0047962470.0271783230

18、.0215827480.028777240.0183853490.0303757250.0303757500.0247802表5表示出每個小區人數所占總人數的比例，反映出每個小區人數對于 不滿意度的權重值Qj(j=050)。2 .對距離進行極值差方法處理：對附錄中的數值進行極值差方法處理，得到無量綱的量化結果，Bij - ( Bi ) minBj，= (BiBi) min (公式其中：Bij表示B矩陣中的第i行第j列的元素(81) min=minB ij(1 < i <50), (Bi) max =maxB ij(1 < i <50)3 .得出滿意度評價函數：Y=(Bi

19、j- (Bi) min)/( (Bi) max- (Bi) min)*(Pj/Po)(公式 3)4.2.3求解結果:n=2時最優解為16區和36區不滿意度為0.4980。當n=3時最優解為15 區、22區和32區不滿意度為0.3720。4.3問題三：4.3.1問題分析:通過總人數與校車的 載人數算出最少需要 的車輛數為54輛盡量少的車輛數作為 一個限制滿意度的條 件建立求解函數結合問題一的算法求 出最終結果圖3如圖3:由于要求使用盡可能少的車輛讓教師和工作人員的滿意度盡量高， 所以我們把車輛數作為一個限制滿意度的條件。通過在問題二的基礎上把車輛數考慮進去運用問題一的算法即可求得答案。4.3.2

20、問題求解：當n=3時最優解為至少需要54輛車對應的區域分別為15、22、32。對應 的車輛數為20、16、18。不滿意度為0.37204.4 問題的合理化建議與考慮：1. 可于上下班高峰期增開幾次校車，在不是高峰期，減少幾次校車運 行；2. 可以運行不同型號的校車，在乘車人數較多的車站運行大校車，人 數較少的車站運行較小的校車。3. 可以增加幾個收費的乘車站點，因為增加站點會提高滿意度，但同 時會增加運行成本，因此進行收費來降低成本。4. 可以將乘車站點不設定在小區內，設定在幾個小區比較靠中央的位 置，在相同情況下回事滿意度提高。5. 有一些應該使乘車站盡量靠近老年人數較多的小區，這樣滿意度提

21、 高。五、模型的評價首先，在解決問題一的時候，我們建立了最小距離模型后，直接用Floyd算法進行運算，得到了每一個小區到其他各個小區的最小距離的矩陣，然后隨機抽取 n 個小區作為車站，對最小距離矩陣的這n 行進行求和，比較求和值得到最終結論。當 n 比較小時，用這種方法可以較好的計算出所求的n 個點。 但是，這種方法的運算量與n 的大小是成指數關系的，所以，當n 很大時運算量會迅速增大。在解決問題二的時候，我們在問題一的基礎上用小區和最近車站的距離和小區人數無量綱化后的乘積來表示教師和工作人員的滿意程度，之后用和問題一相同的思路得出結論。所以，第二問中也存在著第一問中，當n 很大的時候運算量過

22、大的問題。而此無量綱化的過程中我們考慮了任意兩個小區最短距離的極大值和極小值，發現極小值都是0，極大值之間相差不大，因此可以使用極值無量綱化的方法。但是極值無量綱化是通過利用變量取值的最大值和最小值將原始數據轉換為介于某一特定范圍的數據，從而消除量綱和數量級影響，改變變量在分析中的權重來解決不同度量的問題，所以此權重沒有對距離和人數進行差異化對待，而事實上人數和距離的權重肯定是不同的。解決第三個問題時，我們用到了逼近理想值排序法，假設理想的情況是共用53輛車（因為總人數為2502 ,至少需要54輛車才可以），且教師和工作人員 的滿意度最大。我們延用解決問題二的方法，只是在距離與人數無量綱化后再

23、乘以因式（A53）,然后對所有的情況進行排序，找到最接近理想值D的一組數據。六、參考文獻1鄭洲順 科學計算與數學建模 復旦大學出版社。2姜啟源 謝金星 葉俊 數學模型 高等教育出版社。3孫祥 徐流美 吳濤Matlab7.0基礎教程 清華大學出版社。附件1 :50個區之間任意兩點的最短通路值CoZLufrii£- L thuUE工 W-可編輯修改-IQ5；o1N- 04 4X IL - - L«DDODD 3 G巾EE d c 7.5410127S2W1505164DJ 640161613.W10461015WMH180Q1MD師1917159S5Die?sH1Q間后195D

24、:娥M旦口藥15寸J20QH3033LO15即15001?3D650BbO12201期4加1650148516ZD11：10543414小44幼ti品MO4IK230潮M53弧5101&QDO3L0410儂g!D8U電/U11?D刑DITO1"D025DEQ1QD13Q5M334633： JE54】KE543FD?ED自£口430的口同。3BDE20心口Z80把白E7094 DE加11BD1 .1.U.J ：DJ 22010DIN 口9IDiCbO?CDMOJ24D13B0母口1280劃口110J515IS如152014bU3S3O也出iflro15bUJID“如1

25、J9D磔口12M1H41224JBMIJllI21L12而LLIO如口LC6S1530!30舊的L?20劃W年l?B019(SSB187D12702C3515EQ1沏t»2D1630i«o21PE1QWuro2S3512。1)40?105l?D011002065ianzq 口?由ll?0北口LT*1茸口550L和01C.PQ沔Q1540UDD3QQL圾Q1" 口?9O例口50nu甌IMO門口S6LHID11DLTE匚L&00GCcluETiE 11 thraiJih. 20ITB-S1QM21CHUM50iLT&lL IL】站口LUbLtlU由Xb

26、Lson1U4UL對，匚9F01010L2LD*uM0i4-S30J70A70330470CTOI5D2904 MD340M：1000SOL則c'lMJii13。ro17Q-310450痢。即G30鴕Q560roo卻Qeiu網?5Q日id1.ES4舊1 口制I.M4133412741.4 7Q113415?4ITMQ2DienI. KOI?BO33D1L207M93。1L303204和麗dBO600300£5090/0gtu3DBU1220131Q34BU1270113DD23QLD30104UOlilJ利加8&n機U6 口 iM。EM4001160114094012

27、B01240104013401300UOOid號14351235】4鈍tsaoi14 7D3 4 JUIS30'16LU1B.BOLJ70)440bwu14001520IbSU”粕T6MRM174017041MQ1颯ISMSD34Lfl14gHH13皿L134簽p;1004前口饒口l另0小2別IbMLM皿12MIDOD迪口12-I0JUKri134(1L?)009DINri!泓9NiColuaric 21 rhiouEh JCD D g JDI 4Q 5 5 5 o o- £5 1 ? ,tf oJ-X-o o_o 9Mo 75gfl5D塞明例7M?90我口隨4期a670a?

28、D4D05S0?&0喈0現04Mt»Q24Q90 0HOD6301BIO詢?JQ而口甌4?Q行口1090129DafDEM11 so530r；70麗S1Q解口115QM5E)1C?0伽間350d恤制85Q碗口1 口q 口】M口rn即11?0Rfinin 口 inRTfi而口HE910UD后5口陽口IDLOE£ 口烏口口Tin4E 口snn)200wud3卻M IDl?®0in2nI16D9用1T2077QJ四口M4 口run&o1331D班I2LQin網sjaBioJ3ID；“日1DE0I 9fl1 HDID8Qapn6306801070USD后9

29、B0! 1 W1050C40SI31G201210J29DHUH201290IE鐘nsorjo600600?ED卷(J俄。B301120S807M網13Q江qmD5DQ740MQ1200l(i6Q370胤q2ia耽1£D730i3501D001*901150g如MQ47Q5? D2?D7l0iMOHLiO11001200loroS5Q42Cratid£DS5011301300ISOM501260L09Q60in 口行口C4Q?do5L01500lOfiO870隨093口如口1 sD，印魴口1D2U13101170自刈圈口K1U陽口3&D3卬1DB0i.2aj1510

30、1370lLL磯LU1Ueao9-DSID?909回口35口a4aa30o5 0 0IF1L85o 0口 o o 9 d fiT 7 G 4D513n *o oT 95 111211 J 1 i1cru EE U,ft U能 MS TSO -IM 52fi M。3州 184)1 11 111 11111tsu 16U 史b 劃 535 ATO J50 520 BIO no 2«01111111 i i1iii i1LIO a10 KO 210 3=0 2J0 3：0 12E 1-10 MQ31Q "Q 郵n l?0 Mfl rrn MO Brn 6in 翁口 Lin 3 =

31、 0 MD031-ri Leo 2!=6 4Z5 3口 nu r'4U ELU Ll?U 0：,U 2門 11 11 1112JD on 15D 加口 20 D WE) ISO <31S OJD 3JD 13D 南口 N 口 010 9SD 900 門口 5 口 5口口 之目口 240 iJD 制口 .38 DD 匕口 5 31D ：日口 ign 33D SBO fio 算口 92 口 160u b b 2 F ar 3 o 41 2 Jo -u -u B D rj 13s1A -Asooo帥Looo如oo而5570W隨制即新3n廊就20TQ卻MLOu4D4IDD03szn3nT

32、nuij* 則如Ju IL IL IL 1 1 I 1 LarDQ61D fl fl o & J J .3 6 A3 9 11D4U12?DkGd&口1410neoS?Ddio148014101DEO13IDItlQ口|仙OLDS80：0M14gli13301匹。相打即Q16201 II1汴口wi的口l：Jnfio露口6如雨0泗11曲融口1Ei；nliillucmRh 5uD, 5 qyDJ21 53144 1514 ds57 d-4 dpo2沌-I14ICo _D o D fl- u 0 T g2J'li J D s UL口口口 2 6 34 G 8ny o 0 41

33、- 9口 o o 0 ssllJN o b 2 .4a(7,:)=zeros(1,7),170,M,M,M,M,M,M,M,M,M,160,M,M,M,M,M,M,M,M,M,附件 2：問題一的算法clear;clc;M=10000;a(1,:)=0,400,450,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(2,:)=zeros(1,2),M,300,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,230,M, M,M,M,M,

34、M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,140,M,M, M;a(3,:)=zeros(1,3),600,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(4,:)=zeros(1,4),210,M,M,M,M,M,M,M,M,M,M,M,M,M,310,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(5,:)=zeros(1,5),2

35、30,200,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(6,:)=zeros(1,6),320,340,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(8,:)=zeros(1,8),200,M,M,M,M,M,285,M,M,M,M,M,M,M

36、,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(9,:)=zeros(1,9),180,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(10,:)=zeros(1,10),150,M,M,M,160,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(11,:)=zeros(1,11),140,M,130,M,M,M,M

37、,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(12,:)=zeros(1,12),200,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(13,:)=zeros(1,13),M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,400,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(14,:)=zeros(1,14),190,M,M,M,M,M,M,M,M,M

38、,M,190,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(15,:)=zeros(1,15),170,250,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(16,:)=zeros(1,16),140,130,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(17,:)=zeros(1,17),M,M,M,M,M,M,M,M,M,240,M,M,M,M,M,M,M,M,M

39、,M,M,M,M,M,M,M,M,M,M,M,M,M,M;-可編輯修改-a(18,:)=zeros(1,19),204,M,M,M,M,M,180,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(19,:)=zeros(1,19),140,M,M,M,175,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M;a(20,:)=zeros(1,20),180,M,M,190,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M;a(21

40、,:)=zeros(1,21),300,270,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,350,M,M,M;a(22,:)=zeros(1,22),M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,160,270,M,M,180,M,M;a(23,:)=zeros(1,23),240,M,M,M,M,210,290,M,M,M,M,M,M,M,M,M,M,M,M,M,150,M,M,M,M,M,M;a(24,:)=zeros(1,24),170,M,M,130,M,M,M,M,M,M,M,M,M,M,M,

41、M,M,M,M, M,M,M,M,M,M,M;a(25,:)=zeros(1,25),M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M;a(26,:)=zeros(1,26),140,M,M,M,M,M,M,320,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M;a(27,:)=zeros(1,27),190,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M;a(28,:)=zeros(1,28),260,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,

42、M;-可編輯修改-a(29,:)=zeros(1,29),M,190,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(30,:)=zeros(1,30),240,M,M,M,M,M,M,M,M,M,M,130,210,M,M,M,M,M, M,M;a(31,:)=zeros(1,31),230,M,M,M,260,M,M,M,M,M,M,M,M,M,M,M,M,M,21 0;a(32,:)=zeros(1,32),190,M,140,240,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(33,:)=zeros(1,33),210,M,M,M,M,M

43、,M,M,M,M,M,M,M,M,M,M,M;a(34,:)=zeros(1,34),M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(35,:)=zeros(1,35),M,160,M,M,M,M,M,M,M,M,M,M,M,M,M;a(36,:)=zeros(1,36),M,M,180,190,M,M,M,M,M,M,M,M,M,M;a(37,:)=zeros(1,37),135,M,M,M,M,M,M,M,M,M,M,M,M;a(38,:)=zeros(1,38),130,M,M,M,M,M,M,M,M,M,M,M;a(39,:)=zeros(1,39),M,310,M

44、,M,M,M,M,M,M,M,M;a(40,:)=zeros(1,40),140,M,M,M,M,M,M,M,M,190;a(41,:)=zeros(1,41),M,M,M,M,M,M,M,M,M;a(42,:)=zeros(1,42),M,M,M,M,M,M,M,200;a(43,:)=zeros(1,43),260,210,M,M,M,M,M;a(44,:)=zeros(1,44),M,M,M,M,M,M;a(45,:)=zeros(1,45),240,M,M,M,M;a(46,:)=zeros(1,46),M,280,M,M;a(47,:)=zeros(1,47),M,M,M;-可編輯修

45、改-a(48,:)=zeros(1,48),200,M;a(49,:)=zeros(1,49),M;a(50,:)=zeros(1,50);b=a+a'path=zeros(length(b);for k=1:50for i=1:50for j=1:50if b(i,j)>b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k;endendendendu=1;d=zeros(50,1);f=zeros(19600,4);for i=1:48for j=2:49for k=3:50for a=1:50t=b(i,a) b(j,a) b(k,a

46、);d(a,1)=min(t);end;f(u,1)=sum(d);f(u,2)=i;f(u,3)=j;f(u,4)=k;u=u+1;endendend;x,m=min(f(:,1);e=f(m,:);e-可編輯修改-附件 3：問題二的算法clear;M=10000;w=65;67;42;34;38;29;17;64;39;20;61;47;66;21;70;85;12;35;48;54;49;12;54;46;76;16;94;18;29;75;10;86;70;56;65;26;80;90;47;40;57;40;69;67;20;18;68;72;76;62*(1/2502);a(1,:

47、)=0,400,450,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(2,:)=zeros(1,2),M,300,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,230,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,140,M,M,M; a(3,:)=zeros(1,3),600,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,

48、M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(4,:)=zeros(1,4),210,M,M,M,M,M,M,M,M,M,M,M,M,M,310,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(5,:)=zeros(1,5),230,200,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(6,:)=zeros(1,6),320,340,M,M,

49、M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(7,:)=zeros(1,7),170,M,M,M,M,M,M,M,M,M,160,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(8,:)=zeros(1,8),200,M,M,M,M,M,285,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(9

50、,:)=zeros(1,9),180,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(10,:)=zeros(1,10),150,M,M,M,160,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(11,:)=zeros(1,11),140,M,130,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(12,:)=zeros(1,12),200,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M, M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(13,:)=zeros(1,13),M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,4 00,M,M,M,M,M,M,M,M