王冬菊

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

0 引 言

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

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

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

1 產(chǎn)銷不平衡運(yùn)輸問(wèn)題

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

(1)

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

(2)

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

(3)

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

2 改進(jìn)的算法

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

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

為便于理解，下面將結(jié)合具體實(shí)例來(lái)介紹。

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

表1 各造紙廠到各集中用戶的單位運(yùn)價(jià)表

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

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

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

改進(jìn)后最小元素法如下：

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

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

該調(diào)運(yùn)方案的總運(yùn)費(fèi)為：

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

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

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

3 結(jié) 語(yǔ)

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