單純形法檢驗數的新計算方法

韓偉一

(哈爾濱工業大學 >經濟與管理學院，哈爾濱150001)

1 引 言

自1947年由Dantzig提出著名的單純形法以來，線性規劃的理論和應用研究蓬勃發展，已經成為一門具有豐富內容的成熟學科.當前，求解線性規劃的方法主要分為三大類，分別是單純形方法[1-2]、橢球算法[3]和內點算法[4-5].1972年Klee和Minty給出一個例子表明單純形方法具有指數時間復雜性，不是一個多項式算法[6].橢球算法盡管是多項式算法，但其實際效果不佳.當前最為推崇的是內點算法，其不僅是多項式算法，而且在實踐中具有優良的計算性能，一度認為在大規模稀疏線性規劃問題上超越了單純形法.

盡管單純形法不是多項式算法，但它具有良好的平均計算性能[7-8].特別是1973年Harris提出最陡邊規則[9-10]以后，使得單純形法與內點法呈現了伯仲難分的態勢[1].目前，單純形法擁有多個變種，大致可分為原始單純形方法、對偶單純形方法和原始-對偶單純形方法等三類.

最早的原始單純形方法由Dantzig給出，它根據目標函數的最大化或最小化要求，采用最大檢驗數規則或最小檢驗數規則確定入基變量，根據廣泛流行的θ規則來確定出基變量，根本目的是確定用以矩陣變換的主元.在文獻[1]中介紹了幾種確定主元的規則，最為常見的有最小或最大檢驗數規則、最大改進規則[11]和最陡邊規則等.無疑，不同的主元規則將產生不同的計算效率，直接決定了單純形法迭代的次數.值得指出的是，為了避免退化問題對單純形法造成的影響，潘平奇提出了虧基單純形方法[12].

檢驗數在單純形法中扮演著十分重要的角色，它的一項重要功能是判定當前解是否最優.本文通過給出檢驗數新計算方法，為有著70多年歷史的單純形法提出一種全新的實施方式.這種計算方式非常簡單，可實質性地改變單純形法的計算步驟，提高單純形法的計算效率，這將為單純形方法的教學帶來很大的方便[13].

2 檢驗數計算的新原理

首先給出線性規劃的標準形式及其相關定義.定義價值系數向量為C=(c1，c2，…，cn)，資源系數向量為b=(b1，b2，…，bn)T，決策變量向量為X=(x1，x2，…，xn)T，技術矩陣為A，它由n個列向量組成，定義如下

A=[aij]m×n=(p1，p2，…，pn)，

則線性規劃的標準形式為

為了行文方便，針對單純形方法，記

(i)X(B)為基B對應的基可行解，其中非基變量的值為0；

(ii)σ(B)=C-CBB-1A為基可行解X(B)的檢驗數向量，其中CB=(cB1，cB2，…，cBm)為基變量的價值向量，其中CBi為第i行基變量對應的價值系數；

(iii) 設單純形法共需要p次迭代，第k(0≤k≤p-1)次迭代過程中相應的基為Bk，總有B0=Im×m；

(iv) 第k次迭代過程中相應的檢驗數向量為σk(Bk)=(σk1，σk2，…，σkn)，簡寫為σk.

改進單純形法及其檢驗數計算方式的思路是，在保持約束條件不變的情況下，通過改變模型的價值系數形成新的線性規劃模型，這個新模型和模型1具有同樣的最優解和檢驗數，且新模型使得檢驗數的計算更加高效.

設D是模型1的任一可行基，檢驗數向量σ1(D)=C-CDD-1A為模型1中基可行解X(D)的檢驗數，令E=σ1(D)，則新模型如下

定理1對于任意一個基可行解，模型1和模型2具有同樣的檢驗數.

證設該基可行解對應的可行基為B，那么模型1的檢驗數為σ1(B)=C-CBB-1A.

顯然B也是模型2的可行基，設模型2中基變量的價值向量為EB，則

EB=CB-CDD-1B.

定義σ2(B)為模型2的檢驗數，則有

σ2(B)=E-EBB-1A=(C-CDD-1A)-(CB-CDD-1B)B-1A=C-CBB-1A.

從而σ1(B)=σ2(B)，命題成立.

定理2對于某個基可行解，如果其是模型1的最優解，則其也是模型2的最優解.

證若基可行解X1(B1)是模型1的最優基可行解，設最優基為B1，則檢驗數σ1(B1)≤0.顯然X1(B1)是模型2的基可行解，相應的可行基也為B1.

根據定理1，既然σ1(B1)=σ2(B1)，從而有σ2(B1)≤0，故X1(B1)也是模型2的最優基可行解.

定理1和定理2表明，可以用模型2來獲得模型1的最優解.

定理3若X是模型1和模型2的基可行解，D是相應的可行基，設模型1的目標函數值為z1，模型2的目標函數值為z2，則z1=z2+CDD-1b.

證由于z2=(C-CDD-1A)X=CX-CDD-1AX.又因為AX=b且z1=CX，從而

z1=z2+CDD-1b.

推論1模型1和模型2等價.

證兩個模型具有同樣的約束條件，且目標函數值相差一個常數，因而兩模型等價.

3 原始單純形法的新計算方式

利用上述結論可以改變原始單純形法的計算方式.原始單純形法的計算步驟如下：

步驟1 給出初始的基可行解，并使得相應的基為單位陣.

步驟2 計算檢驗數，根據檢驗數判定最優解的狀況.在發生無解或無界的情形下，算法結束，否則轉入步驟3.

步驟3 根據入基規則(本文采用最大檢驗數規則)，確定入基變量；根據θ規則確定出基變量；根據入基變量和出基變量的下標確定主元.

步驟4 以主元為中心進行矩陣變換得到新的基可行解.再轉到步驟2.

在上述原始單純形法中，采用的入基規則可以為最大檢驗數規則、目標函數值最大改進規則或其它規則.新的計算方式如下

步驟1 給出初始的基可行解，并使得相應的基為單位陣，k=0，基為Bk=Im×m.

步驟2 計算檢驗數向量σk，根據檢驗數判定最優解的狀況.在發生無解或無界的情形下，算法結束，否則轉入步驟3.

步驟3 根據入基規則(本文采用最大檢驗數規則)，確定入基變量；根據θ規則確定出基變量；根據入基變量和出基變量的下標確定主元.

步驟4 以主元為中心進行矩陣變換得到新的基可行解.

步驟5 把模型的價值向量改變為σk.k=k+1轉入步驟2.

下面以例1來說明新計算方式的計算效率

例1maxz=4x1+6x2+x3+x4-x5-2x6.

采用單純形表，計算過程如下

表1 第一個單純形表

表2 第二個單純形表

表3 第三個單純形表

根據上例可以看出，新計算方法之所以能提高計算效率，根本原因在于：用檢驗數替換價值系數后，基變量的價值系數向量總有m-1個分量為0，這給檢驗數的計算帶來了極大便利，因而能夠顯著提高檢驗數的計算效率.

根據新計算方式，還可得到如下重要的結論

性質1對于新計算方式，從第2個表開始，基變量的價值系數總是非負的.

證根據前述基變量的價值系數有m-1個的值為0，另外一個為上個表中入基變量的檢驗數，因而只能為非負.命題得證.

性質2根據新計算方式，可得檢驗數的遞推公式如下

證根據檢驗數計算公式及新計算方式的過程立即可得.

4 修正單純形法的新計算方式

步驟7k=k+1， 重復步驟2.

下面用例1來對比原修正單純法和新方法的區別.原方法的計算步驟如下：

當k=0時：

3:選取最大檢驗數對應的變量x2為入基變量，

當k=1時：

7:選取最大檢驗數對應的變量x1為入基變量，

當k=2時：

由于所有檢驗數非正則求解過程結束.

相對于原方法，新方法僅需修改如下兩個步驟：

5 結 論

本文使用檢驗數來替換價值系數得到了線性規劃模型的等價模型，進而給出了單純形法的新實現方式.這種新方式顯著提高了單純形法檢驗數的計算效率，提升了單純形法的計算績效，實質性地改變了單純形法的計算步驟.這種新方式盡管原理簡單，但它具有很廣的應用價值，還可以應用于對偶單純形法、目標規劃單純形法、運輸單純形法等多個場合，能夠提高這些方法的計算效率，無疑將有利于運籌學的教學.

致謝作者非常感謝相關文獻對本文的啟發以及審稿專家提出的寶貴意見.