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

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

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

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

5、和工作人員滿(mǎn)意度最大，該將校車(chē)乘車(chē)點(diǎn)應(yīng)建立在哪個(gè)點(diǎn)。建立一般模型，并給出時(shí)的結(jié)果。（3） 若建立3個(gè)乘車(chē)點(diǎn)，為使教師和工作人員盡量滿(mǎn)意，至少需要安排多少輛車(chē)？給出每個(gè)乘車(chē)點(diǎn)的位置和車(chē)輛數(shù)。設(shè)每輛車(chē)最多載客47人。（4） 關(guān)于校車(chē)安排問(wèn)題，你還有什么好的建議和考慮。可以提高乘車(chē)人員的滿(mǎn)意度，又可節(jié)省運(yùn)行成本。二、基本假設(shè)1.假設(shè)乘客的滿(mǎn)意度只與小區(qū)到車(chē)站之間的距離以及車(chē)站乘車(chē)人數(shù)有關(guān)；2.在問(wèn)題一、二中，假設(shè)每位教師及工作人員只會(huì)到最近的車(chē)站乘車(chē)；3.在問(wèn)題一、二中，假設(shè)每位乘客到達(dá)車(chē)站后，都有校車(chē)乘坐；三、符號(hào)說(shuō)明1. V1，V2，Vk，Vn表示各個(gè)區(qū)；2. A1，A2，Ak,An表示第k個(gè)區(qū)

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

7、較，得到它們中的最小值S0，即為結(jié)果。如圖1：隨機(jī)取得n個(gè)小區(qū)作為車(chē)站V1，V2，Vk，Vn 求得n個(gè)最小距離行向量 A1，A2，Ak,An按位比較n個(gè)行向量，得到最終最小距離行向量A 將最小距離行向量A各項(xiàng)相加，得到此隨機(jī)車(chē)站的最小總距離S將各種隨機(jī)情況得到的最小總距離S比較，得到最小總距離S0，即為結(jié)果圖1：最小距離模型建立的示意圖4.1.2隨機(jī)選取n個(gè)小區(qū)作為乘車(chē)站點(diǎn)： 我們運(yùn)用n個(gè)for循環(huán)語(yǔ)句對(duì)隨機(jī)選取n個(gè)小區(qū)作為乘車(chē)站點(diǎn)的所有情況進(jìn)行一次歷遍，以n=3為例，具體實(shí)現(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個(gè)小區(qū)中隨機(jī)選取三個(gè)作為乘車(chē)站點(diǎn)的所有可能，所選取的站點(diǎn)即為：Vi，Vj，Vk。4.1.3求得這n乘車(chē)站點(diǎn)到各個(gè)小區(qū)的最短距離：1.首先應(yīng)得到由各個(gè)小區(qū)之間的距離組成的鄰接矩陣（見(jiàn)附件1）；2.其次考慮到要計(jì)算任意兩點(diǎn)之間的最短距離，我們采用了Floyd算法進(jìn)行求算；示例：Floyd算法的基本步驟2如圖2所示問(wèn)題，要求的任意兩點(diǎn)之間的對(duì)短距離建立相鄰矩陣，見(jiàn)表1，則從上面的表1開(kāi)始，對(duì)于每?jī)蓚€(gè)頂點(diǎn)u、v，在表1中存儲(chǔ)著一條路徑uv。現(xiàn)在我們考察，試著把a(bǔ)加到u、v的路徑上能否，得到一條更短的路徑，即如果ua+avDbc=2，所以如果

9、從a繞，反而遠(yuǎn)，又因?yàn)镈ca+Dab=3+4Dcb= ，所以如果從a繞，更近，因此，由表1變成表2。從上面的表2開(kāi)始，對(duì)于每?jī)蓚€(gè)頂點(diǎn)u、v，在表2中存儲(chǔ)著一條路徑uv?，F(xiàn)在我們考察，試著把b加到u、v的路徑上能否，得到一條更短的路徑，即如果ub+bvuv的話(huà)，能夠找到一條更短的路徑。同樣地，本來(lái)路徑上源點(diǎn)或終點(diǎn)就有b的不必考慮。對(duì)角線(xiàn)上的也不必考慮，Dab+Dbc=6Dca=3，所以如果從b繞， 反而遠(yuǎn)，因此表2中的數(shù)據(jù)應(yīng)該變?yōu)楸?。 從上面的表2開(kāi)始，對(duì)于每?jī)蓚€(gè)頂點(diǎn)u、v，在表2中存儲(chǔ)。著一條路徑uv?，F(xiàn)在我們考察，試著把c加到u、v的路徑上能否，得到一條更短的路徑，即如果uc+cvDab=

10、4，所以如果從c繞，反而遠(yuǎn)，Dbc+Dca=2+3b(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個(gè)乘車(chē)站點(diǎn)到各個(gè)小區(qū)的最短距離的行矩陣：在2中得到的b矩陣中提取出這n個(gè)小區(qū)對(duì)應(yīng)的行的行向量，例如，選取第一個(gè)小區(qū)作為乘車(chē)站點(diǎn)，則將b矩陣中的第一行取出，作為行向量A1，其他的依此類(lèi)推即可，由此可以得到各個(gè)乘車(chē)站點(diǎn)最短距離的行矩陣A1，A2，Ak,An。4.1.4求得各個(gè)小區(qū)到這n個(gè)乘車(chē)站點(diǎn)的最短距離S：因?yàn)榈玫降男芯仃嘇1，A2，Ak,An的階數(shù)是相同的，因此

11、，我們按位求最小值，得出另一個(gè)行矩陣A，將A中各個(gè)元素相加就可以得到各小區(qū)到達(dá)這n個(gè)乘車(chē)站點(diǎn)的最小距離S，算法見(jiàn)算法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=u+1;算法34.1.5 得出最終結(jié)果S0：遍歷所有可能情況后，通過(guò)比較每種情況得出的S，得出其最小值，得到的S0即為最小距離，取得最小距離時(shí)隨機(jī)選取的i，j，k即為乘車(chē)站點(diǎn)的設(shè)置地點(diǎn)。具體的程序?qū)崿F(xiàn)見(jiàn)程序1。4.1.6 求解結(jié)果：n=2時(shí)應(yīng)該在第18區(qū)和31區(qū)設(shè)立乘車(chē)點(diǎn)，

12、其最短總距離為24492米。n=3時(shí)應(yīng)該在第15區(qū)、21區(qū)和31區(qū)建立乘車(chē)站，最短距離為19660米。4.2 滿(mǎn)意度評(píng)價(jià)模型：4.2.1問(wèn)題分析：對(duì)距離以及人數(shù)兩個(gè)指標(biāo)進(jìn)行無(wú)量綱化處理，得到兩個(gè)指標(biāo)的量化數(shù)據(jù)。 將已經(jīng)無(wú)量綱化后的指標(biāo)參數(shù)相乘得到定義的不滿(mǎn)意度指標(biāo)。將得到后的綜合指標(biāo)當(dāng)作第一問(wèn)中的距離指標(biāo)，建立滿(mǎn)意度評(píng)價(jià)函數(shù)，求解第二問(wèn)中的變化后的距離的最小值。圖3如圖3，對(duì)于滿(mǎn)意度模型：我們對(duì)人數(shù)以及距離兩個(gè)指標(biāo)進(jìn)行無(wú)量綱化處理，使其量化；對(duì)兩組無(wú)量綱化后的數(shù)據(jù)相乘，得到滿(mǎn)意度評(píng)價(jià)函數(shù)，即相乘的結(jié)果越小，其滿(mǎn)意度越大，我們將其定義為不滿(mǎn)意度；再對(duì)所有小區(qū)進(jìn)行歷遍，選取n個(gè)小區(qū)作為乘車(chē)站點(diǎn)，對(duì)

13、其不滿(mǎn)意度進(jìn)行比較；最后得出最小的不滿(mǎn)意度即為本問(wèn)的解4.2.2 對(duì)指標(biāo)進(jìn)行無(wú)量綱化：1.對(duì)人數(shù)進(jìn)行無(wú)量綱化：我們采用每個(gè)小區(qū)人數(shù)除以總?cè)藬?shù)的方法來(lái)實(shí)現(xiàn)其無(wú)量綱化，Qj=Pj/P0（公式1）得到表5：表5區(qū)域人數(shù)區(qū)域人數(shù)10.260.20.270.30.280.40.290.50.300.60.310.70.320.80.330.90.340.100.350.110.360.120.370.130.380.140.390.150.400.160.410.170.420.180.430.190.440.200.450.210.460.220.470.230.480.240.490.250.500

14、. 表5表示出每個(gè)小區(qū)人數(shù)所占總?cè)藬?shù)的比例，反映出每個(gè)小區(qū)人數(shù)對(duì)于不滿(mǎn)意度的權(quán)重值Qj(j=050)。2. 對(duì)距離進(jìn)行極值差方法處理：對(duì)附錄中的數(shù)值進(jìn)行極值差方法處理，得到無(wú)量綱的量化結(jié)果， Bij=Bij-（Bi）minBimax-（Bi）min（公式2）其中： Bij表示B矩陣中的第i行第j列的元素（Bi）min=minBij(1i50)，（Bi）max=maxBij(1i50)3.得出滿(mǎn)意度評(píng)價(jià)函數(shù)：Y=(Bij-（Bi）min)/(（Bi）max-（Bi）min)* （Pj/P0） （公式3）4.2.3求解結(jié)果：n=2時(shí)最優(yōu)解為16區(qū)和36區(qū)不滿(mǎn)意度為0.4980。當(dāng)n=3時(shí)最優(yōu)解為1

15、5區(qū)、22區(qū)和32區(qū)不滿(mǎn)意度為0.3720。4.3 問(wèn)題三：4.3.1問(wèn)題分析：通過(guò)總?cè)藬?shù)與校車(chē)的載人數(shù)算出最少需要的車(chē)輛數(shù)為54輛盡量少的車(chē)輛數(shù)作為一個(gè)限制滿(mǎn)意度的條件建立求解函數(shù)結(jié)合問(wèn)題一的算法求出最終結(jié)果圖3如圖3：由于要求使用盡可能少的車(chē)輛讓教師和工作人員的滿(mǎn)意度盡量高，所以我們把車(chē)輛數(shù)作為一個(gè)限制滿(mǎn)意度的條件。通過(guò)在問(wèn)題二的基礎(chǔ)上把車(chē)輛數(shù)考慮進(jìn)去運(yùn)用問(wèn)題一的算法即可求得答案。4.3.2問(wèn)題求解：當(dāng)n=3時(shí)最優(yōu)解為至少需要54輛車(chē)對(duì)應(yīng)的區(qū)域分別為15、22、32。對(duì)應(yīng)的車(chē)輛數(shù)為20、16、18。不滿(mǎn)意度為0.37204.4問(wèn)題的合理化建議與考慮：1. 可于上下班高峰期增開(kāi)幾次校車(chē)，在不

16、是高峰期，減少幾次校車(chē)運(yùn)行；2. 可以運(yùn)行不同型號(hào)的校車(chē)，在乘車(chē)人數(shù)較多的車(chē)站運(yùn)行大校車(chē)，人數(shù)較少的車(chē)站運(yùn)行較小的校車(chē)。3. 可以增加幾個(gè)收費(fèi)的乘車(chē)站點(diǎn)，因?yàn)樵黾诱军c(diǎn)會(huì)提高滿(mǎn)意度，但同時(shí)會(huì)增加運(yùn)行成本，因此進(jìn)行收費(fèi)來(lái)降低成本。4. 可以將乘車(chē)站點(diǎn)不設(shè)定在小區(qū)內(nèi)，設(shè)定在幾個(gè)小區(qū)比較靠中央的位置，在相同情況下回事滿(mǎn)意度提高。5. 有一些應(yīng)該使乘車(chē)站盡量靠近老年人數(shù)較多的小區(qū)，這樣滿(mǎn)意度提高。五、模型的評(píng)價(jià)首先，在解決問(wèn)題一的時(shí)候，我們建立了最小距離模型后，直接用Floyd算法進(jìn)行運(yùn)算，得到了每一個(gè)小區(qū)到其他各個(gè)小區(qū)的最小距離的矩陣，然后隨機(jī)抽取n個(gè)小區(qū)作為車(chē)站，對(duì)最小距離矩陣的這n行進(jìn)行求和，比較

17、求和值得到最終結(jié)論。當(dāng)n比較小時(shí)，用這種方法可以較好的計(jì)算出所求的n個(gè)點(diǎn)。但是，這種方法的運(yùn)算量與n的大小是成指數(shù)關(guān)系的，所以，當(dāng)n很大時(shí)運(yùn)算量會(huì)迅速增大。在解決問(wèn)題二的時(shí)候，我們?cè)趩?wèn)題一的基礎(chǔ)上用小區(qū)和最近車(chē)站的距離和小區(qū)人數(shù)無(wú)量綱化后的乘積來(lái)表示教師和工作人員的滿(mǎn)意程度，之后用和問(wèn)題一相同的思路得出結(jié)論。所以，第二問(wèn)中也存在著第一問(wèn)中，當(dāng)n很大的時(shí)候運(yùn)算量過(guò)大的問(wèn)題。而此無(wú)量綱化的過(guò)程中我們考慮了任意兩個(gè)小區(qū)最短距離的極大值和極小值，發(fā)現(xiàn)極小值都是0，極大值之間相差不大，因此可以使用極值無(wú)量綱化的方法。但是極值無(wú)量綱化是通過(guò)利用變量取值的最大值和最小值將原始數(shù)據(jù)轉(zhuǎn)換為介于某一特定范圍的數(shù)據(jù)

18、，從而消除量綱和數(shù)量級(jí)影響，改變變量在分析中的權(quán)重來(lái)解決不同度量的問(wèn)題，所以此權(quán)重沒(méi)有對(duì)距離和人數(shù)進(jìn)行差異化對(duì)待，而事實(shí)上人數(shù)和距離的權(quán)重肯定是不同的。解決第三個(gè)問(wèn)題時(shí)，我們用到了逼近理想值排序法，假設(shè)理想的情況是共用53輛車(chē)（因?yàn)榭側(cè)藬?shù)為2502，至少需要54輛車(chē)才可以），且教師和工作人員的滿(mǎn)意度最大。我們延用解決問(wèn)題二的方法，只是在距離與人數(shù)無(wú)量綱化后再乘以因式（A53），然后對(duì)所有的情況進(jìn)行排序，找到最接近理想值D的一組數(shù)據(jù)。六、參考文獻(xiàn)1 鄭洲順 科學(xué)計(jì)算與數(shù)學(xué)建模 復(fù)旦大學(xué)出版社。2 姜啟源 謝金星 葉俊 數(shù)學(xué)模型 高等教育出版社。3 孫祥 徐流美 吳清 Matlab7.0基礎(chǔ)教程

19、清華大學(xué)出版社。附件1：50個(gè)區(qū)之間任意兩點(diǎn)的最短通路值附件2：?jiǎn)栴}一的算法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,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(

20、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),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

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

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(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,M,M,M

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

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

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

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

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

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

29、=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,M,M,M,M,M,M,M,M;a(40,:)=zeros

30、(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;a(48,:)=zeros(1,48),200,M;a(49,:)=z

31、eros(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=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)=su

32、m(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：?jiǎn)栴}二的算法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,

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

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

35、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,:)=zeros(1,9),180,M,M,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,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,

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

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

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

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

41、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,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,13

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

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

44、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;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:5

45、0 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=zeros(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) (

46、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)=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：第三問(wèn)的算法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;

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

48、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),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

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