运筹学第2章对偶与灵敏度分析

第2章对偶与灵敏度分析

Chapter2DualandSensitivity

Analysis

本章内容提要

线性规划问题用单纯形法求得最优解以后，还需要进行对偶分析和灵敏度分析,

以了解线性规划模型的参数对最优解的影响。对偶理论和方法是线性规划的重要内

容，引进了对偶的概念以后，线性规划不仅仅是--种优化的计算方法，而且成为一

种经济分析的工具。对偶的概念在本书第三章、第四章利第五章中都有应用。

通过本章学习，要求掌握以下内容：

■掌握对偶的定义，能够熟练写出各种不同形式原始问题的对偶问题。

■掌握对偶的性质，了解原始问题和对偶问题目标函数值之间的关系以及最

优解之间的关系，能根据原始或对偶问题中一个问题的最优解求出另一个

问题的最优解。

■了解单纯形表和对偶的关系，能根据单纯形表求出对偶问题的解。掌握对

偶单纯形法，从一个对偶可行，原始不可行的解出发求出最优解。

■掌握灵敏度分析原理和方法，能够对目标函数系数和右边常数进行灵敏度

分析，以及增加一个变量，增加一个约束后求新的最优解的方法。

■对偶的经济解释：掌握影子价格、机会成本、差额成本等概念，理解互补

松弛关系的经济解释。

§2.1对偶问题的建立

2.1.1对偶的定义

定义2.1设以下线性规划问题

minz=CTX

s.t.AX2b(P)

X20

为原始问题，则称以下问题

67

maxy=bnW

s.t.ATW^C(D)

w》o

为原始问题的对偶问题。

例2.1设原始问题为

minz=6xi+8x2

s.t.3x1+X224

5xi+2x227

Xl,X220

则对偶问题为

maxy=4w]+7W2

s.t.3w]+5W2W6

W]+2W2W8

whW2NO

例2.2设原始问题为

minz=3x]-2x2+X3

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

2xi-X2+2X4>4

5X2+2X3-X4>8

X1X2X3X4>0

根据定义，相应的对偶问题为

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对偶的对偶

设原始问题为：

minz=CTX

s.t.AXNb(P)

X》0

根据定义2」，对偶问题为

maxy=b1W

s.t.ATW<C(D)

w》o

现在来考虑D的对偶。为了运用定义2.1,将D改写成以下形式

miny-l/w

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

w'o

根据定义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其他形式的对偶问题

这一节是要解决非标准形式的原始问题的对偶问题。分为以下几种情况来讨论:

2.1.3.1等号约束问题

设原始问题的约束条件全是等号约束。即

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极小化目标函数、约束条件为4的问题

设原始问题为

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总结

我们可以用以下的表格，来总结以上定理利推论所表述原始问题和对偶问题之

间的关系：

极小化问题极大化问题

_____(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原始对偶关系

2.2.1原始和对偶问题目标函数值之间的关系

设原始问题为

minz=CTX

s.t.AXNb(P)

X20

则对偶问题为

maxy=bTW

s.t.ATW^C(D)

WNO

设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)两边的向量转置

TTT

XFAWF^bWF(2.4)

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

TTTT

XFC>XFAWF^bWF(2.5)

以上不等式中的各项都是标量，因此有

TTTTT

XFC=CXF,XFAWF=WFAXF

T

注意到XF对应的原始问题的目标函数值ZF=CXF,WF对应的对偶问题的目标函数

T

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

TTT

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

因此有以下定理：

定理2.4极小化原始问题的任一可行解的目标函数值总是大于或等于极大化对偶

问题的任一可行解的目标函数值。

定理可以直接产生以下两个譬：

推论2.3如果XF和WF分别是原始问题和对偶问题的可行解，并且它们对应的目

标函数值相等，则XF和WF分别是原始问题和对偶问题的最优解.

推论2.4如果原始问题和对偶问题中的任一个目标函数无界，则另一个必定无可

行解。

请注意推论2.4之逆命题不真，即一个问题无可行解，不能推得另一个问题目标

函数无界。事实上，一对原始一对偶问题都没有可行解的情况是存在的，以下就是

这样一个例子：

例2.5设原始问题为

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互补松弛关系

设原始问题为

minz=CTX

s.t.AX2b(P)

X20

则对偶问题为

maxz=bTW

s.t.ATW<C(D)

W>0

若X°,W°分别是原始问题和对偶问题的最优解，根据定理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'分别是原始对偶问题的最优解，因此在以上两式中，有

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°)

分别是原始问题和对偶问题的最优解，则有

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

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

(i=1,2,…,m)

j=l

推论2.5若原始问题的最优解X°对于某一个约束i,有

_n

Ea(ixj>bi

j=l

则对偶问题最优解中该约束对应的对偶变量

Wi°=O

反之，若在对偶问题的最优解中，第i个对偶变量

Wj0>0

则原始问题最优解对于相应的第i个约束是等号约束，即

^2aijxj=bi

j=i

也就是说，原始问题最优解中的第i个松弛变量等于0。

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

对于以上的定理，还可以有以下更加直观的看法：如果将原始问题和对偶问题

最优解中的变量(x『或wj)大于零称为该变量是“松的”，而等于零称为是“紧的”,

约束条件取不等号称为该约束是“松的”，取等号称为是“紧的”。则以上定理可表

达成为：

原始问题和对偶问题的最优解，对一个问题如果变量是''松的"，则在另一个问

题中相应的约束一定是“紧的"；对一个问题如果约束是“松的”，则在另一个问题

中相应的变量一定是“紧的”。

如果分别在原始问题和对偶问题中引进松弛变量

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)。

利用原始问题和对偶问题最优解之间的互补松弛关系，可以从其中一个问题的

最优解求得另一问题的最优解。

例2.6求解以下线性规划问题

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

这是个两个变量的线性规划问题，利用图解法，可以求得这个问题的最优解为

TT

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

将这个解代入(2.17)的约束中，容易得到对偶问题各松弛变量的值

W3=0,W4=2,W5=3

即对偶问题的最优解和最优目标函数值为

TTT

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

根据定理2.5,以下的互补松弛关系成立

由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

即原始问题的最优解为

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

容易验证，以上两个最优解满足互补松弛条件

XIW3=X2W4=X3W5=0

WiX4=W2X5=0

-v1「W-

必须指出，定理2.5的逆命题并不成立，也就是说，如果两个向量v和

_xsJLWs.

T

满足互补松弛关系wTXs=0,WsX=0,并不能推出它们分别是原始问题和对偶问题

的最优解。

2.2.3最优解的充分必要条件一Kuhn-Tucker条件

下面我们不加证明地给出线性规划最优解的充分必要条件。

~x"I「w-

定理2.6若向量和分别是原始问题和对偶问题的最优解，当且仅当它

_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单纯形表的结构，单纯形表与K-T条件的关系

引进对偶的概念以后，我们可以从新的角度来分析单纯形表的结构。

设原始问题为

minz=CTX

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

X,Xs>0

其中Xs为松弛变量。相应的系数矩阵为

zXXsRHS

设对于任一可行基B,相应的系数矩阵表为

zXBXNXSRHS

相应的单纯形表为

zXBXNXSRHS

其中基变量XB在目标函数中的系数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是原始可行基而不是最优基，则在X或Xs中，至有一个非基变量当，

使得

z「Ci>0

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

若XjeXs,不妨设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是否是最优解，X、Xs、W、Ws都满足互补松弛关系。

当B是最优基时，所有检验数Zj-Cj40,即-Ws4）、-W<0,也就是WsE）、W>0,

满足对偶可行条件。

综上所述，单纯形法和Kuhn-Tucker条件的关系可叙述如下：

在单纯形检代过程中，如果当前基B是原始可行基而不是最优基，则

1、原始问题相应的解X、Xs满足原始可行条件；

TTTTT

2、对偶问题相应的解W=CBB-'>WS=C-WA中至少有一个不满足对偶可行

条件；

3、X、Xs,W、Ws在单纯形叠代的每一步，都满足互补松弛关系。

TTTTT

当B不仅可行，而且是最优基时，对偶问题相应的解W=CBB-\WS=C-WA

才满足对偶可行条件。

因此，我们可以把单纯形法看成在原始可行条件和互补松弛条件得到满足的条

件下，不断改进对偶可行条件的过程，一旦三个条件都得到满足，也就得到了最优

解。

例2.7求解以下线性规划问题，对每一次叠代得到的基，验证是否满足原始可行条

件、对偶可行条件以及互补松弛条件。

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

原始问题相应的系数矩阵为

zXXsRHS

设对于任一可行基B,相应的系数矩阵表为

zXBXNXsRHS

相应的单纯形表为

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都满足，因而是最优解。

§2.3对偶单纯形法

上•节中，我们已经知道，线性规划取得最优解的充分必要条件是原始可行、

对偶可行和互补松弛条件同时满足。同时，也曾指出，单纯形叠代过程实际上是在

满足原始可行条件和互补松弛条件的基础上，不断改进对偶可行性的过程，一旦对

偶可行条件得到满足，就得到了最优解。对偶单纯形法则是从另一角度来进行的。

对偶单纯形法在叠代过程中保持对偶可行条件和互补松弛条件满足，并且在叠代过

程中不断改进原始可行条件。一旦原始可行条件得到满足，也就求得了最优解。为

了说明对偶单纯形法原理，先建立有关概念和定理。

2.3.1对偶可行基

定义2.2设B为原始问题的一个基，若

WT=CBTB-'是对偶问题的可行解，则称B为

原始问题的对偶可行基。

例2.8求以下线性规划问题的对偶可行基。

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

计算相应的对偶变量

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?相应的极点在图上分别对应于点H和B。容易看出，点B即基B?是

最优解。

定理2.7若基B既是原始问题的可行基，又是原始问题的对偶可行基，则B必定

是原始问题的最优基。

证：因为B是原始问题的可行基，因此

X=>0

N

同时因为B是对偶可行基，根据对偶可行基的定义，W=CBTB」满足对偶问题的约

束条件，即

WTA^CT

w，o

或

CBTB'A-CT<OT

T1

-CBB1^O

以上两个条件，就是

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

因此，B是原始问题的最优基。

2.3.2对偶单纯形法

曲璃纳触BiL播蝌可同网舸律O啜进领幽细阍将幽锄

喇■行性基贝艘邮牌翱基

例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,因此当前的基不是原始可行基。

为了改善基的原始可行性，取一个小于零的基变量离基，如果有数个基变量的

值小于零，一•般可选其中绝对值最大的先离基。这里选X5=4离基。

为了改善原始可行性，应该使旋转运算以后进基变量的值成为非负的，这样就

要在离基行中选择为<0的元素作为主元。在上表中，有丫2尸-2和y23=-3可以选为主

兀。

为了使新的基仍保持对偶可行性，必须使旋转运算后所有检验数Zj-CjWO。因此

按以下方法选择进基列k。

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

Iy「j丫永

在上例中，选取

选取X1进基。即选取丫2尸-2为主元，进行旋转运算，得到以下单纯形表。

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为主元，进行旋转运算，得到

ZX1X2X3X5RHS

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

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

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

当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为

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

注意到以上极小化问题在叠代过程中，每次叠代目标函数值不断增大，这是因

为福代过程是从可行域以外的点向可行域靠拢的缘故。

由于对偶单纯形法是从可行域外开始叠代的，因此可能出现线性规划没有可行

解的情况。当某一个右边常数bi<0时，则选定相应的基变量XBi为离基变量，如果相

应行中约束条件的系数全为正数，也就是无法找到进基变量，则这个问题没有可行

解。

掌握了单纯形法和对偶单纯形法，我们就可以更灵活地进行单纯形叠代来求得

线性规划的最优解，既可以从一个原始可行、对偶不可行的解出发，用单纯形法进

行叠代，也可以从一个原始不可行、对偶可行的解出发，用对偶单纯形法进行叠代,

甚至可以从一个原始不可行，对偶也不可行的解出发，先用适当的进基一离基变换

把解变成原始可行或对偶可行的，然后再用单纯形法或对偶单纯形法求解。

例2.10求解以下线性规划问题

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

初始单纯形表对应的原始问题的解为

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

对应的对偶问题的解为

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

也就是说，以X”X2,X3为非基变量，以X4,X5,X6为基变量，相应的基础解既

不是原始可行的，又不是对偶可行的，但原始问题的解和对偶问题的解满足互补松

弛关系。在以匕的单纯形表中，选取X1进基，X5离基，即丫21=2为主元，旋转运算后,

就可以得到：

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

以上的解为对偶可行,原始不可行。用对偶单纯形法继续求解。X6离基，X3进基

ZXiX2X3x4X5x6RHS

Z10-1