校車(chē)安排問(wèn)題

校車(chē)安排模型摘要本文討論了在不同情況下如何合理安排校車(chē)讓教師和工作人員最大滿意的問(wèn)題。在問(wèn)題一中，把50個(gè)區(qū)看成50個(gè)點(diǎn)，我們先利用佛洛依德算法求出了任意兩點(diǎn)間最短路距離矩陣，得到的一個(gè)50階的矩陣，在此基礎(chǔ)上，我們以各區(qū)域到各自最近乘車(chē)點(diǎn)的距離總和最小為目標(biāo)設(shè)置N個(gè)乘車(chē)點(diǎn)，對(duì)50個(gè)區(qū)域進(jìn)行遍歷分析，總共需要進(jìn)行對(duì)兩點(diǎn)最短距離的查找，在n較小的情況下借助數(shù)學(xué)工具M(jìn)ATLAB可以較快找出各個(gè)區(qū)域到各自最近乘車(chē)點(diǎn)的最小距離和建立模型一，找出n個(gè)最優(yōu)乘車(chē)點(diǎn)。在第一問(wèn)的基礎(chǔ)上并利用已給的一般模型求出了如果設(shè)立2個(gè)乘車(chē)點(diǎn)則區(qū)號(hào)為18區(qū)和31區(qū)，其最短總距離為24492米。如果設(shè)立3個(gè)乘車(chē)個(gè)點(diǎn)則分別為15區(qū)、21區(qū)和31區(qū)，其最短總距離為19660米。在問(wèn)題二中，根據(jù)滿意度與距離成負(fù)相關(guān)的關(guān)系，把各區(qū)人數(shù)（各區(qū)到各自最近乘車(chē)點(diǎn)的最小距離）求和作為評(píng)價(jià)滿意度的指標(biāo)，由分析可知取最小值時(shí)教師職工的滿意度最大然后以所有區(qū)域人員滿意度最大為目標(biāo)函數(shù)建立模型二。并依據(jù)模型求出當(dāng)建立2個(gè)乘車(chē)點(diǎn)時(shí)最優(yōu)解為19點(diǎn)和32點(diǎn)，總滿意度為0.78。當(dāng)建立3個(gè)乘車(chē)點(diǎn)時(shí)的最優(yōu)解為第15，21，32點(diǎn)，滿意度為0.83關(guān)鍵詞：Floyd算法滿意度最短距離MATLAB一問(wèn)題重述許多學(xué)校都建有新校區(qū)，常常需要將老校區(qū)的教師和工作人員用校車(chē)送到新校區(qū)。由于每天到新校區(qū)的教師和工作人員很多，往往需要安排許多車(chē)輛。有效的安排車(chē)輛并讓教師和工作人員盡量滿意是個(gè)十分重要的問(wèn)題。假設(shè)老校區(qū)的教室和工作人員分布在50個(gè)區(qū)。問(wèn)題一：建立個(gè)乘車(chē)點(diǎn)，使各區(qū)人員到乘車(chē)點(diǎn)的距離最小，建立模型，并分別建立兩個(gè)和三個(gè)乘車(chē)點(diǎn)的校車(chē)安排方案。問(wèn)題二：考慮每個(gè)區(qū)的乘車(chē)人數(shù)，使工作人員和教室的滿意度最大，建立模型，并分別建立兩個(gè)和三個(gè)乘車(chē)點(diǎn)的校車(chē)安排方案。(假定車(chē)只在起始點(diǎn)載人)問(wèn)題三：在教師和工作人員盡量滿意的前提下，在50個(gè)區(qū)內(nèi)找出最優(yōu)的三個(gè)乘車(chē)點(diǎn)的位置，并根據(jù)各個(gè)乘車(chē)點(diǎn)的人數(shù)，（車(chē)輛最多載客47人）確定車(chē)輛個(gè)數(shù)。最后，跟據(jù)以上所得出的結(jié)論，在提高乘車(chē)人員的滿意度，又可節(jié)省運(yùn)行成本的前提下，對(duì)如何改進(jìn)校車(chē)的安排方案提出意見(jiàn)。二問(wèn)題分析校車(chē)的安排并讓教師職工盡量滿意是個(gè)很重要的現(xiàn)實(shí)的問(wèn)題，這里首先采用算法求得任意兩點(diǎn)之間最短距離，得到一個(gè)50階的佛洛依德矩陣，在這個(gè)距震中可以方便的查找到任意兩點(diǎn)之間的最短距離和路徑，其次在50個(gè)區(qū)域中任意選取n個(gè)區(qū)域作為乘車(chē)點(diǎn)，找出每個(gè)區(qū)域所對(duì)應(yīng)的最近乘車(chē)點(diǎn)，最后以50個(gè)區(qū)域到各自最近乘車(chē)點(diǎn)的最短距離和的最小值為目標(biāo)函數(shù)建立模型一。并對(duì)設(shè)立2個(gè)和3個(gè)乘車(chē)點(diǎn)時(shí)的校車(chē)安排問(wèn)題進(jìn)行求解。算法的時(shí)間復(fù)雜度O(n^3)優(yōu)缺點(diǎn)分析Floyd算法適用于APSP(AllPairsShortestPaths)，是一種動(dòng)態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。此算法簡(jiǎn)單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對(duì)于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法。優(yōu)點(diǎn)：容易理解，可以算出任意兩個(gè)節(jié)點(diǎn)之間的最短距離，代碼編寫(xiě)簡(jiǎn)單；缺點(diǎn)：時(shí)間復(fù)雜度比較高，不適合計(jì)算大量數(shù)據(jù)。借助MATLAB可以較快實(shí)現(xiàn)。第二問(wèn)要求在教師和工作人員的滿意度最大為前提條件下選出最佳乘車(chē)點(diǎn)。為此需要建立關(guān)于滿意度的衡量指標(biāo)（各區(qū)人數(shù)到各自最近乘車(chē)點(diǎn)的距離最小距離的最小和），并對(duì)每個(gè)區(qū)的人數(shù)進(jìn)行歸一化處理，然后以總滿意度最高為目標(biāo)函數(shù)建立模型二，并對(duì)設(shè)立2個(gè)和3個(gè)乘車(chē)點(diǎn)時(shí)的校車(chē)安排問(wèn)題進(jìn)行求解。第三問(wèn)要去建立3個(gè)乘車(chē)點(diǎn)，在盡量使教師和工作人員滿意的前提下所需的車(chē)輛最少，我們利用模型二和總車(chē)輛數(shù)最少函數(shù)的雙目標(biāo)函數(shù)進(jìn)行優(yōu)化求解，得出最優(yōu)解。第四問(wèn)中我們結(jié)合第三問(wèn)的結(jié)果對(duì)車(chē)輛的安排情況提出了建議。三模型假設(shè)1、假設(shè)每個(gè)人采取到最近點(diǎn)乘車(chē)原則2、假設(shè)汽車(chē)中途不再載人3、假設(shè)每輛車(chē)的型號(hào)一致4、假設(shè)每個(gè)乘車(chē)點(diǎn)的乘車(chē)人數(shù)固定不變，即不考慮意外的發(fā)生和教師職工的搬遷。5、假設(shè)各區(qū)之間路徑由題目給出，并且任意一個(gè)區(qū)到另外一個(gè)區(qū)都應(yīng)經(jīng)過(guò)由題目表中給出的距離的對(duì)應(yīng)點(diǎn)。無(wú)距離對(duì)應(yīng)的區(qū)域視為兩點(diǎn)間沒(méi)有直通路徑。6、乘車(chē)點(diǎn)應(yīng)設(shè)置在50個(gè)區(qū)域。7、校車(chē)中途無(wú)意外發(fā)生，交通秩序暢通。四符號(hào)說(shuō)明Z區(qū)域各自最近乘車(chē)點(diǎn)的距離最短距離之和三個(gè)乘車(chē)點(diǎn)時(shí)的總滿意度三個(gè)乘車(chē)點(diǎn)的總車(chē)輛數(shù)區(qū)域號(hào)區(qū)域到最近乘車(chē)點(diǎn)的最小距離乘車(chē)點(diǎn)（）各區(qū)域人數(shù)到第個(gè)乘車(chē)點(diǎn)的子集合滿意度第各乘車(chē)點(diǎn)的車(chē)輛數(shù)區(qū)域到區(qū)域的最短距離矩陣=（）=（）五模型建立與求解問(wèn)題一要求：建立n個(gè)乘車(chē)點(diǎn)，使各區(qū)人員到乘車(chē)點(diǎn)的距離最小，建立模型，并求的時(shí)的結(jié)果。5.0.1采用算法求得50個(gè)區(qū)域的最短距離矩陣，結(jié)合表一，利用算法求的任意兩點(diǎn)之間最短距離（程序見(jiàn)附錄【1】）。算法如下：1、先根據(jù)題目數(shù)據(jù)為初始矩陣賦值，其中沒(méi)有給出距離的賦給一大值，以便于更新。2、進(jìn)行迭代計(jì)算。對(duì)任意兩點(diǎn)，若存在，使，則更新。3、直到所有點(diǎn)的距離不再更新停止計(jì)算。則得到最短路距離矩陣，。建立模型一在最短路距離矩陣的基礎(chǔ)上，再做如下分析：首先，在50個(gè)區(qū)域中任意選取n個(gè)區(qū)域作為乘車(chē)點(diǎn)∈其次，引入變量，表示k區(qū)域到最近乘車(chē)點(diǎn)的最小距離然后，求出50個(gè)區(qū)域到各自最近乘車(chē)點(diǎn)的最短距離之和，最后，建立模型一最佳乘車(chē)點(diǎn)是使得50個(gè)區(qū)域到各自最近乘車(chē)點(diǎn)的最短距離之和最小的點(diǎn)，基于此建立目標(biāo)函數(shù)：其中∈為選出的最佳乘車(chē)點(diǎn)。依據(jù)模型一，利用軟件(程序見(jiàn)附錄【2】)求得結(jié)果如下：當(dāng)=2時(shí)，選18區(qū)的32個(gè)：1234567891011121415161718192021222324252627284446474849選32的區(qū)域有18個(gè):132930313233343536373839404142434550 當(dāng)=3時(shí)： 選擇的三個(gè)乘車(chē)點(diǎn)為15,21,32。滿意度為0.83。選15點(diǎn)有17個(gè): 56789101112131415161718252627選21點(diǎn)有18個(gè): 12341920212223242843444546474849選32點(diǎn)有15個(gè):293031323334353637383940414250問(wèn)題二要求：考慮每個(gè)區(qū)的乘車(chē)人數(shù)，使工作人員和教師的滿意度最大，建立模型，并求得時(shí)的結(jié)果。1第區(qū)人數(shù)權(quán)重為：50個(gè)區(qū)的總?cè)藬?shù)1.3建立模型二在模型一的基礎(chǔ)上，建立最高滿意度乘車(chē)點(diǎn)選擇模型，目標(biāo)函數(shù)：最大滿意度其中：表示選出的最高滿意度下的最佳乘車(chē)點(diǎn)。依據(jù)模型二，利用軟件求得結(jié)果如下（程序見(jiàn)附錄【3】）：當(dāng)=2時(shí):選擇的兩個(gè)乘車(chē)點(diǎn)為19,32。滿意度為0.78選19的區(qū)域有32個(gè):1234567891011121415161718192021222324252627284446474849選32的區(qū)域有18個(gè):132930313233343536373839404142434550 當(dāng)=3時(shí)： 選擇的三個(gè)乘車(chē)點(diǎn)為15,21,32。滿意度為0.83。選15點(diǎn)有17個(gè): 56789101112131415161718252627選21點(diǎn)有18個(gè): 12341920212223242843444546474849選32點(diǎn)有15個(gè):29303132333435363738394041425問(wèn)題三：根據(jù)題目要求使得教師職工盡可能的滿意同時(shí)乘車(chē)站點(diǎn)固定的情況下：即令上面的n=3；對(duì)問(wèn)題二的分析求解，已知道當(dāng)選擇三個(gè)乘車(chē)點(diǎn)時(shí)，選擇15,21,32為最近乘車(chē)點(diǎn)。于是： 區(qū)號(hào)：56789101112131415161718252627對(duì)應(yīng)最近乘車(chē)點(diǎn)：15 區(qū)號(hào)：12341920212223242843444546474849對(duì)應(yīng)最近乘車(chē)點(diǎn)：21 區(qū)號(hào)：293031323334353637383940414250對(duì)應(yīng)最近乘車(chē)點(diǎn)：32 由以上可知，選擇15，21，32作為乘車(chē)點(diǎn)時(shí)的車(chē)輛數(shù)為： 在15區(qū)乘車(chē)人數(shù)790，校車(chē)=17輛 在21區(qū)乘車(chē)人數(shù)879，校車(chē)=19輛 在32區(qū)乘車(chē)人數(shù)833，校車(chē)=18輛 共17+19+18=54輛而50個(gè)區(qū)的總?cè)藬?shù)為不管怎樣至少需要安排的校車(chē)總數(shù)為：/47（向上取整）=54（輛）恰好是已經(jīng)找到的三個(gè)乘車(chē)點(diǎn)需要安排的校車(chē)總數(shù)同時(shí)滿足了使教師職工盡可能的滿意問(wèn)題四：在前三問(wèn)的分析與解答中，均忽略了一定的實(shí)際決策因素，如：第一問(wèn)中忽略了各區(qū)的人數(shù)和校車(chē)的容量，認(rèn)為各區(qū)的人數(shù)相等或者均為單位1，并且校車(chē)的數(shù)量及可搭載量為任意；第二問(wèn)中雖然考慮了人數(shù)，但仍然未考慮校車(chē)因素；第三問(wèn)只照顧了教師和工作人的滿意度：在保證所有人所走路程之和最小的前提下，各乘車(chē)點(diǎn)的小車(chē)可以任意增加，是第二問(wèn)的具體化。而實(shí)際情況下，我們的目的是使乘車(chē)人員的滿意度最大，即所走路程之和最小，校車(chē)的數(shù)量或者校車(chē)所花的費(fèi)用盡量少，此外，站點(diǎn)的建立需要費(fèi)用，故數(shù)量應(yīng)少，而且必然會(huì)對(duì)周?chē)沫h(huán)境產(chǎn)生影響，等等，實(shí)際處理時(shí)往往要綜合考慮。下面我們提出幾點(diǎn)建議或者措施：根據(jù)實(shí)際需要，各校車(chē)的容量可以不同，因?yàn)楦鲄^(qū)的人員數(shù)量變化不會(huì)很大或者基本上在而一個(gè)穩(wěn)定的狀態(tài)。這樣，在2問(wèn)的理想假設(shè)下，人員多的站點(diǎn)安排大搭載量的車(chē)，人員不足一個(gè)校車(chē)搭載量的站點(diǎn)，則安排較小容量的車(chē)，人員小于一個(gè)大車(chē)搭載量而大于一個(gè)小車(chē)搭載量則安排容量處于之間的，等等，這樣可以減少校車(chē)的數(shù)量。根據(jù)學(xué)校的教學(xué)時(shí)間表，可以得知教師及工作人員上班的人次，然后依據(jù)每天上、下午上班人數(shù)的不同，合理安排校車(chē)的發(fā)車(chē)量及發(fā)車(chē)時(shí)間.對(duì)于環(huán)境需求較高的地方，即使它是最大滿意度點(diǎn)，不能建立乘車(chē)點(diǎn)。例如，很多實(shí)驗(yàn)室附近要盡量避免噪音、電磁輻射等等。參考文獻(xiàn)：《運(yùn)籌學(xué)》清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)》清華大學(xué)出版社附錄：第一問(wèn)程序：n=50;A=zeros(n,n);fori=1:nforj=1:nif(i==j)A(i,j)=0;elseA(i,j)=100000;endendend%M=100000A(1,2)=400;A(1,3)=450;A(2,4)=300;A(2,21)=230;A(2,47)=140;A(3,4)=600;A(4,5)=210;A(4,19)=310;A(5,6)=230;A(5,7)=200;A(6,7)=320;A(6,8)=340;A(7,8)=170;A(7,18)=160;A(8,9)=200;A(8,15)=285;A(9,10)=180;A(10,11)=150;A(10,15)=160;A(11,12)=140;A(11,14)=130;A(12,13)=200;A(13,34)=400;A(14,15)=190;A(14,26)=190;A(15,16)=170;A(15,17)=250;A(16,17)=140;A(16,18)=130;A(17,27)=240;A(18,19)=240;A(18,25)=180;A(19,20)=140;A(19,24)=175;A(20,21)=180;A(20,24)=190;A(21,22)=300;A(21,23)=270;A(21,47)=350;A(22,44)=160;A(22,45)=270;A(22,48)=180;A(23,24)=240;A(23,29)=210;A(23,30)=290;A(23,44)=150;A(24,25)=170;A(24,28)=130;A(26,27)=140;A(26,34)=320;A(27,28)=190;A(28,29)=260;A(29,31)=190;A(30,31)=240;A(30,42)=130;A(30,43)=210;A(31,32)=230;A(31,36)=260;A(31,50)=210;A(32,33)=190;A(32,35)=140;A(32,36)=240;A(33,34)=210;A(35,37)=160;A(36,39)=180;A(36,40)=190;A(37,38)=135;A(38,39)=130;A(39,41)=310;A(40,41)=140;A(40,50)=190;A(42,50)=200;A(43,44)=260;A(43,45)=210;A(45,46)=240;A(46,48)=280;A(48,49)=200;forj=1:nfori=1:j-1A(j,i)=A(i,j);endend[m,n]=size(A);B=zeros(m,n);B=A;forkk=1:4fori=1:nforj=1:nfork=1:nt=B(i,k)+B(k,j);ift<B(i,j)B(i,j)=t;endendendendB;if(sum(sum(B-A))==0)break;endA=B;endd=zeros(n,1);d1=zeros(n,1);d2=zeros(n,1);mins1=100000;fori=1:n-1forj=i+1:nfork=1:nd(k)=min(B(k,i),B(k,j));ends=sum(d);if(s<=mins1)mins1=s;i1=i;j1=j;d1=d;endendendse11=zeros(1,n);num1=0;se12=zeros(1,n);num2=0;fork=1:nif(B(k,i1)<B(k,j1))num1=num1+1;se11(num1)=k;elsenum2=num2+1;se12(num2)=k;endendfprintf('\n問(wèn)題一結(jié)果：\n');fprintf('選取兩點(diǎn)時(shí)結(jié)果（%2d,%2d)=%5.2f\n',i1,j1,mins1);fprintf('\n選%2的點(diǎn)有%2d個(gè)：\n',i1,num1);fori=1:num1;fprintf('%2d',se11(i));endfprintf('\n');fprintf('選%2d的點(diǎn)有%2d個(gè)：\n',j1,num2);fori=1:num2;fprintf('%2d',se12(i));endfprintf('\n');mins2=100000;fori=1:n-2forj=i+1:n-1forp=j+1:nfork=1:nd(k)=min(min(B(k,i),B(k,j)),B(k,p));ends=sum(d);if(s<=mins2)mins2=s;i2=i;j2=j;p2=p;d2=d;endendendendrse11=zeros(1,n);rnum1=0;rse12=zeros(1,n);rnum2=0;rse13=zeros(1,n);rnum3=0;fork=1:nif(B(k,i2)<=B(k,j2)&&B(k,i2)<=B(k,p2))rnum1=rnum1+1;rse11(rnum1)=k;elseif(B(k,j2)<=B(k,i2)&&B(k,j2)<=B(k,p2))rnum2=rnum2+1;rse12(rnum2)=k;elseif(B(k,p2)<=B(k,i2)&&B(k,p2)<=B(k,j2))rnum3=rnum3+1;rse13(rnum3)=k;endendfprintf('\n\n選取三點(diǎn)時(shí)的結(jié)果（%2d,%2d,%2d）=%5.2f\n',i2,j2,p2,mins2);fprintf('\n選取%2d的點(diǎn)有%2d個(gè)：\n',i2,rnum1);fori=1:rnum1;fprintf('%2d',rse11(i));endfprintf('\n');fprintf('\n選取%2d的點(diǎn)有%2d個(gè)：\n',j2,rnum2);fori=1:rnum2;fprintf('%2d',rse12(i));endfprintf('\n');fprintf('\n選取%2d的點(diǎn)有%2d個(gè)：\n',p2,rnum3);fori=1:rnum3;fprintf('%2d',rse13(i));endfprintf('\n');第二問(wèn)程序：n=50;A=zeros(n,n);fori=1:nforj=1:nif(i==j)A(i,j)=0;elseA(i,j)=100000;endendend%M=100000A(1,2)=400;A(1,3)=450;A(2,4)=300;A(2,21)=230;A(2,47)=140;A(3,4)=600;A(4,5)=210;A(4,19)=310;A(5,6)=230;A(5,7)=200;A(6,7)=320;A(6,8)=340;A(7,8)=170;A(7,18)=160;A(8,9)=200;A(8,15)=285;A(9,10)=180;A(10,11)=150;A(10,15)=160;A(11,12)=140;A(11,14)=130;A(12,13)=200;A(13,34)=400;A(14,15)=190;A(14,26)=190;A(15,16)=170;A(15,17)=250;A(16,17)=140;A(16,18)=130;A(17,27)=240;A(18,19)=240;A(18,25)=180;A(19,20)=140;A(19,24)=175;A(20,21)=180;A(20,24)=190;A(21,22)=300;A(21,23)=270;A(21,47)=350;A(22,44)=160;A(22,45)=270;A(22,48)=180;A(23,24)=240;A(23,29)=210;A(23,30)=290;A(23,44)=150;A(24,25)=170;A(24,28)=130;A(26,27)=140;A(26,34)=320;A(27,28)=190;A(28,29)=260;A(29,31)=190;A(30,31)=240;A(30,42)=130;A(30,43)=210;A(31,32)=230;A(31,36)=260;A(31,50)=210;A(32,33)=190;A(32,35)=140;A(32,36)=240;A(33,34)=210;A(35,37)=160;A(36,39)=180;A(36,40)=190;A(37,38)=135;A(38,39)=130;A(39,41)=310;A(40,41)=140;A(40,50)=190;A(42,50)=200;A(43,44)=260;A(43,45)=210;A(45,46)=240;A(46,48)=280;A(48,49)=200;forj=1:nfori=1:j-1A(j,i)=A(i,j);endend[m,n]=size(A);B=zeros(m,n);B=A;forkk=1:4fori=1:nforj=1:nfork=1:nt=B(i,k)+B(k,j);ift<B(i,j)B(i,j)=t;endendendendB;if(sum(sum(B-A))==0)break;endA=B;endmaxd=max(max(B));pp=[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];Total=sum(pp);W=zeros(50,1);W=pp/Total;d=zeros(n,1);d1=zeros(n,1);d2=zeros(n,1);r=zeros(n,1);s=zeros(n,1);r1=zeros(n,1);r2=zeros(n,1);maxs1=0;fori=1:n-1forj=i+1:nfork=1:nr(k)=min(B(k,i),B(k,j));s(k)=W(k)*(1-r(k)/maxd);endss=sum(s);if(ss>=maxs1)maxs1=ss;i1=i;j1=j;d1=d;endendendnum1=0;num2=0;fork=1:nif(B(k,i1)<B(k,j1))num1=num1+1;se11(num1)=k;elsenum2=num2+1;se12(num2)=k;endendfprintf('\n問(wèn)題二結(jié)果：\n');fprintf('選取兩點(diǎn)時(shí)結(jié)果（%2d,%2d)=%5.2f\n',i1,j1,maxs1);fprintf('\n選%2的點(diǎn)有%2d個(gè)：\n',i1,num1);fori=1:num1;fprintf('%2d',se11(i));endfprintf('\n');fprintf('選%2d的點(diǎn)有%2d個(gè)：\n',j1,num2);fori=1:num2;fprintf('%2d',se12(i));endfprintf('\n');maxs2=0;fori=1:n-2forj=i+1:n-1forp=j+1:nfork=1:nr(k)=min(min(B(k,i),B(k,j)),B(k,p));s(k)=W(k)*(1-r(k)/maxd);endss=sum(s);if(ss>=maxs2)maxs2=ss;i2=i;j2=j;p2=p;r2=d;endendendendrse11=zeros(1,n);rnum1=0;rse12=zeros(1,n);rnum2=0;rse13=zeros(1,n);rnum3=0;fork=1:nif(B(k,i2)<=B(k,j2)&&B(k,i2)<=B(k,p2))rnum1=rnum1+1;rse11(rnum1)=k;elseif(B(k,j2)<=B(k,i2)&&B(k,j2)<=B(k,p2))rnum2=rnum2+1;rse12(rnum2)=k;elseif(B(k,p2)<=B(k,i2)&&B(k,p2)<=B(k,j2))rnum3=rnum3+1;rse13(rnum3)=k;endendfprintf('\n\n選取三點(diǎn)時(shí)的結(jié)果（%2d,%2d,%2d）=%5.2f\n',i2,j2,p2,maxs2);fprintf('\選取3點(diǎn)時(shí)情形：\n');fprintf('\n選取%2d的點(diǎn)有%2d個(gè)：\n',i2,rnum1);fori=1:rnum1;fprintf('%2d',rse11(i));endfprintf('\n');fprintf('\n選取%2d的點(diǎn)有%2d個(gè)：\n',j2,rnum2);fori=1:rnum2;fprintf('%2d',rse12(i));endfprintf('\n');fprintf('\n選取%2d的點(diǎn)有%2d個(gè)：\n',p2,rnum3);fori=1:rnum3;fprintf('%2d',rse13(i));endfprintf('\n');第三問(wèn)程序：n=50;A=zeros(n,n);fori=1:nforj=1:nif(i==j)A(i,j)=0;elseA(i,j)=100000;endendendA(1,2)=400;A(1,3)=450;A(2,4)=300;A(2,21)=230;A(2,47)=140;A(3,4)=600;A(4,5)=210;A(4,19)=310;A(5,6)=230;A(5,7)=200;A(6,7)=320;A(6,8)=340;A(7,8)=170;A(7,18)=160;A(8,9)=200;A(8,15)=285;A(9,10)=180;A(10,11)=150;A(10,15)=160;A(11,12)=140;A(11,14)=130;A(12,13)=200;A(13,34)=400;A(14,15)=190;A(14,26)=190;A(15,16)=170;A(15,17)=250;A(16,17)=140;A(16,18)=130;A(17,27)=240;A(18,19)=240;A(18,25)=180;A(19,20)=140;A(19,24)=175;A(20,21)=180;A(20,24)=190;A(21,22)=300;A(21,23)=270;A(21,47)=350;A(22,44)=160;A(22,45)=270;A(22,48)=180;A(23,24)=240;A(23,29)=210;A(23,30)=290;A(23,44)=150;A(24,25)=170;A(24,28)=130;A(26,27)=140;A(26,34)=320;A(27,28)=190;A(28,29)=260;A(29,31)=190;A(30,31)=240;A(30,42)=130;A(30,43)=210;A(31,32)=230;A(31,36)=260;A(31,50)=210;A(32,33)=190;A(32,35)=140;A(32,36)=240;A(33,34)=210;A(35,37)=160;A(36,39)=180;A(36,40)=190;A(37,38)=135;A(38,39)=130;A(39,41)=310;A(40,41)=140;A(40,50)=190;A(42,50)=200;A(43,44)=260;A(43,45)=210;A(45,46)=240;A(46,48)=280;A(48,49)=200;forj=1:nfori=1:j-1A(j,i)=A(i,j);endend[m,n]=size(A);B=zeros(m,n);B=A;forkk=1:4fori=1:nforj=1:nfork=1:nt=B(i,k)+B(k,j);ift<B(i,j)B(i,j)=t;endendendendB;if(sum(sum(B-A))==0)break;endA=B;endmaxd=max(max(B));pp=[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,