運輸問題的表上作業(yè)法中初始方案的優(yōu)化

張曉瑾，劉海生

(華北科技學(xué)院基礎(chǔ)部，北京 東燕郊 101601)

0 引言

運輸問題是特殊的線性規(guī)劃問題，表上作業(yè)法是運用了單純形法的原理，結(jié)合運輸問題自身的特點，而得到的一種求解產(chǎn)銷平衡運輸問題的簡便而有效的方法。但在其迭代計算過程中，其初始方案的確定、檢驗和方案的調(diào)整改進處理不一樣時，計算工作量大相徑庭。如何才能減少迭代次數(shù)，用最少的工作量來求得最優(yōu)方案，本文對表上作業(yè)法中初始方案的確定進行了一定的思考和改進。

對于產(chǎn)銷平衡運輸問題初始方案的確定，常用的方法有三種:最小元素法、西北角法和Vogel法。一般地，Vogel法確定的初始方案質(zhì)量最好，最接近最優(yōu)解;最小元素法次之;西北角法最差。本文重點研究利用Vogel法確定初始方案過程中存在的不足和改進的工作。

1 方法存在的問題

用Vogel法確定初始方案時，其過程中出現(xiàn)的問題:

1)當(dāng)一次計算中出現(xiàn)最大罰數(shù)有2個及2個以上時，究竟選取哪一個罰數(shù)對應(yīng)的行或列來填數(shù)字，選取不當(dāng)時，后期迭代步驟不同，初始方案質(zhì)量不同。針對此問題，教材［7］中以及相關(guān)文獻中未做出明確的說明。

2)在Vogel法確定初始方案過程中出現(xiàn)退化解時，如何確定填“0”的位置。先后有多篇文章討論過這個問題，如［1］－［6］。在文獻［1］中指出:“填到數(shù)字格所在行或所在列的未劃去或未填數(shù)字格中單位運價最小的位置，可以避免可能存在的多余的計算?！睂嵺`表明，這一說法不完善。例如表1(表中“()”中為檢驗數(shù);“○”中為初始方案，下表中相同).

表1 產(chǎn)銷平衡運輸表

在A3B1位置填入數(shù)字2時，供銷關(guān)系同時得到滿足，此時有四個位置 A1B1，A2B1，A3B2和 A3B3可以填0。而單位運價最小者為位置A3B2，選其位置填0，得到初始方案，并計算其檢驗數(shù)見表1?？崭裎恢肁3B3檢驗數(shù)小于零，當(dāng)前方案不是最優(yōu)方案(見表1)。而如果選擇將0填入位置A3B3，計算得到其初始方案和檢驗數(shù)見表2。此時，所有檢驗數(shù)都大于零，得到的初始方案為最優(yōu)方案。故選擇填到“數(shù)字格所在行或所在列的未劃去或未填數(shù)字格中單位運價最小的位置”，這一說法未必能減少迭代次數(shù)。

表2 產(chǎn)銷平衡運輸表

下面針對以上兩個問題，談?wù)劚疚牡母倪M工作:

2 方法的補充和改進

1)用Vogel法確定初始方案時，當(dāng)一次計算中最大罰數(shù)有2個及2個以上時，可以改進提高初始方案的質(zhì)量。

在理論上，由任意最大罰數(shù)所在行或所在列的最小運價確定數(shù)字格均可。但是，當(dāng)最大罰數(shù)所在行或所在列的各最小單位運價不等時，選取最大罰數(shù)對應(yīng)的不同的行或列，初始調(diào)運方案質(zhì)量就不一樣，迭代次數(shù)也不同。實踐證明:由最大罰數(shù)所在行或所在列的各最小單位運價的最小者，確定數(shù)字格而獲得的初始方案質(zhì)量好。而且當(dāng)產(chǎn)地和銷地較少時，有時得到的初始方案就是最優(yōu)方案。例如表3中的產(chǎn)銷平衡問題。

表3 產(chǎn)銷平衡運輸表

在利用Vogel法確定初始方案，填A(yù)2B1時，遵從這一規(guī)則:有相同最大罰數(shù)為2，選取了罰數(shù)為2的所在行和列中未被劃去的行和列中單位運價最小的位置A2B1，優(yōu)先得到滿足。方案確定后，經(jīng)檢驗其方案為最優(yōu)(見表3)。

2)用Vogel法確定初始方案，在填數(shù)字格時，若同時滿足其所在行和所在列的供銷關(guān)系，需選擇某一位置填“0”，此時出現(xiàn)退化解。填“0”的位置不同，由此而獲得初始方案的質(zhì)量不一樣，后期迭代次數(shù)也不一樣。

下面從客觀上分析此問題:在書［7］中明確指出“通過任一空格可以找到，并且只能找到唯一的閉回路，并由此計算出全部空格處的檢驗數(shù)”。據(jù)此任一空格位置檢驗數(shù)的正負(fù)，唯一取決于閉回路各個拐點處數(shù)字格單位運價數(shù)值的相對大小。由于具體不同問題中各個單位運價之間沒有必然的關(guān)聯(lián)，客觀上導(dǎo)致檢驗數(shù)計算結(jié)果的正負(fù)隨機性，填“0”位置沒有一個統(tǒng)一的規(guī)律。于是想從填“0”這方面減少迭代的次數(shù)，沒有一個統(tǒng)一的規(guī)則。

雖然如此，我們還是可以從兩方面著手去優(yōu)化Vogel法確定初始方案:

一方面，通過后期觀察法選取填“0”位置，減少空格位置檢驗數(shù)出現(xiàn)負(fù)值的可能性。

下面舉例說明，具體步驟如下:

第一步:計算行和列的罰數(shù)，確定出第一個數(shù)字格。銷地B1對應(yīng)罰數(shù)為最大，其值為8;選擇在A3B1位置填入數(shù)字5時。此時供銷關(guān)系同時得到滿足，劃去第3行和第1列，需選某一位置填0。有 A1B1，A2B1，A3B2，A3B3和A3B4對應(yīng)的5個位置可以填0，具體位置待定(見表4)。

表4 產(chǎn)銷平衡運輸表

第二步:視A3B1所在行和列已劃去，依據(jù)第一步中的規(guī)則，繼續(xù)確定出其它位置的數(shù)字格(見表4)。

第三步:依據(jù)當(dāng)前5個數(shù)字格，利用閉回路法確定出部分空格的檢驗數(shù)(見表4)。

表5 產(chǎn)銷平衡運輸表

第四步:填“0”的位置影響其它空格位置檢驗數(shù)的正負(fù)，通過位置篩選法，選擇某一位置填0。從5個位置中選擇一個填0，具體作法:當(dāng)A1B1位置填0時，觀察與之相關(guān)的空格，發(fā)現(xiàn)其在A2B1對應(yīng)閉回路中，空格A2B1檢驗數(shù)12－7+2－10=－3＜0，放棄此位置;同理當(dāng)A3B2位置填0時，發(fā)現(xiàn)其在A3B4對應(yīng)閉回路中，空格A3B4的檢驗數(shù)18－14+7－20= －9＜0，放棄此位置;據(jù)此適當(dāng)排除一些位置，一定程度上提高初始方案的質(zhì)量，減少迭代次數(shù)，見表5。

表5 產(chǎn)銷平衡運輸表

當(dāng)產(chǎn)銷平衡的運輸問題中產(chǎn)地和銷地數(shù)相對較少時，此法效果很好。當(dāng)產(chǎn)地和銷地比較多時，試圖通過后期觀察法填“0”，實現(xiàn)初始方案的優(yōu)化，減少迭代次數(shù)已經(jīng)不易操作。

另一方面，在符合條件的任意位置填“0”，依據(jù)檢驗數(shù)為負(fù)的空格調(diào)整量來判斷，實現(xiàn)優(yōu)化。具體作法是:運用Vogel法確定出初始方案，當(dāng)出現(xiàn)一個空格處檢驗數(shù)為負(fù)時，運用閉回路法進行調(diào)整;若調(diào)整量為0時，結(jié)合文獻［6］的說明，文獻［2］中判別方法，可知此時已經(jīng)得到最優(yōu)方案，無需繼續(xù)迭代。若調(diào)整量不為0時，說明當(dāng)前方案不是最優(yōu)方案，運用閉回路法調(diào)整方案，繼續(xù)迭代尋找最優(yōu)方案;當(dāng)出現(xiàn)多個空格處檢驗數(shù)均為負(fù)值但調(diào)整量都為0時，結(jié)合［2］可知，此時已經(jīng)得到最優(yōu)解;否則閉回路調(diào)整方案。此方法對于檢驗數(shù)為負(fù)值且調(diào)整量為0的情形，大大減少了方案迭代的次數(shù)，優(yōu)化了初始方案。

3 結(jié)論

本文中作者給出一個處理“出現(xiàn)相同最大罰數(shù)問題”的規(guī)則，提高了Vogel法確定初始方案的質(zhì)量;運用兩個方法，從兩個角度優(yōu)化了填“0”的問題，減少了方案迭代次數(shù)，提高了初始方案的質(zhì)量。

［1］ 謝凡榮，產(chǎn)銷平衡運輸問題的表上作業(yè)法解法的一個注記［J］. 運籌與管理，2005，14(4):44 －46.

［2］ 楊莉，等，運輸問題的改進算法探討［J］.運籌與管理，2002，11(4):77 －80.

［3］ 劉琳，退化運輸問題最優(yōu)解求法的一個注記［J］.高等數(shù)學(xué)研究，2006，9(4):125 －127.

［4］ 郭鵬，關(guān)于運輸問題最優(yōu)解的進一步討論［J］.數(shù)學(xué)實踐與認(rèn)識，2006，36(5):140 －146.

［5］ 唐文廣，等，運輸問題退化解及其表解中0元的添加［J］.數(shù)學(xué)實踐與認(rèn)識，2009，39(1):160 －166.

［6］ 郝自軍，等，運輸問題表上作業(yè)的再探討［J］.西南民族大學(xué)學(xué)報，2011，37(2):209 －211.

［7］ 胡運權(quán)，等.運籌學(xué)基礎(chǔ)及應(yīng)用(第5版)［M］.北京:高等教育出版社，2008.