張曉瑾，劉海生

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

0 引言

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

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

1 方法存在的問題

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

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

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

表1 產銷平衡運輸表

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

表2 產銷平衡運輸表

下面針對以上兩個問題，談談本文的改進工作:

2 方法的補充和改進

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

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

表3 產銷平衡運輸表

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

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

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

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

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

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

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

表4 產銷平衡運輸表

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

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

表5 產銷平衡運輸表

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

表5 產銷平衡運輸表

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

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

3 結論

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

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

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

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

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

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

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

［7］ 胡運權，等.運籌學基礎及應用(第5版)［M］.北京:高等教育出版社，2008.