【摘 要】本文主要介紹了數(shù)學(xué)建模中的一個(gè)常用的方法（Floyd算法）。我們首先介紹了鄰接矩陣的定義。其次，闡述了Floyd算法的具體內(nèi)容以及Floyd算法的改進(jìn)。最后，給出了Floyd算法的廣泛應(yīng)用，并且列舉了Floyd算法在交巡警服務(wù)平臺(tái)的設(shè)置、物流管理與運(yùn)輸管理方面、校車安排與站點(diǎn)優(yōu)化方面的應(yīng)用。其中不乏對(duì)現(xiàn)代數(shù)學(xué)軟件的應(yīng)用。最后給出具體應(yīng)用，以圖論知識(shí)為基礎(chǔ)，以MATLAB和軟件為工具，建立了數(shù)學(xué)模型，在計(jì)算機(jī)中具體的去操作。將實(shí)際問(wèn)題的相關(guān)數(shù)據(jù)轉(zhuǎn)化為一個(gè)帶權(quán)的鄰接矩陣，從而是問(wèn)題得到解決。

【關(guān)鍵詞】數(shù)學(xué)建模 Floyd算法 計(jì)算機(jī)

我們知道在工程、信息系統(tǒng)、通信和軍事等領(lǐng)域，最短路作為圖的一個(gè)經(jīng)典問(wèn)題一直有著廣泛的應(yīng)用。 頂點(diǎn)對(duì)之間的最短路徑是指:對(duì)于給定的有向，要對(duì)題目中任意一對(duì)頂點(diǎn)有序，找出到的最短距離和到的最短距離。

一、Floyd算法在交巡警平臺(tái)的設(shè)置的應(yīng)用

在未來(lái)的幾年發(fā)展中，在中國(guó)的所有地區(qū)的交通路口和重要路段都將設(shè)置交巡警服務(wù)平臺(tái)。這些交巡警服務(wù)平臺(tái)將會(huì)更有效的處理交通事故。但是因?yàn)榫焓敲Σ贿^(guò)來(lái)的，如何在各個(gè)城市合理地設(shè)置交巡警服務(wù)平臺(tái)、分配各平臺(tái)的管轄范圍呢？ 為了解決這個(gè)問(wèn)題，我們首先要建立了交通網(wǎng)絡(luò)的數(shù)學(xué)模型，將交通網(wǎng)絡(luò)的相關(guān)數(shù)據(jù)轉(zhuǎn)化為一個(gè)帶權(quán)即有具體數(shù)字的鄰接矩陣。

建立數(shù)學(xué)模（1）基本符號(hào)：表示出模型中第i個(gè)交巡警平臺(tái)，表示模型中第j個(gè)路口，表示模型中平臺(tái)的總數(shù)，表示模型中路口的總數(shù)（2）配置矩陣：我們用一個(gè)矩陣來(lái)為各交巡警平臺(tái)分配管轄范圍。表示平臺(tái)管轄路口。由于一個(gè)路口被一個(gè)平臺(tái)管轄，所以應(yīng)當(dāng)滿足條件。（3）平臺(tái)工作量計(jì)算公式，其中為配置矩陣，為發(fā)案率列向量，在此問(wèn)題中，平臺(tái)個(gè)數(shù)路口個(gè)數(shù)。決策變量為配置矩陣。由快速出警的原則，配置矩陣應(yīng)當(dāng)是在服務(wù)半徑為3km的預(yù)配置矩陣的基礎(chǔ)上進(jìn)行配置。即：約束條件可由預(yù)配置矩給出，由于一個(gè)路口只能由一個(gè)平臺(tái)管轄。目標(biāo)函數(shù)即工作量均衡性指標(biāo) 。

由假設(shè)汽車速度為60km/h或10m/min，計(jì)算得3分鐘內(nèi)距離為3000m。

通過(guò)計(jì)算得到A區(qū)任意兩點(diǎn)到達(dá)的最短時(shí)間矩陣T。

交巡警服務(wù)平臺(tái)管轄范圍（由僅考慮時(shí)間的T2矩陣得到）

為求得服務(wù)平臺(tái)工作的均衡，建立動(dòng)態(tài)規(guī)劃模型。運(yùn)用Floyd 算法構(gòu)造距Floyd最短路徑算法在配送中心選址中的應(yīng)用

現(xiàn)在隨著網(wǎng)購(gòu)的流行，買家對(duì)送貨的質(zhì)量和時(shí)間要求越來(lái)越高，這樣就出現(xiàn)了問(wèn)題。怎么樣以最少物流費(fèi)用達(dá)到最好的服務(wù)目標(biāo)，是現(xiàn)在需要解決的問(wèn)題。當(dāng)中自然少不了Floyd算法的應(yīng)用。具體在計(jì)算機(jī)中：

第一步，輸入帶權(quán)鄰接矩陣，賦初值：對(duì)所有 與的取值；第二步，更新原矩陣；

第三步，若原矩陣停止．否則繼續(xù)下一步．

（2）計(jì)算各頂點(diǎn)作為配送中心時(shí)的總費(fèi)用。第一步賦初值：對(duì)所有矩陣都進(jìn)行賦值 ，第二步更新矩陣： 第三步若運(yùn)算停止．否則繼續(xù)，轉(zhuǎn)第二步 （3）求出頂點(diǎn)，則該點(diǎn)就是最優(yōu)的配送中心頂點(diǎn)．

二、Floyd在校車安排與站點(diǎn)優(yōu)化方面的應(yīng)用

該問(wèn)題中涉及到求解最短距離以及教師及其他工作人員對(duì)這種安排的滿意度等問(wèn)題。關(guān)于這些問(wèn)題的解決，可以利用計(jì)算機(jī)求解結(jié)果，然后統(tǒng)一實(shí)施安排。

現(xiàn)在的大學(xué)也許都會(huì)建造新的校區(qū)，這樣的話，大學(xué)一般會(huì)把以前的大學(xué)里的教師和工作人員通過(guò)校車接送到新校區(qū)。為了使得人們更加舒適的乘車，怎么樣安排校車的時(shí)間和站牌的位置才更合理呢？下面給出一個(gè)問(wèn)題：如果建立n個(gè)乘車點(diǎn)，為使各區(qū)人員到最近乘車點(diǎn)的距離是最小的，我們會(huì)通過(guò)建立數(shù)學(xué)模型，通過(guò)對(duì)數(shù)據(jù)的仔細(xì)認(rèn)真的分析，利用Floyd 算法，求出最短路程。問(wèn)題要求建立個(gè)乘車點(diǎn)，使各區(qū)人員到最近乘車點(diǎn)的距離最小。我們就可以利用Floyd算法求得任意兩點(diǎn)之間最短距離；

其次在50個(gè)區(qū)域中任意選取個(gè)區(qū)域作為乘車點(diǎn)，，找出每個(gè)區(qū)域所對(duì)應(yīng)的最近乘車點(diǎn)；

最后以50個(gè)區(qū)域到各自最近乘車點(diǎn)的最短距離和的最小值為目標(biāo)函數(shù)建立模型。并對(duì)設(shè)立2個(gè)和3個(gè)乘車點(diǎn)時(shí)的校車安排問(wèn)題進(jìn)行求解。

下面我們可以看出本算法在這里面的應(yīng)用。

首先，我們?cè)?0個(gè)區(qū)域中選取n個(gè)區(qū)域當(dāng)作乘車點(diǎn)。其次，因?yàn)槊總€(gè)地方的乘客都會(huì)理所應(yīng)當(dāng)?shù)倪x距離本區(qū)最近的乘車點(diǎn)乘車，隨即引入變量，表示第個(gè)k區(qū)域到最近乘車點(diǎn)的距離。求出50個(gè)區(qū)域到各自最近乘車點(diǎn)的最短距離之和，建立針對(duì)問(wèn)題1所述的數(shù)學(xué)模型。最佳乘車點(diǎn)是使得50個(gè)區(qū)域到各自最近乘車點(diǎn)的距離之和最小的點(diǎn)，基于此建立目標(biāo)函數(shù)，其中所取點(diǎn)為選出的個(gè)最佳乘車點(diǎn)所在的區(qū)域號(hào)。依據(jù)模型，利用MATLAB軟件求得結(jié)果：當(dāng)時(shí)：乘車點(diǎn)設(shè)立在18區(qū)和31區(qū)，各個(gè)區(qū)域到各自最近乘車點(diǎn)的最短距離之和為Z=24492米。

選21區(qū)域有:1、2、3、4、19、20、21、22、23、24、44、45、46、47、48、49。

由結(jié)果可看出當(dāng)乘車點(diǎn)越多時(shí)，Z值越小。

在當(dāng)今日益復(fù)雜的社會(huì)形態(tài)下，利用Floyd算法的地方非常之多，比如在工程、地理信息、通信和軍事等方面均有重要的體現(xiàn)。

參考文獻(xiàn)：

[1］劉智勇，智能交通控制理論及其應(yīng)用［M］． 北京: 科學(xué)出版社， 2003．

[2] 繆成，許維勝，吳啟迪，等. 大規(guī)模應(yīng)急物資運(yùn)輸問(wèn)題的研究現(xiàn)狀與發(fā)展方向［J］. 新疆職業(yè)大學(xué)學(xué)報(bào)，2007，15(3):35 38.

[3] 唐邦民，謝晗昕.數(shù)據(jù)結(jié)構(gòu)與算法分析[M].北京:電子工業(yè)出版社，2005.

作者簡(jiǎn)介：

田席屹（1986-），男，漢族，山西沁水人，山西省沁水縣沁水中學(xué)