時間不固定的運輸問題的求解研究

李 敏

（湖北文理學院 數(shù)學與計算機科學學院，湖北 襄陽 441053）

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

1 時間不固定的運輸問題的數(shù)學模型

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

2 時間不固定的運輸問題的求解

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

2.1 算法思想

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

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

2.2 算法步驟

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

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

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

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

3 算例

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

表1 cij和運輸物資量

表2 影響系數(shù)aij

解 因為總供應量（6+5+7=18）大于總需求量（7+8=15），所以這是一個產(chǎn)銷不平衡運輸問題，故需要虛擬一個銷地B3，且各產(chǎn)地到它的基礎(chǔ)運輸時間 ci3=0（i=1，2，3）。又因為地震造成了A1到B2的道路中斷，所以A1到B2

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

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

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

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

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

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

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