林磊

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

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

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

1問題引入與分析

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

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

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

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

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

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

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

2改進的補零規(guī)則

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

補零規(guī)則對運輸問題進行表上作業(yè)法碰到退化解時，選擇同時劃去的行列中未添供銷量格中運費最小的格補上0。

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

3結(jié)論

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

參考文獻：

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