第二章 线性规划的对偶性理论
与灵敏度分析
§1 对偶问题
对偶理论是线性规划的内容之一。任何
一个线性规划都有一个伴生的线性规划，称
之为原规划对偶规划问题。下面通过实例引
出对偶问题，然后给出对偶线性规划的定
义。
上一章例1提出的线性规划问题为：某
工厂生产Ⅰ，Ⅱ型两种型号的计算机，每生
产一台Ⅰ型和Ⅱ型计算机所需的原料、工时
和提供的利润以及资源的限制量如下表：
资源 产品 I II 总量
原料 2 3 100
工时 4 2 120
利润 6 4
试确定获利最大的生产方案。
该问题的线性规划数学模型为：
12max64Zxx=+
12
12
12
23100
42120
,0
xx
xx
xx
+≤?
? +≤?
? ≥?
假如现在工厂自己不生产产品Ⅰ、Ⅱ，
而将可利用的资源都出让给其他企业，试确
定这些资源的最低可接受价格。
最低可接受价格是指按这种价格转让
资源比自己生产产品Ⅰ、Ⅱ合算的价格。
设 12,yy为这两种资源的价格，为了使工
厂出让资源合算，显然应该使出让原来生产
一台Ⅰ的资源所得的收入不低于自己生产
一台产品Ⅰ的利润，即 12246yy+≥，对于产
品Ⅱ，同样可以建立类似的约束条件
12324yy+≥.
显然在满足这两个约束的前提下，价格
越高，该工厂越合算，但价格太高，接受方
面又不会愿意购买。因此，我们需要确定的
价格是使工厂合算的最低价格，故应建立目
标函数：
12min10 120Wyy=+
12
12
12
246
324
,0
yy
yy
yy
+≥?
? +≥?
? ≥?
原来： 12max64Zxx=+
12
12
12
23100
42120
,0
xx
xx
xx
+≤?
? +≤?
? ≥?
工厂决策者所面临的两个问题的数学
模型都是线性规划，它们在结构上具有某种
对称性，称后一个线性规划为原规划的对偶
问题。
定义：称线性规划
min
() 0
WYb
YACD
Y
=
≥?
? ≥?
为原规划问题
max
() 0
ZCX
AXbL
X
=
≤?
? ≥?
的对偶规划问题。
§2 对偶理论
本节将进一步讨论线性规划问题的对
偶问题的性质
性质 1（对称性）对偶问题（D）的对偶是
原问题（L）
性质 2 若原问题第i个约束为等式，则其对
偶问题中第i个变量为自由变量；反之，若原
问题的第j个变量是自由变量，则其对偶问
题的第j个约束为等式。
线性规划的原问题与对偶问题的变换规则为：
原问题（或对偶问题） 对偶问题（或原问题）
目标函数max Z
变量 00
n?
?≥?
?≤
?
??
个
无约束
目标函数minW
约束条件
n?
?≥?
?≤
?
?=?
个
约束条件
m?
?≤?
?≥
?
?=?
个
变量 00
m?
?≥?
?≤
?
??
个
无约束
例1 试求下述线性规划原问题的对偶问题
1234min235Zxxxx=+?+
1234
134
234
1234
35
224
6
0,,0,
xxxx
xxx
xxx
xxxx
+?+≥?
? +?≤?
?++=
?
?≤≥? 无约束
解：原问题的对偶为：
123max546Wyyy=++
12
13
123
123
123
22
3
325
1
0,0,
yy
yy
yyy
yyy
yyy
+≥?
?+≤
?
?++≤??
? ?+=
?
≥≤?? 无约束
线性规划原问题与其对偶问题不仅有
形式上的对称性，而且它们的解之间也有紧
密的联系。
性质3（弱对偶性）设 ,XY分别是原问题（L）
和对偶问题（D）的任一可行解，则CXYb≤ .
性质4 设X是原问题的可行解，Y是对偶问
题的可行解，且CXYb= ，则X，Y是各自问
题的最优解.
性质5 若原问题
max
() 0
ZCX
AXbL
X
=
≤?
? ≥?
有最优解，则对偶问题也有最优解，且它们
的最优值相等.
这里 1BYbCXCBb?==Q ， 1BYCB?∴= 是
对偶问题的最优解。
对偶最优解 Y 实际是原问题松弛变量
检验数的相反数。
§3 对偶问题的经济意义—影子价格
在单纯形算法中，设 1 ,0BNXBbX?==是
最优解，最优值 1BZCBb??= ，取
1
12(,,)BmYCByyy
?==L ，
则Y是对偶最优解.
下面讨论 (1,2,)iyim= L 的经济意义：
设 ib有单位增量 1ib?=，其它参数不变，
则 1((0,0,,0))TBiiiZZC bbZyb?+?=+?=+?LL ，
即 iiiZyby?=?=
所以 iy表示在原问题已取得最优解的情
况下，第 i种资源改变一个单位时总收益的变
化值，也可以说 iy是对第i种资源的一种价格
估计。这种价格估计并不是第i种资源的实际
价值或成本，而是由该企业在生产产品的收
益来估计所用资源的单位价值，称为影子价
格。
由于影子价格是指资源增加时对最优
收益的贡献。所以，也称为资源的机会成本
或边际成本。它表示资源在最优产品组合
时，具有“潜在价值”或“贡献”，资源的影子
价格是与具体的企业及产品有关的，同一种
资源，在不同企业，或生产不同产品对应的
影子价格并不相同。
从对偶问题引出的实例中，可以看出，
影子价格也是企业出让资源的最低价格，企
业按这种价格出让资源与用这种资源自己
生产获得的收益是相等的。
影子价格是经济学中重要概念，将一个
企业拥有资源的影子价格与市场价格相比
较，可以决定是购入还是出让该种资源。当
某资源的市场价格低于影子价格时，企业应
买进资源，用于扩大生产；而当市场价格高
于影子价格时，则企业的决策者应将已有的
资源卖掉。这样获利会更多。在考虑一个地
区或一个国家某种资源的进出口决策中，资
源的影子价格是影响决策的一个重要因素。
利用单纯形表求解线性规划，在求解最
优解的同时，很容易得到问题的各种资源的
影子价格。某资源的影子价格，就是该资源
对应的约束条件所加松弛变量在最优表中
的检验数的相反数。
§4 对偶单纯形法
在单纯形法中，原问题的最优解满足：
（1）是基本解
（2）可行（ 1 0BXBb?=≥）
（3） 1 0BCC AYAC??≤?≥.即对偶解可行
单纯形法是从满足（1）（ 2 ）的一个基
可行解出发，转换到另一个基可行解，一直
迭代到（3）得到满足，即对偶解可行为止。
而对偶单纯形法则是从满足（1）（ 3 ）
的一个对偶可行解出发，以基变量值是否全
非负为检验数，连续迭代直到（2）得到满
足，即原问题的基解可行为止。
两种算法结果是一样的，区别是对偶单
纯形法的初始解不一定可行，只要求所有检
验数都非正，在保证所得解始终是对偶可行
解的前提下，连续迭代到原问题的基解可
行，从而取得问题的最优解。
对偶单纯形法计算步骤如下：
步骤 1：确定原问题（L）的初始基 B,使所
有检验数 1 0jjBjCCBPs ?=?≤，即 1BYCB?=
是对偶可行解，建立初始单纯形表。
步骤2：检查基变量的取值，若 1 0BXBb?=≥，
则已得到最优解，计算停；否则求
{ }111min()()0()ilBbBbBb???<= ，确定单纯形
表第L行对应的基变量为旋出变量。
步骤3：若所有 0lja ≥ ，则原问题无可行解，
计算停；否则，计算
}{min/0/jljl klkaaaqss=<=
（这里注意q的符号），确定对应的 KX 为旋
入变量。
步骤 4：以 lka 为主元作（L,K）旋转变换，
得新的单纯形表，转步骤2.
可以证明，按上述方法进行迭代，所得解始终是对偶可行
解。
例2 用对偶单纯形法求解下列问题
1234min1281612Zxxxx=+++
123
124
1234
242
2243
,,,0
xxx
xxx
xxxx
++≥?
? ++≥?
? ≥?
解：令ZZ=? ,则问题可变为：
1234max1281612Zxxxx=????
1235
1246
123456
242
2243
,,,,,0
xxxx
xxxx
xxxxxx
???+=??
????+=??
? ≥?
取 56(,)BPP= 为初始基，易见所有检验数
0js≤，从而可建立单纯形表，计算结果如
下：
C 128161200????
BC BX
1Bb?
123456XXXXXX
0
0
5
6
X
X
2
3
?
?
214 0 1 0
22 0 0 [4] 1
???
??
s 12816120 0????
0
12?
5
4
X
X
2
3/4
? 4 0 1 0
1/21/2 0 1 0
[1
1
]
/4
???
s 62 160 0 3????
8
12
?
?
2
4
X
X
2
1/4?
2 1 4 0 -1 0
1102 11 -
2] 4[ 2 ??
s 2 08 02 3????
8
12
?
?
2
1
X
X
2
1/2
0 1-4 4 1 1
1 04 -21 1/2
?
?
s 0 0 0 44 2???
最优解： 12341,1,0,min142XXXXZ=====
如果选 3X进基，
2314
31,,0,min14
28XXXXZ=====
本例如果用单纯形法计算，确定初始基
可行解时需引入两个人工变量，计算量要多
于对偶单纯形法。
一般情况下，如果问题能够用对偶单纯
形法计算，计算量会少于单纯形法。但是，
对偶单纯形法并不是一种普遍算法，它有一
定的局限性，不是任何线性规划问题都能用
对偶单纯形法计算的。当线性规划问题具备
下面条件时，可以用对偶单纯形法求解：
（1）问题标准化后，价值系数全非正
（2）所有约束全是不等式
§5 灵敏度分析
在线性规划问题中，目标函数，约束条
件的系数以及资源的限制量等都当做确定
的常数，并在这些系数值的基础上求得最优
解。但是实际上，这些系数或资源限制量并
非一成不变的，它们是一些估计或预测的数
字，比如价值系数随着市场的变化而变化，
约束系数随着工艺的变化或消耗定额的变
化而变化，计划期的资源限制量也是经常变
化的。当这些系数发生变化时，最优解会受
到什么影响？最优解对哪些参数的变动最
敏感？搞清楚这些问题，会使我们在处理实
际问题时，具有更大的主动性和可靠性。
分析线性规划模型的某些系数或限制
的变动对最优解的影响，被称作灵敏度分
析。
灵敏度分析主要解决两个问题：
（1）这些系数在什么范围内变化时，原先
求出的最优解或最优基不变？即最优解相
对参数变化的稳定性。
（2）如果系数的变化引起了最优解的变化，
如何用最简便的方法求出新的最优解。
下面分别介绍各类参数变化的灵敏度分析
5.1 目标函数中价值系数C的分析
分别就非基变量和基变量的价值系数
两种情况来讨论：
1、设非基变量 jX 的价值系数 jC ，有增
量 jC? ，其它参数不变，求 jC? 的范围使原最
优解不变。由于 jC 是非基变量的价值系数，
因此它的改变仅仅影响检验数 js 的变化，而
对其它检验数没有影响。
由 1 0jjjBjjjCCCBPCss?=+??=+?≤
知，当 jjC s?≤? 时，原最优解不变。
2、设基变量 BrX （r行）的价值系数 BrC
有增量 BrC? ，其它参数不变，求 BrC? 的范围
使原最优解不变。由于 BrC 是基变量的价值系
数，因此它的变化将影响所有非基变量检验
数的变化。
由新的非基变量检验数：
1
1
[(00)]
(00)
0
jjBBrj
jBrj
jrjBr
CCCBP
CBP
aC
s
s
s
?
?
=?+?
=??
=??≤
LL
LL
当max0min0jjrjBrrj
r rj
aCaaass????????>≤?≤
????????
时，原最优解不变。
例3 已知第一章例1的最优解及最优值如下：
C 6 4 0 0
BC BX
1Bb?
1X 2X 3X 4X
0
0
3
4
X
X
100
120
2
[4]
3
2
1
0
0
1
s 6 4 0 0
4
6
2
1
X
X
20
20
0
1
1
0
1/2
1/4?
1/4
3/8
?
s 0 0 1/2? 5/4?
（1）求使原最优解不变的 2C? 的变化范围
（2）若 1C变为12，求新的最优解
解（1）： 2C 即 1BC ,是基变量价值系数，用非
基变量的检验数与单纯形表 2X 所在行相应
元素相比得：
2
5124
11C
??≤?≤
? ,即 215C?≤?≤,
最优值不变
（2）： 1
5 142
3148 C
??≤?≤
? ，
即 110 23 C?≤?≤, 18 83 CC≤+?≤原 .
1C不在这个变化范围内，所以最优解发生了
变化。
将 1 12C = 代入原最优解，重新计算检验
数及最优值
C 12 4 0 0
BC BX
1Bb?
1X 2X 3X 4X
4
12
2
1
X
X
20
20
0
1
1
0
[1/2]
1/4?
1/4
3/8
?
s 0 0 1/2? 7/2?
0
12
3
1
X
X
40
30
0
1
2
1/2
1
0
1/1
1/4
?
s 0 2? 0 3?
新的最优解： 132430,40,0.XXXX====
最优值： 360Z = .
5.2 资源系数b的分析
设 rb有增量 rb? ，其它参数不变，则 rb的
变化将影响基变量所取的值，但对检验数没
有影响，记新的基变量为 BX , 则
1()
BXBbb
?=+? ，这里 (0,,,0)T
rbb?=?LL，
只要 0BX ≥ ，最终表中检验数不变，则最优
基不变。由此可知，当 rb? 所满足的范围为：
11111
0
()
0
rBbbBbBbBbB b
?????
??
??
??
+?=+?=+???
??
??
??
M
M
1 1
1
0
0
r rr
ir irrr r
mr mrr
ab a
Bbbab a
ab a
?
???????
??????
????
????==???? ?
????
??????
???? ? ????
M MM
M M M
若 1()0,1,2,,irirBbabim? +?≥=L .由此可
得 1(),1,2,,ir riabBbim??≥?=L .
当
1()
0,;iir r
ir
Bbab
a
??
>?≥
1()
0,.iir r
ir
Bbab
a
??
于是得到
11()()
max0min0.iiirirr
i ir
BbBbaba
aa
??????
>≤?≤
????
结果说明， rb? 的变化范围是由原基变量
的相反数与 1B? 的第 r 列元素的比值所确定
的。
如果 rb? 不在上述变化范围内，则变化后
的基变量所取值 BX 肯定会出现负分量。但由
于 rb? 不影响检验数的变化，因此可以用 BX
取代原最优解 1BXBb?= ，以该解为初始解，
用对偶单纯形法继续求解。
例 4 已知线性规划问题的初始解及最优解见例 3.
（1）求 1b? 的范围，使原初始基不变；（2）若 1b变
为200，，试求新的最优解
C 6 4 0 0
BC BX
1Bb?
1X 2X 3X 4X
0
0
3
4
X
X
100
120
2
[4]
3
2
1
0
0
1
s 6 4 0 0
4
6
2
1
X
X
20
20
0
1
1
0
1/2
1/4?
1/4
3/8
?
s 0 0 1/2? 5/4?
解：（1）由已知单纯形表，
11
11
2024,
13 20
48
BBb??
???
????==
??????
???
所以 11 1
1
20 2 0
201
4
BbBbb??
??
????+?=+?≥
??????
???
??
根据公式 1202011
24
b??≤?≤
?
，即 14080b?≤?≤ .
由此也可知b的范围60180b≤≤ .
（2） 1 200b = ，超出了原始基的范围，所以最
优解也发生了变化。
1
11
2007024
131205
48
BXBb?
???
??????===
???????????
???
C 6 4 0 0
BC BX
1Bb?
1X 2X 3X 4X
4
6
2
1
X
X
70
5?
0
1
1
0 ]
/2
[
1
1/4?
1/4
3/8
?
s 0 0 1/2? 5/4?
4
0
2
3
X
X
60
20
2
4?
1
0
0
1
1/2
3/2?
s -2 0 0 -2
5.3 系数矩阵A的分析
分4种情况讨论系数矩阵的变化
1.增加一个新变量的分析（增加一个列）
设 1nX +是新增加的变量，其对应的系数
列向量为 1nP +，价值系数为 1nC +，试讨论原最
优解有无改变？级如何尽快地求出新的最
优解。
如果原问题增加一个新变量，则系数矩
阵增加一个列，注意到新增加的列在以B为
基的单纯形表中应变为 1 1nBP? +，所以可先计
算 1 1nBP? +及 1111nnBnCCBPs ?+++=? ,若 1 0ns + ≤ ，
则原最优解不变。反之，将 1 1nBP? +增添到原
最优表的后面，用单纯形法继续求解。
例5 设第一章例1的原线性规划问题中考虑
生产Ⅲ型计算机，已知生产每台Ⅲ型计算机
所需原料4个单位，工时3个单位，可获利
润8个单位。试问该厂是否应该生产Ⅲ型计
算机？如果生产，应该生产多少？
解：设生产Ⅲ型计算机 3x′台，由原最优基的
1B?可得
1
3
115
4244
1313
488
BP?
?????
??????′==
???????
????? ??
????
( )1333
5
9484,6
1 4
8
BCCBPs
?
??
??′′′=?=?=
??
????
??
因为 3 0s ′ > ，所以安排生产Ⅲ型计算机有利，将
1
3BP
? ′增添到原最优表的后面，并用单纯形表继续
计算，结果如下：
C 6 4 0 0 8
BC BX
1Bb?
1X 2X 3X 4X 3X ′
4
6
2
1
X
X
20
20
0
1
1
0
1/2
1/4?
1/4
3/8
? [5/4]
1/8
s 0 0 1/2? 5/4? 9/4
8
6
3
1
X
X
′ 16
18
0
1
5/4
1/10
2/5
3/10
1/5
2/5
? 1
0
s 0 9/5? 7/5? 4/5? 0
最优解：
1233418,0,0,16,0.XXXXX
′=====
最优值： 236.Z ? =
2.增加一个新的约束条件的分析（增加一行）
设 1,111,2 1,1mmmnnmaXaXaXb++++++≤L 是
新增加的约束条件，试分析原问题最优解有
无变化？
将原有最优解代入新约束条件中，如果
满足新约束条件，则原最优解不变。反之，
则需进一步求出新的最优解。考虑到单纯形
算法中，每步迭代得到的单纯形表对应的约
束方程组都与原方程组等价。因此，可以将
新的约束方程组
1,111,2 1,11mmmnnnmaXaXaXXb++++++++=L
增添到原最优表的下面，变化后的单纯形表
增加一个行，一个列，新约束对应的基变量
是 1nX +，在单纯形表中，由于增加了新约束，
原基变量对应的列向量可能不再是单位列
向量。所以用初等行变换将表中基变量对应
的列向量变为单位列向量。变换后，原最优
表的检验数不变，但基变量 1nX +所取的值一
般要变了。若 1110,nmXBb?++=≥则已得到最优
解。反之，若 1110,nmXBb?++=<则用对偶单纯
形法继续求解。
例 6 设第一章例 1 的原线性规划问题中增加一道
加工工序，需要在另一台设备上进行。已知每台Ⅰ，
Ⅱ型产品在该设备上加工工时分别为2,3个单位，
计划期内该设备总台时为90单位。试分析原最优
解有无变化？如果有变化，求出新最优解。
解：新工序对应的约束条件为 122390.xx+≤将原
问题最优解 1220xx==代入该约束左端，显然不
满足约束条件，因此原最优解不再是最优解。
将 1252390.xxx++=填到原最优表下面，用
初等变换及对偶单纯形算法，计算如下：
C 6 4 0 0 0
BC BX
1Bb?
1X 2X 3X 4X 5X
4
6
0
2
1
5
X
X
X
20
20
90
0
1
2
1
0
3
1/2
1/4
0
?
1/4
3/8
0
?
0
0
1
s 0 0 1/2? 5/4? 0
4
6
0
2
1
5
X
X
X
20
20
10?
0
1
0
1
0
0
1/2
1/
1
4
[]
?
?
1/4
3/8
0
?
0
0
1
s 0 0 1/2? 5/4? 0
4
6
0
2
1
3
X
X
X
15
22.5
10
0
1
0
1
0
0
0
0
1
1/4
3/8
0
?
1/2
1/4
1
?
?
s 0 0 0 5/4? 1/2?
由此得最优解：
1234522.5,15,10,0.XXXXX=====
最优值： 195.Z ? =
3.改变某非基变量的系数列向量分析
设非基变量 jx 的系数列向量 jP′，试分析
原最优解有何变化？
该变化只影响单纯形表的第j列及其检
验数。因此，可以先计算 1 jBP? ′ 及
1
jjBjCCBPs
?′′=? .若 0
js
′ ≤ ，则最优解不变。
反之，若 0js ′ > ，则以 1 jBP? ′替代原最优表的
第j列，用单纯形表继续求解。
4.改变基变量的系数列向量的分析
设基变量 jx 的系数列向量为 jP′，试分析
原最优解有何变化？
显然， jP的变化将导致B的变化，因而
原最优表的所有元素都将发生变化，似乎只
能重新计算变化后的模型。但是，经过认真
分析，还是可以利用原最优解来计算新最优
解的。
我们可以将 jx 看作新增加的变量，用
1
jBP
? ′替代原最优表的第j列（单位列向量），
然后利用初等行变换将表中的 1 jBP? ′恢复到
原来的单位列向量，并重新计算检验数。则
变化后的单纯形表有以下几种情况：
①基变量取值全非负，且检验数全非
正，已得到新的最优解
②基变量取值全非负，但存在正检验
数，该解是基可行解，可以用单纯形法继续
求解
③存在取负值的基变量，但检验数全非
正，该解是对偶可行解，可以用对偶单纯形
法继续求解
④存在取负值的基变量，且存在正的检
验数，该解既不是基可行解，又不是对偶可
行解，对于这种情况，我们将表中取负值的
基变量 BiX 对应的行还原成约束方程，用-1
乘方程两端，再在方程左端加一个人工变量
1nX +，用该方程替代原单纯形表的第i行，其
对应的数值为 1()iBb?? ，其价值系数为 M? 。
可以用单纯形表继续求解。
例7 第一章例1的原问题中，如果 1X 的系数
列向量变为 84????
??
，试分析原问题最优解有何
变化。
解： 1 1
11 3
824
1134
248
BP?
?????
????′ ??==
?? ???????
? ????
，用
3
1
2
??
??
?????取代
原最优表的第1列，再用初等行变换将该列变为原
来的单位列向量，结果如下：
C 6 4 0 0
BC BX
1Bb?
1X 2X 3X 4X
4
6
2
1
X
X
20
20
3
1/2?
1
0
1/2
1/4?
1/4
3/8
?
s 0 0 1/2? 5/4?
C 6 4 0 0
BC BX
1Bb?
1X 2X 3X 4X
4
6
2
1
X
X
140
40?
0
1
1
0
1
1/2
? 2
3/4?
s 0 0 1 2/7?
该解既不是基可行解，又不是对偶可行
解，将表中第二行乘以-1，并用人工变量 5X
取代 1X ,重新计算检验数，然后利用单纯形法
继续运算，结果如下：
C 6 4 0 0 -M
BC BX
1Bb?
1X 2X 3X 4X 3X ′
4
M?
2
5
X
X
140
40
0
1?
1
0
1
1/2?
2
5/4
0
1
s 6-M 0 4 2M? 3 84 M ? 0
4
0
2
4
X
X
100
3
160
3
8
3
4
3?
10
1
3
2
3?
01
8
3
4
3
?
s 14/3? 0 4/3? 0 -M+32/3
由此计算：
24135
100160,,0.
33XXXXX=====
最优值： 4003Z?=
|
|
