運籌學第2章對偶與靈敏度分析

第2章對偶與靈敏度分析

Chapter2DualandSensitivity

Analysis

本章內(nèi)容提要

線性規(guī)劃問題用單純形法求得最優(yōu)解以后，還需要進行對偶分析和靈敏度分析,

以了解線性規(guī)劃模型的參數(shù)對最優(yōu)解的影響。對偶理論和方法是線性規(guī)劃的重要內(nèi)

容，引進了對偶的概念以后，線性規(guī)劃不僅僅是--種優(yōu)化的計算方法，而且成為一

種經(jīng)濟分析的工具。對偶的概念在本書第三章、第四章利第五章中都有應(yīng)用。

通過本章學習，要求掌握以下內(nèi)容：

■掌握對偶的定義，能夠熟練寫出各種不同形式原始問題的對偶問題。

■掌握對偶的性質(zhì)，了解原始問題和對偶問題目標函數(shù)值之間的關(guān)系以及最

優(yōu)解之間的關(guān)系，能根據(jù)原始或?qū)ε紗栴}中一個問題的最優(yōu)解求出另一個

問題的最優(yōu)解。

■了解單純形表和對偶的關(guān)系，能根據(jù)單純形表求出對偶問題的解。掌握對

偶單純形法，從一個對偶可行，原始不可行的解出發(fā)求出最優(yōu)解。

■掌握靈敏度分析原理和方法，能夠?qū)δ繕撕瘮?shù)系數(shù)和右邊常數(shù)進行靈敏度

分析，以及增加一個變量，增加一個約束后求新的最優(yōu)解的方法。

■對偶的經(jīng)濟解釋：掌握影子價格、機會成本、差額成本等概念，理解互補

松弛關(guān)系的經(jīng)濟解釋。

§2.1對偶問題的建立

2.1.1對偶的定義

定義2.1設(shè)以下線性規(guī)劃問題

minz=CTX

s.t.AX2b(P)

X20

為原始問題，則稱以下問題

67

maxy=bnW

s.t.ATW^C(D)

w》o

為原始問題的對偶問題。

例2.1設(shè)原始問題為

minz=6xi+8x2

s.t.3x1+X224

5xi+2x227

Xl,X220

則對偶問題為

maxy=4w]+7W2

s.t.3w]+5W2W6

W]+2W2W8

whW2NO

例2.2設(shè)原始問題為

minz=3x]-2x2+X3

s.t.X1+X2-3X3+X4>6

2xi-X2+2X4>4

5X2+2X3-X4>8

X1X2X3X4>0

根據(jù)定義，相應(yīng)的對偶問題為

maxy=6wi+4W2+8W3

s.t.W|+2w?<3

W]-W2+5W3<-2

-3wi+2W3<1

W|+2\V2-W3<0

W|W2W3>0

2.1.2對偶的對偶

設(shè)原始問題為：

minz=CTX

s.t.AXNb(P)

X》0

根據(jù)定義2」，對偶問題為

maxy=b1W

s.t.ATW<C(D)

w》o

現(xiàn)在來考慮D的對偶。為了運用定義2.1,將D改寫成以下形式

miny-l/w

s.t.-ATW^-C(D5)

w'o

根據(jù)定義2.1,D，的對偶為

maxz?=-CTX

s.t.-AXWb

X》。

即

maxz'=-C1X

s.t.AX》b

X20

令g：,上式成為

minz=CTX

s.t.AX》b

XeO

這金是型竺題P。由此得到以工gg：

定理2.1對偶問題的對偶就是原始問題。

2.1.3其他形式的對偶問題

這一節(jié)是要解決非標準形式的原始問題的對偶問題。分為以下幾種情況來討論:

2.1.3.1等號約束問題

設(shè)原始問題的約束條件全是等號約束。即

minz=CTX

s.t.AX=b(P)

X20

這個問題等價于

minz=C!X

s.t.AX2b(Pl)

AXWb

X20

將Pl中《約束兩邊都乘以?1,得到

minz=CTX

s.t.AX2b(P2)

-AX>-b

X20

P2寫成矩陣形式，成為

minz=CTX

「A[「b]

s.t.X>(P3)

-Aj|_-b

X>0

P3的對偶為

maxy=[b1-b1]-

L^2.

s.t.[AT-AT].A4C

W,>0,W2>0

即

TT

maxy=bW1-bW2

TT

s.t.AW(-AW2^C

W|,W2>0

T

或maxy=b(W!-W2)

T

s.t.A(WI-W2)^C

Wi.W?》。

令W=w,-W2

則w無符號限制(unrestricted,簡寫成unr)。得到約束為等號的原始問題的對偶問

題

maxy=b1W

s.t.A'WWC

VV：unr

由此得到以下定理:

定理2.2如果原始問題的約束條件是等式，則對偶問題中的變量無符號限制。

2.1.3.2極小化目標函數(shù)、約束條件為4的問題

設(shè)原始問題為

minz=CTX

s.t.AXWb(P)

X>0

將約束不等式兩邊同乘以-1,得到

minz=CTX

s.t.-AX>-b(PI)

X20

運用定義2.1,Pl的對偶為

maxy=-bTW'

s.t.ATW(DI)

W>0

令W=-W'DI成為

maxy=b1W

s.t.A'WWC(DI)

wwo

由此得到以下定理：

定理2.3如果極小化原始問題中的約束條件(不包括變量非負約束)為《，則對

偶問題中的變量具有非正((0)約束。

將定理2.1所闡述的原始問題和對偶問題的對稱性用于定理2.2和定理2.3,科

得到如爐個推論：

推論2.1如果原始問題中的變量無符號限制，則對偶問題中的約束條件為等式約

束

推論2.2如果原始問題中的變量具有非正(<0)約束，則極小化對偶問題的約束

條件為V約束。

2.1.3.4總結(jié)

我們可以用以下的表格，來總結(jié)以上定理利推論所表述原始問題和對偶問題之

間的關(guān)系：

極小化問題極大化問題

_____(min)(max)_____

Xj20<------->EaqWiWcj

變量Xj：unr<------->叢嚴不約束

XjWO<------->ZayWi^Cj

ZaijXj^bi——wRO

約束ZaijXj-bj<>Wj：unr變量

EajXjWbi<>wWO

運用以上定理和推論，可以直接寫出各種形式的原始問題的對偶問題。

例2.3寫出以下問題的對偶問題

maxz=8xi+5X2

s.t.-Xi+2x2《4

3xi-x2=7

2xi+4x2N8

Xi》0,X2WO

其對偶問題為

miny=4wi+7W2+8W3

s.t.-W|+3W2+2W328

2wi-w2+4W3W5

wi20,w2:unrW3〈O

例2.4寫出以下原始問題的對偶問題

maxz=2xi-X2+4X3+X4

s.t.X|+3x2?X3+5x4<12

-2x1-2x2+3x3-2x4=25

3xi+X2-2X3+X4218

X|>0x2<0:X3：unrX4>0

對偶問題為

miny=12\V]+25W2+18W3

-2W2

s.t.W]+3W3>2

3w]-2W2+W3<-l

-W]+3W2-2W3=4

5W]-2W2+W3>1

W]>0W2：unrw3<0

§2.2原始對偶關(guān)系

2.2.1原始和對偶問題目標函數(shù)值之間的關(guān)系

設(shè)原始問題為

minz=CTX

s.t.AXNb(P)

X20

則對偶問題為

maxy=bTW

s.t.ATW^C(D)

WNO

設(shè)XF為原始問題P的一個可行解，WF為對偶問題D的一個可行解，則XF滿

足

AXF^b

XF>0(2.1)

WF滿足

T

AWF^C

WF》O(2.2)

T

在(2.1)兩邊同時左乘WF^O

TT

WFAXF^WPb(2.3)

將(2.3)兩邊的向量轉(zhuǎn)置

TTT

XFAWF^bWF(2.4)

將(2.2)中的A「WFWC代入(2.4),得到

TTTT

XFC>XFAWF^bWF(2.5)

以上不等式中的各項都是標量，因此有

TTTTT

XFC=CXF,XFAWF=WFAXF

T

注意到XF對應(yīng)的原始問題的目標函數(shù)值ZF=CXF,WF對應(yīng)的對偶問題的目標函數(shù)

T

yF=bWF,(2.5)也可以寫成

TTT

ZF=CXF>WFAXF>bWF=yF(2.6)

因此有以下定理：

定理2.4極小化原始問題的任一可行解的目標函數(shù)值總是大于或等于極大化對偶

問題的任一可行解的目標函數(shù)值。

定理可以直接產(chǎn)生以下兩個譬：

推論2.3如果XF和WF分別是原始問題和對偶問題的可行解，并且它們對應(yīng)的目

標函數(shù)值相等，則XF和WF分別是原始問題和對偶問題的最優(yōu)解.

推論2.4如果原始問題和對偶問題中的任一個目標函數(shù)無界，則另一個必定無可

行解。

請注意推論2.4之逆命題不真，即一個問題無可行解，不能推得另一個問題目標

函數(shù)無界。事實上，一對原始一對偶問題都沒有可行解的情況是存在的，以下就是

這樣一個例子：

例2.5設(shè)原始問題為

minz=-X]-Xi

S.t.XI-X2

-X]+x2》1

X],X2

對偶問題為

maxy=w1+w2

s.t.Wj-w2WT

-W|+W2WT

W),w2

用圖解法就可以證實，以上兩個問題都沒有可行解。

2.2.2互補松弛關(guān)系

設(shè)原始問題為

minz=CTX

s.t.AX2b(P)

X20

則對偶問題為

maxz=bTW

s.t.ATW<C(D)

W>0

若X°,W°分別是原始問題和對偶問題的最優(yōu)解，根據(jù)定理2」，有

CTX°=W°TAX0=W,Tb(2.7)

即CTX°-W°TAX°=O

W,,TAXo-WoTb=0(2.8)

上兩式也可以寫成

(CT-W°TA)X0=O

W°T(AX°-b)=O(2.9)

將(2.9)寫成分量的形式：

[:,-WoTa,c-WoTa…q_W°Taj

220

n

aob

zuJ?-1

j=nIjx

x

zjob

a--2

21^1

月

n(2.10)

Eaux'-bi

j=l

n

>^[慌)j-bm

>1

由于x°,w'分別是原始對偶問題的最優(yōu)解，因此在以上兩式中，有

xJ>0

Cj-W^a^O(j=l,2,…,n)

wf>0

_n

^a0xj-bj>0(i=l,2,…,m)

j=i

即(2.10)兩式中各分量均為非負，因此有以下定理:

定理2.5(互補松弛定理)

廿V。/ooO\T

右'X=(X?,X29…，Xn)

T

和W°=(W1°,W2°,…，Wm°)

分別是原始問題和對偶問題的最優(yōu)解，則有

(Cj-W'^apx；=0(j=l,2,…,n)

w；(汽a,jX；-bj)=O(2.11)

(i=1,2,…,m)

j=l

推論2.5若原始問題的最優(yōu)解X°對于某一個約束i,有

_n

Ea(ixj>bi

j=l

則對偶問題最優(yōu)解中該約束對應(yīng)的對偶變量

Wi°=O

反之，若在對偶問題的最優(yōu)解中，第i個對偶變量

Wj0>0

則原始問題最優(yōu)解對于相應(yīng)的第i個約束是等號約束，即

^2aijxj=bi

j=i

也就是說，原始問題最優(yōu)解中的第i個松弛變量等于0。

同樣，若Xj°>0,,則必定有Cj=W°Taj；反之，若c/W，，則必定有修°=0。

對于以上的定理，還可以有以下更加直觀的看法：如果將原始問題和對偶問題

最優(yōu)解中的變量(x『或wj)大于零稱為該變量是“松的”，而等于零稱為是“緊的”,

約束條件取不等號稱為該約束是“松的”，取等號稱為是“緊的”。則以上定理可表

達成為：

原始問題和對偶問題的最優(yōu)解，對一個問題如果變量是''松的"，則在另一個問

題中相應(yīng)的約束一定是“緊的"；對一個問題如果約束是“松的”，則在另一個問題

中相應(yīng)的變量一定是“緊的”。

如果分別在原始問題和對偶問題中引進松弛變量

TT

Xs°=(X°n+1,X°n+2，X°n+m)

MKToT/0O,0\T

Ws=(wm+1,Wm+2，…，wm+n)

則定理2.5可以表示為

T

W°XS°=O

OT

WSX°=0(2.12)

即

w°+1

wm+2

(2.13)

而推論可以表示為

W」x"n+i=O

W°m+jXj°=()(2.14)

即，由

Wi0>0可以推出Xn+i°=O；

xn+i°>0可以推出Wi°=O；

wm+j°>0可以推出Xj°=O；(2.15)

Xj°>0可以推出Wm+jH)。

利用原始問題和對偶問題最優(yōu)解之間的互補松弛關(guān)系，可以從其中一個問題的

最優(yōu)解求得另一問題的最優(yōu)解。

例2.6求解以下線性規(guī)劃問題

minz=6xj+8x2+3X3

s.t.X】+x221

X1+2X2+X32-1(2.16)

NO

Xi,X2,X3

寫出對偶問題

maxy=W]-W2

s.t.W]+W2W6

W]+2w2W8(2.17)

W2W3

W1,w220

這是個兩個變量的線性規(guī)劃問題，利用圖解法，可以求得這個問題的最優(yōu)解為

TT

(W|,W2)=(6,0)

將這個解代入(2.17)的約束中，容易得到對偶問題各松弛變量的值

W3=0,W4=2,W5=3

即對偶問題的最優(yōu)解和最優(yōu)目標函數(shù)值為

TTT

W=(w)，W2，W3,W4,W5)=(6,0,0,2,3)y=6

根據(jù)定理2.5,以下的互補松弛關(guān)系成立

由w)>0得到x4=0

由w4>0得到x2=0

由w5>0得到x3=0

因此原始問題的約束條件

Xj+X2-X4=1

X|+2X2+X3-X5=-1

成為

X|=1

X|-X5=-1

由此得到

x]—1,X5=2

即原始問題的最優(yōu)解為

TT

X=(xi,X2，X3,卬X5)=(1,0,0,0,2)Z=6

對照對偶解

WT=(W),W2,W3,W4,W5)T=(6,0,0,2,3)Ty=6

容易驗證，以上兩個最優(yōu)解滿足互補松弛條件

XIW3=X2W4=X3W5=0

WiX4=W2X5=0

-v1「W-

必須指出，定理2.5的逆命題并不成立，也就是說，如果兩個向量v和

_xsJLWs.

T

滿足互補松弛關(guān)系wTXs=0,WsX=0,并不能推出它們分別是原始問題和對偶問題

的最優(yōu)解。

2.2.3最優(yōu)解的充分必要條件一Kuhn-Tucker條件

下面我們不加證明地給出線性規(guī)劃最優(yōu)解的充分必要條件。

~x"I「w-

定理2.6若向量和分別是原始問題和對偶問題的最優(yōu)解，當且僅當它

_XSJ|_Ws_

們滿足以下三個條件：

1、X、Xs是原始問題

minz=CTX

s.t.AX-Xs=b(P)

X,Xs》O

的可行解.這個條件稱為原始可行條件(PrimalFeasibleCondition,PFC).

2、W?Ws是對偶問題

maxz=bTW

s.t.ATW+WS=C(D)

W,Ws》0

的可行解。這個條件稱為對偶可行條件(DualFeasibleCondition,DFC).

3、X、Xs、W、Ws滿足

WTXs=0

WsTX=O

這個條件稱為互補松弛條件(ComplementarySlacknessCondition,CSC)。

2.2.4單純形表的結(jié)構(gòu)，單純形表與K-T條件的關(guān)系

引進對偶的概念以后，我們可以從新的角度來分析單純形表的結(jié)構(gòu)。

設(shè)原始問題為

minz=CTX

s.t.AX-Xs=b(P)

X,Xs>0

其中Xs為松弛變量。相應(yīng)的系數(shù)矩陣為

zXXsRHS

設(shè)對于任一可行基B,相應(yīng)的系數(shù)矩陣表為

zXBXNXSRHS

相應(yīng)的單純形表為

zXBXNXSRHS

其中基變量XB在目標函數(shù)中的系數(shù)0「可以寫成

TTT

O=CBB'B-CB

基變量在約束中的矩陣I可以寫成

I=B'B

因此，以上單純形表可以寫成

zXXsRHS

記

則

WST=CT-WTA=CT-CBTBJA

因此以上單純形表可以寫為

zXXsRHS

TTT

1-VVs；-WCBB'b

0B'A-B1B'b

如果B是原始可行基而不是最優(yōu)基，則在X或Xs中，至有一個非基變量當，

使得

z「Ci>0

當j=l,2,,,,,n時，XjeX,當上=11+1,…，n+m時，XjeXs。

若XjeXs,不妨設(shè)j=n+i,則Zj-Cj=-Wi>0,即出<0,也就是第i個對偶變量違背

非負約束；

若XjWX,則Zj-Cj=-Wm+j>0,即Wm+j<0,也就是第j個對偶松弛變量違背非負約

束，即Wm+j=Cj-WTaj<0,或WaK，也就是對偶問題的第j個約束不滿足。

另外，由單純形法可知,在X中,如果Xj是基變量，則Xj>0,而Zj-Cj=-Wm+j=O,

如果Xj是非基變量，貝l」Xj=O,而Zj-Cj=-Wm+j>0；同樣，在Xs中，如果X"+i是基變量,

則Xn+i>0,而Zj-Cj=-Wi=O,如果Xn+i是非基變量,則Xn+i=O,而Zj-Cj=-Wi>0。由此可

見，無論X、Xs是否是最優(yōu)解，X、Xs、W、Ws都滿足互補松弛關(guān)系。

當B是最優(yōu)基時，所有檢驗數(shù)Zj-Cj40,即-Ws4）、-W<0,也就是WsE）、W>0,

滿足對偶可行條件。

綜上所述，單純形法和Kuhn-Tucker條件的關(guān)系可敘述如下：

在單純形檢代過程中，如果當前基B是原始可行基而不是最優(yōu)基，則

1、原始問題相應(yīng)的解X、Xs滿足原始可行條件；

TTTTT

2、對偶問題相應(yīng)的解W=CBB-'>WS=C-WA中至少有一個不滿足對偶可行

條件；

3、X、Xs,W、Ws在單純形疊代的每一步，都滿足互補松弛關(guān)系。

TTTTT

當B不僅可行，而且是最優(yōu)基時，對偶問題相應(yīng)的解W=CBB-\WS=C-WA

才滿足對偶可行條件。

因此，我們可以把單純形法看成在原始可行條件和互補松弛條件得到滿足的條

件下，不斷改進對偶可行條件的過程，一旦三個條件都得到滿足，也就得到了最優(yōu)

解。

例2.7求解以下線性規(guī)劃問題，對每一次疊代得到的基，驗證是否滿足原始可行條

件、對偶可行條件以及互補松弛條件。

minz=-Xj-X2-X3

s.t.X|+x2+X3<3

)<4

2x+2x2+X3

X1X2X3>0

對偶問題為

maxy=3wi+4W2

Wi+2W2<-l

Wj+2W2<-l

Wi+W2<-l

Wl.W2<0

這個問題的原始問題用矩陣表示的形式為

minz=CTX

s.t.AX4b

X>0

對偶問題為

maxy=bTW

s.t.ATW<C

W<0

原始問題引進松弛變量Xs,成為

minz=C*X

s.t.AX+Xs=b

X,Xs>0

對偶問題引進松弛變量，成為

maxy=bTW

s.t.ATW+Ws=C

W<0,Ws>0

即WTS=CT-WTA

原始問題相應(yīng)的系數(shù)矩陣為

zXXsRHS

設(shè)對于任一可行基B,相應(yīng)的系數(shù)矩陣表為

zXBXNXsRHS

相應(yīng)的單純形表為

zXBXNXsRHS

將XB和XN合并成X,以上單純形表可以寫成

zXXsRHS

W^CB'B-'

由對偶問題的形式可以知道

TTTTT

-WS=-(C-WA)=CBB'A-C

因此以上單純形表可以寫為

zXXsRHS

在原始問題中引進松弛變量X4、X5,得到

minz=?X]-X2-X3

s.t.Xi+x2+X3+X4=3

2X14-2X2+X3+X5=4

Xl,x2,x3x4,x5>0

在對偶問題中引進松弛變量W3、W4、W5,得到

maxy=3wi+4w2

由此得到

X|=0,X2=0,X4—3,X5=4

W|=o>W2=0,W3=T,W4=-T,W5=T

因此有

X|W3=0,X3W4H),X3W5H),X4W|=0,X5W2=0

PFC和CSC滿足，松弛變量W3、W4、W5都小于0,DFC不滿足。

XI進基，X5離基，得到以下單周型

ZXiX2X3x4x5RHS

由此得到

X]=2,x.—0，X3—0,x4=1,X5=0

W|=0>W2=-l/2>W3=0,W4=0,W5=-1/2

因此有

X|W3=0,X3W4H),X3W5H),X4W|=0,X5W2H)

PFC和CSC滿足，W5=-1/2<0,DFC不滿足。

X3進基，。離基，得到以下單純形表

ZXiX2X3X4x5RHS

1000-10-3

00012-12

0110-111

由此得到

Xj=l,X2=0,X3=2,X4=0?X5=0

Wj—1,W2=0?W3=0,W4=0,W5=0

因此有

X]W3=0,X3W4=0,X3W5=0,X4W|=0,x5w2=0

PFC、CSC和DFC都滿足，因而是最優(yōu)解。

§2.3對偶單純形法

上?節(jié)中，我們已經(jīng)知道，線性規(guī)劃取得最優(yōu)解的充分必要條件是原始可行、

對偶可行和互補松弛條件同時滿足。同時，也曾指出，單純形疊代過程實際上是在

滿足原始可行條件和互補松弛條件的基礎(chǔ)上，不斷改進對偶可行性的過程，一旦對

偶可行條件得到滿足，就得到了最優(yōu)解。對偶單純形法則是從另一角度來進行的。

對偶單純形法在疊代過程中保持對偶可行條件和互補松弛條件滿足，并且在疊代過

程中不斷改進原始可行條件。一旦原始可行條件得到滿足，也就求得了最優(yōu)解。為

了說明對偶單純形法原理，先建立有關(guān)概念和定理。

2.3.1對偶可行基

定義2.2設(shè)B為原始問題的一個基，若

WT=CBTB-'是對偶問題的可行解，則稱B為

原始問題的對偶可行基。

例2.8求以下線性規(guī)劃問題的對偶可行基。

minz=?X]?X2

st2xi+3X2W12

2xj+X2W8

X2W3

Xl,X220

這個問題的圖解如右。引進松弛變量X3,X4,

x5>0,得到

minz=-xj-X2

st2xi+3X2+X3

2xj+X2+X4

X2+X5=3

X4,XNO

Xi,X2.x3,5

原問題的對偶問題為

maxy=12\V|+8w2+3W3

)

st2w+2W2W-l

3w]+W2+W3W-l

W|,W2,W3WO

在原始問題中取基

310

B]=[a2a3a5]=100

10I

計算相應(yīng)的對偶變量

01O-

T1

W=C^BI-=[-l0O]-1-30=[O-10]

0-11

即W1=O,W2=-l,W3=O。容易驗證W滿足對偶的所有約束條件，包括變量非正的條

230

再取基B2=[a,a2a5]=210

011

--1/43/4O'

WT=C￡B”[-1-10].1/2-1/20=[-1/4-1/40]

-1/21/21

W滿足對偶問題的約束條件，因而B2是對偶可行基。同時

因此B2也是原始可行基。

基Bi和B?相應(yīng)的極點在圖上分別對應(yīng)于點H和B。容易看出，點B即基B?是

最優(yōu)解。

定理2.7若基B既是原始問題的可行基，又是原始問題的對偶可行基，則B必定

是原始問題的最優(yōu)基。

證：因為B是原始問題的可行基，因此

X=>0

N

同時因為B是對偶可行基，根據(jù)對偶可行基的定義，W=CBTB」?jié)M足對偶問題的約

束條件，即

WTA^CT

w，o

或

CBTB'A-CT<OT

T1

-CBB1^O

以上兩個條件，就是

Zj-CjWO,j=l,2,,,,,n,n+1,…，n+m

因此，B是原始問題的最優(yōu)基。

2.3.2對偶單純形法

曲璃納觸BiL播蝌可同網(wǎng)舸律O啜進領(lǐng)幽細閽將幽鋤

喇■行性基貝艘郵牌翱基

例2.9用對偶單純形法求解以下問題

minz=2x]+3X2+4X3

X1+2x2+X323

2xi?X2+3X324

X|,X2,X320

引進松弛變量X4,x5>0,得到

minZ=2xi+3x2+4X3

X1+2x2+X3-X4=3

2xi-X2+3x3-X5=4

X|,X2,X3,X4,X5NO

為了得到單位矩陣形式的初始基，將約束等式兩邊同乘以-1,得到

+3X2

minz=2x]+4x3

-xi-2x2-x3+X4=-3

-2x]+X2-3X3+X5=-4

Xl,X2,X3,X4,X520

列出初始單純形表

ZX|X2X3X4X5RHS

Z

-2/-2-4A3

由于表中所有的「竽0,因此當前基是對偶可行基。但當前基變量的值X3=-3<0,

X4=-4<0,因此當前的基不是原始可行基。

為了改善基的原始可行性，取一個小于零的基變量離基，如果有數(shù)個基變量的

值小于零，一?般可選其中絕對值最大的先離基。這里選X5=4離基。

為了改善原始可行性，應(yīng)該使旋轉(zhuǎn)運算以后進基變量的值成為非負的，這樣就

要在離基行中選擇為<0的元素作為主元。在上表中，有丫2尸-2和y23=-3可以選為主

兀。

為了使新的基仍保持對偶可行性，必須使旋轉(zhuǎn)運算后所有檢驗數(shù)Zj-CjWO。因此

按以下方法選擇進基列k。

min<—~—lyrj<0■=-——

Iy「j丫永

在上例中，選取

選取X1進基。即選取丫2尸-2為主元，進行旋轉(zhuǎn)運算，得到以下單純形表。

ZX]X2X3X4X5RHS

Z

刈

X1

-4/-5Z2-1/-1/2

由于新的基仍不是原始可行的。取X4離基，選擇進基變量。

.z-cZ5-C5-4

min<-2-----2-,—------->=min〈--------

,y12y15J1-5/2

選取X2進基。即以力2=-5/2為主元，進行旋轉(zhuǎn)運算，得到

ZX1X2X3X5RHS

Z100-9/5-8/5-1/528/5

X2001-1/5-2/51/52/5

X]0107/5-1/5-2/511/5

當前基既是原始可行基，又是對偶可行基，因而是最優(yōu)基。最優(yōu)解為

X|=l1/5>X2=2/5?X3=X4=X5=0,minz=28/5

注意到以上極小化問題在疊代過程中，每次疊代目標函數(shù)值不斷增大，這是因

為福代過程是從可行域以外的點向可行域靠攏的緣故。

由于對偶單純形法是從可行域外開始疊代的，因此可能出現(xiàn)線性規(guī)劃沒有可行

解的情況。當某一個右邊常數(shù)bi<0時，則選定相應(yīng)的基變量XBi為離基變量，如果相

應(yīng)行中約束條件的系數(shù)全為正數(shù)，也就是無法找到進基變量，則這個問題沒有可行

解。

掌握了單純形法和對偶單純形法，我們就可以更靈活地進行單純形疊代來求得

線性規(guī)劃的最優(yōu)解，既可以從一個原始可行、對偶不可行的解出發(fā)，用單純形法進

行疊代，也可以從一個原始不可行、對偶可行的解出發(fā)，用對偶單純形法進行疊代,

甚至可以從一個原始不可行，對偶也不可行的解出發(fā)，先用適當?shù)倪M基一離基變換

把解變成原始可行或?qū)ε伎尚械?，然后再用單純形法或?qū)ε紗渭冃畏ㄇ蠼狻?/p>

例2.10求解以下線性規(guī)劃問題

minz=-3xi+2x2+X3

stX]++X2+X3>12(1)

2xi4-X?+X3<38(2)

X1+2x2+2X3>24(3)

X]X2X3>0

引進松弛變量

minz=-3xi+2X2+X3

stX|++X2+X3-X4=12(1)

2xi+X2+X3+X5=38(2)

+2X2+2X3=24(3)

X1-x6

x>0

X12X3X4X5x6

約束條件（1）、（3）兩邊分別乘以-1

minz=-3xi+2X2+X3

st-xi?+X4=-12(1)

-X2X3

2xi+X2+X3+X5=38(2)

-xi-2X2-2X3+X6=-24(3)

X1X2X3X4X5X6>0

列出單純形表

zXlX2X3X4X5X6RHS

z13-2-10000

X40-1-1-1]00-12

X5012]1101038

X60-1-2-2001-24

初始單純形表對應(yīng)的原始問題的解為

(xi，x2,X3,x4,x5,X6)=(0,0,0,-12,38,-24)

對應(yīng)的對偶問題的解為

(wpw2,W3,w4,W5,W6)=(O,0,0,-3,2,1)

也就是說，以X”X2,X3為非基變量，以X4,X5,X6為基變量，相應(yīng)的基礎(chǔ)解既

不是原始可行的，又不是對偶可行的，但原始問題的解和對偶問題的解滿足互補松

弛關(guān)系。在以匕的單純形表中，選取X1進基，X5離基，即丫21=2為主元，旋轉(zhuǎn)運算后,

就可以得到：

ZX1X2X3X4X5X6RHS

Z10-7/2-5/20-3/20-57

X400-1/2-1/211/207

X]011/21/201/2019

X600-3/2[-3/2]01/21-5

以上的解為對偶可行,原始不可行。用對偶單純形法繼續(xù)求解。X6離基，X3進基

ZXiX2X3x4X5x6RHS

Z10-1