林 磊

（廣東技術(shù)師范學(xué)院 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，廣東廣州510665）

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

林 磊

（廣東技術(shù)師范學(xué)院 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，廣東廣州510665）

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

表上作業(yè)法；檢驗(yàn)數(shù)；退化解；運(yùn)籌學(xué)；運(yùn)輸問題

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

圖1 表上作業(yè)法流程圖

1 問題引入與分析

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

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

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

表1 產(chǎn)銷供需量與單位運(yùn)價(jià)表

表2 初始調(diào)運(yùn)方案

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

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

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

表3 (A2,B1)閉回路

顯然，初始方案與新的方案的目標(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)?，選任何一格補(bǔ)0最后得到的調(diào)運(yùn)方案所計(jì)算的總運(yùn)費(fèi)是一樣的.假設(shè)，在所有這些方案中，有一種方案已知是最優(yōu)的且對(duì)應(yīng)的檢驗(yàn)數(shù)皆為正值.那么，其它方案中一旦有檢驗(yàn)數(shù)為負(fù)值的情況就都屬于所介紹的這種現(xiàn)象.為了減少這種情況出現(xiàn)，下一節(jié)給出了改進(jìn)的補(bǔ)零規(guī)則.

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

根據(jù)上一節(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ī)則：對(duì)運(yùn)輸問題進(jìn)行表上作業(yè)法碰到退化解時(shí)，選擇同時(shí)劃去的行列中未添供銷量格中運(yùn)費(fèi)最小的格補(bǔ)上0.

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

3 結(jié)論

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

［1］胡運(yùn)權(quán).運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用[M].5版.北京：高等教育出版社,2015.

［2］唐四云.運(yùn)輸問題表上作業(yè)法中初始方案的改進(jìn)[J].廣東技術(shù)師范學(xué)院學(xué)報(bào),2016,37（5）:39-42.

［3］張曉瑾,劉海生.運(yùn)輸問題的表上作業(yè)法中初始方案的優(yōu)化[J].華北科技學(xué)院學(xué)報(bào),2014,11（6）:73-75.

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

［5］賈春玉.運(yùn)輸問題新解法的探討[J].系統(tǒng)工程學(xué)報(bào),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

國家自然科學(xué)基金青年項(xiàng)（61601131）；廣東省自然科學(xué)基金（2016A030313727）；廣東省教育廳青年創(chuàng)新人才項(xiàng)目（2015KQNCX086）.

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

（責(zé)任編輯：邵曉軍）