洪玲玲

摘 要：在保證救災(zāi)物資快速調(diào)運(yùn)的情況下且滿足各受災(zāi)地的需求，使總的費(fèi)用最小。根據(jù)實(shí)際情況建立相應(yīng)的運(yùn)輸問(wèn)題的數(shù)學(xué)模型，用最小費(fèi)用最大流理論求解。當(dāng)給出問(wèn)題中所涉及的所有參數(shù)的具體數(shù)值，該模型就可以用Mathematica或者LINDO軟件來(lái)求解，得到問(wèn)題的最優(yōu)救災(zāi)物資調(diào)運(yùn)方案，該問(wèn)題具有很好的通用性和實(shí)用性。

關(guān)鍵詞：最小費(fèi)用最大流；救災(zāi)物資；運(yùn)輸規(guī)劃

一、問(wèn)題的背景

我國(guó)是自然災(zāi)害多發(fā)的國(guó)家之一。因此嚴(yán)重的自然災(zāi)害一旦發(fā)生，就需要緊急調(diào)運(yùn)大量的救災(zāi)物資，用于搶險(xiǎn)救災(zāi)，所以如何快速調(diào)運(yùn)就是一個(gè)需要研究的實(shí)際問(wèn)題。在實(shí)際中，各種物資的儲(chǔ)存地與受災(zāi)地的位置不同、距離不同，物資的需求量也不同，有時(shí)或許還需要經(jīng)過(guò)中轉(zhuǎn)站等情況。當(dāng)然，在救災(zāi)物資的調(diào)運(yùn)過(guò)程中，包括運(yùn)輸和中轉(zhuǎn)等都是需要成本的。于是，怎么樣才能在保證快速調(diào)運(yùn)的情況下，使總的費(fèi)用最小。

二、問(wèn)題的提出

因某地區(qū)發(fā)生了嚴(yán)重的自然災(zāi)害，需要緊急調(diào)運(yùn)一批救災(zāi)物資，現(xiàn)在所掌握的情況是共有位于m個(gè)不同地方的倉(cāng)庫(kù)存有該種物資，并且第i個(gè)倉(cāng)庫(kù)的儲(chǔ)存量為ai（i=1，2，…m），根據(jù)不同受災(zāi)地的實(shí)際需求，共有n個(gè)受災(zāi)地需要這些物資，且第j個(gè)受災(zāi)地的需求量為bj（j=1，2，…n）。已知要將這批救災(zāi)物資從各個(gè)儲(chǔ)存?zhèn)}庫(kù)運(yùn)送到各受災(zāi)地時(shí)途中都需要經(jīng)過(guò)個(gè)中轉(zhuǎn)站之一，每啟用一次第個(gè)中轉(zhuǎn)站（無(wú)論轉(zhuǎn)運(yùn)量多少）均發(fā)生固定費(fèi)用fk（k=1，2，…p），且已知在要求的時(shí)間內(nèi)第k個(gè)中轉(zhuǎn)站的最大轉(zhuǎn)運(yùn)量為ck（k=1，2，…p），用dik和ekj分別表示從第i個(gè)儲(chǔ)存?zhèn)}庫(kù)到第k個(gè)中轉(zhuǎn)站和從第個(gè)中轉(zhuǎn)站到第j個(gè)受災(zāi)地的運(yùn)輸費(fèi)用?，F(xiàn)在的問(wèn)題是如何確定一個(gè)方案來(lái)快速調(diào)運(yùn)這批救災(zāi)物資，使得總的費(fèi)用最少。

三、問(wèn)題的分析

對(duì)問(wèn)題進(jìn)行分析可知，這個(gè)問(wèn)題是一個(gè)比較復(fù)雜的有中轉(zhuǎn)站的運(yùn)輸問(wèn)題。在該問(wèn)題中所產(chǎn)生的費(fèi)用來(lái)自3個(gè)方面，即從各個(gè)儲(chǔ)存地到某個(gè)中轉(zhuǎn)站的運(yùn)輸費(fèi)用、從中轉(zhuǎn)站到各個(gè)受災(zāi)地的運(yùn)輸費(fèi)用和每個(gè)中轉(zhuǎn)站的啟用費(fèi)用，因此這個(gè)問(wèn)題的優(yōu)化目標(biāo)為3個(gè)方面費(fèi)用之和的最小化。為了建立問(wèn)題的數(shù)學(xué)模型引入如下的決策變量：用xik表示從第i個(gè)儲(chǔ)存?zhèn)}庫(kù)到第k個(gè)中轉(zhuǎn)站的轉(zhuǎn)運(yùn)物資數(shù)量；用yki表示從第k個(gè)中轉(zhuǎn)站到第j個(gè)受災(zāi)地的運(yùn)輸物資數(shù)量；用lk表示0-1變量，當(dāng)啟用第k個(gè)中轉(zhuǎn)站時(shí)取值為1，當(dāng)不啟用第k個(gè)中轉(zhuǎn)站時(shí)取值為0.

四、模型的建立與求解

（一）模型的建立。

（二）模型求解。求解該不平衡的運(yùn)輸問(wèn)題有兩種方法。一是用運(yùn)輸單純形法，二是用網(wǎng)絡(luò)流中的最小費(fèi)用最大流思想。在這里主要介紹最小費(fèi)用最大流求解運(yùn)輸問(wèn)題。

最小費(fèi)用最大流的實(shí)質(zhì)：將問(wèn)題轉(zhuǎn)化為最短路問(wèn)題求解，即能求解救災(zāi)物資的快速調(diào)運(yùn)問(wèn)題。

定義：設(shè)f是一個(gè)可行流，如果存在一條從發(fā)點(diǎn)vs到收點(diǎn)vt的鏈，滿足：（1）所有前向弧上fij0，則該鏈稱(chēng)為增廣鏈，記為μ，前向弧集合記為μ+，后向弧集合記為μ-。定理：設(shè)f是最小費(fèi)用流，而μ是關(guān)于f的所有增廣鏈中費(fèi)用最小的一條，則在μ上對(duì)f進(jìn)行調(diào)整后所得到的新流仍是最小費(fèi)用流。

五、模型的評(píng)價(jià)

這里給出了具有一般意義的運(yùn)輸規(guī)劃模型，如果能夠給出問(wèn)題中的所有參數(shù)的具體數(shù)值，該模型就可以用Mathematica或者LINDO軟件來(lái)求解，得到問(wèn)題的最優(yōu)救災(zāi)物資的調(diào)運(yùn)方案。該問(wèn)題具有很好的通用性和實(shí)用性，在實(shí)際中可以根據(jù)災(zāi)情的變化及最低需求量來(lái)改變運(yùn)輸方案。

參考文獻(xiàn)：

[1] 熊偉. 運(yùn)籌學(xué)[M]. 北京：機(jī)械工業(yè)出版社，2009.9.

[2] 邱攀，胡圣能. 網(wǎng)絡(luò)流理論在地震救災(zāi)物資運(yùn)輸模型中的應(yīng)用[J]. 物流科技，2010年第三期.