產(chǎn)銷不平衡運輸問題初始方案的改進—基于表上作業(yè)法①

王冬菊

(安徽師范大學皖江學院 管理系，安徽蕪湖 241000)

0 引 言

運輸問題是運籌學中一類特殊的線性規(guī)劃問題[1]，經(jīng)典的運輸問題是針對單一品種物資的運輸調(diào)度方案的研究[2]。由于產(chǎn)銷平衡的運輸問題的約束系數(shù)矩陣的特殊性，使用表上作業(yè)法可以較高效地實現(xiàn)手工求解。表上作業(yè)法本質(zhì)仍是單純形法，基本思想與單純形法相似，具體步驟如圖1所示。

圖1 產(chǎn)銷平衡運輸問題表上作業(yè)法流程

其中求解初始調(diào)運方案的確定至關重要[3]，常用的方法有最小元素法和沃格爾(Vogel)法和西北角法等，尤其是最小元素法。然而實際運輸問題多為產(chǎn)銷不平衡運輸問題，即總產(chǎn)量與總銷量并不相等。使用最小元素法求解產(chǎn)銷不平衡運輸問題時容易出現(xiàn)多次迭代影響求解效率的情況。本文正是探討如何使用最小元素法確定產(chǎn)銷不平衡運輸問題初始調(diào)運方案從而盡可能地減少調(diào)整次數(shù)以提升計算效率。

1 產(chǎn)銷不平衡運輸問題

對于產(chǎn)銷不平衡的運輸問題應先將其轉(zhuǎn)換為產(chǎn)銷平衡再使用表上作業(yè)法求解。

(1)

因供大于求，因此增加一個虛擬的銷地(或倉庫)Bn+1,其銷量需求bn+1為公式(2)：

(2)

由于銷地Bn+1并非真實存在，因而從產(chǎn)地Ai(i=1,2,…,3)調(diào)運到這個虛擬銷地的物品數(shù)量xi,n+1實際上是就地存儲在Ai的物品數(shù)量，不會發(fā)生運輸，因此其單位運價ci,n+1=0，(i=1,2,…,m)。那么模型公式(1)將轉(zhuǎn)換為如下產(chǎn)銷平衡的運輸問題，如公式(3)：

(3)

借助增加虛擬銷地(或倉庫)或虛擬產(chǎn)地可將產(chǎn)銷不平衡的運輸問題轉(zhuǎn)化為產(chǎn)銷平衡問題，進而使用表上作業(yè)法實現(xiàn)求解[4-5]。

2 改進的算法

前一節(jié)最后提到的問題可通過如下規(guī)則得到很大程度的改進：

使用最小元素法求存在虛擬產(chǎn)地(或虛擬銷地)的運輸問題初始調(diào)運方案時，不考慮因引入的虛擬產(chǎn)地(或虛擬銷地)而增加的為零的單位運價，直接從產(chǎn)銷不平衡運輸問題原有的單位運價表按照最小元素法的步驟求解。

為便于理解，下面將結合具體實例來介紹。

例1(摘自文獻[2]p95)某市有三個造紙廠A1,A2和A3，其紙的產(chǎn)量分別為8個單位、5個單位和9個單位，有4個集中用戶B1,B2,B3和B4，其需用量分別為4個單位、3個單位、5個單位和6個單位。由各造紙廠到各用戶的單位運價如表1所示，用表上作業(yè)法確定總運費最少的調(diào)運方案。

表1 各造紙廠到各集中用戶的單位運價表

解：該問題的總產(chǎn)量為22個單位大于總銷量18個單位，因此本問題為產(chǎn)銷不平衡運輸問題。假設有一虛擬用戶B5，且其需用量為4個單位，三個造紙廠運往虛擬用戶B5的單位運價ci5=0,(i=1,2,3)，這樣原問題將被轉(zhuǎn)換為產(chǎn)銷平衡問題，此時轉(zhuǎn)換后的對應產(chǎn)銷供需量和單位運價表如表2所示。

表2 轉(zhuǎn)換后的產(chǎn)銷供需量和單位運價表

根據(jù)表上作業(yè)法求解的求解步驟，應首先確定初始調(diào)運方案。

改進后最小元素法如下：

按照前文的改進規(guī)則，使用最小元素法確定初始調(diào)運方案時，確定最小單位運價時忽略ci5=0,(i=1,2,3)，只在原問題的所有單位運價cij(i=1,2,3;j=1,2,3,4)范圍內(nèi)尋找。那么最先找到的最小單位運價應為c33=1，在單元格(A3,B3)中填入最大的運輸量5，則集中用戶B3的銷量需求已滿足，將該列劃去同時把造紙廠A3的產(chǎn)量剩余量修改為4。然后再從剩下的單元格中尋找最小單位運價，為c22=2，盡量滿足其所在單元格(A2,B2)對應供銷關系即x22=3，則集中用戶B2的銷量需求已滿足，將B2列劃去同時把造紙廠A2的產(chǎn)量剩余量修改為2。重復此過程直至得到如下表3中的初始調(diào)運方案。

表3 初始調(diào)運方案

該調(diào)運方案的總運費為：

z1=4×3+2×4+2×0+3×2+2×0+5×1+4×5=51

顯然該調(diào)運方案較初始調(diào)運方案一總運費少了10個單位。類似地使用閉回路法或位勢法對其進行最優(yōu)性判別，由于存在空格檢驗數(shù)為負σ35=-1，因此也需要對其進行調(diào)整。但僅需調(diào)整一次即可得到表5中的最優(yōu)調(diào)運方案。

通過比較改進算法和經(jīng)典算法的計算過程可知，使用改進后的算法求得的初始調(diào)運方案明顯優(yōu)于原算法，計算效率得到大幅提升。

3 結 語

對于由產(chǎn)銷不平衡運輸問題轉(zhuǎn)換得到的產(chǎn)銷平衡運輸問題求解時，由于存在多個最小的值為零的單位運價，選擇何者作為最開始的最小單位運價會對獲得的初始調(diào)運方案的質(zhì)量影響很大。針對此類問題提出了改進規(guī)則，即在選擇最小單位運價時不考慮因引入的虛擬產(chǎn)地或虛擬銷地增加的值為零的單位運價，只在原有的實際單位運價范圍內(nèi)確定。運用此改進算法可以有效減少表上作業(yè)法方案調(diào)整的工作量，簡化求解此類問題最優(yōu)解的過程。