廈門(mén)大學(xué)運(yùn)籌學(xué)2

第二章對(duì)偶理論與靈敏度分析

在這一章中，我們將通過(guò)舉例來(lái)說(shuō)明線性規(guī)劃對(duì)偶問(wèn)題的提出并說(shuō)明它的經(jīng)濟(jì)意義；由此來(lái)闡述它們兩者之間的關(guān)系。進(jìn)一步來(lái)探討如何求一個(gè)線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題、以及線性規(guī)劃與它的對(duì)偶問(wèn)題之間的關(guān)系、對(duì)偶單純形算法以及對(duì)線性規(guī)劃問(wèn)題解的變化的進(jìn)一步討論（即靈敏度分析和參數(shù)規(guī)劃等等）。第一節(jié)對(duì)偶問(wèn)題的提出在第一章第一節(jié)的例1中，我們討論了工廠生產(chǎn)計(jì)劃模型及其解法，現(xiàn)從另一個(gè)角度來(lái)討論這個(gè)問(wèn)題。假設(shè)該工廠的決策者決定不生產(chǎn)產(chǎn)品I、II，而將其所有資源出租或出售。這時(shí)，工廠的決策者就要考慮給每種資源進(jìn)行定價(jià)的問(wèn)題。設(shè)用

y1、y2、y3

分別表示出租單位設(shè)備臺(tái)時(shí)的租金和出讓單位原材料A、B

的附加費(fèi)。作決策時(shí)，需要如下的比較：若一個(gè)單位設(shè)備臺(tái)時(shí)和四個(gè)單位原材料A可以生產(chǎn)一件產(chǎn)品I，可獲利2元，那么生產(chǎn)每件產(chǎn)品I的設(shè)備臺(tái)時(shí)和原材料出租和出讓的所有收入應(yīng)不低于生產(chǎn)一件產(chǎn)品I的利潤(rùn)。這就有：

y1+4y2

2；對(duì)于產(chǎn)品II同理有：2y2+4y3

3；把工廠所有設(shè)備臺(tái)時(shí)和資源都出租和出讓，其收入應(yīng)為：w=8y1+16y2+12y3。從工廠的決策者來(lái)看，當(dāng)然希望w

的值越大越好；但從接受者的角度來(lái)看，他支付的越少越好。所以工廠決策者只能在滿足所有產(chǎn)品的單位利潤(rùn)條件下，使其總收入盡可能地小，才能實(shí)現(xiàn)工廠決策者的意愿。為此需要解如下的線性規(guī)劃問(wèn)題：我們稱這個(gè)線性規(guī)劃問(wèn)題為例1線性規(guī)劃問(wèn)題（我們稱為原問(wèn)題）的對(duì)偶問(wèn)題。根據(jù)上述例題可見(jiàn)，對(duì)于形如如下形式的線性規(guī)劃問(wèn)題：我們可以馬上得出它的對(duì)偶問(wèn)題：其中：AT、bT

分別是原線性規(guī)劃問(wèn)題中的約束條件矩陣A的轉(zhuǎn)置矩陣與約束條件中右邊列向量的轉(zhuǎn)置(即為行向量)。從以上的線性規(guī)劃問(wèn)題和其對(duì)偶問(wèn)題中，我們可以得出：原問(wèn)題的約束條件的個(gè)數(shù)m

就是對(duì)偶問(wèn)題的變量的個(gè)數(shù)；原問(wèn)題的變量的個(gè)數(shù)n

就是對(duì)偶問(wèn)題的約束條件的個(gè)數(shù)；若原問(wèn)題的目標(biāo)函數(shù)是Max型，則對(duì)偶問(wèn)題的目標(biāo)函數(shù)必是Min型。它們二者的最優(yōu)目標(biāo)函數(shù)值相等。二、對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋——影子價(jià)格設(shè)B

是線性規(guī)劃問(wèn)題{MaxZ=CTX|AX

b，X0}的最優(yōu)基，則該線性規(guī)劃問(wèn)題的最優(yōu)解為(B-1b，0)T，其對(duì)應(yīng)的目標(biāo)函數(shù)最優(yōu)值則為：Z*=CTB-1b=(Y*)b，其中：Y*=CTB-1(我們稱為單純形乘子)由此可得：所以變量的經(jīng)濟(jì)義是在其它條件不變的情況下，第i種資源的變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。由第一章的例1的最終計(jì)算表表1—7可見(jiàn)：這說(shuō)明，在其它條件不變的情況下，機(jī)器臺(tái)時(shí)增加一臺(tái)時(shí)，該廠按最優(yōu)計(jì)劃安排生產(chǎn)可多獲利1.5元，原材料A

每增加一公斤，可多獲利0.125元，原材料B每增加一公斤，對(duì)獲利沒(méi)有影響。從上圖我們可以看到：設(shè)備每增加一臺(tái)時(shí)，代表約束條件的直線就由移至

，相應(yīng)地最優(yōu)解由點(diǎn)A=(4，2)移到點(diǎn)B=(4，2.5)，目標(biāo)函數(shù)值Z=24+32.5=15.5，即比原來(lái)的增大1.5。又若原材料A

增加一公斤，代表約束條件的直線就由

移至'，相應(yīng)地最優(yōu)解由點(diǎn)A=(4，2)移到點(diǎn)B=(4.25，1.875)，目標(biāo)函數(shù)值Z=24.25+31.875=14.125，即比原來(lái)的增大0.125。原材料B

增加一公斤時(shí)，該約束條件的直線由

移至

‘，這時(shí)的最優(yōu)解不變。

yi

的值代表對(duì)第i

種資源的估價(jià)。這種估價(jià)是針對(duì)具體產(chǎn)品而存在的一種特殊價(jià)格，我們稱它為“影子價(jià)格”。在該廠現(xiàn)有資源和現(xiàn)有生產(chǎn)方案的條件下，設(shè)備的每小時(shí)出租費(fèi)為1.5元，一公斤原材料A

的出讓費(fèi)為除成本外再附加0.125元，一公斤原材料B

可按原成本出讓，這時(shí)該廠的收入與自己組織生產(chǎn)時(shí)獲利相等。影子價(jià)格隨具體情況而異。在完全市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，企業(yè)應(yīng)買(mǎi)進(jìn)該資源用于擴(kuò)大再生產(chǎn)；而當(dāng)某種資源的市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，則企業(yè)的決策者應(yīng)把已有的資源賣(mài)出，這時(shí)企業(yè)的獲利比由自己生產(chǎn)的還高?？梢?jiàn)，影子價(jià)格對(duì)市場(chǎng)有調(diào)節(jié)作用。下面再?gòu)牧硪粋€(gè)角度來(lái)討論該問(wèn)題：從第一章第三節(jié)得到的檢驗(yàn)數(shù)的表達(dá)式是CNT-CBTB-1N

與0–CBTB-1（松弛變量對(duì)應(yīng)的檢驗(yàn)數(shù)）。當(dāng)滿足條件：CNT-CBTB-1N

0，–CBTB-1

0(2.1)這表示線性規(guī)劃問(wèn)題已得到最優(yōu)解?？梢?jiàn)(2.1)式是作為得到最優(yōu)解的條件。引進(jìn)記號(hào)YT=CBTB-1，稱為單純形乘子。由(2.1)式，可知對(duì)于最優(yōu)解所對(duì)應(yīng)的單純形表有Y0。對(duì)應(yīng)于基變量XB

的檢驗(yàn)數(shù)是0，它是CBT-CBTB-1B=0。包括基變量在內(nèi)的所有檢驗(yàn)數(shù)可用CT-CBTB-1A

0表示。由此可以得到CT-YTA

0即ATY

C。由于-YT=-CBTB-1，將此式兩邊同時(shí)右乘于b

得到：-YTb=-CBTB-1b即：YTb=CBTB-1b=Z綜合1、2、3的討論，我們可以得到另一個(gè)線性規(guī)劃問(wèn)題：(2.2)稱此線性規(guī)劃問(wèn)題為原線性規(guī)劃問(wèn)題{MaxZ=CTX|AX

b，X0}的對(duì)偶線性規(guī)劃問(wèn)題。從這兩個(gè)規(guī)劃問(wèn)題的表達(dá)式可以看出，只要根據(jù)原線性規(guī)劃問(wèn)題的系數(shù)矩陣A、C、b，就可以寫(xiě)出它的對(duì)偶問(wèn)題。

第二節(jié)線性規(guī)劃問(wèn)題的對(duì)偶理論以上討論可以直觀地了解到原線性規(guī)劃問(wèn)題與對(duì)偶問(wèn)題之間的關(guān)系，這一節(jié)將從理論上進(jìn)一步討論線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題。2.1原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系

由第一節(jié)的討論，如下形式的線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題是(2.2)(2.3)我們稱(2.3)與(2.2)是原問(wèn)題與對(duì)偶問(wèn)題的標(biāo)準(zhǔn)形式。對(duì)其他形式的原問(wèn)題的對(duì)偶問(wèn)題，我們可進(jìn)行如下分析：首先我們可以總結(jié)得出：

1.線性規(guī)劃原問(wèn)題的約束條件的個(gè)數(shù)m，就是其對(duì)偶問(wèn)題的變量的個(gè)數(shù)；原問(wèn)題的變量個(gè)數(shù)n，就是其對(duì)偶問(wèn)題的約束條件的個(gè)數(shù)。

在原問(wèn)題目標(biāo)函數(shù)為極大化（Max）的條件下有：

2.若原問(wèn)題的第i個(gè)約束條件是“”，則對(duì)偶問(wèn)題的第i個(gè)變量yi

0；原問(wèn)題的第i個(gè)約束條件是“”，則對(duì)偶問(wèn)題的第i個(gè)變量yi

0（0

i

m）。

證明：對(duì)于“”約束條件，由標(biāo)準(zhǔn)型(2.3)與(2.2)可知：

yi

0，0

i

m；對(duì)于“”約束條件，設(shè)：

ai1x1+ai2x2+···+ainxn

bi

將上式兩邊同乘以（-1）得：

（-ai1x1）+（-ai2x2）+···+（-ainxn）

-bi

利用標(biāo)準(zhǔn)型對(duì)偶關(guān)系可知原問(wèn)題的對(duì)偶問(wèn)題是：另–yi/=yi，則yi

0，上述問(wèn)題變成：

3.若原問(wèn)題的第i個(gè)約束條件是“=”，則對(duì)偶問(wèn)題的第i個(gè)變量yi

無(wú)約束。

證明：對(duì)于“=”約束條件，設(shè)：ai1x1+ai2x2+···+ainxn

=bi

則此式等價(jià)于ai1x1+ai2x2+···+ainxn

bi

-ai1x1

-

ai2x2

-

···-

ainxn

-bi

利用標(biāo)準(zhǔn)型對(duì)偶關(guān)系可知原問(wèn)題的對(duì)偶問(wèn)題是：令yi=yi/-yi//

，則顯然yi

無(wú)非負(fù)限制，上述問(wèn)題變成如下形式：

4.若原問(wèn)題的第j

個(gè)變量xj

0，則對(duì)偶問(wèn)題的第j

個(gè)約束條件為“”型；若原問(wèn)題的第j

個(gè)變量xj

0，則對(duì)偶問(wèn)題的第j

個(gè)約束條件為“”型。

證明：對(duì)于xj

0，則由標(biāo)準(zhǔn)型(2.3)與(2.2)可知對(duì)偶問(wèn)題的第j

個(gè)約束條件為“”型；對(duì)于xj

0，問(wèn)題，令：

xj/=-xj，則xj/

0，原問(wèn)題變成：其對(duì)偶問(wèn)題變?yōu)椋杭礊椋?/p>

5.若原問(wèn)題的第j

個(gè)變量xj

無(wú)約束，則其對(duì)偶問(wèn)題的第j

個(gè)約束條件為“=”號(hào)。

證明：假設(shè)xj

無(wú)約束，令xj=xj/-xj//

，則原問(wèn)題和對(duì)偶問(wèn)題分別為如下形式：原問(wèn)題：對(duì)偶問(wèn)題：即：綜合1、2、3、4、5點(diǎn)，線性規(guī)劃問(wèn)題與其對(duì)偶問(wèn)題的關(guān)系其變換形式可歸結(jié)為如下表2—1：

表2—1原問(wèn)題對(duì)偶問(wèn)題目標(biāo)函數(shù)（maxZ）目標(biāo)函數(shù)（minW）約束條件個(gè)數(shù)m

個(gè)對(duì)偶變量個(gè)數(shù)m

個(gè)約束條件為“”型對(duì)偶變量為“0”約束條件為“”型對(duì)偶變量為“

0”約束條件為“=”型對(duì)偶變量為無(wú)約束變量個(gè)數(shù)為n

個(gè)約束條件個(gè)數(shù)為n

個(gè)變量為“0”約束條件為“”型變量為“

0”約束條件為“”型變量為無(wú)約束約束條件為“=”型下面舉一例說(shuō)明如何利用以上規(guī)則來(lái)求一個(gè)線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題。

例1試求如下線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題

解：設(shè)對(duì)應(yīng)于約束條件(1)，(2)，(3)的對(duì)偶變量分別為y1y2，y3，則由表2—1中原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系，可以直接寫(xiě)出上面問(wèn)題的對(duì)偶問(wèn)題，它是：

2.2對(duì)偶問(wèn)題的基本定理

1.對(duì)稱性：線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。

證明：設(shè)原問(wèn)題是：maxZ=CTX；AX

b；X0。它的對(duì)偶問(wèn)題是：minW=bTY；ATY

C；Y0。將此對(duì)偶問(wèn)題作形式上的變換，等價(jià)于：

max(-W)=-bTY；-ATY

-C；Y0；這個(gè)問(wèn)題的對(duì)偶問(wèn)題是：

minZ/=-CTX；-AX

-b；X0；即：max(-Z/)=CTX；AX

b；X0;也就是原問(wèn)題。

2.弱對(duì)偶性：假如X*與Y*分別是原問(wèn)題與對(duì)偶問(wèn)題的可行解。則必有：CTX*

bTY

*。

證明：假設(shè)原問(wèn)題與對(duì)偶問(wèn)題分別是(2.3)與(2.2)形式，因?yàn)閄*

是原問(wèn)題的可行解，所以滿足約束條件，即：

AX*

b；X*0由因?yàn)閅*0，所以有：(Y*)TAX*

(Y*)Tb

=

bTY

*；又Y*是對(duì)偶問(wèn)題的可行解，所以滿足約束條件，即：ATY

*

C；Y*0由因?yàn)閄*0，所以有：(X*)TATY

*

(X*)TC=CTX

*

又因?yàn)椋?Y*)TAX*=(X*)TATY

*

所以有：CTX

*

bTY

*。3.無(wú)界性：若原問(wèn)題（對(duì)偶問(wèn)題）為無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解。

證明：由弱對(duì)偶性顯然便可得到。應(yīng)當(dāng)指出的是本性質(zhì)不存在逆，即當(dāng)原問(wèn)題（對(duì)偶問(wèn)題）無(wú)可行解時(shí)，并不能斷言對(duì)偶問(wèn)題（原問(wèn)題）必定具有無(wú)界解。如下問(wèn)題便可說(shuō)明：

例2：原問(wèn)題對(duì)偶問(wèn)題顯然在例2中，原問(wèn)題與對(duì)偶問(wèn)題都沒(méi)有可行界。

4.可行解是最優(yōu)解時(shí)的性質(zhì)：設(shè)X*與Y*分別是原問(wèn)題與對(duì)偶問(wèn)題的可行解，當(dāng)CTX

*=

bTY

*

時(shí)，

X*與Y*分別是原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解解。

證明：當(dāng)CTX

*=

bTY

*

時(shí)，根據(jù)弱對(duì)偶性可知，對(duì)于對(duì)偶問(wèn)題的任何一個(gè)可行解Y，都有bTY

CTX

*=

bTY

*，可見(jiàn)Y

*

是對(duì)偶問(wèn)題的最優(yōu)解。同理可證明：對(duì)于原問(wèn)題的任何一個(gè)可行解X，比有CTX

*=

bTY

*

CTX，所以X

*必然是原問(wèn)題的最優(yōu)解。

5.對(duì)偶定理：若原問(wèn)題有最優(yōu)解，則其對(duì)偶問(wèn)題也有最優(yōu)解，且它們的目標(biāo)函數(shù)值相等。

證明：設(shè)X*是原問(wèn)題最優(yōu)的基可行解，它對(duì)應(yīng)的基矩陣為B必使得CT-CBTB-1A

0，即得到(Y*)TA

CT

也就是

ATY

*

C，其中：(Y*)T=CBTB-10這時(shí)Y*

是對(duì)偶問(wèn)題的可行解，它使得：(Y*)Tb=CBTB-1b=CTX

*

由性質(zhì)4可知，Y*

是對(duì)偶問(wèn)題的可行解。

6.互補(bǔ)松弛性：若X*與Y*分別是原問(wèn)題與對(duì)偶問(wèn)題的可行解，那么(Y*)TXs=0和YsTX=0的充分必要條件是X*與Y*分別是原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解解。這里Xs

和Ys

分別為原問(wèn)題與對(duì)偶問(wèn)題的松弛向量和剩余向量。

證明：設(shè)原問(wèn)題和對(duì)偶問(wèn)題的標(biāo)準(zhǔn)型是：原問(wèn)題對(duì)偶問(wèn)題將原問(wèn)題目標(biāo)函數(shù)中的系數(shù)向量C

用C=ATY–Ys

代替，得到：Z=(ATY–Ys)TX=YTAX–YsTX(2.4)將對(duì)偶問(wèn)題目標(biāo)函數(shù)中的系數(shù)向量b

用b=AX+Xs代替，得到：W=YT(AX+Xs)=YTAX+YTXs(2.5)

若(Y*)TXs=0和YsTX*=0，則

CTX

*=

bTY

*=(Y*)TAX*

由性質(zhì)4可知X*與Y*分別是原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解。由若X*與Y*分別是原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解，由性質(zhì)2可知CTX

*=(Y*)TAX*

=

bTY

*

再由(2.4)、(2.5)式知道，這時(shí)必有(Y*)TXs=0和YsTX*=0

7.設(shè)原問(wèn)題是：maxZ=CTX；AX+Xs=b；X，Xs

0對(duì)偶問(wèn)題是：minW=YTb；ATY–Ys=C；Y，Ys

0則原問(wèn)題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問(wèn)題的一個(gè)基解

，其對(duì)應(yīng)關(guān)系見(jiàn)表2—2。

表2—2XBXNXs0CNT–CBTB-1N-CBTB-1Ys1-Ys2T-Y

這里Ys1是對(duì)應(yīng)原問(wèn)題中基變量XB

的剩余變量，Ys2是對(duì)應(yīng)原問(wèn)題中非基變量XN

的剩余變量。

證明：設(shè)B

是原問(wèn)題的一個(gè)可行基，于是A=(B,N)；原問(wèn)題可改寫(xiě)為：相應(yīng)地對(duì)偶問(wèn)題可表示為：這里：，當(dāng)求得原問(wèn)題的一個(gè)可行解XB=B-1b時(shí)，其相應(yīng)的非基變量XN、Xs

檢驗(yàn)數(shù)為：CNT–CBTB-1N-CBTB-1。現(xiàn)分析這些檢驗(yàn)數(shù)與對(duì)偶問(wèn)題的解之間的關(guān)系：令YT=CBTB-1，將它代入(2.6)、(2.7)式得到Y(jié)s1=0，

-Ys2T=CNT–CBTB-1N。

現(xiàn)舉兩個(gè)例子說(shuō)明這些性質(zhì)的應(yīng)用。

例3：對(duì)于如下線性規(guī)劃問(wèn)題，試?yán)脤?duì)偶理論證明該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。

證明：首先我們可以知道該線性規(guī)劃問(wèn)題存在可行解X=(0，0，0)；而上述問(wèn)題的對(duì)偶問(wèn)題是：由第一約束條件可知對(duì)偶問(wèn)題無(wú)可行解，因此無(wú)最優(yōu)解。再由對(duì)偶定理可知原問(wèn)題必?zé)o最優(yōu)解。

例4已知線性規(guī)劃問(wèn)題：的對(duì)偶問(wèn)題的最優(yōu)解為y1*=4/5，y2*=3/5，目標(biāo)函數(shù)值為Z*=5，試用對(duì)偶理論找出原問(wèn)題的最優(yōu)解。

解：首先寫(xiě)出該線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題：將y1*、y2*

的值代入約束條件，得(2)、(3)、(4)為嚴(yán)格不等式；由互補(bǔ)松弛性（性質(zhì)6）可得：x2*=x3*=x4*=0，同樣由互補(bǔ)松弛性，因?yàn)閥1*、y2*>0，所以原問(wèn)題的兩個(gè)約束條件應(yīng)該取等式，故有：求解此方程組便可得到：x1*=1，x5*=1；所以原問(wèn)題的最優(yōu)解為：X*=(x1*,x2*,x3*,x4*,x5*)=(1,0,0,0,1)。

最優(yōu)目標(biāo)函數(shù)值為：W

*=5。

第三節(jié)對(duì)偶單純形算法

本章第二節(jié)講到原問(wèn)題與對(duì)偶問(wèn)題的解之間的對(duì)應(yīng)關(guān)系（性質(zhì)7）時(shí)指出：在單純形表進(jìn)行迭代計(jì)算時(shí)，在列中得到的是原問(wèn)題的基可行解，而在檢驗(yàn)數(shù)行中得到的是對(duì)偶問(wèn)題的基解。通過(guò)逐步迭代計(jì)算，當(dāng)在檢驗(yàn)數(shù)行得到對(duì)偶問(wèn)題的解也是可行解時(shí)，根據(jù)性質(zhì)2、4便可知道，已得到最優(yōu)解。此時(shí)原問(wèn)題與對(duì)偶問(wèn)題都是最優(yōu)解。根據(jù)對(duì)偶問(wèn)題的對(duì)稱性，也可以這樣考慮問(wèn)題：若保持對(duì)偶問(wèn)題的解是基可行解，即檢驗(yàn)數(shù)：

σj=cj–CBTB-1Pj

0

而原問(wèn)題在非可行解的基礎(chǔ)上，通過(guò)逐步迭代計(jì)算達(dá)到可行，即：0，這樣也可以得到原問(wèn)題的最優(yōu)解。其優(yōu)點(diǎn)是原問(wèn)題的初始解不一定要求是基可行解，可從非基可行解開(kāi)始迭代計(jì)算。這個(gè)方法可具體表述如下：設(shè)原問(wèn)題是：又設(shè)B

是一個(gè)基（不一定是可行基），不失一般性，令

B=(P1,P2,···,Pm)

它對(duì)應(yīng)的基變量為XB=(x1,x2,···,xm)T

。當(dāng)非基變量都為0時(shí)可以得到XB=B-1b。若在B-1b

中至少有一個(gè)負(fù)分量，設(shè)(B-1b)i<0，并且在單純形表檢驗(yàn)數(shù)行中的檢驗(yàn)數(shù)都0，即對(duì)偶問(wèn)題保持可行，它的各分量是：對(duì)應(yīng)于基變量x1,x2,···,xm

的檢驗(yàn)數(shù)是σj=cj–CBTB-1Pj

=0，j=1,2,···,m

對(duì)應(yīng)于非基變量

xm+1,xm+2,···,xn的檢驗(yàn)數(shù)是σj=cj–CBTB-1Pj

0，j=

m+1,···,n

每次迭代是將基變量中的負(fù)分量xl

取出，去替換非基變量中的xk

，并使所有檢驗(yàn)數(shù)繼續(xù)保持0。在列中小于的元素個(gè)數(shù)要減少。即從原問(wèn)題來(lái)看，經(jīng)過(guò)每次迭代，原問(wèn)題由非可行解向可行解靠近，而當(dāng)原問(wèn)題得到可行解時(shí)，便得到了原問(wèn)題的最優(yōu)解。

對(duì)偶單純形算法的計(jì)算步驟如下：（1）首先根據(jù)線性規(guī)劃問(wèn)題，列出初始單純形表。（所給出的基要使得非基變量檢驗(yàn)數(shù)全都0，也就是所給出的解是一個(gè)對(duì)偶可行解，這時(shí)也稱所給出的基為對(duì)偶可行基），檢查列的數(shù)字，若都為非負(fù)，則已得到原問(wèn)題的最優(yōu)解，停止計(jì)算。（2）若列中存在某個(gè)，且所對(duì)應(yīng)的該行的系數(shù)矩陣元素，則原問(wèn)題無(wú)可行解，停止計(jì)算。我們對(duì)第（2）項(xiàng)內(nèi)容說(shuō)明如下：取，這時(shí)可知

Y

T是對(duì)偶問(wèn)題的可行解，對(duì)應(yīng)于這個(gè)可行解的對(duì)偶問(wèn)題的目標(biāo)函數(shù)值是：即對(duì)偶問(wèn)題的可行解使得對(duì)偶問(wèn)題目標(biāo)函數(shù)值無(wú)界，則由性質(zhì)3（無(wú)界性）可知原問(wèn)題沒(méi)有可行解。(3)若非（1）、（2）情形，則進(jìn)行基變換，具體如下：首先確定換出變量：由

對(duì)應(yīng)的基變量xl

為換出變量。其次確定換入變量：由

對(duì)應(yīng)的非基變量xk

為換入變量（只有這樣，才能保持得到的對(duì)偶問(wèn)題的解仍為可行解）。（4）以ylk

為主元素，按原單純形算法在表中進(jìn)行迭代運(yùn)算（即進(jìn)行基變換），得到新的計(jì)算表。

重復(fù)（1）~（4）的步驟，直到的所有分量全都0。

下面舉例說(shuō)明具體算法。

例5用對(duì)偶單純形算法求解如下線性規(guī)劃問(wèn)題

解：先將該問(wèn)題化成下面形式，以便得到原問(wèn)題的一個(gè)對(duì)偶初始可行解，進(jìn)而得到一個(gè)初始對(duì)偶可行基。以x4,x5

為初始基變量，建立這個(gè)問(wèn)題的初始單純形表，見(jiàn)表2—3；然后，利用對(duì)偶單純形算法進(jìn)行計(jì)算得到表2—4、表2—5，具體如下：表2—3Cj

-2-3-400CBXBx1x2x3x4x50x4-3-1-2-1100x5-4[-2]1-301

j0-2-3-400

表2—4Cj

-2-3-400CBXBx1x2x3x4x50x4-10[-5/2]1/21-1/2-2x121-1/23/20-1/2

j40-4-10-1

表2—5Cj

-2-3-400CBXBx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5

j28/500-3/5-8/5-1/5在表2—5中，，檢驗(yàn)數(shù)全都0，所以原問(wèn)題的最優(yōu)解為X

*=(x1*,x2*,x3*,x4*,x5*)=(11/5,2/5,0,0,0)。

原問(wèn)題對(duì)應(yīng)于兩個(gè)約束條件的對(duì)偶變量分別為y1,y2,則由表2—5的檢驗(yàn)數(shù)行便可得出原問(wèn)題的對(duì)偶問(wèn)題的最優(yōu)解是Y*=(y1*,y2*)=(8/5,1/5)即對(duì)應(yīng)于原問(wèn)題的兩個(gè)松弛變量x4

和x5

的檢驗(yàn)數(shù)的反號(hào)。從以上求解過(guò)程可以看到，對(duì)偶單純形算法有以下優(yōu)點(diǎn)：(1)初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都0，就可以進(jìn)行基變換，這時(shí)無(wú)需加人工變量，因此，可以簡(jiǎn)化計(jì)算。(2)當(dāng)變量多于約束條件時(shí)，對(duì)于這樣的線性規(guī)劃問(wèn)題，用對(duì)偶單純形算法計(jì)算可以減少計(jì)算工作量。因此，對(duì)變量較少而約束條件較多的線性規(guī)劃問(wèn)題，可先將它變換成對(duì)偶問(wèn)題，然后利用對(duì)偶單純形算法求解。（3）在靈敏度分析中，有時(shí)需要利用對(duì)偶單純形算法，這樣可使問(wèn)題的處理簡(jiǎn)化。

當(dāng)然，對(duì)偶單純形算法也有它的不足之處，其極限性主要是，對(duì)大多數(shù)線性規(guī)劃問(wèn)題，很難找到一個(gè)初始對(duì)偶可行解（基），因此，這種方法在求解線性規(guī)劃問(wèn)題時(shí)很少單獨(dú)使用。

第四節(jié)靈敏度分析在以前討論線性規(guī)劃問(wèn)題時(shí)，都假定aij,bi

,cj

都是常數(shù)。但實(shí)際上這些系數(shù)往往是估計(jì)值或預(yù)測(cè)值。如果市場(chǎng)條件發(fā)生變化，cj

值就會(huì)發(fā)生變化；aij

往往是因?yàn)楣に嚄l件的改變而改變；

bi

是根據(jù)資源投入后的經(jīng)濟(jì)效果決定的一種決策選擇。因此，我們會(huì)提出這樣的問(wèn)題（1）當(dāng)這些系數(shù)有一個(gè)或若干個(gè)發(fā)生變化時(shí)，原先已求得的線性規(guī)劃問(wèn)題的最優(yōu)解會(huì)有什么變化；（2）或者這些系數(shù)在什么范圍變化時(shí)，線性規(guī)劃問(wèn)題的最優(yōu)解或最優(yōu)基不變。前一個(gè)問(wèn)題我們稱為參數(shù)規(guī)劃，將在第五節(jié)中討論；而后一個(gè)問(wèn)題我們稱為靈敏度分析，將在本節(jié)中進(jìn)行討論。顯然，當(dāng)線性規(guī)劃問(wèn)題中這些系數(shù)有一個(gè)或若干個(gè)發(fā)生變化時(shí)，原先已求得的線性規(guī)劃問(wèn)題的最優(yōu)解一般是會(huì)發(fā)生變化的。當(dāng)然可以用單純形算法從頭開(kāi)始計(jì)算，以便得到新的最優(yōu)解。但是，這樣做很麻煩，而且也沒(méi)有必要。由于在單純形法迭代計(jì)算時(shí)，每次計(jì)算都和基變量所對(duì)應(yīng)的系數(shù)矩陣B

有關(guān)，因此，可以把發(fā)生變化的個(gè)別系數(shù)，經(jīng)過(guò)一定計(jì)算后直接填入最終計(jì)算表中，并進(jìn)行檢查和分析，可按表2—6中的幾種情況進(jìn)行處理。下面就各種情況分別進(jìn)行討論。

表2—6原問(wèn)題對(duì)偶問(wèn)題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解表中的解仍為最優(yōu)解可行解非可行解用單純形法繼續(xù)計(jì)算求最優(yōu)解非可行解可行解用對(duì)偶單純形法繼續(xù)計(jì)算求最優(yōu)解非可行解非可行解引進(jìn)人工變量，編制新的單純形表求最優(yōu)解

4.1資源數(shù)量變化的分析資源數(shù)量變化是指系數(shù)br

發(fā)生變化，即br/=

br+Δbr

。并假定規(guī)劃問(wèn)題其他系數(shù)都保持不變；這樣使最終表中原問(wèn)題的解相應(yīng)地變化為：XB/=B-1(b+Δb)

這里Δb=(0,···,Δbr,···,0)T

，只要XB/

0，最終表中檢驗(yàn)數(shù)不變，則最優(yōu)基不變。但最優(yōu)解的值發(fā)生了變化，所以XB/

為新的最優(yōu)解。新最優(yōu)解的值可允許變化范圍用以下方法確定。這時(shí)在最終表中求得的列的所有元素：由此可得：即當(dāng)約束條件中的第r

種資源變化范圍的改變量在上述范圍變化時(shí)，原問(wèn)題的最優(yōu)基不發(fā)生變化。例如我們求第一章例1中第二個(gè)約束條件b2

的變化范圍Δb2

時(shí)，可計(jì)算：因此，b2

的變化范圍是：b2+Δb2=[8，32]。

例6我們知道第一章例1中，每設(shè)備臺(tái)時(shí)的影子價(jià)格為1.5元，若該廠又從別處抽出4個(gè)臺(tái)時(shí)用于生產(chǎn)產(chǎn)品I、II，求這時(shí)該廠生產(chǎn)產(chǎn)品I、II的最優(yōu)方案。

解：首先計(jì)算將上述結(jié)果反映到最終計(jì)算表中，得表2—7，并利用對(duì)偶單純形算法求得表2—8如下：

表2—7Cj

23000CBXBx1x2x3x4x52x14+01000.2500x54-800[-2]0.513x22+2010.5-0.1250

j00-1.5-0.1250表2—8Cj

23000CBXBx1x2x3x4x52x141000.2500x32001-0.25-0.53x2301000.25

j000-0.5-0.75即該廠最優(yōu)生產(chǎn)方案應(yīng)改為生產(chǎn)產(chǎn)品I4件，生產(chǎn)產(chǎn)品II3件，最大獲利Z*=42+33=17（元）。從表2—8中可看出x3=2，即設(shè)備有2臺(tái)時(shí)未利用。

4.2目標(biāo)函數(shù)中價(jià)值系數(shù)cj

的變化分析

可以分別就cj

對(duì)應(yīng)的變量是非基變量和基變量?jī)煞N情形加以討論：（1）若cj

對(duì)應(yīng)的變量xj

是非基變量，這時(shí)它在計(jì)算表中所對(duì)應(yīng)的檢驗(yàn)數(shù)是：σj=cj–CBTB-1Pj

當(dāng)cj

變化Δcj

后，為了保證最終表中這個(gè)檢驗(yàn)數(shù)仍然小于0，即：σj/=cj

+Δcj

–CBTB-1Pj

0

cj

+Δcj

YTPj(YT=CBTB-1)

Δcj

YTPj

-cj=-σj

即Δcj

的值必須小于等于YTPj

-cj

，也就是-σj

，才可以滿足原解仍然是最優(yōu)解的這一結(jié)果，這樣我們就確定了

Δcj

的取值范圍。即當(dāng)Δcj(-,-σj

]時(shí)，原問(wèn)題的最優(yōu)解不變。

（2）若cr對(duì)應(yīng)的變量xr

是基變量，因?yàn)閏r

CB，當(dāng)cr

變化時(shí)，就會(huì)引起

CB

的變化，這時(shí)：(CBT+ΔCBT)B-1A=CBTB-1A+(0,···,Δcr,···,0)B-1A

=CBTB-1A+Δcr(ar1,ar2,···,arn)

其中：(ar1,ar2,···,arn)

表示B-1A矩陣的第r

行?？梢?jiàn)，當(dāng)

cr

變化Δcr

后，最終表中的檢驗(yàn)數(shù)是：σj/=cj–CBTB-1Pj

–Δcjarj

=σj–Δcjarj

(j

IN

)若要求原最優(yōu)解不變，即必須滿足σj/

0,j

IN

，于是得到：例7：試以第一章例1的最終表為例。若基變量x2

的系數(shù)

c2

變化Δc2，在原最優(yōu)解不變的條件下，確定Δc2

的變化范圍。

解：這時(shí)由表1—7表1—7cj23000CBXBx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80-Z-1400-1.5-1/80經(jīng)修改后可得表2—9

表2—9cj23+Δc2

000CBXBx1x2x3x4x52x141001/400x5400-21/213+Δc2

x22011/2-1/80-Z-1400-1.5-Δc2/2-1/8+Δc2/80從表2—9可看出，為使表中解仍然為最優(yōu)解，就必須有：

-1.5-Δc2/20，

-1/8+Δc2/80聯(lián)立以上兩個(gè)不等式求解變得：-3Δc21即當(dāng)x2

的價(jià)值系數(shù)c2

在[0，4]區(qū)間變化時(shí)，原問(wèn)題的最優(yōu)解不變。

4.3技術(shù)系數(shù)aij

的變化對(duì)最優(yōu)解的影響

下面分兩種情況討論技術(shù)系數(shù)

aij

的變化，并以具體例子加以說(shuō)明。

例8分析在原計(jì)劃中是否應(yīng)該安排一種新產(chǎn)品。以第一章例1為例，設(shè)該廠除了生產(chǎn)產(chǎn)品I、II外，還有一種新產(chǎn)品III。已知生產(chǎn)產(chǎn)品III，每件需消耗原材料A、B各為6kg、3kg，使用設(shè)備2臺(tái)時(shí)；每件可獲利5元，問(wèn)該廠是否應(yīng)生產(chǎn)該產(chǎn)品和生產(chǎn)多少？

解：分析此問(wèn)題的步驟是：（1）設(shè)生產(chǎn)產(chǎn)品IIIx3/

件，其技術(shù)系數(shù)向量P3/=(2,6,3)T

，然后計(jì)算表中對(duì)應(yīng)于x3/

的檢驗(yàn)數(shù)：

3/=c3/

-CBTB-1P3/

=5–(1.5,0.125,0)(2,6,3)T=1.25>0

說(shuō)明安排生產(chǎn)產(chǎn)品III是有利的。（2）計(jì)算產(chǎn)品III在最終表中對(duì)應(yīng)

x3/

的列向量：并將（1）、（2）中的計(jì)算結(jié)果填入最終表中可得表2—10

表2—10cj230005CBXBx1x2x3x4x5x3/2x141001/403/20x5400-21/21[2]3x22011/2-1/801/4-Z-1400-1.5-1/805/4

由于列的數(shù)字沒(méi)有變化，原問(wèn)題的解是可行解，但檢驗(yàn)數(shù)中還有正檢驗(yàn)數(shù)，說(shuō)明目標(biāo)函數(shù)值還可以改善。（3）將x3/

作為換入變量，x5

作為換出變量，進(jìn)行基變換，求出新的最優(yōu)解。這時(shí)得出新的最優(yōu)解為：x1=1，

x2=1.5，x3/=2，總利潤(rùn)為16.5元，比原計(jì)劃增加了2.5元，具體見(jiàn)下表2—11

表2—11cj230005CBXBx1x2x3x4x5x3/2x11101.5-0.125-0.7505x3/200-10.250.513x21.5010.75-0.1875-0.1250-Z-16.500-0.25-0.4375-0.6250

例9分析原計(jì)劃生產(chǎn)產(chǎn)品的工藝結(jié)構(gòu)發(fā)生變化。仍以第一章例1為例加以說(shuō)明，若原來(lái)計(jì)劃生產(chǎn)產(chǎn)品I的工藝結(jié)構(gòu)有了改進(jìn)，這時(shí)有關(guān)它的技術(shù)向量變?yōu)镻1/=(2,5,2)T

，每件利潤(rùn)為4元，試分析對(duì)原最優(yōu)計(jì)劃有什么影響？解：把改進(jìn)工藝結(jié)構(gòu)的產(chǎn)品I看作新產(chǎn)品I/，設(shè)x1/

為其產(chǎn)量，于是計(jì)算在最終表中對(duì)應(yīng)x1/

的列向量：同時(shí)計(jì)算出x1/

的檢驗(yàn)數(shù)為：

1/=c1/

-CBTB-1P1/

=4–(1.5,0.125,0)(2,5,2)T=0.375>0將以上結(jié)果填入最終表附加的x1/

列向量位置得表2—12cj230004CBXBx1x2x3x4x5x1/2x141000.250[1.25]0x5400-20.510.53x22010.5-0.12500.375-Z-1400-1.5-0.12500.375顯然在表2—12中，x1/

正好替換x1，經(jīng)基變換運(yùn)算之后將x1

列去掉，以x1/

代替x1

列可得表2—13如下：

表2—13cj43000CBXBx1/x2x3x4x54x1/3.21000.200x52.400-20.413x20.8010.5-0.20-Z-15.200-1.5-0.20即這時(shí)應(yīng)當(dāng)生產(chǎn)產(chǎn)品I/3.2件，產(chǎn)品II0.8件，可獲利15.2元

例10：假設(shè)上例的產(chǎn)品I/

的技術(shù)向量變?yōu)镻1/=(4,5,2)T

，而每件產(chǎn)品獲利仍為4元。試問(wèn)該廠如何安排最優(yōu)生產(chǎn)方案？

解：方法與上例相同，以x1/

代替x1，計(jì)算：同時(shí)計(jì)算出x1/

的檢驗(yàn)數(shù)為：

1/=c1/

-CBTB-1P1/

=4–(1.5,0.125,0)(4,5,2)T=-2.625<0將以上結(jié)果填入最終表附加的x1/

列向量位置得表2—14表2—14cj230004CBXBx1x2x3x4x5x1/2x141000.250[1.25]0x5400-20.51-3.53x22010.5-0.12501.375-Z-1400-1.5-0.1250-2.625由單純形法的計(jì)算規(guī)則可知，這時(shí)原解仍為最優(yōu)解。但我們?nèi)砸詘1/

強(qiáng)行替換x1，將運(yùn)算后的x1/

列填入x1

列位置，去掉x1

列可得表2—15如下：

表2—15

cj43000CBXBx1/x2x3x4x54x1/3.21000.200x515.200-21.213x2-2.4010.5-0.40-Z-5.600-1.50.40從該表可見(jiàn)原問(wèn)題和對(duì)偶問(wèn)題都是非可行解，于是引入人工變量x6(放入出現(xiàn)負(fù)的那一行)，用方程表示即為0x1/+x2+0.5x3

–0.4x4+0x5=-2.4

引入人工變量x6，上式就變?yōu)椋?/p>