運輸問題表上作業法補零規則的改進

林磊

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

【關鍵詞】表上作業法；檢驗數；退化解

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

1問題引入與分析

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

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

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

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

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

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

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

2改進的補零規則

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

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

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

3結論

本文對運籌學中運輸問題的表上作業法出現檢驗數為0方案卻已最優的情況進行了分析，指出其原因是在同時劃去行列時的補零操作過于隨機。為了減少這種情況的發生，本文給出了一種改進的補零規則。

參考文獻：

[1]胡運權等.《運籌學基礎及應用》[M].高等教育出版社，2015endprint