運(yùn)輸問(wèn)題的簡(jiǎn)化解法

[摘 要] 本文對(duì)運(yùn)輸問(wèn)題的傳統(tǒng)解法(表上作業(yè)法)做了改進(jìn)，提出跳過(guò)計(jì)算“檢驗(yàn)數(shù)”，直接采用“閉回路法”和“對(duì)角相加法”可以簡(jiǎn)化運(yùn)輸問(wèn)題的求解過(guò)程。

[關(guān)鍵詞] 運(yùn)輸問(wèn)題 檢驗(yàn)數(shù) 位勢(shì)法 閉回路法 對(duì)角相加法

多數(shù)運(yùn)籌學(xué)或物流管理教科書(shū)對(duì)運(yùn)輸問(wèn)題（表上作業(yè)法）一般先采用最小元素法找出一個(gè)可行解，然后采用閉回路法或位勢(shì)法計(jì)算“檢驗(yàn)數(shù)”，驗(yàn)證這個(gè)可行解是否最優(yōu)解。如果不是最優(yōu)解，再用閉回路法調(diào)整。調(diào)整后還要用閉回路法或位勢(shì)法計(jì)算“檢驗(yàn)數(shù)”，直到驗(yàn)證表明調(diào)整后的方案是最優(yōu)解才算完成。解法可用如下程序圖所示：

注：不平衡的要虛設(shè)需方或產(chǎn)地，已有成熟方法，本文對(duì)此不加討論

在上述程序中，“采用閉回路法或位勢(shì)法計(jì)算‘檢驗(yàn)數(shù)’，驗(yàn)證這個(gè)可行解是否最優(yōu)解”是一個(gè)比較復(fù)雜的過(guò)程。當(dāng)產(chǎn)地和銷地?cái)?shù)量較大時(shí)，閉回路尋找比較復(fù)雜。多數(shù)運(yùn)籌學(xué)或物流管理教科書(shū)采用位勢(shì)法計(jì)算檢驗(yàn)數(shù)，這要先分解運(yùn)價(jià)，列出并求解一個(gè)聯(lián)立方程（有時(shí)列出的聯(lián)立方程還可能未知數(shù)與方程數(shù)不等，還要做技術(shù)處理）， 再計(jì)算每一個(gè)未使用的運(yùn)價(jià)（空格）的檢驗(yàn)數(shù)，要所有檢驗(yàn)數(shù)不小于零才表明所得方案是最優(yōu)解。這個(gè)過(guò)程有時(shí)要重復(fù)多次，比較繁瑣，能否簡(jiǎn)化呢？

筆者從后面的閉回路法得到啟示，是否可以這么認(rèn)為：只要還存在可以用閉回路法調(diào)整優(yōu)化的“回路”，原方案就不是最優(yōu)解，一直到所有的“回路”都不能再調(diào)整優(yōu)化時(shí)，該方案就是最優(yōu)解。并且筆者認(rèn)為閉回路的尋找也可以從已采用的最大運(yùn)價(jià)開(kāi)始著手，便于使不合理的運(yùn)價(jià)及時(shí)得到調(diào)整，這樣上述程序圖就可修改如下：

在上述程序中，“判斷所在運(yùn)量閉回路是否可調(diào)整”可以用一個(gè)比較簡(jiǎn)單的“對(duì)角相加法”來(lái)加以判斷，下面用一個(gè)例子來(lái)加以說(shuō)明：設(shè)有5個(gè)產(chǎn)地A1，A2，A3，A4，A5和4個(gè)銷地B1，B2，B3，B4的運(yùn)輸問(wèn)題，它們的供應(yīng)量與需求量及單位運(yùn)費(fèi)表如下：

求解這個(gè)問(wèn)題的第一步:按“最小元素法”根據(jù)運(yùn)價(jià)從小到大滿足需求得一可行解：

注：在此用“P/M”表示以P運(yùn)價(jià)運(yùn)輸量M，未打“/”的運(yùn)價(jià)暫不采用

第二步：找到所采用的最大運(yùn)價(jià)20，找其所在的“運(yùn)量閉回路”。所謂的“運(yùn)量閉回路”應(yīng)滿足以下條件：

(1)“運(yùn)量閉回路”是由水平線和垂線及其角上元素組成的矩形。

(2)該矩形包含角上的4個(gè)元素（運(yùn)價(jià)）。

(3)4個(gè)運(yùn)價(jià)中有3個(gè)是采用的，一個(gè)是暫不采用的。

最大運(yùn)價(jià)20所在的這樣的“運(yùn)量閉回路”有兩個(gè)：

第三步：任選一個(gè)回路，采用“對(duì)角相加法”判斷：將對(duì)角的兩個(gè)運(yùn)價(jià)相加。針對(duì)回路一有：20+1=21，7+5=12；可以看出，兩個(gè)均采用的對(duì)角運(yùn)價(jià)之和大于另外兩個(gè)對(duì)角運(yùn)價(jià)（其中一個(gè)暫不采用）之和，20+1＞7+5，說(shuō)明可以調(diào)整優(yōu)化，采用“閉回路法”調(diào)整為：

此時(shí)，7+5＜20+1；兩個(gè)均采用的對(duì)角運(yùn)價(jià)之和小于另外兩個(gè)對(duì)角運(yùn)價(jià)（其中一個(gè)暫不采用）之和，說(shuō)明該回路已經(jīng)優(yōu)化（不能再調(diào)整優(yōu)化）。并且得到第二個(gè)可行解。

然后再找到現(xiàn)方案中的最大運(yùn)價(jià)15，再找相應(yīng)回路進(jìn)行判斷和調(diào)整。這樣調(diào)整4次以后得到最優(yōu)解：

最小運(yùn)費(fèi)=5×10+9×20+4×30+7×30+0×10+3×30+12×10+5×10=820，可以判斷在這個(gè)方案中已不存在可以調(diào)整優(yōu)化的回路。該方案確為最優(yōu)解。

由此可以看出，跳過(guò)計(jì)算“檢驗(yàn)數(shù)”，直接采用“閉回路法”和“對(duì)角相加法”可以簡(jiǎn)化運(yùn)輸問(wèn)題(表上作業(yè)法)的求解過(guò)程。也許這對(duì)于當(dāng)今使用計(jì)算機(jī)軟件解決該問(wèn)題幫助不大，但是對(duì)于初學(xué)者用手工解決問(wèn)題時(shí)是有幫助的。與“位勢(shì)法”相比，上述“閉回路法”和“對(duì)角相加法”都比較容易理解和運(yùn)用。

參考文獻(xiàn):

[1]王自勤:現(xiàn)代物流管理.電子工業(yè)出版社，2007.6

[2]盧向南:應(yīng)用運(yùn)籌學(xué).浙江大學(xué)出版社，2005.2

[3]韓伯棠:管理運(yùn)籌學(xué).高等教育出版社，2005.7

[4]李維錚等:運(yùn)籌學(xué).清華大學(xué)出版社，1982.2