劉雁靈

(長(zhǎng)治醫(yī)學(xué)院 數(shù)學(xué)教研室,山西 長(zhǎng)治 046000)

1 引言

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

2 實(shí)例與方法

表1運(yùn)價(jià)表(元/噸)

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

解 具體的計(jì)算步驟和相應(yīng)的差額計(jì)算表如下：

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

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

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

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

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

表2差額計(jì)算表

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

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

注：以下實(shí)例不再列出運(yùn)價(jià)表，均仿照實(shí)例1列出差額計(jì)算表進(jìn)行計(jì)算.

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

解 按照本文方法進(jìn)行差額計(jì)算：

表3差額計(jì)算表(小時(shí)/件)

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

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

解 進(jìn)行差額計(jì)算：

表4差額計(jì)算表(元/臺(tái))

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

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

解 進(jìn)行差額計(jì)算：

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

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

3 結(jié)論

在文獻(xiàn)[1-5]的基礎(chǔ)上，本文給出了運(yùn)輸問(wèn)題建立初始方案的新方法:通過(guò)尋找行列運(yùn)費(fèi)差額的最大值來(lái)確定運(yùn)輸方案.通過(guò)幾個(gè)實(shí)例的計(jì)算，可以看出該法的可行性，而且該法簡(jiǎn)單易操作，與其它建立初始解的方法相比較，往往一步就能達(dá)到最優(yōu)解，對(duì)解決運(yùn)費(fèi)差額大的運(yùn)輸問(wèn)題尤為適用.

參考文獻(xiàn)：

[1]寧宣熙.運(yùn)籌學(xué)實(shí)用教程[M].北京:科學(xué)出版社,2013.

[2]胡運(yùn)權(quán).運(yùn)籌學(xué)[M].北京:清華大學(xué)出版社,1986.

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

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

[5]蔣宏峰.運(yùn)輸問(wèn)題表上作業(yè)法的改進(jìn)[J].長(zhǎng)沙大學(xué)學(xué)報(bào),2002,16(2):47-48.

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