校車安排問題

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