細(xì)說單純形法

摘 要：本文從分析檢驗(yàn)數(shù)的本質(zhì)含義入手，用通俗易懂的語言介紹了線性規(guī)劃的最優(yōu)化原理，并在此基礎(chǔ)上重構(gòu)單純形法，避免了傳統(tǒng)的利用矩陣語言來介紹單純形法帶來的閱讀和理解上的困難。

關(guān)鍵詞：線性規(guī)劃 檢驗(yàn)數(shù) 單純形法

線性規(guī)劃是運(yùn)籌學(xué)里至關(guān)重要的內(nèi)容，單純形法又是解決線性規(guī)劃問題最重要的方法，如果不能深刻地理解單純形法，對(duì)線性規(guī)劃的學(xué)習(xí)，甚至是運(yùn)籌學(xué)的學(xué)習(xí)都將帶來嚴(yán)重的負(fù)面影響。但大部分運(yùn)籌學(xué)教材在介紹單純形法的時(shí)候都利用矩陣語言，顯得艱澀難懂，這對(duì)初學(xué)運(yùn)籌學(xué)的人來講是一個(gè)不小的打擊，會(huì)大大削弱他們學(xué)習(xí)運(yùn)籌學(xué)的興趣。為此，我們需要尋找一種更有效的方法來介紹單純形法。（我們默認(rèn)讀者對(duì)線性規(guī)劃模型以及關(guān)于線性規(guī)劃解的基本概念有一定的了解，如果讀者不了解，可以參考任意一本運(yùn)籌學(xué)教材學(xué)習(xí)這些概念）

單純形法大體分三步：

（1） 找出第一個(gè)（初始的）基可行解。

（2） 判斷這個(gè)基可行解是否最優(yōu)。

（3） 如果不是最優(yōu)，我們將它調(diào)整為一個(gè)“更好的”基可行解，直至最終求出最優(yōu)解。

以上三個(gè)步驟，我們通過“單純形表”來完成。

下面我們通過具體的例子來了解單純形表的構(gòu)造。

上表包括了線性規(guī)劃問題中所有關(guān)鍵數(shù)據(jù)，而且我們可以很方便地找到初始基為：β=（X ，X ，X ），因?yàn)橄禂?shù)列向量P 、P 、P 都是不同的單位向量，前面我們介紹過P 、P 、P 線性無關(guān)。β確定的初始基可行解是:X =X =0，X =15，X =5，X =11，相應(yīng)此解的目標(biāo)函數(shù)值：Z =0。我們將上表稱為初始基β的單純形表。

通過初始基β的單純形表，我們找出了初始基可行解，下面的問題是如何判斷初始基可行解是否最優(yōu)解。我們觀察一下Z 行中X 、X 的系數(shù)為-5、-4，而X 、X 又是非基變量，取值都為0，這樣對(duì)于求最小的Z 是很不利的，試想如果將X、X 都變成基變量，即允許X 、X 取值為正，那么Z 勢(shì)必會(huì)減少（增加一個(gè)X ，Z 減少5；增加一個(gè)X ，Z 減少4），由此我們判斷初始基并非最優(yōu)基，初始基可行解也并非最優(yōu)解。我們看到判斷當(dāng)前解是否最優(yōu)解主要依據(jù)非基變量在目標(biāo)函數(shù)中的系數(shù)。但要注意的是基變量的取值是有約束方程決定的，而非基變量取值是我們約定的為0，這種約定是否合理只有在目標(biāo)函數(shù)中不含基變量或者說目標(biāo)函數(shù)中基變量系數(shù)為0時(shí)才能很明顯地表現(xiàn)出來，因此，我們?cè)谂袛喈?dāng)前基可行解是否最優(yōu)時(shí)一定要保證基變量在目標(biāo)函數(shù)中系數(shù)為0。此時(shí)如果非基變量在目標(biāo)函數(shù)中系數(shù)存在負(fù)數(shù)，則說明當(dāng)前基可行解并非最優(yōu)解，反之，如果非基變量在目標(biāo)函數(shù)中系數(shù)全為正，則讓它們等于0就是最好的選擇，因此，當(dāng)前基可行解就是最優(yōu)解。

我們把基變量在目標(biāo)函數(shù)中系數(shù)為0時(shí)，非基變量在目標(biāo)函數(shù)中的系數(shù)稱為檢驗(yàn)數(shù)。記為σ (j=1，2，...n)。這樣判定當(dāng)前基可行解是否是最優(yōu)解的標(biāo)準(zhǔn)可以描述為：如果所有檢驗(yàn)數(shù)σ ≥0，則相應(yīng)的基可行解是最優(yōu)解。

如果經(jīng)檢驗(yàn)當(dāng)前基可行解不是最優(yōu)解，如何得到一個(gè)“更好的”基可行解呢？拿上面的例子來說，很自然的想法就是將X 、X 變成基變量，同時(shí)把X 、X 、X 中的某些變量變成非基變量，這步操作稱為換基，前半步操作稱為入基，后半步操作稱為出基。為了便于操作，我們只選擇一個(gè)變量入基，選擇誰呢？我們注意到當(dāng)X 增加1時(shí)，Z 會(huì)減少5，而X 增加1時(shí)，Z 只減少4，首先將X 入基優(yōu)化的效果會(huì)更好些，所以我們選擇X 入基。由此，我們得到選擇入基變量的標(biāo)準(zhǔn)，即負(fù)檢驗(yàn)數(shù)中最小的檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量入基。入基變量選定后，如何選擇出基變量呢？假如我們隨便選取出基變量，比如選擇X ，看看會(huì)出現(xiàn)什么樣的結(jié)果。

怎么才能使X 入基X 出基呢？很簡單，以前我們選擇X 為基變量是因?yàn)閄 的系數(shù)列向量是（1，0，0）T，現(xiàn)在我們只需要把X 的系數(shù)列向量變成（1，0，0） ，那么X 就將會(huì)代替X 的位置變成基變量，同時(shí)X 就出基了。具體的操作，我們借助單純形表2來完成。

首先將第一個(gè)約束方程中X 的系數(shù)變成1，只需等式兩邊同除以3就可以了。然后將第二個(gè)、第三個(gè)約束方程中的X 的系數(shù)變成0，只需將第一個(gè)約束方程的左右兩端乘以-2加在第二、三個(gè)約束方程的左右兩端即可（我們前面所做的都是方程組的同解變形，不會(huì)改變方程組的解。換句話說，變形后的約束方程組和變形前的本質(zhì)上是一樣的）。把上面所做的變換稱為單純行變換。這時(shí)X 已經(jīng)入基，X 已經(jīng)出基，但我們注意到X =-5，基解不是可行解！所以選擇X 出基是個(gè)錯(cuò)誤。那么該選誰出基呢，這里我們看到，要選出的出基變量必須保證新基解可行，也就是說變換后右端項(xiàng)都要大于或等于0。若令X 出基，仿照上面的單純形變換，右端項(xiàng)b 變?yōu)閎 - ·a = ≥0，b 變?yōu)?，b 變?yōu)閎 - ·a =6≥0，這時(shí)右端項(xiàng)全都大于0，我們所得到的新基解可行。怎么才能迅速地找出合適的入基變量呢？我們觀察一下上面的不等式，經(jīng)變換可得 ≥ ， ≥ 。可以看到 是｛ (j=1，2，3)｝ 中最小的那一個(gè)，因此，我們可以通過這一特征來判定出基變量，若 =min{ }，j=1，2，3 則 b 所在方程中系數(shù)非零的基變量為出基。當(dāng)然，如果是 是｛ (j=1，2，3)｝中最小的那一個(gè)，但它是負(fù)數(shù)，我們?nèi)匀徊荒苓x擇X 出基。因?yàn)檫@時(shí)x = 是負(fù)數(shù)，新基解仍不可行。由此我們必須保證所有的 ≥0，又在標(biāo)準(zhǔn)化的線性規(guī)劃問題中總有的，因此這里我們必須限定a ≥0。綜合以上的分析我們可以得到判定出基變量的方法：若X 入基，設(shè)θ=min{ |a ＞0}，j=1，2，3，若θ= 則b 所在約束方程中系數(shù)非零的基變量出基，這種方法我們稱之為最小比例原則。當(dāng)確定了出基變量后，利用前面介紹過的單純形變換，就可獲得新基的單純形表3如下：

為了進(jìn)一步判斷新的基可行解是否最優(yōu)，如前所述我們需要求出當(dāng)前基可行解的檢驗(yàn)數(shù)，為此我們需要把基變量X 在目標(biāo)函數(shù)中的系數(shù)變?yōu)榱悖趺醋瞿?？由?易知：

由于Z 和Z ′僅相差一個(gè)常數(shù)，因此Z ′的取得最優(yōu)值時(shí)Z 也應(yīng)取得最優(yōu)值，所以如果把目標(biāo)函數(shù)改為Z ′=- X + X ，那么新線性規(guī)劃問題的最優(yōu)解和原線性規(guī)劃問題的最優(yōu)解是一致的，所以判斷新LP問題的最優(yōu)性的檢驗(yàn)數(shù)也是判斷原LP問題最優(yōu)性的檢驗(yàn)數(shù)，易知新的LP問題的檢驗(yàn)數(shù)為：-3/2，5/2，我們就求得了當(dāng)前基可行解的檢驗(yàn)數(shù)為-3/2，5/2。

因?yàn)槲覀冎魂P(guān)心檢驗(yàn)數(shù)的取值，在實(shí)際運(yùn)算過程中，只需用表3系數(shù)矩陣中第二行乘以5加在Z 行中即可得到檢驗(yàn)數(shù)。這種做法其實(shí)和上面介紹的方程組同解變換是一樣的。這點(diǎn)不難體會(huì)。由此我們就得到改進(jìn)后的新基的單純形表4：

新基為（X ，X ，X ），新基的可行解為：x = ，x =0，x = ，x =0，x =6。新目標(biāo)函數(shù)Z =-5· +（-4）·0=- ，顯然新目標(biāo)函數(shù)值比原目標(biāo)函數(shù)值更小了。但從表4可以看到，當(dāng)前基可行解并非最優(yōu)解。因?yàn)闄z驗(yàn)數(shù)不全大于等于零，因此我們要進(jìn)一步優(yōu)化。仿照前面的過程繼續(xù)尋找“更好”的基可行解直到找到最優(yōu)解或確定該LP問題無最優(yōu)解為止。下面給出單純形法基本步驟的流程圖，以供大家參考：

參考文獻(xiàn)：

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

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

[3]韓伯堂.管理運(yùn)籌學(xué)(2版)[M].北京:高等教育出版社，2005.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文?！?/p>