基于表上作業(yè)法確定貨物運輸?shù)淖顑?yōu)調(diào)配方案

李國蓉

(渤海大學數(shù)學科學學院 遼寧錦州 121013)

隨著經(jīng)濟的深入發(fā)展，運輸業(yè)致力于打造“綠色、節(jié)約”的運輸環(huán)境。而在鐵路運輸中，不乏出現(xiàn)運輸成本高、貨物運輸物流繁瑣的問題[1]，并且在各地方之間存在著貨物運輸和調(diào)配問題。如何有效地減小運輸成本并提高貨物運輸效率，從而更好地實現(xiàn)經(jīng)濟全球化、利益最大化是一個值得研究的課題。

上述的貨物調(diào)配問題很明顯可以看成是一個線性規(guī)劃模型。一般地，將物資運輸問題描述如下：某物資有n個產(chǎn)地Ai，i=1，2，…，n，產(chǎn)地Ai的產(chǎn)量為ai，i=1，2，…，n；有m個銷地Bj，j=1，2，…，m，銷地Bj的需求量為bj，j=1，2，…，m；從各產(chǎn)地到各銷地的單位物資運費為cij，尋求從產(chǎn)地運往銷地總運費最小的運輸方案，數(shù)學模型如下：

設xij為產(chǎn)地i送往銷地j的運輸量，則滿足：

在運輸問題的模型上，可采用一種更簡便的算法——表上作業(yè)法[2]。

1 表上作業(yè)法

表上作業(yè)法[3]是求解運輸問題的一種有效方法，算法如下：

步驟1：列出產(chǎn)銷平衡表和運價表(見表1，表2)

表1 產(chǎn)銷平衡表

表2 產(chǎn)銷運價表

步驟2：確定初始運輸方案。

確定初始運輸方案有以下幾種方法：

方法一：西北角法

優(yōu)先考慮產(chǎn)銷平衡表左上角的產(chǎn)地，銷地從左到右進行調(diào)配。若產(chǎn)地滿足該銷地的需求，并且有多余，則考慮下一個銷地。若產(chǎn)地不足該銷地的需求，則從下一個產(chǎn)地進行調(diào)配，以滿足該銷地的需求，由此可得出初始調(diào)配方案。

方法二：最小元素法

從單位運價表中依次找出最小運價所在地優(yōu)先供給，比較產(chǎn)量和銷量，以判斷劃去行或列。在未劃線的運價元素中再挑出最小的運價元素，重復上述過程。由此可得出初始調(diào)配方案。

方法三：行伏格爾法

在單位運價表中，比較同一產(chǎn)地到各銷地的最小和次小運費之間的差額，找出最大差額的那一行，將盡可能多的物資從該產(chǎn)地運到運費最小的銷地，劃去沒有剩余的產(chǎn)地和滿足需求的銷地，再重復上述過程，由此得出初始調(diào)配方案。

方法四：行列伏格爾法

在單位運價表中，比較同一產(chǎn)地到各銷地的最小和次小運費之間的差額和同一銷地到各產(chǎn)地的最小和次小運費之間的差額，找出最大差額的那一行或列，將盡可能多的物資從該產(chǎn)地運到運費最小的銷地，劃去沒有剩余的產(chǎn)地和滿足需求的銷地，再重復上述過程，由此得出初始調(diào)配方案。

在以上方法中，行列伏格爾法是最接近最優(yōu)方案的方法。

步驟3：計算檢驗數(shù)，若最優(yōu)解已得，則計算停止，否則繼續(xù)。

對于計算檢驗數(shù)，可采用最簡單的運價矩陣法。對運價矩陣做變換即行加列減，將所有對應數(shù)字格的運價變?yōu)?。此時，運價矩陣中對應空格的矩陣元素值，即所求的檢驗數(shù)。

步驟4：調(diào)整方案，轉(zhuǎn)步驟3。

2 案例分析

假設某貨物共有4個供應地，供應量分別為7箱、8箱、5箱和10箱；有5個需求地，需求量分別為5箱、6箱、4箱、7箱和8箱。通過產(chǎn)銷平衡表確定最優(yōu)運輸方案，各供應地到各需求地的單位運價如表3所示。

表3 各供應地到各需求地的單位運價表

根據(jù)單位運價表可以得出數(shù)學模型為：

2.1 確定初始運輸方案

本題運用最好的行列伏格爾法來確定初始調(diào)配方案，結(jié)果如表4所示。

表4 初始運輸方案

由此可得，出初始運輸方案為A1運4箱給B3，A1運3箱給B4，A2運5箱給B1，A2運3箱給B5，A3運5箱給B5，A4運6箱給B2，A4運4箱給B4。

2.2 計算檢驗數(shù)

計算檢驗數(shù)進行變換時，優(yōu)先考慮數(shù)字格多的那一列，即第4列和第5列，要使每一列數(shù)字格相等，即第三行每個數(shù)加2，第四行每個數(shù)加2，再將每一列減去每列的數(shù)字格，剩下的數(shù)字則為檢驗數(shù)。

由此可以發(fā)現(xiàn)，所有檢驗數(shù)為0是非負數(shù)，因此最優(yōu)方案已經(jīng)得出。最優(yōu)調(diào)撥方案為A1運4箱給B3，A1運3箱給B4，A2運5箱給B1，A2運3箱給B5，A3運5箱給B5，A4運6箱給B2，A4運4箱給B4。

此時的總運費最小為4*7+3*10+5*4+3*7+5*5+6*7+4*8=198元

3 案例改進

當求解產(chǎn)銷不平衡問題時，可將此類問題通過方法轉(zhuǎn)換成產(chǎn)銷平衡問題，再利用表上作業(yè)法進行求解。

注意：當運用表上作業(yè)法來確定初始運輸方案時，運價全為0的那一列或行，可不考慮[5]。

上述為目標函數(shù)極小化問題，當問題改為極大化問題時，也可使用表上作業(yè)法進行求解。運用行列伏格爾法時，應按“最大”和“次大”元素之差的大小優(yōu)先考慮，并且當所有檢驗數(shù)全為負時，即為最優(yōu)方案。

當遇到無運輸路線情況時，即將對應的運價改為M(M＞1)。

下面通過簡單的案例進一步理解產(chǎn)銷不平衡問題。

問題：假設某種物資共有3個供應地，4個需求地，各供應地到各需求地的單位運價如表5所示，通過產(chǎn)銷平衡表確定最優(yōu)運輸方案。

表5 運價表

解：該問題的總供應量為50箱，總銷量為40箱，屬于產(chǎn)銷不平衡問題。由此通過增加一列虛擬銷地B5，將問題轉(zhuǎn)換為產(chǎn)銷平衡問題，虛擬銷地B5需求量為50-40為10箱，任何產(chǎn)地對該虛擬銷地的單位運價為0。

3.1 運用行列伏格爾法確定初始運輸方案

初始運輸方案如表6所示。

表6 初始運輸方案

3.2 計算檢驗數(shù)

檢驗數(shù)全為非負，最優(yōu)方案已求得。最優(yōu)運輸方案為A1運7箱給B1，A1運10箱給B2，A1運3箱給B4，A2運15箱給B3，A3運5箱給B4。

4 結(jié)語

本文以貨物運輸為案例，用表上作業(yè)法來處理產(chǎn)銷平衡問題，后以增加虛擬產(chǎn)地或銷地來處理產(chǎn)銷不平衡問題。表上作業(yè)法是處理此類問題的有效方法，簡單實用，能有效實現(xiàn)效益最大化。