數(shù)學建模校車安排問題

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

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

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

4、分別為15、22、32。對應的車輛數(shù)為20、16、18。針對問題四，我們通過對前三個問題的深入分析對校車安排問題提出了合理化的建議和措施。關鍵詞：最短乘車距離模型 滿意度評價模型 Floyd算法一、問題重述如今越來越多的學校需要經(jīng)常將老校區(qū)的教師和工作人員用校車送到新校區(qū)，如何實現(xiàn)以最少的車輛讓教師和工作人員盡量滿意是個十分重要的問題?，F(xiàn)已知老校區(qū)的教師和工作人員分布在50個區(qū)，以及各區(qū)的距離與各區(qū)人員分布情況。需要對以下問題進行研究：（1） 建立個乘車點，要求使各區(qū)人員到最近乘車點的距離最小，該將校車乘車點應建立在哪個點。建立一般模型，并給出時的結(jié)果。（2） 若考慮每個區(qū)的乘車人數(shù)，為使教師

5、和工作人員滿意度最大，該將校車乘車點應建立在哪個點。建立一般模型，并給出時的結(jié)果。（3） 若建立3個乘車點，為使教師和工作人員盡量滿意，至少需要安排多少輛車？給出每個乘車點的位置和車輛數(shù)。設每輛車最多載客47人。（4） 關于校車安排問題，你還有什么好的建議和考慮?？梢蕴岣叱塑嚾藛T的滿意度，又可節(jié)省運行成本。二、基本假設1.假設乘客的滿意度只與小區(qū)到車站之間的距離以及車站乘車人數(shù)有關；2.在問題一、二中，假設每位教師及工作人員只會到最近的車站乘車；3.在問題一、二中，假設每位乘客到達車站后，都有校車乘坐；三、符號說明1. V1，V2，Vk，Vn表示各個區(qū)；2. A1，A2，Ak,An表示第k個區(qū)

6、到其他區(qū)的最短距離的矩陣；3.S表示任意一種隨機取得的車站方式所得到的最短距離；4.S0表示所有可能存在的組合方式構(gòu)成車站的最短距離；5.Y 滿意度評價函數(shù)。四、模型的建立與求解4.1 最短乘車距離模型：4.1.1 問題分析：要求得使每個小區(qū)與車站距離最小，可以用以下幾步來實現(xiàn)：（1）隨機選擇n個小區(qū)作為車站V1，V2，Vk，Vn ；（2）求得這n個車站到任意一個小區(qū)的最小距離，并得到n個50階的行矩陣A1，A2，Ak,An；（3）按位比較這n個行向量，得到最終每個小區(qū)到達最近車站的最短距離A；（4）將A中每個元素加起來，得到S，即為最短距離。（5）將所有隨機可能性得出所有最終最短距離，進行比

7、較，得到它們中的最小值S0，即為結(jié)果。如圖1：隨機取得n個小區(qū)作為車站V1，V2，Vk，Vn 求得n個最小距離行向量 A1，A2，Ak,An按位比較n個行向量，得到最終最小距離行向量A 將最小距離行向量A各項相加，得到此隨機車站的最小總距離S將各種隨機情況得到的最小總距離S比較，得到最小總距離S0，即為結(jié)果圖1：最小距離模型建立的示意圖4.1.2隨機選取n個小區(qū)作為乘車站點： 我們運用n個for循環(huán)語句對隨機選取n個小區(qū)作為乘車站點的所有情況進行一次歷遍，以n=3為例，具體實現(xiàn)如算法1： for i=1:48 for j=2:49 for k=3:50 算法1算法1 是用循環(huán)的方法，將i，j，

8、k分別從1取到48，2取到49，3取到50，這樣就能得到從50個小區(qū)中隨機選取三個作為乘車站點的所有可能，所選取的站點即為：Vi，Vj，Vk。4.1.3求得這n乘車站點到各個小區(qū)的最短距離：1.首先應得到由各個小區(qū)之間的距離組成的鄰接矩陣（見附件1）；2.其次考慮到要計算任意兩點之間的最短距離，我們采用了Floyd算法進行求算；示例：Floyd算法的基本步驟2如圖2所示問題，要求的任意兩點之間的對短距離建立相鄰矩陣，見表1，則從上面的表1開始，對于每兩個頂點u、v，在表1中存儲著一條路徑uv。現(xiàn)在我們考察，試著把a加到u、v的路徑上能否，得到一條更短的路徑，即如果ua+av<uv的話，能

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

10、Dca=3，所以如果從b繞， 反而遠，因此表2中的數(shù)據(jù)應該變?yōu)楸?。 從上面的表2開始，對于每兩個頂點u、v，在表2中存儲。著一條路徑uv?，F(xiàn)在我們考察，試著把c加到u、v的路徑上能否，得到一條更短的路徑，即如果uc+cv<uv的話，能夠找到一條更短的路徑。同樣地，本來路徑上源點或終點就有c的不必考慮。對角線上的也不必考慮，Dac+Dcb=6+7>Dab=4，所以如果從c繞，反而遠，Dbc+Dca=2+3<Dba=6，所以如果從c繞，更近，因此表3應該變成表4中的數(shù)據(jù)?，F(xiàn)在，已經(jīng)把所有的頂點都試了一遍，算法結(jié)束。每兩個頂點之間的路徑如表4所示。 表1abca,0411b602

11、c30表2abca0411B602c370abca046b602c370表3表4abca046b502c370A0即為我們要得到的任意兩點之間的最小距離的矩陣，見算法2：b=a+a'path=zeros(length(b);for k=1:50 for i=1:50 for j=1:50 if b(i,j)>b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k; end end endendb,path算法2算法2即為Floyd算法的核心程序3得到n個乘車站點到各個小區(qū)的最短距離的行矩陣：在2中得到的b矩陣中提取出這n個小區(qū)對應的行的行向

12、量，例如，選取第一個小區(qū)作為乘車站點，則將b矩陣中的第一行取出，作為行向量A1，其他的依此類推即可，由此可以得到各個乘車站點最短距離的行矩陣A1，A2，Ak,An。4.1.4求得各個小區(qū)到這n個乘車站點的最短距離S：因為得到的行矩陣A1，A2，Ak,An的階數(shù)是相同的，因此，我們按位求最小值，得出另一個行矩陣A，將A中各個元素相加就可以得到各小區(qū)到達這n個乘車站點的最小距離S，算法見算法3： for a=1:50 t=b(i,a) b(j,a) b(k,a); d(a,1)=min(t); end; f(u,1)=sum(d); f(u,2)=i; f(u,3)=j; f(u,4)=k; u=

13、u+1;算法34.1.5 得出最終結(jié)果S0：遍歷所有可能情況后，通過比較每種情況得出的S，得出其最小值，得到的S0即為最小距離，取得最小距離時隨機選取的i，j，k即為乘車站點的設置地點。具體的程序?qū)崿F(xiàn)見程序1。 求解結(jié)果：n=2時應該在第18區(qū)和31區(qū)設立乘車點，其最短總距離為24492米。n=3時應該在第15區(qū)、21區(qū)和31區(qū)建立乘車站，最短距離為19660米。4.2 滿意度評價模型：4.2.1問題分析：對距離以及人數(shù)兩個指標進行無量綱化處理，得到兩個指標的量化數(shù)據(jù)。 將已經(jīng)無量綱化后的指標參數(shù)相乘得到定義的不滿意度指標。將得到后的綜合指標當作第一問中的距離指標，建立滿意度評價函數(shù)，求解第二

14、問中的變化后的距離的最小值。圖3如圖3，對于滿意度模型：我們對人數(shù)以及距離兩個指標進行無量綱化處理，使其量化；對兩組無量綱化后的數(shù)據(jù)相乘，得到滿意度評價函數(shù)，即相乘的結(jié)果越小，其滿意度越大，我們將其定義為不滿意度；再對所有小區(qū)進行歷遍，選取n個小區(qū)作為乘車站點，對其不滿意度進行比較；最后得出最小的不滿意度即為本問的解4.2.2 對指標進行無量綱化：1.對人數(shù)進行無量綱化：我們采用每個小區(qū)人數(shù)除以總?cè)藬?shù)的方法來實現(xiàn)其無量綱化，Qj=Pj/P0（公式1）得到表5：表5區(qū)域人數(shù)區(qū)域人數(shù)10.0259792260.006394920.0267786270.037569930.0167866280.00

15、7194240.0135891290.011590750.0151878300.02997660.0115907310.003996870.0067946320.034372580.0255795330.027977690.0155875340.0223821100.0079936350.0259792110.0243805360.0103917120.018785370.0319744130.0263789380.0359712140.0083933390.018785150.0279776400.0159872160.0339728410.0227818170.0047962420.015

16、9872180.0139888430.0275779190.0191847440.0267786200.0215827450.0079936210.0195843460.0071942220.0047962470.0271783230.0215827480.028777240.0183853490.0303757250.0303757500.0247802 表5表示出每個小區(qū)人數(shù)所占總?cè)藬?shù)的比例，反映出每個小區(qū)人數(shù)對于不滿意度的權(quán)重值Qj(j=050)。2. 對距離進行極值差方法處理：對附錄中的數(shù)值進行極值差方法處理，得到無量綱的量化結(jié)果， Bij'=Bij-（Bi）minBimax-

17、（Bi）min（公式2）其中： Bij表示B矩陣中的第i行第j列的元素（Bi）min=minBij(1i50)，（Bi）max=maxBij(1i50)3.得出滿意度評價函數(shù)：Y=(Bij-（Bi）min)/(（Bi）max-（Bi）min)* （Pj/P0） （公式3）4.2.3求解結(jié)果：n=2時最優(yōu)解為16區(qū)和36區(qū)不滿意度為0.4980。當n=3時最優(yōu)解為15區(qū)、22區(qū)和32區(qū)不滿意度為0.3720。4.3 問題三：4.3.1問題分析：通過總?cè)藬?shù)與校車的載人數(shù)算出最少需要的車輛數(shù)為54輛盡量少的車輛數(shù)作為一個限制滿意度的條件建立求解函數(shù)結(jié)合問題一的算法求出最終結(jié)果圖3如圖3：由于要求使用

18、盡可能少的車輛讓教師和工作人員的滿意度盡量高，所以我們把車輛數(shù)作為一個限制滿意度的條件。通過在問題二的基礎上把車輛數(shù)考慮進去運用問題一的算法即可求得答案。4.3.2問題求解：當n=3時最優(yōu)解為至少需要54輛車對應的區(qū)域分別為15、22、32。對應的車輛數(shù)為20、16、18。不滿意度為0.37204.4問題的合理化建議與考慮：1. 可于上下班高峰期增開幾次校車，在不是高峰期，減少幾次校車運行；2. 可以運行不同型號的校車，在乘車人數(shù)較多的車站運行大校車，人數(shù)較少的車站運行較小的校車。3. 可以增加幾個收費的乘車站點，因為增加站點會提高滿意度，但同時會增加運行成本，因此進行收費來降低成本。4. 可

19、以將乘車站點不設定在小區(qū)內(nèi)，設定在幾個小區(qū)比較靠中央的位置，在相同情況下回事滿意度提高。5. 有一些應該使乘車站盡量靠近老年人數(shù)較多的小區(qū)，這樣滿意度提高。五、模型的評價首先，在解決問題一的時候，我們建立了最小距離模型后，直接用Floyd算法進行運算，得到了每一個小區(qū)到其他各個小區(qū)的最小距離的矩陣，然后隨機抽取n個小區(qū)作為車站，對最小距離矩陣的這n行進行求和，比較求和值得到最終結(jié)論。當n比較小時，用這種方法可以較好的計算出所求的n個點。但是，這種方法的運算量與n的大小是成指數(shù)關系的，所以，當n很大時運算量會迅速增大。在解決問題二的時候，我們在問題一的基礎上用小區(qū)和最近車站的距離和小區(qū)人數(shù)無量綱

20、化后的乘積來表示教師和工作人員的滿意程度，之后用和問題一相同的思路得出結(jié)論。所以，第二問中也存在著第一問中，當n很大的時候運算量過大的問題。而此無量綱化的過程中我們考慮了任意兩個小區(qū)最短距離的極大值和極小值，發(fā)現(xiàn)極小值都是0，極大值之間相差不大，因此可以使用極值無量綱化的方法。但是極值無量綱化是通過利用變量取值的最大值和最小值將原始數(shù)據(jù)轉(zhuǎn)換為介于某一特定范圍的數(shù)據(jù)，從而消除量綱和數(shù)量級影響，改變變量在分析中的權(quán)重來解決不同度量的問題，所以此權(quán)重沒有對距離和人數(shù)進行差異化對待，而事實上人數(shù)和距離的權(quán)重肯定是不同的。解決第三個問題時，我們用到了逼近理想值排序法，假設理想的情況是共用53輛車（因為總

21、人數(shù)為2502，至少需要54輛車才可以），且教師和工作人員的滿意度最大。我們延用解決問題二的方法，只是在距離與人數(shù)無量綱化后再乘以因式（A53），然后對所有的情況進行排序，找到最接近理想值D的一組數(shù)據(jù)。六、參考文獻1 鄭洲順 科學計算與數(shù)學建模 復旦大學出版社。2 姜啟源 謝金星 葉俊 數(shù)學模型 高等教育出版社。3 孫祥 徐流美 吳清 Matlab7.0基礎教程 清華大學出版社。附件1：50個區(qū)之間任意兩點的最短通路值附件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,

22、M,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,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

23、),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,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,

24、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,:)=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,

25、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,

26、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,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,

27、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,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(18,:)=zeros(1,18),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,:

28、)=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,:)=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,

29、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,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,

30、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,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,:

31、)=zeros(1,31),230,M,M,M,260,M,M,M,M,M,M,M,M,M,M,M,M,M,210;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,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),

32、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,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,:)=ze

33、ros(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;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:50 for i=1:50 for j=1:50 if b(i,j)>b(i,k)+

34、b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k; end end endend u=1; d=zeros(50,1); f=zeros(19600,4);for i=1:48 for j=2:49 for k=3:50 for a=1:50 t=b(i,a) b(j,a) b(k,a); 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; end end end;x,m=min(f(:,1);e=f(m,:);e附件3：問題二的算法clear;M=10000;w=65;

35、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,:)=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

36、,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,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

37、,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,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,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

38、,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,:)=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

39、,M,M,M,M,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

40、,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,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

41、,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,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(18,:)=zeros(1,18),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(2

42、0,:)=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,:)=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

43、,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,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

44、,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,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,210;a(32,:)=zeros(1,32),190,M

45、,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,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(3

46、8,:)=zeros(1,38),130,M,M,M,M,M,M,M,M,M,M,M;a(39,:)=zeros(1,39),M,310,M,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

47、,M,M,M,M;a(46,:)=zeros(1,46),M,280,M,M;a(47,:)=zeros(1,47),M,M,M;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:50 for i=1:50 for j=1:50 if b(i,j)>b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k; end end endend u=1; d=zeros(50,1); f=zero

48、s(19600,4);for i=1:48 for j=2:49 for k=3:50 mii=min(b(i,:),2);mai=max(b(i,:),2); mij=min(b(j,:),2);maj=max(b(j,:),2); mik=min(b(k,:),2);mak=max(b(k,:),2); for a=1:50 t=(b(i,a)-mii)/(mai-mii)*w(a,1) (b(j,a)-mij)/(maj-mij)*w(a,1) (b(k,a)-mik)/(mak-mik)*w(a,1); d(a,1)=min(t); end; f(u,1)=sum(d); f(u,2)

49、=i; f(u,3)=j; f(u,4)=k; u=u+1; end end end;x,m=min(f(:,1);e=f(m,:);e附件4：第三問的算法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,:)=0,400,450,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,

50、M,M,M,M,M,M,M,M,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,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M;a(

51、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,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,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