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