細說運輸問題中的位勢

摘 要：本文擺脫了傳統(tǒng)的通過位勢方程介紹位勢的束縛，從單純形法入手解決運輸問題，其間引出位勢這一概念，并討論了利用位勢確定檢驗數(shù)的原理和方法。

關(guān)鍵詞：位勢方程組 位勢 檢驗數(shù)

位勢是解決運輸問題過程中的一個重要的概念，然而在一般的文獻中對位勢都沒有做系統(tǒng)的介紹，大多數(shù)情況是利用位勢方程來定義位勢，然后再利用位勢來計算運輸問題的檢驗數(shù)，其間不加任何說明，初學(xué)者往往會丈二和尚摸不著頭腦，對以后的學(xué)習(xí)帶來負面影響。本文利用單純行法解決運輸問題，其間引出位勢這一概念，讓大家深刻地領(lǐng)悟位勢的本質(zhì)，同時也可以很清楚地了解為什么可以用位勢計算運輸問題的檢驗數(shù)以及如何來計算檢驗數(shù)。

在運籌學(xué)中，運輸問題是一類非常重要的問題，其中最重要的是平衡運輸問題，即總發(fā)量等于總銷量的運輸問題。其它的運輸問題都可以轉(zhuǎn)化為平衡的運輸問題，因此我們這里只討論平衡的運輸問題。平衡運輸問題的一般模型如下：

表一

其中a_i是產(chǎn)地A 的產(chǎn)量(i=1，2，…，m)，b_j是銷地B_j的銷量，c_ij是由A_i運輸單位貨物到B_i的運價。

從運輸問題的模型可以看出，其實運輸問題也是線性規(guī)劃問題，完全可以通過單純形法來解決運輸問題。首先需要確定一組初始可行基，確定初始可行基的方法很多，經(jīng)常用的有三種：西北角法、最小元素法、Vogel法。（在任何一本運籌學(xué)教材里都可以找到這些方法的詳細介紹，這里就不再贅述了）確定了初始可行基后，列出初始可行基的單純行表如下：

表二表一左邊的X是初始基可行解向量，易證運輸問題的任何一個基都由m+n-1個變量組成（具體的證明可在參考文獻（1）內(nèi)找），因此，X的分量有m+n-1個。不妨設(shè)m=3，n=4，X=（x ， x ， x ， x ， x ， x ）表一變?yōu)椋?/p>

要想從上面的單純形表中判斷當(dāng)前基可行解是否是最優(yōu)解，還得把基變量在目標函數(shù)z中的系數(shù)消為零，如果對單純形法有足夠的認識，理解這點應(yīng)該沒有什么問題，為了幫助讀者更好地理解本文，這里對單純形法的原理做個簡單的回顧。

單純形法的基本思想是：確定一組系數(shù)向量線性獨立的基可行解，然后令其它的非基可行解取值為零，再在約束方程組里解出基可行解，然后判斷由基可行解和取值為零的非基可行解所組成的規(guī)劃問題的解是否最優(yōu)，這個過程稱之為單純型迭代。怎么判斷當(dāng)前解是否最優(yōu)呢？從迭代過程中看到，基變量的取值是由約束方程來確定的我們無法控制，我們能控制的是非基變量的取值，令其為零，要想知道這樣做是否合理，我們可以利用約束方程組中的基變量和非基變量的關(guān)系在目標函數(shù)里消去基變量，只留下非基變量，然后觀察非基變量的系數(shù)。如果系數(shù)都是正的，那么我們令非基變量取值為零就是最合理的，此時的解也是最合理的，就是最優(yōu)解，如果系數(shù)存在負數(shù)，那么令系數(shù)為負的非基變量為零就不合理了，因為如果非基變量不為零，會給目標函數(shù)帶來消減，從而優(yōu)化目標函數(shù)。綜上所述，判斷當(dāng)前解是否最優(yōu)的標準其實是將基變量消去后的目標函數(shù)中非基變量的系數(shù)，所以稱它們?yōu)闄z驗數(shù)。

回到我們的問題當(dāng)中，在表二中如何將基變量在目標函數(shù)中的系數(shù)消去呢？比如說我們?nèi)绾蜗ツ繕撕瘮?shù)中的基變量x₁₁？觀察表二，我們發(fā)現(xiàn)在約束方程組里有兩個關(guān)于₁₁的約束方程（從上往下數(shù)第一個和第四個），我們可以借助這兩個方程將目標函數(shù)里的₁₁消去，具體的做法是：Z-第一個方程×U₁+第四個方程×V₁，這個做法的本質(zhì)是高斯消元法，其實再說得簡單點就是我們中學(xué)里解線性方程組常用的消元法。這樣做也不會改變目標函數(shù)的最優(yōu)值，當(dāng)然也不會改變最優(yōu)解。此時x₁₁的系數(shù)就變成c₁₁-U₁- V₁只要令它等于零就達到我們的目的了。這樣，我們就得到了關(guān)系式：

c₁₁=U₁+V₁ (2)

對其他五個基變量用同樣的方法，我們可以得到類似（2）式的等式，將這六個等式聯(lián)立成一個方程組：

（3）是一個有七個變量而只有六個方程的線性方程組，這就是通常所說的“位勢方程組”，U _i(i=1，2，3)，V_j(j=1，2，3，4)就是所謂的“位勢”。由線性代數(shù)方程組理論可知，它有一個自由變量，因此有無數(shù)個解，不妨就令這個自由變量是U₁、U₁取不同的值，就會得到不同的解，最簡單的情形是令U₁等于零。

在一般的運輸問題當(dāng)中，位勢言和組為:

c_ij=U_i+V_j(c_ij是基變量在目標函數(shù)中的系數(shù))

有了位勢以后，怎么求檢驗數(shù)呢？

很簡單，我們曾說過，檢驗數(shù)其實是將目標函數(shù)中基變量消去后非基變量的系數(shù)，前面我們在表二中所做的工作將目標函數(shù)中基變量消去，既將基變量的系數(shù)消為零的同時，對非基變量的系數(shù)也做了相應(yīng)的變動，設(shè)C 是非基變量系數(shù)c 變動過后的值，則C_ij= c_ij-U_i-V_j，C_ij就是判斷當(dāng)前解是否最優(yōu)的檢驗數(shù)。

參考文獻：

[1]朱求長.運籌學(xué)及其應(yīng)用(修訂本)[M].武漢:武漢大學(xué)出版社，1997.

[2]宋學(xué)鋒，魏嘵平.運籌學(xué)[M].南京:東南大學(xué)出版社，2003.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”