運(yùn)輸問(wèn)題表上作業(yè)法補(bǔ)零規(guī)則的改進(jìn)

林磊

【摘 要】本文對(duì)運(yùn)輸問(wèn)題表上作業(yè)法過(guò)程中，檢驗(yàn)數(shù)計(jì)算出現(xiàn)負(fù)值，而方案卻已經(jīng)達(dá)到最優(yōu)這種情況進(jìn)行了分析，指出了其原因在于問(wèn)題出現(xiàn)退化時(shí)進(jìn)行補(bǔ)零操作的規(guī)則不明確。本文進(jìn)一步給出了一種改進(jìn)的補(bǔ)零規(guī)則以減少這種情況出現(xiàn)。

【關(guān)鍵詞】表上作業(yè)法；檢驗(yàn)數(shù)；退化解

運(yùn)輸問(wèn)題是運(yùn)籌學(xué)的一個(gè)重要分支線性規(guī)劃問(wèn)題的特例[1]。對(duì)于一般線性規(guī)劃問(wèn)題，可以使用單純形法來(lái)解決。而運(yùn)輸問(wèn)題由于其約束條件變量的系數(shù)矩陣的特殊性，可以使用比單純形法更為簡(jiǎn)單的方式來(lái)處理，然而，有時(shí)，雖然檢驗(yàn)數(shù)出現(xiàn)了負(fù)值，調(diào)運(yùn)方案卻已達(dá)到了最優(yōu)。本文就這種情況形成的原因進(jìn)行了分析，發(fā)現(xiàn)這是由于問(wèn)題出現(xiàn)退化時(shí)進(jìn)行補(bǔ)零操作的規(guī)則不明確而導(dǎo)致的。故而，本文設(shè)計(jì)了一種改進(jìn)的補(bǔ)零規(guī)則減少此種情況的出現(xiàn)。

1問(wèn)題引入與分析

這一節(jié)將詳細(xì)地描述本文所要解決的問(wèn)題。為了便于理解，下面將結(jié)合具體的實(shí)例來(lái)引出問(wèn)題。

例子1：已知運(yùn)輸問(wèn)題的產(chǎn)銷(xiāo)地的供需量與單位運(yùn)價(jià)表如表1所示，用表上作業(yè)法求解其最優(yōu)解。

解：這是一個(gè)產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題，文中單位運(yùn)價(jià)用符號(hào)表示，從地銷(xiāo)往地的運(yùn)量用符號(hào)表示，檢驗(yàn)數(shù)用符號(hào)表示。第一步通過(guò)Vogel法尋找初始調(diào)運(yùn)方案。在第一輪計(jì)算行列最大差時(shí)，出現(xiàn)第一行和第一列的最低和次低運(yùn)費(fèi)的差值都為8，是最大的運(yùn)費(fèi)差，所以按照Vogel法的規(guī)則，可選擇劃掉第一列，設(shè)置。由于所在行的產(chǎn)量等于其所在列的銷(xiāo)量，還要同時(shí)劃掉第三行，并可以設(shè)置第三行或是第一列除去的某一格運(yùn)量為0，并將此格所代表的變量視為基變量。假設(shè)設(shè)置，繼續(xù)使用Vogel法，得到初始調(diào)運(yùn)方案如表2所示。

表2中括號(hào)里面的數(shù)字代表對(duì)應(yīng)的行產(chǎn)地運(yùn)往列銷(xiāo)地的運(yùn)量。接下來(lái)計(jì)算空格變量的檢驗(yàn)數(shù)。使用閉回路法算出檢驗(yàn)數(shù)為：

σ13=16，σ21=-3，σ24=4，σ32=14，σ33=20，σ34=15.

可以看出，檢驗(yàn)數(shù)當(dāng)中有負(fù)值，根據(jù)表上作業(yè)法該方案沒(méi)有達(dá)到最優(yōu)，需要調(diào)整。從所對(duì)應(yīng)的空格出發(fā)，做一條除該空格外其余頂點(diǎn)都為有數(shù)字格的閉回路，如表3所示。由于這條閉回路上最大的調(diào)整值為0，所以調(diào)整之后的總運(yùn)費(fèi)是不會(huì)改變的。換句話說(shuō)，調(diào)整后的方案和原方案所對(duì)應(yīng)的目標(biāo)函數(shù)值是一樣的。對(duì)這個(gè)閉回路，調(diào)整后，只有和有變化，從基變量0變成了非基變量0，而從非基變量0變成了基變量0。對(duì)新的方案，計(jì)算檢驗(yàn)數(shù)，原來(lái)為正的檢驗(yàn)數(shù)依然為正的，新的非基變量的檢驗(yàn)數(shù)此時(shí)也為正，且剛好是原非基變量檢驗(yàn)數(shù)的相反數(shù)。因此，由于所有非基變量的檢驗(yàn)數(shù)都為正，新方案已達(dá)到最優(yōu)。

顯然，初始方案與新的方案的目標(biāo)函數(shù)值是相等的。由于新的方案達(dá)到了最優(yōu)，所以初始方案也達(dá)到了最優(yōu)。然而初始方案的檢驗(yàn)數(shù)卻有負(fù)數(shù)值。為什么會(huì)出現(xiàn)這種現(xiàn)象？原因在于，求初始方案的時(shí)候出現(xiàn)要同時(shí)劃去一行和一列的情況（稱為退化），在這個(gè)時(shí)候?yàn)榱耸够兞康膫€(gè)數(shù)不減少，需要在劃去的行列中隨機(jī)選擇一格賦值0作為基變量。選擇哪一格補(bǔ)0按傳統(tǒng)的規(guī)則是隨機(jī)挑選的，這種規(guī)則會(huì)導(dǎo)致表上作業(yè)法出現(xiàn)以上的漏洞。因?yàn)椋x任何一格補(bǔ)0最后得到的調(diào)運(yùn)方案所計(jì)算的總運(yùn)費(fèi)是一樣的。

2改進(jìn)的補(bǔ)零規(guī)則

回顧上一節(jié)的例子，可以看出，如果一個(gè)方案已經(jīng)達(dá)到最優(yōu)，此時(shí)出現(xiàn)了退化。傳統(tǒng)的補(bǔ)零規(guī)則是隨機(jī)選取同時(shí)劃去的行列中除最小運(yùn)費(fèi)之外的任意格做為基變量。假設(shè)補(bǔ)零的時(shí)候選取某一格為基變量，利用閉回路算法計(jì)算檢驗(yàn)數(shù)時(shí)這一格的檢驗(yàn)數(shù)恰好卻出現(xiàn)了負(fù)值。那么就會(huì)出現(xiàn)檢驗(yàn)數(shù)為負(fù)值，方案卻已達(dá)到最優(yōu)這種情況。為了減少這種情況出現(xiàn)的次數(shù)，本文給出了一種改進(jìn)的補(bǔ)零規(guī)則，如下所示。

補(bǔ)零規(guī)則對(duì)運(yùn)輸問(wèn)題進(jìn)行表上作業(yè)法碰到退化解時(shí)，選擇同時(shí)劃去的行列中未添供銷(xiāo)量格中運(yùn)費(fèi)最小的格補(bǔ)上0。

規(guī)則解釋?zhuān)翰皇б话阈?，假設(shè)需要同時(shí)劃去的行列中未添供銷(xiāo)量格子中最小運(yùn)費(fèi)格為。計(jì)算被劃去行列中這些非基變量的檢驗(yàn)數(shù)時(shí)，某些非基變量格的閉回路會(huì)以格做為其回路頂點(diǎn)。對(duì)這些非基變量格計(jì)算檢驗(yàn)數(shù)時(shí)，可以分為兩種情況分析。一種是計(jì)算檢驗(yàn)數(shù)時(shí)需要加上格的運(yùn)費(fèi)，這種情況下格貢獻(xiàn)的是正數(shù)，不會(huì)導(dǎo)致檢驗(yàn)數(shù)為負(fù)；另一種是計(jì)算檢驗(yàn)數(shù)時(shí)需要減去格的運(yùn)費(fèi)，這種情況下格貢獻(xiàn)的是負(fù)數(shù)，但由于所要計(jì)算檢驗(yàn)數(shù)的非基變量格的運(yùn)費(fèi)按改進(jìn)的規(guī)則是大于等于，兩者相減得數(shù)非負(fù)，故也不會(huì)導(dǎo)致檢驗(yàn)數(shù)為負(fù)。

3結(jié)論

本文對(duì)運(yùn)籌學(xué)中運(yùn)輸問(wèn)題的表上作業(yè)法出現(xiàn)檢驗(yàn)數(shù)為0方案卻已最優(yōu)的情況進(jìn)行了分析，指出其原因是在同時(shí)劃去行列時(shí)的補(bǔ)零操作過(guò)于隨機(jī)。為了減少這種情況的發(fā)生，本文給出了一種改進(jìn)的補(bǔ)零規(guī)則。

參考文獻(xiàn)：

[1]胡運(yùn)權(quán)等.《運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用》[M].高等教育出版社，2015endprint