摘要：針對救災(zāi)物資運(yùn)輸方特征，在滿足各災(zāi)區(qū)救災(zāi)物資需求量的前提下使運(yùn)輸時間最短，運(yùn)用最短時間最大流理論建立數(shù)學(xué)模型，討論了該理論在地震救災(zāi)物資運(yùn)輸中的運(yùn)用，最后給出一個算例驗(yàn)證了該模型的有效性。
　　關(guān)鍵詞：最短時間最大流；救災(zāi)物資；運(yùn)輸
　　隨著近些年自然災(zāi)害突發(fā)事件頻頻出現(xiàn)，應(yīng)急救援物資運(yùn)輸理論成為各國學(xué)者研究的重點(diǎn)。應(yīng)急救援往往具有很強(qiáng)的時間約束，本文在對最短時間最大流理論研究的基礎(chǔ)上，建立應(yīng)急救災(zāi)物資運(yùn)輸數(shù)學(xué)模型，得出在滿足各災(zāi)區(qū)救災(zāi)物資最小需求的前提下，以最短的運(yùn)輸時間將救災(zāi)物資運(yùn)送到各災(zāi)區(qū)。
　　1最短時間最大流理論[1-3]
　　定義1：整個應(yīng)急物流網(wǎng)絡(luò)可以分解為若干條自起點(diǎn)到終點(diǎn)的鏈，每條鏈由若干個弧組成，若鏈上弧的方向與鏈的方向相同（起點(diǎn)到終點(diǎn)），則稱這個弧為鏈的正向弧,記為；否則稱為逆向弧，記為。
　　定義2：設(shè)是一個可行流，是從起點(diǎn)到終點(diǎn)的一條鏈，若滿足下列條件，則稱之為一條增廣鏈。（1）在弧上，，即中每一條弧是非飽和弧；（2）在弧上，，即中每一條弧是非飽和弧。
　　1.2最短時間最大流問題的描述
　　在網(wǎng)絡(luò)中，對應(yīng)每一條弧，除了已給弧的容量外，還給了一個單位流量通過弧的費(fèi)用。是的一條可行流，則其總費(fèi)用為。則求使得為最小且流量最大的問題稱為最短時間最大流問題。
　　1.3最短時間最大流理論的算法思想
　　若是流量為的可行流中費(fèi)用最小者，而是關(guān)于的所有增廣鏈中費(fèi)用最小的增廣鏈，那么沿著以去調(diào)整，得到的可行流就是流量為（）的所有可行流中的最短時間流。這樣，當(dāng)為最大流時，它也就是我們所要求的最短時間最大流了。根據(jù)這個結(jié)論，如果已知是流值為的最短時間流，則關(guān)鍵是要求出關(guān)于的最短時間的增廣鏈。為此，需要在原網(wǎng)絡(luò)的基礎(chǔ)上構(gòu)造一個新的賦權(quán)有向圖，使其頂點(diǎn)與的頂點(diǎn)相同，且將中每條弧均變成兩個方向相反的弧和。新圖中各弧的權(quán)值與中弧的權(quán)值有密切關(guān)系，圖中各弧的權(quán)值定義為:
　　
　　
　　由增廣鏈費(fèi)用的概念及圖中權(quán)的定義可知，在網(wǎng)絡(luò)中尋求關(guān)于可行流的最短時間增廣鏈，等價于在圖中尋求從源點(diǎn)到匯點(diǎn)的最短路。
　　2數(shù)學(xué)模型
　　2.1救災(zāi)物資模型建立
　　自然災(zāi)害突發(fā)時間救災(zāi)物資運(yùn)輸要求在滿足各災(zāi)區(qū)救災(zāi)物資需求的前提下，以最短的時間用將盡可能多的救災(zāi)物資從各救災(zāi)物資收集點(diǎn)運(yùn)送到各災(zāi)區(qū)，因此，假設(shè)運(yùn)輸時間與數(shù)量成線性關(guān)系。定義兩個常量和。為運(yùn)送物資從第救災(zāi)物資收集點(diǎn)到第災(zāi)區(qū)所需時間；為從第救災(zāi)物資收集點(diǎn)到第災(zāi)區(qū)運(yùn)送救災(zāi)物資的數(shù)量。構(gòu)建模型如下：
　　式中為第個倉庫的物資儲備數(shù)量；為第個災(zāi)區(qū)至少所需要的物資數(shù)量；為從第個倉庫到第個災(zāi)區(qū)道路運(yùn)輸能力；表示起點(diǎn)，表示終點(diǎn)。第1個約束條件表示各節(jié)點(diǎn)救災(zāi)物資流量守恒；第2個約束條件表示從第個倉庫到第個災(zāi)區(qū)救災(zāi)物資運(yùn)輸量必須在運(yùn)輸能力范圍內(nèi)。第3個約束條件表示從第個倉庫運(yùn)走的所有物資數(shù)量必須小于第個倉庫的物資儲備量；第4個約束條件表示運(yùn)送到第個災(zāi)區(qū)的所有物資數(shù)量必須不小于第個災(zāi)區(qū)最少需求量。
　　2.2模型求解
　　該模型求解過程是對單一源點(diǎn)到單一匯點(diǎn)進(jìn)行的，當(dāng)救災(zāi)物資運(yùn)輸問題涉及到多個儲存物資的倉庫(源點(diǎn))和多個需求物資的水庫(匯點(diǎn))時就需要引進(jìn)點(diǎn)作為單源，引進(jìn)點(diǎn)作為單匯。
　　定義1：規(guī)定從點(diǎn)到第個倉庫的道路運(yùn)輸能力為個倉庫的物資儲備量，從點(diǎn)運(yùn)送到第個倉庫的單位物資運(yùn)輸時間為0；
　　定義2：規(guī)定從第個災(zāi)區(qū)到點(diǎn)的道路運(yùn)輸能力為，從第個災(zāi)區(qū)運(yùn)送到點(diǎn)的單位物資運(yùn)輸時間為0。
　　這樣一來，運(yùn)輸?shù)目倳r間不會變，也可以應(yīng)用最小費(fèi)用最大流算法對模型進(jìn)行求解。求解步驟如下:
　　(1)確定初始可行流，它是運(yùn)輸量為0的最短時間流；
　　(2)記為經(jīng)k次調(diào)整得到的最短時間流，構(gòu)造賦權(quán)有向圖；
　　(3)在賦權(quán)有向圖中尋求從源點(diǎn)到匯點(diǎn)的最短時間路(調(diào)用Dijkstra算法)，若不存在最短時間路，則就是最短時間最大運(yùn)量流，計算終止；若存在最短時間路，則此最短時間路即為原網(wǎng)絡(luò)中相應(yīng)的增廣鏈,轉(zhuǎn)入下一步；
　　(4)在增廣鏈μ上對進(jìn)行調(diào)整,調(diào)整量為:
　　令
　　(5)得到新的可行流,使流值增大,令,返回到第(2)步驟。
　　3結(jié)語
　　該模型可以求解出任意的對應(yīng)于某個最低運(yùn)輸量的運(yùn)輸方案，即只要給定災(zāi)區(qū)的最低需求量，就可以根據(jù)最小費(fèi)用最大流理論求解出在這個最低運(yùn)輸量限制下的運(yùn)輸方案，實(shí)際中可以根據(jù)災(zāi)情的變化，隨時根據(jù)災(zāi)區(qū)的實(shí)際需求量，改變運(yùn)輸方案。
　　參考文獻(xiàn)
　　[1]歐忠文,王會云,姜大力等.應(yīng)急物流[J].重慶大學(xué)學(xué)報,2004,27(3):164-167.
　　[2]李德,錢頌迪.運(yùn)籌學(xué)[M].北京:清華大學(xué)出版社,1982.
　　[3]郭耀煌等.運(yùn)籌學(xué)原理與方法[M].成都:西南交通大學(xué)出版社,2000.