朱 翔

（無錫職業(yè)技術(shù)學院 基礎(chǔ)部，江蘇 無錫 214121）

運輸問題［1］是運籌學中一類重要的線性規(guī)劃問題，它的一般模型如下：

由于運輸問題模型的特殊性，常用表上作業(yè)法［1］來求解該問題。在通過最小元素法確定初始調(diào)運方案（初始可行基）時，有時會出現(xiàn)基變量數(shù)小于m＋n-1的情況，從而產(chǎn)生退化解（在這里我們稱之為退化型運輸問題），這給后面用閉回路法和位勢法繼續(xù)迭代帶來了困難，下面通過一道實例來說明該類問題的求解方法。

1 實例及求解

已知某運輸問題的產(chǎn)銷平衡表及單位運價資料（見表1），試確定最優(yōu)的運輸方案。

表1 產(chǎn)銷及運價表

利用最小元素法得到如下的初始方案（見表2），我們發(fā)現(xiàn)在此題中m＋n-1＝4＋6-1＝9，而數(shù)字格只有8個，屬于退化情形。

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

為了保證基變量個數(shù)，此時必須在空格處添加一個“0”。但是0運量添加的位置并不是任意的，有如下命題：

命題1［2］用表上作業(yè)法給出運輸問題初始方案時，遇到退化解的情形，0運量應添在不與其他數(shù)字格構(gòu)成閉回路的格子里。

故此題中，0運量只能添加在A1行或B2列的空格處，下面討論兩種不同的初始方案。

情況Ⅰ：x11＝0（見表3、表4）

表3 調(diào)運方案1.1

表4 空格檢驗數(shù)2.1

由于檢驗數(shù)x45＝-1＜0，故不是最優(yōu)解，需調(diào)整。表3中，x34，x35，x45，x44組成閉回路，取△＝min｛x35，x43｝＝10，則

x34＝9＋△＝19，x35＝10-△＝0（成為非基變量空格），x45＝△＝10，x44＝31-△＝21，調(diào)整后的方案如下（見表5、表6）：

表5 調(diào)運方案1.2

此時檢驗數(shù)λ22＝-1＜0，同上做法繼續(xù)調(diào)整。

考慮閉回路：x11-x12-x22-x25-x45-x44-x34-x31-x11，調(diào)整量△＝20，調(diào)整后的方案如下（見表7、表8）：

表6 空格檢驗數(shù)2.2

表7 調(diào)運方案1.3

表8 空格檢驗數(shù)2.3

此時，所有空格的檢驗數(shù)均大于0，從而當前方案為最優(yōu)運輸方案。

情況Ⅱ：x22＝0

類似上述方法，可得到與表7一致的最優(yōu)運輸方案。

2 關(guān)于此類問題的求解

本題中“0”可以添在A1行或B2列空格的任一位置，但本文僅討論了兩種不同的初始方案，看似“不太全面”。事實上，其余的添加方案都會最終歸結(jié)為這兩種情況。對于A1行其他位置的空格，不妨設(shè)x13＝0，這時考慮閉回路：x11-x13-x23-x25-x35-x31-x11這時調(diào)整運量△＝0，表面上看數(shù)值無變化，但是x11由空格變成了數(shù)字格0，而x13由數(shù)字格0變成了空格，也就是說，基變量發(fā)生了變化，完成了一次換基迭代。這時正好就變成了情況Ⅰ。不難驗證，A1行空格處添加“0”后都可轉(zhuǎn)化為情況Ⅰ，B2列空格處添加“0”后都可轉(zhuǎn)化為情況Ⅱ。而這個結(jié)論具有一般性，下面給出證明。

命題2［3］運輸問題列向量線性無關(guān)向量對應格集中不含閉回路

引理在退化型運輸問題（僅一個退化解）的初始調(diào)運方案表中，同一行（列）上不與其他數(shù)字格構(gòu)成閉回路的任意兩個空格之間一定存在閉回路。

證明設(shè)xik和xij是第i行上不與其他數(shù)字格構(gòu)成閉回路的任意兩個空格。令xik＝0，此時xik從空格變成了數(shù)字格，從而變成了基變量，此時基變量數(shù)與運輸問題約束矩陣的秩相同（等于m＋n-1）。xij作為非基變量，其對應列向量可由基向量組線性表示，又空格xij不與其他數(shù)字格構(gòu)成閉回路，由命題2易推出，xij與xik之間一定存在閉回路。對于同一列的情況類似可證。

定理對于僅一個退化解的退化型運輸問題，在利用添加0運量的方法保證基變量數(shù)時，在同一行（列）可添加0運量的任一空格處添加0運量的方案彼此等價。

證明設(shè)xik和xij是第i行可添加0運量的任意兩個空格，選擇在xik處添加0稱為方案Ⅰ，選擇在xij處添加0稱為方案Ⅱ，下面證明這兩個方案等價。

對于方案Ⅰ，因為xik和xij是可添加0運量的空格，根據(jù)命題1，xik和xij不與其他數(shù)字格構(gòu)成閉回路。從而由引理可知，必存在通過xik和xij的一條閉回路，且xik與xij是相鄰的兩個節(jié)點。此時作運量調(diào)整△＝0，則xij從空格變成了0數(shù)字格，而相鄰節(jié)點xik從0數(shù)字格變成了空格，其余數(shù)字格的數(shù)值不變，這時候即為方案Ⅱ。同理，方案Ⅱ也可以轉(zhuǎn)化為方案Ⅰ，從而這兩種方案是等價的。同一列的情況類似可證。

3 結(jié)束語

在利用表上作業(yè)法求解運輸問題時，一定要始終考察其數(shù)字格是否為m＋n-1個。當出現(xiàn)退化解時，可利用本文提出的添加“0”的辦法來解決。特別地，對于僅有一個退化解的運輸問題，所有可行的添加0運量方案都是等價的，因此我們只需任意選擇其中一種方案。

［1］《運籌學》教材編寫組.運籌學［M］.3版.北京：清華大學出版社，2005.

［2］唐文廣.運輸問題的退化解及表解中0元的添加［J］.數(shù)學的實踐與認識，2009，39（1）：160-166.

［3］高旅端.線性規(guī)劃［M］.北京：北京工業(yè)大學出版社，1989.