李 敏

（湖北文理學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖北 襄陽(yáng) 441053）

運(yùn)輸問題可描述為：已知某物資有m個(gè)產(chǎn)地Ai，i=1，2，…m，其產(chǎn)量分別為 ai，i=1，2，…m。有 n 個(gè)銷地 Bj，j=1，2，…n。銷量分別為 bj，j=1，2，…n。從 Ai到 Bj的最短時(shí)間為 cij，問如何組織調(diào)運(yùn)，才能使完成調(diào)運(yùn)任務(wù)的總時(shí)間最短?雖然運(yùn)輸問題是線性規(guī)劃問題，但由于它的特殊結(jié)構(gòu)，并不采用線性規(guī)劃的單純形法來求解，一般都是利用表上作業(yè)法來求解的，后來人們又陸續(xù)提出了各種簡(jiǎn)易的算法。文章則是在運(yùn)輸時(shí)間不固定的情況下，基于簡(jiǎn)算法及對(duì)角線調(diào)整法給出了一種能快速找到最優(yōu)運(yùn)輸方案的新算法。

1 時(shí)間不固定的運(yùn)輸問題的數(shù)學(xué)模型

在上述運(yùn)輸問題的描述中，將從Ai到Bj的最短時(shí)間改為fij（xij）=aijxij+cij，其中cij為僅依賴于運(yùn)輸距離長(zhǎng)短的基礎(chǔ)運(yùn)輸時(shí)間，aij為影響系數(shù)，xij為產(chǎn)地Ai到銷地Bj的運(yùn)量，在產(chǎn)銷平衡條件情況下其數(shù)學(xué)模型為：

2 時(shí)間不固定的運(yùn)輸問題的求解

由于產(chǎn)銷不平衡運(yùn)輸問題可以通過添加虛擬的產(chǎn)地或銷地而化為產(chǎn)銷平衡運(yùn)輸問題，因此下面僅針對(duì)平衡運(yùn)輸問題展開敘述。

2.1 算法思想

簡(jiǎn)算法是求解單目標(biāo)最短時(shí)限的算法，它可求出完成任務(wù)的最短時(shí)限，但卻不一定使時(shí)間總和達(dá)到最優(yōu)。在產(chǎn)銷平衡條件，本算法的思想為：首先找到完成調(diào)運(yùn)任務(wù)的僅依賴于運(yùn)輸距離長(zhǎng)短的基礎(chǔ)運(yùn)輸時(shí)間的最短時(shí)限，即min max｛cij|xij＞ ｝

0的最優(yōu)解T，則C=（cij）中一定存在m+n-1個(gè)不大于T的元素，使目標(biāo)（1）最少。

2.2 算法步驟

Step1找基礎(chǔ)運(yùn)輸時(shí)間的最短時(shí)限。T1=max，其中

Step2將基礎(chǔ)運(yùn)輸時(shí)間矩陣C中不大于T1的元素全部標(biāo)出，并記為矩陣 C（T1）。

Step3首先對(duì)C（T1）中行和列中大于T1的元素和最大的行或列開始調(diào)運(yùn)，對(duì)行（列），如不能將該產(chǎn)地（銷地）的產(chǎn)量（銷量）按照“先小后大”全部給不大于T1的元素，則轉(zhuǎn)Step4。否則，劃去該行（列）所有元素，再對(duì)剩余的行和列重復(fù)此操作，直至找到關(guān)于的最優(yōu)運(yùn)輸方案，再轉(zhuǎn)Step5。

Step5任取以具有調(diào)運(yùn)量的元素為對(duì)角頂點(diǎn)的矩形，檢查該對(duì)角線上兩頂點(diǎn)的aijxij+cij的和，如大于另一對(duì)角線上兩頂點(diǎn)的aijxij+cij的和，且另一對(duì)角線上兩頂點(diǎn)中至少有一元素不大于T1，則在保證不給大于T1的元素調(diào)運(yùn)的前提下按實(shí)際可調(diào)整的量重新調(diào)運(yùn)，否則，保持不變。重復(fù)該過程，直至找到最優(yōu)運(yùn)輸方案。

3 算例

某地區(qū)發(fā)生地震災(zāi)害，發(fā)現(xiàn)有2個(gè)村莊B1、B2受災(zāi)，需從3個(gè)城市A1，A2，A3緊急調(diào)運(yùn)救災(zāi)物資。已知3個(gè)城市可調(diào)出的救災(zāi)物資量分別為6t、5t和7t；2個(gè)村莊的物資需求量分別為7t和8t。已知運(yùn)輸時(shí)間函數(shù)為fij（xij）=aijxij+cij，其中cij為僅依賴于運(yùn)輸距離長(zhǎng)短的基礎(chǔ)運(yùn)輸時(shí)間（表1），aij為影響系數(shù)（表2）。另外，地震造成了A1到B2的道路中斷，問如何組織調(diào)運(yùn)才能使救災(zāi)物資到達(dá)所用總時(shí)間最短。

表1 cij和運(yùn)輸物資量

表2 影響系數(shù)aij

解 因?yàn)榭偣?yīng)量（6+5+7=18）大于總需求量（7+8=15），所以這是一個(gè)產(chǎn)銷不平衡運(yùn)輸問題，故需要虛擬一個(gè)銷地B3，且各產(chǎn)地到它的基礎(chǔ)運(yùn)輸時(shí)間 ci3=0（i=1，2，3）。又因?yàn)榈卣鹪斐闪薃1到B2的道路中斷，所以A1到B2

是禁運(yùn)的，故將其基礎(chǔ)運(yùn)輸時(shí)間c12和影響系數(shù)a12都更改為∞，則C變?yōu)镃′。因?yàn)锽1、B2的需求要全部滿足，所以必須優(yōu)先考慮它們，故由C及Step1得，T1=19。將C′中屬于C的且不大于T1的元素做上標(biāo)記，并記為矩陣C′（T1）：

顯然，第5次分配給了大于T1的元素21，故轉(zhuǎn)step4，得T2=21，則有：

經(jīng)對(duì)角線檢驗(yàn)，可知已得最優(yōu)運(yùn)輸方案，總時(shí)間Z=113。通過與文獻(xiàn)［4］比較發(fā)現(xiàn)，本算法所得總時(shí)間要少得多，且計(jì)算更簡(jiǎn)單。對(duì)于小規(guī)模問題可以手工操作，對(duì)于大規(guī)模問題可編程實(shí)現(xiàn)，因此具有較強(qiáng)的可操作性和適用性。

［1］李敏.運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用［M］.武漢：武漢大學(xué)出版社，2014.

［2］張勁松.農(nóng)業(yè)運(yùn)輸問題的新算法［J］.安徽農(nóng)業(yè)科學(xué)，2009，37（10）：4645-4646.

［3］白國(guó)仲.線性不可微規(guī)劃—基于可持續(xù)發(fā)展的決策技術(shù)［M］.北京：中國(guó)社會(huì)科學(xué)出版社，2007.

［4］董麗，周強(qiáng)，郭淑利.一類產(chǎn)銷不平衡最短時(shí)限運(yùn)輸問題的求解［J］.2009，22（4）：503-506.