關(guān)于一類退化型運(yùn)輸問題求解的研究

朱 翔

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

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

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

1 實(shí)例及求解

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

表1 產(chǎn)銷及運(yùn)價(jià)表

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

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

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

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

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

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

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

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

由于檢驗(yàn)數(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)運(yùn)方案1.2

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

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

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

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

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

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

情況Ⅱ：x22＝0

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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

［1］《運(yùn)籌學(xué)》教材編寫組.運(yùn)籌學(xué)［M］.3版.北京：清華大學(xué)出版社，2005.

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

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