關于一類退化型運輸問題求解的研究

朱 翔

（無錫職業技術學院 基礎部，江蘇 無錫 214121）

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

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

1 實例及求解

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

表1 產銷及運價表

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

表2 初始調運方案

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

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

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

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

表3 調運方案1.1

表4 空格檢驗數2.1

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

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

表5 調運方案1.2

此時檢驗數λ22＝-1＜0，同上做法繼續調整。

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

表6 空格檢驗數2.2

表7 調運方案1.3

表8 空格檢驗數2.3

此時，所有空格的檢驗數均大于0，從而當前方案為最優運輸方案。

情況Ⅱ：x22＝0

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

2 關于此類問題的求解

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

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

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

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

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

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

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

3 結束語

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

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

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

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