邱 攀， 胡圣能 （華北水利水電學(xué)院，河南 鄭州 450011）

地震是對人類生存安全危害最大的自然災(zāi)害之一。2007年全世界有災(zāi)情的地震共計13次，經(jīng)濟損失總數(shù)達(dá)200億美元。2008年中國汶川8.0級大地震是新中國成立以來破壞性最強、涉及范圍最廣、救災(zāi)難度最大的一次地震，重災(zāi)區(qū)面積達(dá)10萬平方公里；地震直接經(jīng)濟損失超過1萬億元人民幣。地震的一大特點就是突發(fā)性強，以目前的預(yù)報水平，還不能準(zhǔn)確地知道在什么時候、什么地方、發(fā)生多大地震，這就要求必須提高地震應(yīng)急反應(yīng)能力。

所謂應(yīng)急物流，就是指以提供突發(fā)性自然災(zāi)害、突發(fā)性公共衛(wèi)生事件等突發(fā)性事件所需應(yīng)急物資為目的，以追求時間效益最大化和災(zāi)害損失最小化為目標(biāo)的特種物流活動[1]。我國是世界上地震活動最強烈和地震災(zāi)害最嚴(yán)重的國家之一，歷次地震災(zāi)害都造成了建筑損毀、人員死傷、交通中斷等巨大損失。在災(zāi)害發(fā)生時，盡管各級政府均積極成立救災(zāi)指揮中心以及救災(zāi)專門小組，但面對復(fù)雜的道路交通情況和各地救災(zāi)物資需求量的不同，如果不統(tǒng)籌安排會造成運輸費用增加，局部救災(zāi)物資短缺或過剩，會影響搶救生命財產(chǎn)的進(jìn)度和社會穩(wěn)定。這就給決策者提出一個問題：怎樣在滿足各受災(zāi)地區(qū)物資最小需求的前提下，以最低的運輸費用將盡可能多的救災(zāi)物資運送到各災(zāi)區(qū)。本文在對最小費用最大流理論研究的基礎(chǔ)上，建立地震救災(zāi)物資運輸數(shù)學(xué)模型，得出在滿足各災(zāi)區(qū)救災(zāi)物資最小需求的前提下，以最低的運輸費用將救災(zāi)物資運送到各災(zāi)區(qū)的運輸方案。

1 最小費用最大流理論[2－4]

定義1整個應(yīng)急物流網(wǎng)絡(luò)可以分解為若干條自起點vs到終點vt的鏈，每條鏈由若干個弧組成，若鏈上弧的方向與鏈的方向相同 （起點到終點），則稱這個弧為鏈的正向弧，記為u+；否則稱為逆向弧，記為u－。

定義2一個可行流，u是從起點vs到終點vt的一條鏈，若u滿足下列條件，則稱之為一條增廣鏈。

（1） 在弧 （ vi, vj）∈u+上，0≤qi,j＜ci,j， 即u+中每一條弧是非飽和弧； （2） 在弧 （vi, vj）∈u－上，即 u－中每一條弧是非飽和弧。

1.1 最小費用最大流問題的描述。 在網(wǎng)絡(luò)D=（V,A,C ）中， 對應(yīng)每一條弧 （vi, vj）∈A， 除了已給弧 （vi,vj）的容量ci,j（ci,j＞0 ）外， 還給了一個單位流量通過弧 （vi,vj）的費用fi,j（fi,j＞0D的一條可行流，則其總費用為則求使最小且流量大的問題稱為最小費用最大流問題。

1.2 最小費用最大流理論的算法思想。若q是流量為v（q ）的可行流中費用最小者，而u是關(guān)于q的所有增廣鏈中費用最小的增廣鏈，那么沿著u以ε去調(diào)整q，得到的可行流q'就是流量為v（ q'）（v（ q'）=v（q）+ε ）的所有可行流中的最小費用流。這樣，當(dāng)q'為最大流時，它也就是我們所要求的最小費用最大流了。根據(jù)這個結(jié)論，如果已知q是流值為v（q ）的最小費用流，則關(guān)鍵是要求出關(guān)于q的最小費用的增廣鏈。為此，需要在原網(wǎng)絡(luò)D的基礎(chǔ)上構(gòu)造一個新的賦權(quán)有向圖h（q ），使其頂點與D的頂點相同， 且將D中每條弧 （vi, vj）均變成兩個方向相反的弧 （vi, vj）和（vj, vi）。 新圖h（q ）中各弧的權(quán)值與q中弧的權(quán)值有密切關(guān)系，圖h（q ）中各弧的權(quán)值定義為：

由增廣鏈費用的概念及圖h（q ）中權(quán)的定義可知，在網(wǎng)絡(luò)D中尋求關(guān)于可行最小費用增廣鏈，等價于在圖h（q）中尋求從源點到匯點的最短路。

2 數(shù)學(xué)模型

2.1 救災(zāi)物資模型建立。地震救災(zāi)物資運輸要求在滿足各災(zāi)區(qū)救災(zāi)物資需求的前提下，以最低的運輸費用將盡可能多的救災(zāi)物資從各救災(zāi)物資收集點運送到各災(zāi)區(qū)，這要求考慮3個問題： （1）滿足各災(zāi)區(qū)的最低物資需求； （2）在滿足最低物資需求的前提下，將盡可能多的物資從各救災(zāi)物資收集點運送到災(zāi)區(qū)； （3）總運輸費用最小。為了更好地處理這3個問題，我們定義兩個常量fij和qij。fij為運送單位救災(zāi)物資從第i救災(zāi)物資收集點到第j災(zāi)區(qū)所需費用，qij為從第i救災(zāi)物資收集點到第j災(zāi)區(qū)運送救災(zāi)物資的數(shù)量。這樣以總運輸費用最小和救災(zāi)物資運輸量最大為目標(biāo)函數(shù)，以各救災(zāi)物資收集點的物資儲備量、道路運輸能力、各災(zāi)區(qū)所需要的最小物資量為約束條件構(gòu)造模型如下：

式中pi為第i個倉庫的物資儲備數(shù)量，wi為第j個災(zāi)區(qū)至少所需要的物資數(shù)量，cij為從第i個倉庫到第j個災(zāi)區(qū)道路運輸能力，s表示起點，t表示終點。第1個約束條件表示各節(jié)點救災(zāi)物資流量守恒；第2個約束條件表示從第i個倉庫到第j個災(zāi)區(qū)救災(zāi)物資運輸量必須在運輸能力范圍內(nèi)。第3個約束條件表示從第i個倉庫運走的所有物資數(shù)量必須小于第i個倉庫的物資儲備量；第4個約束條件表示運送到第j個災(zāi)區(qū)的所有物資數(shù)量必須不小于第j個災(zāi)區(qū)最少需求量。

2.2 模型求解。最小費用最大流理論的求解過程是對單一源點到單一匯點進(jìn)行的，當(dāng)救災(zāi)物資運輸問題涉及到多個儲存物資的倉庫 （源點）和多個需求物資的倉庫 （匯點）時就需要引進(jìn)s點作為單源，引進(jìn)t點作為單匯。

定義1規(guī)定從s點到第i個倉庫的道路運輸能力為i個倉庫的物資儲備量，從s點運送到第i個倉庫的單位物資運輸費用為0；

定義2規(guī)定從第j個災(zāi)區(qū)到t點的道路運輸能力為+∞，從第j個災(zāi)區(qū)運送到t點的單位物資運輸費用為0。

這樣一來，運輸?shù)目傎M用不會變，也可以應(yīng)用最小費用最大流算法對模型進(jìn)行求解。求解步驟如下:（1）確定初始可行流它是運輸量為0的最小費用流； （2）經(jīng)k次調(diào)整得到的最小費用流，構(gòu)造賦權(quán)有向圖（3） 在賦權(quán)有向圖尋求從源點vs到匯點vt的最小費用路 （調(diào)用Dijkstra算法），若不存在最小費用路，是最小費用最大運量流，計算終止；若存在最小費用路，則此最小費用路即為原網(wǎng)絡(luò)D中相應(yīng)的增廣鏈u，轉(zhuǎn)入下一步； （4）在增廣鏈μ上行調(diào)整，調(diào)整量為：（5）得到新的可行流使流值增大，令k=k+1，返回到第 （2）步驟。

3 結(jié)束語

利用最小費用最大流理論時應(yīng)注意流的可行性和經(jīng)濟性。實際網(wǎng)絡(luò)中的流必須是可行流，其流量不可以超過最大流量，費用不會低于最小費用時的費用。最小費用最大流理論可以求解出任意的對應(yīng)于某個最低運輸量的運輸方案，即只要給定災(zāi)區(qū)的最低需求量，就可以根據(jù)最小費用最大流理論求解出在這個最低運輸量限制下的運輸方案，實際中可以根據(jù)災(zāi)情的變化，隨時根據(jù)災(zāi)區(qū)的實際需求量，改變運輸方案。

[1] 歐忠文，王會云，姜大力,等.應(yīng)急物流[J].重慶大學(xué)學(xué)報，2004,27(3):164-167.

[2] 李德，錢頌迪.運籌學(xué)[M].北京：清華大學(xué)出版社，1982.

[3] 劉家壯，徐源.網(wǎng)絡(luò)最大化[M].北京：高等教育出版社，1991.

[4] 郭耀煌,等.運籌學(xué)原理與方法[M].成都：西南交通大學(xué)出版社，2000.