韓偉一

(哈爾濱工業(yè)大學(xué) >經(jīng)濟與管理學(xué)院，哈爾濱150001)

1 引 言

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

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

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

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

2 檢驗數(shù)計算的新原理

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

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

則線性規(guī)劃的標(biāo)準(zhǔn)形式為

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

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

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

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

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

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

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

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

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

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

EB=CB-CDD-1B.

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

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

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

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

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

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

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

定理3若X是模型1和模型2的基可行解，D是相應(yīng)的可行基，設(shè)模型1的目標(biāo)函數(shù)值為z1，模型2的目標(biāo)函數(shù)值為z2，則z1=z2+CDD-1b.

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

z1=z2+CDD-1b.

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

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

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

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

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

步驟2 計算檢驗數(shù)，根據(jù)檢驗數(shù)判定最優(yōu)解的狀況.在發(fā)生無解或無界的情形下，算法結(jié)束，否則轉(zhuǎn)入步驟3.

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

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

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

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

步驟2 計算檢驗數(shù)向量σk，根據(jù)檢驗數(shù)判定最優(yōu)解的狀況.在發(fā)生無解或無界的情形下，算法結(jié)束，否則轉(zhuǎn)入步驟3.

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

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

步驟5 把模型的價值向量改變?yōu)棣襨.k=k+1轉(zhuǎn)入步驟2.

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

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

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

表1 第一個單純形表

表2 第二個單純形表

表3 第三個單純形表

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

根據(jù)新計算方式，還可得到如下重要的結(jié)論

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

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

性質(zhì)2根據(jù)新計算方式，可得檢驗數(shù)的遞推公式如下

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

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

步驟7k=k+1， 重復(fù)步驟2.

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

當(dāng)k=0時：

3:選取最大檢驗數(shù)對應(yīng)的變量x2為入基變量，

當(dāng)k=1時：

7:選取最大檢驗數(shù)對應(yīng)的變量x1為入基變量，

當(dāng)k=2時：

由于所有檢驗數(shù)非正則求解過程結(jié)束.

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

5 結(jié) 論

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

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