对偶

Chapter 2 Dual and Sensitive Analysis

§2.1 对偶问题的建立

2.1.1 对偶的定义

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

min z=CTX

s.t. AX≥b (P) X≥0

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

max y=bW

s.t. ATW≤C (D) W≥0 为原始问题的对偶问题。 例2.1 设原始问题为

min z= 6x1 +8x2 s.t.

则对偶问题为

max y= 4w1 +7w2 s.t.

67

w1 +2w2 ≤8 w1,

w2 ≥0

3w1 +5w2 ≤6

3x1 +x2 ≥4 5x1 +2x2 ≥7 x1,

x2 ≥0

T

第二章 对偶线性规划与灵敏度分析

例2.2 设原始问题为 min s.t.

z= 3x1 x1 2x1

-2x2 +x2 -x2

+x3

6 4 8 0

-3x3 +x4

+2x4

-x4 x4

5x2 +2x3

x1 x2 x3 根据定义，相应的对偶问题为 max s.t.

y= 6w1 w1 w1 w1 w1

+4w2 +2w2 -w2

+2w2 w2

+8w3

 3 +5w3 -2 +2w3  1 -w3  0 w3  0

-3w1

2.1.2 对偶的对偶

设原始问题为： min z=CTX

s.t. AX≥b (P) X≥0 根据定义2.1，对偶问题为

max y=bTW

s.t. ATW≤C (D) W≥0

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

min y’=-bTW

s.t. -AW≥-C (D’) W≥0 根据定义2.1，D’的对偶为

max z’=-CTX s.t. -AX≤-b X≥0 即

max z’=-CTX s.t. AX≥b

68

T

第二章 对偶线性规划与灵敏度分析

X≥0 令z=-z’，上式成为

min z=CTX s.t. AX≥b X≥0

这就是原始问题P。由此得到以下定理： 定理2.1 对偶问题的对偶就是原始问题。

2.1.3 其他形式的对偶问题

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

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

s.t. AX=b (P) X≥0 这个问题等价于

min z=CTX

s.t. AX≥b (P1) AX≤b X≥0

将P1中约束两边都乘以-1，得到

min z=CTX

s.t. AX≥b (P2) -AX≥-b X≥0 P2写成矩阵形式，成为

minzCXAXAX0TT

s.t.b (P3) bP3的对偶为

69

第二章 对偶线性规划与灵敏度分析

max s.t.W1ybbW2W1TTAAC

W2W10,W20TT即

max y=bTW1-bTW2 s.t. ATW1-ATW2≤C W1,W2≥0 或 max y=bT(W1-W2)

s.t. A(W1-W2)≤C W1,W2≥0 令 W=W1-W2

则W无符号（unrestricted，简写成unr）。得到约束为等号的原始问题的对偶问题

max y=bW s.t. ATW≤C W：unr 由此得到以下定理：

定理2.2 如果原始问题的约束条件是等式，则对偶问题中的变量无符号。 2.1.3.2 极小化目标函数、约束条件为的问题

设原始问题为 min z=CTX

s.t. AX≤b (P) X0

将约束不等式两边同乘以-1，得到

min z=CTX

s.t. -AX≥-b (P1) X≥0 运用定义2.1，P1的对偶为

max y=-bTW’

s.t. -ATW’≤C (D1) W’≥0

70

TT

第二章 对偶线性规划与灵敏度分析

令W=-W’，D1成为

max y=bTW

s.t. ATW≤C (D1) W≤0 由此得到以下定理：

定理2.3 如果极小化原始问题中的约束条件（不包括变量非负约束）为≤，则对偶问题中的变量具有非正（≤0）约束。

将定理2.1所阐述的原始问题和对偶问题的对称性用于定理2.2和定理2.3，可以得到如下两个推论：

推论2.1 如果原始问题中的变量无符号，则对偶问题中的约束条件为等式约束。 推论2.2 如果原始问题中的变量具有非正（≤0）约束，则极小化对偶问题的约束条件为约束。 2.1.3.4 总结

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

变

量

极小化问题（min） xj≥0 xj:unr xj≤0

约 束

—— —— —— —— —— ——

极大化问题（max）

约 束

aijwi≤cj aijwi=cj aijwi≥cj

wi≥0 wi:unr wi≤0

aijxj≥bi aijxj=bi aijxj≤bi

变 量

运用以上定理和推论，可以直接写出各种形式的原始问题的对偶问题。 例2.3 写出以下问题的对偶问题

max z= s.t.

其对偶问题为

min y= s.t.

4w1 +7w2 +8w3

-w1 +3w2 +2w3 ≥8

71

8x1 +5x2 3x1

-x2

=7

-x1 +2x2 ≤4 2x1 +4x2 ≥8

x1≥0, x2≤0

第二章 对偶线性规划与灵敏度分析

2w1 -w2 +4w3 ≤5

12 =25 18

w1≥0, w2:unr w3≤0

例2.4 写出以下原始问题的对偶问题 max s.t.

z=

2x1

-x2

+4x3 -x3 +3x3 -2x3

+x4 +5x4 -2x4 +x4 x40

x1 +3x2 3x1

+x2

-2x1 -2x2

x10 x20 x3:unr 对偶问题为 min s.t.

y= 12w1

w1 3w1 -w1 5w1 w10

+25w2 -2w2 -2w2 +3w2 -2w2 w2:unr

+18w3

+3w3  2 +w3 -1 -2w3 = 4 +w3  1 w30

72

第二章 对偶线性规划与灵敏度分析

§2.2 原始对偶关系

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

设原始问题为 min z=CTX

s.t. AX≥b (P) X≥0 则对偶问题为

max y=bTW

s.t. ATW≤C (D) W≥0

设XF为原始问题P的一个可行解，WF为对偶问题D的一个可行解，则XF满足

AXF≥b

XF≥0 (2.1) WF满足

ATWF≤C

WF≥0 (2.2) 在(2.1)两边同时左乘WFT≥0

WFTAXF≥WFTb (2.3) 将(2.3)两边的向量转置

XFTATWF≥bTWF (2.4) 将(2.2)中的AWF≤C代入(2.4)，得到

XFTC≥XFTATWF≥bTWF (2.5) 以上不等式中的各项都是标量，因此有

XFTC=CTXF，XFTATWF=WFTAXF

注意到XF对应的原始问题的目标函数值zF=CXF，WF对应的对偶问题的目标函数值yF=bTWF，(2.5)也可以写成

zF=CTXF≥WFTAXF≥bTWF=yF (2.6) 因此有以下定理：

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

73

T

T

第二章 对偶线性规划与灵敏度分析

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

以上定理可以直接产生以下两个推论：

推论2.3 如果XF和WF分别是原始问题和对偶问题的可行解，并且它们对应的目标函数值相等，则XF和WF分别是原始问题和对偶问题的最优解。

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

请注意推论2.4之逆命题不真，即一个问题无可行解，不能推得另一个问题目标函数无界。事实上，一对原始—对偶问题都没有可行解的情况是存在的，以下就是这样一个例子： 例2.5 设原始问题为

min z= -x1 -x2 s.t.

对偶问题为

max y= s.t.

w1 +w2

w1 -w2 ≤-1

≥0

x1 -x2 ≥1

x2 ≥0

-x1 +x2 ≥1 x1,

-w1 +w2 ≤-1 w1, w2

用图解法就可以证实，以上两个问题都没有可行解。

2.2.2 互补松弛关系

设原始问题为 min z=CTX

s.t. AX≥b (P) X≥0 则对偶问题为

max z=bTW

s.t. ATW≤C (D) W≥0

若Xo，Wo分别是原始问题和对偶问题的最优解，根据定理2.1，有 CTXo=WoTAXo=WoTb (2.7)

74

第二章 对偶线性规划与灵敏度分析

即

CTXo-WoTAXo=0

WoTAXo-WoTb=0 (2.8) 上两式也可以写成

(C-WA)X=0

W(AX-b)=0 (2.9) 将(2.9)写成分量的形式：

ox1ox2o0 xjoxnToTo

oTo

c1WoTa1c2WoTa2cjWoTajcnWoTanwo1w2owiowomnj1nj1noa1jxjao2jxjaj1noijxjaj1omjxjb1b20bibm (2.10)

由于X，W分别是原始对偶问题的最优解，因此在以上两式中，有

xojoo

0oTcjWaj0(j1,2,,n) wo0in

ojaj1ijxbi0(i1,2,,m)即(2.10)两式中各分量均为非负，因此有以下定理： 定理2.5（互补松弛定理）

若 Xo=(x1o，x2o，…，xno)T

和 W=(w1，w2，…，wm)

o

o

o

oT

75

第二章 对偶线性规划与灵敏度分析

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

（cjWoTaj）xojoj0(j1,2,,n)(i1,2,,m)

nw(aijxj1oibi)0o

(2.11)

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

n

j1aijxojbi

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

wio=0 wio>0

n反之，若在对偶问题的最优解中，第i个对偶变量 则原始问题最优解对于相应的第i个约束是等号约束，即

aj1xjbi ijo也就是说，原始问题最优解中的第i个松弛变量等于0。

同样，若xj>0，，则必定有cj=Waj；反之，若cj>Waj，则必定有xj=0。 对于以上的定理，还可以有以下更加直观的看法：如果将原始问题和对偶问题最优解中的变量（xjo或wio）大于零称为该变量是“松的”，而等于零称为是“紧的”，约束条件取不等号称为该约束是“松的”，取等号称为是“紧的”。则以上定理可表达成为：

原始问题和对偶问题的最优解，对一个问题如果变量是“松的”，则在另一个问题中相应的约束一定是“紧的”；对一个问题如果约束是“松的”，则在另一个问题中相应的变量一定是“紧的”。

如果分别在原始问题和对偶问题中引进松弛变量 XsoT=(xon+1，xon+2，„，xon+m)T WsoT=(wom+1，wom+2，„，wom+n)T 则定理2.5可以表示为

WoTXso=0

WsoTXo=0 (2.12) 即

o

oT

oT

o

76

第二章 对偶线性规划与灵敏度分析

w1ow2owiowmoxon1oxn2o0 xnioxnm x1ox2oxojxnowom1owm2o0 (2.13) wmjowmn而推论可以表示为

wioxon+i=0

wom+jxjo=0 (2.14) 即，由

wio>0 可以推出 xn+io=0； xn+io>0 可以推出 wio=0；

wm+jo>0 可以推出 xjo=0； (2.15) xj>0 可以推出 wm+j=0。

利用原始问题和对偶问题最优解之间的互补松弛关系，可以从其中一个问题的最优解求得另一问题的最优解。 例2.6 求解以下线性规划问题

min z= 6x1 +8x2 +3x3 s.t.

写出对偶问题

max y= w1 -w2 s.t.

w1 +w2 w1 +2w2

w2

≤6 ≤8 ≤3

o

o

77

(2.17)

x1 +x2 x2,

≥1 +x3 ≥-1 x3 ≥0

x1 +2x2 (2.16)

x1,

第二章 对偶线性规划与灵敏度分析

w1, w2 ≥0

这是一个两个变量的线性规划问题，利用图解法，可以求得这个问题的最优解为 (w1，w2)T=(6，0)T

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

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

WT=(w1，w2，w3，w4，w5)T=(6，0，0，2，3)T y=6 根据定理2.5，以下的互补松弛关系成立 由 w1>0 得到 x4=0 由 w4>0 得到 x2=0 由 w5>0 得到 x3=0 因此原始问题的约束条件

x1

成为

x1 =1 x1 -x5 =-1

由此得到

x1=1，x5=2 即原始问题的最优解为

X=(x1，x2，x3，x4，x5)T=(1，0，0，0，2)T z=6 对照对偶解

WT=(w1，w2，w3，w4，w5)T=(6，0，0，2，3)T y=6 容易验证，以上两个最优解满足互补松弛条件 x1w3=x2w4=x3w5=0 w1x4=w2x5=0

XW必须指出，定理2.5的逆命题并不成立，也就是说，如果两个向量和XWSS+x2 -x4 +x3

=1

x1 +2x2 -x5 =-1

满足互补松弛关系WTXS=0，WSTX=0，并不能推出它们分别是原始问题和对偶问题的最优解。

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

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

78

第二章 对偶线性规划与灵敏度分析

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

XWSS们满足以下三个条件：

1、X、XS是原始问题 min z=CX

s.t. AX-Xs=b (P) X，Xs≥0

的可行解。这个条件称为原始可行条件（Primal Feasible Condition，PFC）。

2、W、Ws是对偶问题 max z=bTW

s.t. ATW+Ws=C (D) W，Ws≥0

的可行解。这个条件称为对偶可行条件（Dual Feasible Condition，DFC）。

3、X、Xs、W、Ws满足 WXs=0 WsX=0

这个条件称为互补松弛条件（Complementary Slackness Condition，CSC）。

TT

T

2.2.4 单纯形表的结构，单纯形表与K-T条件的关系

引进对偶的概念以后，我们可以从新的角度来分析单纯形表的结构。 设原始问题为 min z=CTX

s.t. AX-Xs=b (P) X，Xs≥0

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

z 1 0 X -C A TXs 0T -I RHS 0 b 设对于任一可行基B，相应的系数矩阵表为

z 1 XB -CBT XN -CNT 79

Xs 0T RHS 0 第二章 对偶线性规划与灵敏度分析

0 相应的单纯形表为

z XB

z 1 0 B N -I b XB 0T I XN CBTB-1N-CNT BN -1Xs RHS -CBTB-1 CBTB-1b -B -1Bb -1其中基变量XB在目标函数中的系数0T可以写成

0T=CBTB-1B-CBT 基变量在约束中的矩阵I可以写成 I=B-1B

因此，以上单纯形表可以写成

z XB 记

WT=CBTB-1 则

WsT=CT-WTA=CT-CBTB-1A 因此以上单纯形表可以写为

z XB z 1 0 X -Ws B-1A Tz 1 0 X CBBA-C B-1A T-1TXs T-1RHS T-1-CBB CBBb -B-1 B-1b Xs -W -B-1 TRHS CBBb B-1b T-1如果B是原始可行基而不是最优基，则在X或Xs中，至有一个非基变量xj，使得

zj-cj>0

当j=1，2，„，n时，xjX，当j=n+1，„，n+m时，xjXs。

80

第二章 对偶线性规划与灵敏度分析

若xjXs，不妨设j=n+i，则zj-cj=-wi>0，即wi<0，也就是第i个对偶变量违背非负约束；

若xjX，则zj-cj=-wm+j>0，即wm+j<0，也就是第j个对偶松弛变量违背非负约束，即wm+j=cj-Waj<0，或Waj>cj，也就是对偶问题的第j个约束不满足。

另外，由单纯形法可知，在X中，如果xj是基变量，则xj>0，而zj-cj=-wm+j=0，如果xj是非基变量，则xj=0，而zj-cj=-wm+j>0；同样，在Xs中，如果xn+i是基变量，则xn+i>0，而zj-cj=-wi=0，如果xn+i是非基变量，则xn+i=0，而zj-cj=-wi>0。由此可见，无论X、Xs是否是最优解，X、Xs、W、Ws都满足互补松弛关系。

当B是最优基时，所有检验数zj-cj0，即-Ws0、-W0，也就是Ws0、W0，满足对偶可行条件。

综上所述，单纯形法和Kuhn-Tucker条件的关系可叙述如下： 在单纯形叠代过程中，如果当前基B是原始可行基而不是最优基，则 1、原始问题相应的解X、Xs满足原始可行条件；

2、对偶问题相应的解WT=CBTB-1、WsT=CT-WTA中至少有一个不满足对偶可行条件；

3、X、Xs、W、Ws在单纯形叠代的每一步，都满足互补松弛关系。 当B不仅可行，而且是最优基时，对偶问题相应的解WT=CBTB-1、WsT=CT-WTA才满足对偶可行条件。

因此，我们可以把单纯形法看成在原始可行条件和互补松弛条件得到满足的条件下，不断改进对偶可行条件的过程，一旦三个条件都得到满足，也就得到了最优解。

例2.7 求解以下线性规划问题，对每一次叠代得到的基，验证是否满足原始可行条件、对偶可行条件以及互补松弛条件。

min z= -x1 s.t.

对偶问题为

max y= 3w1 +4w2

w1 +2w2 -1 w1 +2w2 -1 w1

+w2 -1 w2 0

81

x1 x1

-x2 -x3

+x2 +x3 3 x2

x3 0

T

T

2x1 +2x2 +x3 4

w1,

第二章 对偶线性规划与灵敏度分析

这个问题的原始问题用矩阵表示的形式为 min z=CTX s.t. AXb X0 对偶问题为

max y=bTW s.t. ATWC W0

原始问题引进松弛变量Xs，成为

min z=CTX s.t. AX+Xs=b X，Xs0 对偶问题引进松弛变量，成为 max y=bTW s.t. ATW+Ws=C W0，Ws0 即 WTs=CT-WTA

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

z 1 0 X -C A TXs 0T I RHS 0 b 设对于任一可行基B，相应的系数矩阵表为

z 1 0 相应的单纯形表为

z

z 1 XB 0T XN CBTB-1N-CNT 82

Xs RHS CBTB-1 CBTB-1b XB -CBT B XN -CNT N Xs 0T I RHS 0 b 第二章 对偶线性规划与灵敏度分析

XB 0 I B-1N B-1 B-1b 将XB和XN合并成X，以上单纯形表可以写成

z XB 记

W=CBB

由对偶问题的形式可以知道

-WsT=-(CT-WTA)=CBTB-1A-CT 因此以上单纯形表可以写为

z XB z 1 0 X -WsT BA -1T

T-1

z 1 0 X CBTB-1A-CT BA -1Xs RHS CBTB-1 CBTB-1b B -1Bb -1Xs WT B -1RHS CBTB-1b Bb -1在原始问题中引进松弛变量x4、x5，得到

min z= -x1 s.t.

x1

-x2 -x3

+x2 +x3 +x4 x2,

x3 x4,

=3 x5 0

2x1 +2x2 +x3 x1,

+x5 =4

在对偶问题中引进松弛变量w3、w4、w5，得到

max y=

z

3w1 +4w2 w1 +2w2 w1 +w2 w1 +2w2 +w3

=-1 =-1

RHS 0

+w4

+w5 =-1

w10 w20 w30 w40 w50 z 1 x1 1 x2 1 x3 1 x4 0 x5 0 83

原始问题的初始单纯形表为 第二章 对偶线性规划与灵敏度分析

x4 x5 由此得到

0 0 1 [2] 1 2 1 1 1 0 0 1 3 4 3/1 4/2 x1=0，x2=0，x3=0，x4=3，x5=4 w1=0，w2=0，w3=-1，w4=--1，w5=-1 因此有

x1w3=0，x3w4=0，x3w5=0，x4w1=0，x5w2=0 PFC和CSC满足，松弛变量w3、w4、w5都小于0，DFC不满足。 x1进基，x5离基，得到以下单纯形表 z x4 x1 由此得到

x1=2，x2=0，x3=0，x4=1，x5=0

w1=0，w2=-1/2，w3=0，w4=0，w5=-1/2 因此有

x1w3=0，x3w4=0，x3w5=0，x4w1=0，x5w2=0 PFC和CSC满足，w5=-1/2<0，DFC不满足。 x3进基，x4离基，得到以下单纯形表

z x3 x1

由此得到

x1=1，x2=0，x3=2，x4=0，x5=0 w1=-1，w2=0，w3=0，w4=0，w5=0 因此有

x1w3=0，x3w4=0，x3w5=0，x4w1=0，x5w2=0 PFC、CSC和DFC都满足，因而是最优解。

z 1 0 0 x1 0 0 1 x2 0 0 1 x3 0 1 0 x4 -1 2 -1 x5 0 -1 1 RHS -3 2 1

z 1 0 0 x1 0 0 1 x2 0 0 1 x3 1/2 [1/2] 1/2 x4 0 1 0 x5 -1/2 -1/2 1/2 RHS -2 1 2 1/1/2 2/1/2 84

第二章 对偶线性规划与灵敏度分析

§2.3 对偶单纯形法

上一节中，我们已经知道，线性规划取得最优解的充分必要条件是原始可行、对偶可行和互补松弛条件同时满足。同时，也曾指出，单纯形叠代过程实际上是在满足原始可行条件和互补松弛条件的基础上，不断改进对偶可行性的过程，一旦对偶可行条件得到满足，就得到了最优解。对偶单纯形法则是从另一角度来进行的。对偶单纯形法在叠代过程中保持对偶可行条件和互补松弛条件满足，并且在叠代过程中不断改进原始可行条件。一旦原始可行条件得到满足，也就求得了最优解。为了说明对偶单纯形法原理，先建立有关概念和定理。

2.3.1 对偶可行基

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

T

=CBTB-1是对偶问题的可行解，则称

B为

原始问题的对偶可行基。

x2 8 H 7 6 5 4 2 1 例2.8 求以下线性规划问题的对偶可行基。 min st

z=

-x1 2x1 2x1 x1,

-x2 +3x2 +x2 x2 x2

≤12 ≤8 ≤3 ≥0

E C F B O 0 1 2 3 D A 3 4 5 G 6 x1

这个问题的图解如右。引进松弛变量x3，x4，x50，得到

min st max st z= y=

-x1 2x1 2x1 x1,

-x2 +3x2 +x2 x2 x2,

+x3 x3,

+x4 x4,

+x5 x5

=12 =8 =3

≥0

原问题的对偶问题为

12w1 +8w2 +3w3 2w1 +2w2 3w1 w1,

+w2 w2,

≤-1 +w3 ≤-1 w3

≤0 85

第二章 对偶线性规划与灵敏度分析

在原始问题中取基

B1a2a33a51110000 11310001计算相应的对偶变量

WTCBB11T10001010

即w1=0，w2=-1，w3=0。容易验证W满足对偶的所有约束条件，包括变量非正的条件。根据定义，B1是对偶可行基。但是B1并不是原始可行基，这是因为

x201B1bx31x5013101280812 135不满足原始可行条件。

再取基

B2a1a22a520131100 13/41/21/2001/411/40

WTCBB21T11/401/21/2W满足对偶问题的约束条件，因而B2是对偶可行基。同时

x11/41B2bx21/2x51/23/41/21/201230820 131因此B2也是原始可行基。

基B1和B2相应的极点在图上分别对应于点H和B。容易看出，点B即基B2是最优解。

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

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

86

第二章 对偶线性规划与灵敏度分析

1XBBbX0 XN0同时因为B是对偶可行基，根据对偶可行基的定义，WT=CBTB-1满足对偶问题的约束条件，即

WTA≤CT WT≥0

或

CBTB-1A-CT≤0T -CBTB-1≤0T

以上两个条件，就是

zj－cj≤0, j=1, 2, „, n, n+1, „, n+m

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

2.3.2 对偶单纯形法

对偶单纯形法是从一个原始不可行而对偶可行的基出发，进行基变换，每次基变换时都保持基的对偶可行性，一旦获得一个原始可行基，则该基必定是最优基。 例2.9 用对偶单纯形法求解以下问题

min z= 2x1 +3x2 +4x3

x1 +2x2 x1,

x2,

2x1

+x3 ≥3 x3 ≥0

-x2 +3x3 ≥4

引进松弛变量x4，x5≥0，得到

min z= 2x1 +3x2 +4x3

x1 +2x2 x1,

x2,

2x1

-x2 +3x3

+x3 -x4 x3, x4,

=3 x5 ≥0

-x5 =4

为了得到单位矩阵形式的初始基，将约束等式两边同乘以-1，得到

min z= 2x1 +3x2 +4x3

列出初始单纯形表

87

-x1 -2x2 -2x1 x1,

+x2 x2,

-3x3

-x3 +x4 x3, x4,

=-3 x5 ≥0

+x5 =-4

第二章 对偶线性规划与灵敏度分析

z x4 x5 z 1 0 0 x1 -2 -1 [-2] -2/-2 x2 -3 -2 1 x3 -4 -1 -3 -4/-3 x4 0 1 0 x5 0 0 1 RHS 0 -3 -4 由于表中所有的zj－cj0，因此当前基是对偶可行基。但当前基变量的值x3=-3<0，x4=-4<0，因此当前的基不是原始可行基。

为了改善基的原始可行性，取一个小于零的基变量离基，如果有数个基变量的值小于零，一般可选其中绝对值最大的先离基。这里选x5=-4离基。

为了改善原始可行性，应该使旋转运算以后进基变量的值成为非负的，这样就要在离基行中选择yrj<0的元素作为主元。在上表中，有y21=-2和y23=-3可以选为主元。

为了使新的基仍保持对偶可行性，必须使旋转运算后所有检验数zj-cj≤0。因此按以下方法选择进基列k。

zjcjzck min|yrj0kyrkyrj在上例中，选取

zc1z3c3244min1,,minmin1,1

y23233y21选取x1进基。即选取y21=-2为主元，进行旋转运算，得到以下单纯形表。

z x4 x1

由于x4=-1<0，新的基仍不是原始可行的。取x4离基，选择进基变量。

zc2z5c51488min2,min,min,2

yy5/21/2551215z 1 0 0 x1 0 0 1 x2 -4 -5/2 -1/2 -4/-5/2 x3 -1 1/2 3/2 x4 0 1 0 x5 -1 -1/2 -1/2 -1/-1/2 RHS 4 -1 2 选取x2进基。即以y12=-5/2为主元，进行旋转运算，得到

88

第二章 对偶线性规划与灵敏度分析

z x2 x1 z 1 0 0 x1 0 0 1 x2 0 1 0 x3 -9/5 -1/5 7/5 x4 -8/5 -2/5 -1/5 x5 -1/5 1/5 -2/5 RHS 28/5 2/5 11/5 当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为 x1=11/5，x2=2/5，x3=x4=x5=0，min z=28/5

注意到以上极小化问题在叠代过程中，每次叠代目标函数值不断增大，这是因为叠代过程是从可行域以外的点向可行域靠拢的缘故。

掌握了单纯形法和对偶单纯形法，我们就可以更灵活地进行单纯形叠代来求得线性规划的最优解，既可以从一个原始可行、对偶不可行的解出发，用单纯形法进行叠代，也可以从一个原始不可行、对偶可行的解出发，用对偶单纯形法进行叠代，甚至可以从一个原始不可行，对偶也不可行的解出发，先用适当的进基—离基变换把解变成原始可行或对偶可行的，然后再用单纯形法或对偶单纯形法求解。 例2.10 求解以下线性规划问题 min st min st min st z= z= z=

-3x1 +2x2 x1+ 2x1 x1

+x2 +x2 x2

+x3 +x3 +x3 x3 +x3 +x3 +x3 x3 +x3 -x3 +x3 -2x3 x3

12 38 24 0 -x4 x4 +x4 x4

+x5 x5 +x5 x5

(1) (2) (3) -x6 x6

=12 =38 =24 0

(1) (2) (3) (1) (2) (3)

x1 +2x2 +2x3

引进松弛变量

-3x1 +2x2 x1+ 2x1 x1

+x2 +x2 x2

x1 +2x2 +2x3

约束条件（1）、（3）两边分别乘以-1

-3x1 +2x2 -x1 2x1 -x1 x1

-x2 +x2 -2x2 x2

=-12 = 38 +x6 =-24 x6

0

列出单纯形表

第二章 对偶线性规划与灵敏度分析

z x4 x5 x6 z 1 0 0 0 x1 3 -1 [2] -1 x2 -2 -1 1 -2 x3 -1 -1 1 -2 x4 0 1 0 0 x5 0 0 1 0 x6 0 0 0 1 RHS 0 -12 38 -24 初始单纯形表对应的原始问题的解为

(x1，x2，x3，x4，x5，x6)=(0，0，0，-12，38，-24) 对应的对偶问题的解为

(w1，w2，w3，w4，w5，w6)=(0，0，0，-3，2，1)

也就是说，以x1，x2，x3为非基变量，以x4，x5，x6为基变量，相应的基础解既不是原始可行的，又不是对偶可行的，但原始问题的解和对偶问题的解满足互补松弛关系。在以上的单纯形表中，选取x1进基，x5离基，即y21=2为主元，旋转运算后，就可以得到： z x4 x1 x6 z x4 x1 x3

z 1 0 0 0 x1 0 0 1 0 x2 -7/2 -1/2 1/2 -3/2 x3 -5/2 -1/2 1/2 [-3/2] x4 0 1 0 0 x5 -3/2 1/2 1/2 1/2 x6 0 0 0 1 RHS -57 7 19 -5 以上的解为对偶可行，原始不可行。用对偶单纯形法继续求解。x6离基，x3进基。

z 1 0 0 0 x1 0 0 1 0 x2 -1 0 0 1 x3 0 0 0 1 x4 0 1 0 0 x5 -7/3 1/3 2/3 -1/3 x6 -5/3 -1/3 1/3 -2/3 RHS -146/3 26/3 52/3 10/3 以上的解原始可行，对偶可行，并且满足互补松弛关系，因而是最优解。最优解为：

(x1，x2，x3，x4，x5，x6)=(52/3，0，10/3，26/3，0，0)，min z=-146/3。

对偶问题的最优解为：

（w1，w2，w3，w4，w5，w6）=（0，-7/3，5/3，0，1，0）。

90

第二章 对偶线性规划与灵敏度分析

§2.4 灵敏度分析

灵敏度分析是要在求得最优解以后，解决以下几方面的问题：

1、 线性规划问题中的各系数在什么范围内变化，不会影响已获得的最优基。 2、 如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解 3、 当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础

上获得新的最优解。

2.4.1 目标函数系数C的变化范围

首先，应该指出目标函数系数C向量中的元素数值变化，只会影响最优解中zjcjCBBajcj （j=1,2,„,n）的值，而不会影响bB1b的值。也就是

T1说，C中元素的变化只会影响最优解的对偶可行性而不会影响原始可行性。

C中元素cj的变化范围与相应的变量xj是基变量还是非基变量有所不同，下面分别就这两种情况来讨论。

2.4.1.1 非基变量在目标函数中系数的灵敏度分析

m个基变量xBr（r=1,2,„,m）在目标函数中的系数为：

01cBr0 0zBrcBrCBBaBrcBrcB1T1cBrcBmn-m个非基变量xj在目标函数中的系数为：

zjcjCBBajcj

T1设某一个非基变量xk在目标函数中的系数为ck，当这个非基变量xk的系数ck 变化成为ck’=ck+ 时，由上式可知，对基变量在目标函数中的系数没有影响，所有基变量在目标函数中的系数仍为0。

当这个非基变量xk的系数ck 变化成为ck’=ck+ 时，n-m个非基变量xj在目标函数中的系数为：

zjcj T1zjcjCBBajcj zkckzkckjkjk

即非基变量xk在目标函数中的系数ck的变化，在最优解中只会影响这个非基变量在

91

第二章 对偶线性规划与灵敏度分析

目标函数中的系数，其他非基变量的系数不会变化。如果检验数zk-ck-0，则原来的最优基仍保持为最优基，如果检验数zk-ck->0，则原来的最优基不再是最优基，新的最优基可以通过将xk进基，并进行后续的单纯形叠代，得到新的最优基和最优解。

例2.9线性规划问题为

min s.t. z= -2x1

+x2

-x3

x1 +x2 +x3 -x1 +2x2 x1,

x2,

x3

≤6 ≤4 ≥0

求c2=1在什么范围内变化，原来的最优基保持不变；当c2=-3时，最优基是否变化，如果变化，求新的最优基和最优解。

首先用单纯形法得到以上问题的最优单纯形表。为了灵敏度分析的方便，表中同时注明各变量以及基变量的目标函数系数。

CB -2 0

z x1 x5

TBC z 1 0 0 1-2 x1 0 1 0 1 x2 -3 1 3 TB-1 x3 -1 1 1 0 x4 -2 1 1 m0 x5 0 0 1 RHS -12 6 10 注意到zjcjCBajcjCyjcj(cBiyij)cj，有

i1z1c1(c1y11c5y21)c1(2100)(2)0 z2c2(c1y12c5y22)c2(2103)13 z3c3(c1y13c5y23)c3(2101)(1)1 z4c4(c1y14c5y24)c4(2101)02 z5c5(c1y15c5y25)c5(2001)00

当c2’=c2+时，只有非基变量x2在目标函数中的系数相应变化成为：

z2c2(c1y12c5y22)c2(2103)13

其他变量在目标函数中的系数都不变。相应的单纯形表如下：

CB -2 0

z x1 x5

C z 1 0 0 -2 x1 0 1 0 1+ x2 -3- 1 3 -1 x3 -1 1 1 92

0 x4 -2 1 1 0 x5 0 0 1 RHS -12 6 10 第二章 对偶线性规划与灵敏度分析

为了保持基的对偶可行性，必须满足所有检验数zj-cj≤0（j=1,2,3,4,5），也就是-3-≤0，即≥-3，或c2’=c2+≥1+（-3）=-2，即c2’≥-2。也就是说，x2在目标函数中的系数从原来的值1减少到-2时，最优基保持不变。由于最优解XB=B-1b以及最优解的目标函数值z=CBTB-1b与非基变量在目标函数中的系数CN无关，因此，当c2在以上范围内变化时，最优解以及最优解的目标函数值不会变化。

当c2’=-3时，=c2’-c2=（-3）-1=-4，已经超出保持最优基不变的范围，因此单纯形表不再是最优单纯形表。将=-4代入单纯形表，x2在目标函数中的系数为-3-=1，得到以下单纯形表：

z x1 x5 z x1 x2

z 1 0 0 z 1 0 0 x1 0 1 0 x1 0 1 0 x2 1 1 [3] x2 0 0 1 x3 -1 1 1 x3 -4/3 2/3 1/3 x4 -2 1 1 x4 x5 0 0 1 x5 RHS -12 6 10 RHS -46/3 8/3 10/3 x2进基，x5离基

-7/3 -1/3 2/3 1/3 -1/3 1/3 得到新的最优解：x1=8/3，x2=10/3，x3=0，x4=0，x5=0，min z=-46/3 2.4.1.2 基变量在目标函数中系数的灵敏度分析 例2.10 在线性规划问题中，对c1=1进行灵敏度分析。

min

s.t.

CB 1 0 -4

z x1 x5 x3 z=

x1 +x2 -4x3 x1 +x2 +2x3 x1 +x2 -x1 +x2 x1, C z 1 0 0 0 x2, 1 x1 0 1 0 0 -x3 +x3 x3 1 x2 -4 -1/4 2 2/3 ≤9 ≤2 ≤4 ≥0 -4 x3 0 0 0 1 93

0 x4 -1 1/3 0 1/3 0 x5 0 0 1 0 0 x6 -2 -2/3 1 1/3 RHS -17 1/3 6 13/3 先得到以上问题的最优单纯形表：

第二章 对偶线性规划与灵敏度分析

当c1’=c1+时，相应的单纯形表为：

CB 1+ 0 -4

z x1 x5 x3

C z 1 0 0 0 1+ x1 0 1 0 0 1 x2 -4-1/3 -1/4 2 2/3 -4 x3 0 0 0 1 0 x4 -1+1/3 1/3 0 1/3 0 x5 0 0 1 0 0 x6 -2-2/3 -2/3 1 1/3 RHS -17+3 1/3 6 13/3 要使原来的基仍保持最优基，就要检验数zj-cj≤0（j=1,2,3,4,5），即-4-1/3012 11/30，也就是3。由此得到，-33，即当-2c14时，最优

322/30基保持不变。当c1的变化超出以上范围时，至少会使一个检验数zj-cj>0，用单纯形法继续运行，就可以得到新的最优基和最优解。

2.4.2 右边常数的灵敏度分析

当右边常数向量b发生变化，成为b’时，对变量在目标函数中的系数

zjcjCBBajcj

T1没有影响，而单纯形表中的右边常数将变成b B1b 。即右边常数向量的变化只会影响最优基的原始可行性而不会影响其对偶可行性。当变化以后的

bBb0时，原来的最优基仍为最优基，否则，原来的基成为对偶可行基但

1 不是原始可行基，这时要用对偶单纯形法求得新的最优基。

例2.11 对以下线性规划问题中第一个约束右边常数b1=9进行灵敏度分析。

min s.t. z x1 x5 x3

z 1 0 0 0 z=

x1 +x2 x1 +x2 -x1 +x2 x1, x1 0 1 0 0 x2, x2 -4 -1/4 2 2/3 -4x3 -x3 +x3 x3 x3 0 0 0 1 x1 +x2 +2x3

≤9 ≤2 ≤4 0 x4 -1 1/3 0 1/3 94

x5 0 0 1 0 x6 -2 -2/3 1 1/3 RHS -17 1/3 6 13/3 先求得最优单纯形表：

第二章 对偶线性规划与灵敏度分析

由于初始单纯形表中，约束矩阵中松弛变量x4，x5，x6的系数构成一个单位矩阵，因此最优单纯形表中松弛变量在约束矩阵中的系数就是最优基的逆矩阵。即

B11/301/30101/32/311，bBb01/31/32/39121/340102/311/30102/311/39241/36 13/3当b1’=b1+=9+时，最后一张单纯形表中的右边常数将成为

1/3'1'bBb01/30101/31/36

13/31/3922174这时，最后单纯形表中目标函数的值也将发生变化，成为：

zCBBb1 T1 01/3401/392140单纯形表成为

z x1 x5 x3

z 1 0 0 0 x1 0 1 0 0 x2 -4 -1/3 2 2/3 x3 0 0 0 1 x4 -1 1/3 0 1/3 x5 0 0 1 0 x6 -2 -2/3 1 1/3 RHS -17- 1/3+1/3 6 13/3+1/3 由此可以看出，当第一个约束的右边常数b1变化时，新的单纯形表的RHS列就是原来最优单纯形表的RHS列加上第一个松弛变量x4在原来单纯形表中对应的列与的乘积。根据这个规则，容易得到第二个约束的右边常数b2=2变为b2’=2+时的单纯形表：

z x1 x5 x3

95

z 1 0 0 0 x1 0 1 0 0 x2 -4 -1/3 2 2/3 x3 0 0 0 1 x4 -1 1/3 0 1/3 x5 0 0 1 0 x6 -2 -2/3 1 1/3 RHS -17- 1/3 6+ 13/3 以及第三个约束的右边常数b3=4变为b3’=4+时的单纯形表：

第二章 对偶线性规划与灵敏度分析

z x1 x5 x3

z 1 0 0 0 x1 0 1 0 0 x2 -4 -1/3 2 2/3 x3 0 0 0 1 x4 -1 1/3 0 1/3 x5 0 0 1 0 x6 -2 -2/3 1 1/3 RHS -17-2 1/3-2/3 6+ 13/3+1/3 这样就可以分别求出在保持原来最优基原始可行性条件下，b1=9，b2=2，b3=4的变化范围。对于b1’=9+，由第一张单纯形表约束条件的原始可行条件可以得到，当

1/31/301，即 13/31/3013或-1，b1’=b1+8时，原来的最优基仍为原始可行基，由于这时这个基仍是对偶可行的，这时这个基仍是最优基。

当b1的变化超过以上范围，例如b1’=7，即 =b1’-b1==7-9=-2时，单纯形表成为： z x1 x5 x3 z x6 x5 x3

z 1 0 0 0 x1 0 1 0 0 x2 -4 -1/3 2 2/3 x3 0 0 0 1 x4 -1 1/3 0 1/3 x5 0 0 1 0 x6 -2 [-2/3] 1 1/3 RHS -15 -1/3 6 11/3 用对偶单纯形法继续求解，x1离基，x6进基

z 1 0 0 0 x1 -3 -3/2 3/2 1/2 x2 -3 1/2 3/2 1/2 x3 0 0 0 1 x4 -2 -1/2 1/2 1/2 x5 0 0 1 0 x6 0 1 0 0 RHS -14 1/2 11/2 10/3 得到新的最优解为：（x1,x2,x3,x4,x5,x6）=（0,0,10/3,0,11/2,1/2），min z=14。对于b2和b3的灵敏度分析，则分别可以由相应的单纯形表得到。

2.4.3 增加一个新的变量

当前最优基是B。设新增加的变量xj在目标函数中的系数为cj，在约束中的系数向量是aj，计算

YjBaj，zjcjCBBajcj

在原单纯形表中增加一个新的变量以及新的一列，将以上系数置于原单纯形表中，

96

1T1第二章 对偶线性规划与灵敏度分析

构成新的单纯形表。若新变量的检验数zj-cj0，则原来的基仍为最优基，原来的基变量以及基变量的值保持不变，新的变量xj=0是非基变量。否则xj进基，用单纯形法继续运行，直至获得新的最优基和最优解。 例2.12 在例2.9

min s.t.

1z=

-2x1 x1 x1,

+x2 +x2

-x3 +x3

6 4

-x1 +2x2

x2, x30

中，增加一个新的变量x6，它在目标函数中的系数c6=1，在约束条件中的系数向量为a6，求新的最优基和最优解。

2列出原问题的最优单纯形表：

z x1 x5

z 1 0 0 TBx1 0 1 0 c1Tx2 -3 1 3 x3 -1 1 1 x4 -2 1 1 0,Bx5 0 0 1 1RHS -12 6 10 从中可以看出，Cc521110， 1z6c6CBBa6c6

11Y6Ba61011 121新的单纯形表为： z x1 x5 z x1 x6

z 1 0 0 x1 0 1 0 x2 -3 1 3 x3 -1 1 1 x4 -2 1 1 x5 0 0 1 x6 1 -1 1 RHS -12 6 10 x6进基x5离基，得到下一个单纯形表

z 1 0 0 x1 0 1 0 x2 -6 4 3 x3 -2 2 1 x4 -3 2 1 x5 -1 1 1 x6 0 0 1 RHS -22 16 10 得到新的最优基为B=[a1，a6]，新的最优解为

97

第二章 对偶线性规划与灵敏度分析

(x1,x2,x3,x4,x5,x6)=（16,0,0,0,0,10），min z=-22。

2.4.4 增加一个新的约束

增加一个新的约束以后，如果原来的最优解满足新的约束，则原来的最优解仍是新问题的最优解，否则，最优解将发生变化。 例2.13 设线性规划问题为

min s.t.

最优单纯形表为

z x1 x5

z 1 0 0 x1 0 1 0 x2 -3 1 3 x3 -1 1 1 x4 -2 1 1 x5 0 0 1 RHS -12 6 10 z= -2x1 x1 x1,

+x2 +x2

-x3 +x3

6 4

-x1 +2x2

x2, x30

增加一个约束-x1+2x2≥2，求新的最优基和最优解。

在新的约束中引进松弛变量x6，将新的约束变为等式： -x1+2x2-x6=2 两边同乘以-1，得到 x1-2x2+x6=-2

并取x6作为新的基变量，得到新的单纯形表：

z x1 x5 x6 z x1 x5 x6 z 1 0 0 0 z 1 0 0 0 x1 0 1 0 1 x1 0 1 0 0 x2 -3 1 3 0 x2 -3 1 3 -3 x3 -1 1 1 -2 x3 -1 1 1 [-1] x4 -2 1 1 0 x4 -2 1 1 -1 x5 0 0 1 0 x5 0 0 1 0 x6 0 0 0 1 x6 0 0 0 1 RHS -12 6 10 -2 RHS -12 6 10 -8 消去x1在第三个约束中的系数，使得基变量x1在约束条件中的系数成为单位向量：

显然原来的最优解不满足新的约束，用对偶单纯形法继续求解，x6离基，x3进基：

98

第二章 对偶线性规划与灵敏度分析

z x1 x5 x3

z 1 0 0 0 x1 0 1 0 0 x2 -8/3 2/3 8/3 1/3 x3 0 0 0 1 x4 -5/3 2/3 2/3 1/3 x5 0 0 1 0 x6 -1/3 1/3 1/3 -1/3 RHS -28/3 10/3 22/3 8/3 新的最优解为（x1,x2,x3,x4,x5,x6）=（10/3,0,8/3,0,22/3,0），min z=-28/3。

如果新增加的约束是等号约束，则需要在这个约束中增加一个人工变量作为新的基变量，然后用两阶段法求得新的最优解（算例略）。

2.4.5 A矩阵中系数的灵敏度分析

我们已经知道，目标函数系数C向量中的元素数值变化，只会影响最优解中zjcjCBBajcj （j=1,2,„,n）的值，而不会影响bB1b的值，即会影响

T1最优解的对偶可行性而不会影响原始可行性；而右边常数向量b发生变化，对变量在目标函数中的系数zjcjCBBajcj没有影响，而要影响最优解中的右边常数将变成b B1b ，即会影响最优基的原始可行性而不会影响其对偶可行性。

A矩阵中元素的变化情况比较复杂，如果这个元素是最优解中非基变量的系数，那么这个元素不包含在最优基B中，它的变化只会影响这个非基变量在目标函数中的系数zjcjCBBajcj，而且对目标函数系数的影响只反映在aj中；如果这个元素是最优解中基变量在A矩阵中的系数，那么这个元素包含在最优基B中，它的变化不仅会影响这个所有变量在目标函数中的系数zjcjCBBajcj，而且同时会影响最优解的右边常数bBb。 2.4.5.1 A矩阵中非基变量系数的灵敏度分析

非基变量xj对应的非基列向量aj中元素的变化，只会影响这个非基变量在目标函数中的系数

zjcjCBBajcjWajcj

T1T1T1T1T1而且，由于列向量aj不在基B中，因此aj中元素的变化不会影响WTCBBT1。

当aj中的第r个元素arj变成arj’=arj+时，变量xj的目标函数系数

a1j T TzjcjWajcjw1wrwmarjcjWajcjwramj99

第二章 对偶线性规划与灵敏度分析

当 z jcjWTajcjwr0

基的对偶可行性保持不变，由此可以得到的变化范围。 例2.14在例2.9

min s.t.

z=

x1 +x2 -4x3 x1 +x2 +2x3 x1 +x2 -x1 +x2 x1, x2,

-x3 +x3 x3

≤9 ≤2 ≤4 ≥0

中，对变量x2在第一个约束中的系数a12=1进行灵敏度分析。

这个问题的最优单纯形表如下：

z x1 x5 x3

z 1 0 0 0 x1 0 1 0 0 x2 -4 -1/4 2 2/3 x3 0 0 0 1 x4 -1 1/3 0 1/3 x5 0 0 1 0 x6 -2 -2/3 1 1/3 RHS -17 1/3 6 13/3 其中z2-c2=-4。设

a12’=a12+

则

z2’-c2=z2-c2+w1=-4-0 即当

-4 或

a12’=a12+1+(-4)=-3

时，原来的最优基保持不变。

2.4.5.1 A矩阵中基变量系数的灵敏度分析

要象非基变量在约束矩阵中的系数一样，来确定基变量在约束条件中系数的变化范围，是十分困难的，在这里不作讨论。对于基变量在约束条件中的系数，我们仅考虑当其中一个元素变化时如何求得新的最优解。 例2.15对于例2.11中的线性规划问题

min s.t. z= -2x1 x1 x1,

+x2 +x2 x2,

-x3 +x3 x3

≤6 ≤4 ≥0 100

-x1 +2x2

第二章 对偶线性规划与灵敏度分析

已经得到它的最优单纯形表为：

z x1 x5

z 1 0 0 x1 0 1 0 x2 -3 1 3 x3 -1 1 1 x4 -2 1 1 x5 0 0 1 RHS -12 6 10 1 其中x1是基变量，当x1在约束条件中的系数向量a1变为a1时，求新

16的最优解。

引进一个新的变量x1’，它在目标函数中的系数与x1的系数相同为-2，在约束中的系数向量为a1。对于x1’，计算它在目标函数中的系数

6z1c1CBBa1c1Wa1c12 T1 T 3330(2)4 6以及x1’在约束矩阵中的列向量

1 1 Y1Ba11033 169在原最优单纯形表中增加新的变量x1’： z x1 x5 z x’1 x5 z x’1 x3

z 1 0 0 x1 0 1 0 x’1 -4 [3] 9 x2 -3 1 3 x3 -1 1 1 x4 -2 1 1 x5 0 0 1 RHS -12 6 10 将x1’进基，x1离基，得到： z 1 0 0 x1 4/3 1/3 -3 x’1 0 1 0 x2 -5/3 1/3 0 x3 1/3 1/3 [-2] x4 -2/3 1/3 -2 x5 0 0 1 RHS -4 2 -8 x3进基，x5离基，得到

z 1 0 0 x1 5/6 -1/6 3/2 x’1 0 1 0 x2 -5/3 1/3 0 x3 0 0 1 x4 -1 0 1 x5 -1/3 -1/3 1 RHS -16/3 2/3 4 由于x1已被x1’取代，在单纯形表中删除x1

101

第二章 对偶线性规划与灵敏度分析

z x’1

z 1 0 x’1 0 1 x2 -5/3 1/3 x3 0 0 x4 -1 0 x5 -1/3 -1/3 RHS -16/3 2/3 x3 0 0 0 1 1 1 4 得到新的最优解为：（x’1,x2,x3,x4,x5）=（2/3,0,4,0,0），min z=-16/3。

102

第二章 对偶线性规划与灵敏度分析

§2.5 对偶的经济解释

对偶概念的引入和对偶理论的建立，使线性规划不仅成为优化的工具，而且赋予线性规划理论和算法以明确的经济意义，从而使线性规划成为对企业经济活动进行经济分析的重要工具。企业经济活动就其目标分析，可以归纳为“最小成本”和“最大利润”两大类。

2.5.1 最小成本问题

设有一个工厂，用n种设备，生产m种产品（单位：件）。第j种设备每小时可以生产第i种产品aij件（i=1,2,„,m；j=1,2,„,n)，第j种设备每小时运行费用为cj元，第i种产品的需求量为bi件。该工厂应如何确定各种设备的运行时间，使生产的产品既满足需求，又使生产成本为最低。

设第j种设备运行xj小时，则可构造线性规划问题如下： min z= c1x1 +c2x2 +„ +cjxj +„ +cnxn s.t. a11x1 +a12x2 +„ +a1jxj +„ +a1nxn ≥b1 a21x1 +a22x2 +„ +a2jxj +„ +a2nxn ≥b2

„ „ „ „

ai1x1 +ai2x2 +„ +aijxj +„ +ainxn ≥bi

„ „ „ „

am1x1 +am2x2 +„ +amjxj +„ +amnxn ≥bm

x1,

x2, „,

xj, „,

xn

≥0

假设这时有一个推销同样产品的商人，愿意以价格w1，w2，„，wm向这个工厂出售这m种产品，并保证他所报的每一种产品的价格都不会高于同一产品的生产成本。当然，这个推销商在确定推销价格时总是希望总的销售额最大。这样，推销商确定价格的方法可以用以下线性规划表示：

max y= b1w1 +b2w2 +„ +biwi +„ +bmwm s.t. a11w1 +a21w2 +„ +ai1wi +„ +am1wm ≤c1 a12w1 +a22w2 +„ +ai2wi +„ +am2wm ≤c2

„ „ „ „ a1jw1 +a2jw2 +„ +aijwi +„ +amjwm ≤cj

„ „ „ „ a1nw1 +a2nw2 +„ +ainwi +„ +amnwn ≤cn w1, w2, „, wj, „, wn ≥0

用矩阵形式表示为

103

第二章 对偶线性规划与灵敏度分析

max y=bW s.t. WTA≤C W≥0

容易看出，这就是企业最小生产成本问题的对偶问题。这个对偶问题的经济意义是产品定价问题。

在对偶问题中第j个约束条件可以表示为 WTaj≤cj (j=1，2，„，n)

在这个约束中，向量aj表示第j种设备每开工1小时可以生产的m种产品的产量，单位是“件/小时”；向量W表示推销商愿意提供的m种产品的价格，单位是“元/件”。因此乘积WTaj表示第j种设备每小时生产的m种产品，分别用推销商提供的价格核算的总成本，我们称之为第j种设备开工时间的“机会成本”（Opportunity Cost）。以上不等式表明推销商的承诺：按照他提供的产品价格，每一种设备的机会成本都不会超过这种设备的运行成本。设备的运行成本和机会成本之差CT-WTA成为“差额成本”（Reduced Cost）。 2.5.1.1 影子价格

对于企业来说，在总成本最小时，第i种产品的需求量bi增加一件，所引起的总成本的增加，成为这种产品的“影子价格”。即设zo为最小总成本，则

zoT

bi

称为第i种产品的影子价格。对成本最小问题来说，某一产品的影子价格就是这种产品的边际生产成本。

根据对偶理论，当最小成本取得最优解时，有： z=y=b1w1+b2w2+„+biwi+„+bmwm因此

zoo0oooo

biwio(i1,2,,m)

即第i种产品的影子价格等于对偶问题最优解中第i个对偶变量的值。 2.5.1.2 定理2.4的经济解释

定理2.4指出，对于企业任何一项设备开工计划X和推销商的任何一组产品定价W，必定有

CX≥WAX≥Wb

其中左边一项是设备运行的实际总成本，中间一项是企业实际生产的m种产品用推销商提供的价格核算的总成本，右边一项是m种产品的需求量用推销商提供的价格

104

T

T

T

第二章 对偶线性规划与灵敏度分析

核算的总成本。左边一个不等式是由于设备的实际运行成本C总是高于设备的机会成本WTA，而右边一个不等式是由于实际生产的产品AX一定要大于需求量b。

至于如何解释最优解时以上三项会相等，我们将在给出了互补松弛关系的经济解释以后再讨论。

2.5.1.3 互补松弛关系的经济解释

1）如果在最优设备运行计划下，第i种产品的实际生产量超过需求量，即

nT

或松弛变量

aj1ijxjbi

xn+i>0

这时再增加一个单位需求，不会影响设备运行计划，即对最小成本没有影响，因此有

zobiwi0o(i1,2,,m)

即影子价格等于0。于是互补松弛关系

xn+iwi=0 成立。

反之，如果某一种产品需求的影子价格wi>0，这时产品需求每增加一个单位将会引起总成本z的增加，这说明实际生产这种产品的数量恰等于需求量，即

no

或松弛变量

aj1ijxjbi

xn+i=0 于是互补松弛关系 xn+iwi=0 成立。

2）如果在对偶问题最优解中，有

m

ai1ijwicj(j1,2,,n)

即第j种设备开工的机会成本小于实际成本，或者说松弛变量wm+j>0，在这种情况下，对降低总成本来说，这种设备不开工更为有利，即xj=0。于是互补松弛关系

xjwm+j=0

105

第二章 对偶线性规划与灵敏度分析

成立。

反之，如果在最优解中，某一种设备开工，即xj>0，可以肯定，这种设备的实际成本与机会成本相等，即

m

ai1ijwicj(j1,2,,n)

即松弛变量wm+j=0，这时互补松弛关系

xjwm+j=0 也成立。

下面我们说明为什么最优解时定理2.4中两个不等式都会成为等式。 我们已经指出，CTX≥WTAX中的不等式是由于某些设备运行的实际成本高于机会成本引起的，但由于最优解满足互补松弛条件，凡有成本差异的设备（cj-WTaj>0）一定不会投入运行（xj=0），于是，这种成本差异也就不会引起左右两项不等了。

同样，WAX≥Wb中的不等式是由于实际生产的产品数量大于需求量引起

nTT

的，同样由于互补松弛条件的作用，凡是生产量大于需求量（aijxjbi）的产

j1品，其影子价格都等于零（wi=0），因而这些产品数量的不平衡也就不会引起左右两项不等了。

2.5.2 最大利润问题

设一个企业生产n种产品，每种产品的单位利润为c（单位：元/件，j=1,2,„,n），j

同时企业受到m种设备工时的，第i种设备的能力为bi（单位：小时）。生产一件j产品要消耗第i种设备工时数为aij（单位：小时/件，i=1,2,„,m；j=1,2,„,n）。设第j种产品的计划生产量为xj（单位：件，j=1,2,„,n），则使总利润最大的线性规划模型为：

max z= c1x1 +c2x2 +„ +cjxj +„ +cnxn

s.t. a11x1 +a12x2 +„ +a1jxj +„ +a1nxn ≤b1

a21x1 +a22x2 +„ +a2jxj +„ +a2nxn ≤b2

„ „ „ „

ai1x1 +ai2x2 +„ +aijxj +„ +ainxn ≤bi „ „ „

am1x1 +am2x2 +„ +amjxj +„ +amnxn ≤bm

x1,

x2, „,

xj, „,

xn

≥0

„

设有一个商人想租用这m种设备，他愿意出的租金是w1,w2,„,wi,„,wm（单

106

第二章 对偶线性规划与灵敏度分析

位：元/小时，i=1,2,„,m）。该商人保证，生产每一种产品所要消耗的各种设备工时，如用以上租金出租，所得得收益不会低于每一种产品得单位利润。当然，该商人的目标是支付的租金总额最小。这样，商人用于确定各种设备租金的线性规划模型为

min y= b1w1 +b2w2 +„ +biwi +„ +bmwm

s.t. a11w1 +a21w2 +„ +ai1wi +„ +am1wm ≥c1 a12w1 +a22w2 +„ +ai2wi +„ +am2wm ≥c2

„ „ „ „ a1jw1 +a2jw2 +„ +aijwi +„ +amjwm ≥cj

„ „ „ „ a1nw1 +a2nw2 +„ +ainwi +„ +amnwn ≥cn w1, w2, „, wj, „, wn ≥0

o

o

o

o

o

由对偶理论可知，当以上两个问题都取得最优解时，有 z=y=b1w1+b2w2+„+biwio+„+bmwm因此，各种设备能力的边际利润率为

zobiwio(i1,2,,m)

o

由此可知，对偶问题最优解中对偶变量wi(i=1,2,„,m)的值就是相应设备的能力对总利润的边际贡献。wio也成为相应设备能力约束的影子价格，wio越大，表明相应的设备能力增加一个单位，引起总利润的增加越大，也就是说，相对于最优生产计划来说，这种设备能力比较紧缺；wi较小，表明设备能力相对不紧缺；wi=0，说明在最优生产计划下第I种设备能力有剩余。 2.5.2.1 互补松弛条件的经济解释

1）互补松弛条件的经济解释

若在最优生产计划下，第i种设备的能力大于这种设备实际耗用，即

noo

xnibiaj1ijxij0

或者说第i种设备能力有剩余，则按边际贡献的概念，有

zobio

wi0

o从而满足互补松弛条件xn+iowio=0。

反之，若 wi>0 即

zobi0

107

第二章 对偶线性规划与灵敏度分析

n可以断定这种设备能力没有剩余，即aijxjbi，也就是xn+i=0，从而同样满足互

j1补松弛条件xn+iowio=0。

2）对偶问题约束的左边

m

ai1ijwi(j1,2,,n)

表示生产每单位j产品（j=1,2,„,n）所耗用的各种设备能力应能产生的利润，称为j种产品的机会成本，

若某种产品的机会成本高于这种产品的利润，即

m

ai1ijwicj(j1,2,,n)

则在最优解中这种产品一定不会安排生产，即xjo=0，从而满足互补松弛条件

xjowm+jo=0

反之，如果在最优解中第j种产品投入生产，即xj>0，这种产品的机会成本和利润必定相等即

mo

womjai1ijwicj0(j1,2,,n)

因而互补松弛条件xjwm+j=0成立。 2.5.2.2 定理2.4的经济解释

对于最大利润问题，定理2.4的形式成为 CTX≤WTAX≤WTb

上式种左边的不等式，是由于某些产品的利润率和机会成本不相等引起的，即CT≤WTA。当取得最优解时，由于互补松弛条件的作用，凡机会成本和利润率不相等的产品都将不安排生产，因而使得不等式成为等式。

右边的不等式是由于某些设备的实际耗用小于设备的实际能力引起的，即AX

≤b同样由于互补松弛条件，实际耗用和能力不等的这些设备，影子价格都等于零，

oo

从而使右边的不等式也成为等式。这样，当原始和对偶问题都取得最优解时，有

CTX=WTAX=WTb

作为一个例子，我们再来看第一章中的例1.1

例2.13 某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：

108

第二章 对偶线性规划与灵敏度分析

每件产品占用的机时数（小时/件） 设备A 设备B 设备C 利润（元/件） 产品甲 产品乙 产品丙 产品丁 1.5 1.0 1.5 5.24 1.0 5.0 3.0 7.30 2.4 1.0 3.5 8.34 1.0 3.5 1.0 4.18 设备能力 （小时） 2000 8000 5000 用线性规划制订使总利润最大的生产计划。

设变量xi为第i种产品的生产件数（i＝1，2，3，4），目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型：

maxs.t.z5.24x17.30x28.34x34.18x41.5x11.0x22.4x31.0x420001.0x15.0x21.0x33.5x480001.5x13.0x23.5x31.0x45000x1,x2,x3,x40

求解这个线性规划，可以得到最优解为：

x1=294.12 ，x2=1500，x3=0，x4=58.82 （件）z=12737.06（元）

请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产，其原因可以通过机会成本分析来说明。

求解以上问题的对偶问题，得到三种设备的影子价格分别为： w1o=1.9535，w2o=0.2423，w3o=1.3792

这说明三种设备在最优生产计划下，能力都没有剩余，并且第一种设备能力最为紧缺。

分别计算四种产品的机会成本，得到

3产品甲：

ai13i1wi1.5w1+1.0w2+1.5w3

=1.5×1.9535＋1.0×0.2423＋1.5×1.3792=5.24=c1

产品乙：

ai1i2wi1.0w1+5.0w2+3.0w3

=1.0×1.9535＋5.0×0.2423＋3.0×1.3792=7.30=c2

3产品丙：

ai1i3wi2.4w1+1.0w2+3.5w3

=2.4×1.9535＋1.0×0.2423＋3.5×1.3792=9.75>c3

109

第二章 对偶线性规划与灵敏度分析

3产品丁：

ai1i4wi1.0w1+3.5w2+1.0w3

=1.0×1.9535＋3.5×0.2423＋1.0×1.3792=4.18=c4

例2.16 设利润最大问题为 资源1 资源2 资源3 资源4 利润（万元/件） 产品1 2.0 1.0 3.0 2.0 4.0 产品2 1.0 2.0 4.0 3.0 3.0 产品3 3.0 2.0 1.0 2.0 5.0 资源限量（吨） 200 350 220 400 利润最大问题的线性规划模型为

max z= 4x1 +3x2 +5x3

s.t. 2x1

+x2 +3x3 ≤200

+x3 ≤220 x3

≥0

x1 +2x2 +2x3 ≤350

3x1 +4x2 x1,

x2,

2x1 +3x2 +2x3 ≤400

引进松弛变量x4，x5，x6，x70，得到

max z= 4x1 +3x2 +5x3

x1 +2x2 +2x3 3x1 +4x2 x1,

x2,

+x3

2x1 +3x2 +2x3

s.t. 2x1 +x2 +3x3 +x4

=200 =350 =220 +x7 =400 x7

≥0

+x5

+x6

x3, x4, x5, x6,

其中松弛变量表示资源的剩余量，单位为“吨”。 如果已经求得以上问题的最优生产计划为：

x1=0（件），x2=460/11=41.82（件），x3=580/11=52.73（件）

最大利润z=3.09（万元），可以计算最优生产计划时各种资源的剩余量：

x4=200-(2x1+x2+3x3)=0（吨）

x5=350-(x1+2x2+2x3)=1770/11=160.9（吨） x6=220-(3x1+4x2+2x3)=0（吨）

x7=400-(2x1+3x2+2x3)=1860/11=169.90（吨） 这个问题的对偶问题如下：

110

第二章 对偶线性规划与灵敏度分析

min y= 200w1 +350w2 +220w3 +400w4

s.t.

2w1 w1 3w1 w1,

+w2 +2w2 +2w2 w2,

+3w3 +4w3 +w3 w3,

+3w4 +2w4

+2w4 -w5

=4 =3 -w7 =5 w7 ≥0

-w6

w4 w5, w6,

利用互补松弛关系，可以得到：

x2w6=0，x3w7=0，x5w2=0，x7w4=0

而其中x2，x3，x5，x7>0，因此有

w6=w7=w2=w4=0

代入对偶问题，得到对偶问题的最优解

w1=17/11，w2=0，w3=4/11，w4=0，w5=2/11，w6=0，w7=0

即四种资源的影子价格为

w1=17/11=1.55(万元/吨), w2=0(万元/吨), w3=4/11=0.36(万元/吨), w4=0(万元/

吨)

由此可以计算三种产品的机会成本：

产品1: 2w1 +w2 +3w3 +2w4 =27/11+10+34/11+20=46/11=4.18（万元/件） 产品2: w1 +2w2 +4w3 +3w4 =117/11+20+44/11+30=33/11=3.0（万元/件） 产品3: 3w1 +2w2 +w3 +2w4 =317/11+20+14/11+20=55/11=5.0（万元/件） 由此可以列表如下： 资源1 资源2 资源3 资源4 利润率(万元/件) 机会成本(万元/件) 机会成本－利润率 (万元/件) 产品产量(件) 产品1 产品2 产品3 资源限量 （吨） 资源剩余 （吨） 影子价格 （万元/吨） 2.0 1.0 3.0 2.0 4.0 4.18 0.18  0 1.0 2.0 4.0 3.0 3.0 3.0 0  41.8 3.0 2.0 1.0 2.0 5.0 5.0 0  52.7 200 350 220 400 0 160.90  0 169.09   17/11 0  4/11 0 由此可以清楚地看出，资源剩余量和影子价格之间以及“机会成本－利润率”和产品产量之间的互补松弛关系（表中箭头表示“一个变量大于零，导致另一个变量等于零”的互补松弛关系）。

111

第二章 对偶线性规划与灵敏度分析

可以看出最优解中产品不安排生产的原因是这种产品的机会成本高于利润率。一般来说，一种产品在最优解中是否安排生产，不仅与这种产品的利润率有关，还与这种产品对资源的消耗以及各种资源的紧缺程度有关。而线性规划模型，正是提供了对以上诸多因素进行系统分析的工具。

112