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

林 磊

（廣東技術師范學院 數學與系統科學學院，廣東廣州510665）

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

林 磊

（廣東技術師范學院 數學與系統科學學院，廣東廣州510665）

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

表上作業法；檢驗數；退化解；運籌學；運輸問題

運輸問題是運籌學的一個重要分支線性規劃問題的特例［1］.對于一般線性規劃問題，可以使用單純形法來解決［2］.而運輸問題由于其約束條件變量的系數矩陣的特殊性，可以使用比單純形法更為簡單的方式來處理，例如表上作業法［3］.圖1給出了表上作業法的流程圖.如圖1所示，在得到某一個調運方案后，需要計算檢驗數來判斷該方案是否達到最優.當檢驗數出現負值時，應該調整方案來獲得更優的解.然而，有時，雖然檢驗數出現了負值，調運方案卻已達到了最優.本文就這種情況形成的原因進行了分析，發現這是由于問題出現退化時進行補零操作的規則不明確而導致的.故而，本文設計了一種改進的補零規則減少此種情況的出現.

圖1 表上作業法流程圖

1 問題引入與分析

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

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

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

表1 產銷供需量與單位運價表

表2 初始調運方案

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

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

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

表3 (A2,B1)閉回路

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

2 改進的補零規則

根據上一節的例子，可以看出，如果一個方案已經達到最優，此時出現了退化.傳統的補零規則是隨機選取同時劃去的行列中除最小運費之外的任意格做為基變量.假設補零的時候選取某一格為基變量，利用閉回路算法計算檢驗數時這一格的檢驗數恰好卻出現了負值.那么就會出現檢驗數為負值，方案卻已達到最優這種情況.為了減少這種情況出現的次數，本文給出了一種改進的補零規則：對運輸問題進行表上作業法碰到退化解時，選擇同時劃去的行列中未添供銷量格中運費最小的格補上0.

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

3 結論

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

［1］胡運權.運籌學基礎及應用[M].5版.北京：高等教育出版社,2015.

［2］唐四云.運輸問題表上作業法中初始方案的改進[J].廣東技術師范學院學報,2016,37（5）:39-42.

［3］張曉瑾,劉海生.運輸問題的表上作業法中初始方案的優化[J].華北科技學院學報,2014,11（6）:73-75.

［4］何莉敏,李玉,于濤,等.Vogel法求解最大值問題[J].鄭州大學學報（理學版）,2011,43（1）:25-28.

［5］賈春玉.運輸問題新解法的探討[J].系統工程學報,2004,19（2）:207-211.

Improvement in Zero Filling Rule of the Table-working Scheme in Transportation Problem

LIN Lei
（School of Mathematics and Systems Science,Guangdong Polytechnic Normal University,Guangzhou 510665,Guangdong,China）

While the table-working scheme is used to solve the transportation problem,there exists an exceptional situation,in which the solution is optimal but some check numbers of non-base variables are negative.The reason is that the rules of zero filling are not clear in the case of degeneration.In order to reduce the situation,an improved zero filling rule is presented.

table-workingscheme；checknumber；degenerationsolution；operationalresearch；transportationproblem

O152.7

A

1007-5348（2017）03-0019-03

2017-02-02

國家自然科學基金青年項（61601131）；廣東省自然科學基金（2016A030313727）；廣東省教育廳青年創新人才項目（2015KQNCX086）.

林磊（1982-），女，安徽潛山人，廣東技術師范學院數學與系統科學學院講師，博士；研究方向：快變信道.

（責任編輯：邵曉軍）