單純形法檢驗(yàn)數(shù)的新計(jì)算方法

韓偉一

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

1 引 言

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

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

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

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

2 檢驗(yàn)數(shù)計(jì)算的新原理

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

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

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

為了行文方便，針對(duì)單純形方法，記

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

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

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

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

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

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

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

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

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

EB=CB-CDD-1B.

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

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

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

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

證若基可行解X1(B1)是模型1的最優(yōu)基可行解，設(shè)最優(yōu)基為B1，則檢驗(yàn)數(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來(lái)獲得模型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.又因?yàn)锳X=b且z1=CX，從而

z1=z2+CDD-1b.

推論1模型1和模型2等價(jià).

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

3 原始單純形法的新計(jì)算方式

利用上述結(jié)論可以改變?cè)紗渭冃畏ǖ挠?jì)算方式.原始單純形法的計(jì)算步驟如下：

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

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

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

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

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

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

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

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

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

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

下面以例1來(lái)說(shuō)明新計(jì)算方式的計(jì)算效率

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

采用單純形表，計(jì)算過(guò)程如下

表1 第一個(gè)單純形表

表2 第二個(gè)單純形表

表3 第三個(gè)單純形表

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

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

性質(zhì)1對(duì)于新計(jì)算方式，從第2個(gè)表開(kāi)始，基變量的價(jià)值系數(shù)總是非負(fù)的.

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

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

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

4 修正單純形法的新計(jì)算方式

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

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

當(dāng)k=0時(shí)：

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

當(dāng)k=1時(shí)：

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

當(dāng)k=2時(shí)：

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

相對(duì)于原方法，新方法僅需修改如下兩個(gè)步驟：

5 結(jié) 論

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

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