運輸規(guī)劃問題算法的改進

劉雁靈

(長治醫(yī)學院 數(shù)學教研室,山西 長治 046000)

1 引言

求解運輸問題常用的解法是表上作業(yè)法，但其本質還是單純形法[1,2]，在確定初始方案時，最常用的方法有三種：西北角法、最小費用法、Vogel法.由最小費用法、Vogel法得出的初始解已比較接近最優(yōu)解，但仍有不足.大量文獻討論了優(yōu)化初始方案的算法，文獻[3]提出了最大差額法、最大運輸量滿足法、列差額法，分別從運輸角度、最大運輸量角度、需求角度出發(fā)來建立初始方案，得出的初始方案往往比較接近最優(yōu)解，有時就是最優(yōu)解；文獻[4]是在Vogel法的基礎上提出了最大罰數(shù)有兩個的情況以及有退化解時提高初始方案的運算法則.本文在前面文獻的基礎上，給出了新的改進方法，該法往往一步就可以得到最優(yōu)解，計算量大大減少，并通過實例加以驗證.

2 實例與方法

表1運價表(元/噸)

實例1 已知有A1,A2,A3三個產(chǎn)糧地，可供應的糧食分別為5,2,3(萬噸)，現(xiàn)將糧食運往B1,B2,B3,B4四個地區(qū)，其需求量分別為3,2,3,2(萬噸).從各個產(chǎn)地運往各個地區(qū)的運價如表1[3]所示.試安排一個運費最低的運輸計劃.

解 具體的計算步驟和相應的差額計算表如下：

步驟:①計算出每一行每一列費用的最大差額，行差額放在表中的最后一列，列差額放在表中的最后一行.如表2中最后一列為4,2,5，最后一行為2,4,5,3；

②在差額最大的數(shù)對應的行或列中找費用最小的盡可能滿足.這里有兩個差額都是5，即第三行和第三列，分別找最小費用，均為3，可任選其一，如先滿足差額最大的數(shù)5對應的行中的c32=3;x32=2;

③劃去已滿足需求的行或列，若同時滿足可同時劃去行和列.表2中劃去了第二列;

④重新計算差額，這時注意已經(jīng)劃去的行或列不再參與計算差額，返回到①.

本題中第二次計算出來的行差額為3,1,4，列差額為2,5,3，最大值為5，在5對應的列中找費用最小的盡可能滿足，即滿足c23=3;x23=2；這時第二行已滿足，后面計算差額時不再計算這一行.以此類推，直到供求全部滿足，行列全部劃去.

表2差額計算表

該初始解和文獻[3]求得的解一樣，已是最優(yōu)解.

幾點注釋:(1)當行和列的最大差額有相同的值時，應滿足費用最小者，若仍相同，可任選其一；(2)如行列同時滿足可同時劃去行和列，這時出現(xiàn)退化解，需填“0”，填“0”的方法可參考文獻[4]、[6];(3)該法是考慮所有供或求費用的差額最大的情況下滿足最小費用的供或求，所以得到的初始解往往就是最優(yōu)解;(4)所填的數(shù)不會超過m+n-1[3].

注：以下實例不再列出運價表，均仿照實例1列出差額計算表進行計算.

實例2 有A1,A2,A3三臺機床，加工B1,B2,B3,B4四種零件.已知三臺機床的日加工任務量分別為9,5,7(件)，四種零件的日需求量分別為3,8,4,6(件)，各臺機床加工各個零件所需的時間如表3[3]所示.試安排一個總的加工時間最少的生產(chǎn)計劃.

解 按照本文方法進行差額計算：

表3差額計算表(小時/件)

所得初始解為退化解，可按文獻[4]或[6]的方法填“0”，如在x13處填“0”，則該解為最優(yōu)解[3].在文獻[3]中計算該題是利用列差額法，但得出的初始解并非最優(yōu)解，需通過找出調整量才可得出最優(yōu)解，而本文方法一步即得最優(yōu)解.

實例3 設某品牌手機生產(chǎn)廠有A1,A2,A3三個分廠，供應B1,B2,B3,B4四個地區(qū)銷售.已知三個分廠的日供應量分別為70,80,50(臺)，四個地區(qū)的需求量分別為40,30,70,60(臺).從各個產(chǎn)地運往各個地區(qū)的運價如表4[4]所示.試安排一個運費最低的運輸計劃.

解 進行差額計算：

表4差額計算表(元/臺)

所得初始解為退化解，可按文獻[4]或[6]的方法填“0”，如在X23處填“0”，求得的初始解和文獻[4]中用Vogel法求得的一致，為最優(yōu)解.若用西北角法建立初始解則需迭代兩次才能得出最優(yōu)解[4].

實例4 設有A1,A2,A3三個蘋果園，供應B1,B2,B3,B4四個地區(qū)銷售.已知三個蘋果園的日供應量分別為8,6,9(百斤)，四個地區(qū)的需求量分別為5,7,5,6(百斤).從各個蘋果園運往各個地區(qū)的運價如表5[5]所示.試安排一個運費最低的運輸計劃.

解 進行差額計算：

表5差額計算表(元/十斤)

此例得出的初始解和文獻[5]通過三次迭代得出的最優(yōu)解一致.

3 結論

在文獻[1-5]的基礎上，本文給出了運輸問題建立初始方案的新方法:通過尋找行列運費差額的最大值來確定運輸方案.通過幾個實例的計算，可以看出該法的可行性，而且該法簡單易操作，與其它建立初始解的方法相比較，往往一步就能達到最優(yōu)解，對解決運費差額大的運輸問題尤為適用.

參考文獻：

[1]寧宣熙.運籌學實用教程[M].北京:科學出版社,2013.

[2]胡運權.運籌學[M].北京:清華大學出版社,1986.

[3]楊莉,等..運輸問題的改進算法探討[J].運籌與管理,2002,11(4):77-80.

[4]郭秀英.論運輸問題表上作業(yè)法[J].科技與管理,2007,43(3):33-35.

[5]蔣宏峰.運輸問題表上作業(yè)法的改進[J].長沙大學學報,2002,16(2):47-48.

[6]謝凡榮.產(chǎn)銷平衡運輸問題的表上作業(yè)法解法的一個注記[J].運籌與管理,2005,14(4):44-46.