在事物之间普遍存在某种对偶关系：从不同的角度（立场）观察事物时，有两种拟似 
对立的表述。如“平面上矩形的面积与周长的关系”可分别表述为：周长一定，面积最大 
的矩形是正方形；面积一定，周长最短的矩形是正方形。同样，每个线性规划问题都有一 
个与之对应的另一个线性规划问题，我们称之为“对偶问题”（dual problem）。对偶理论是 
线性规划中最重要的理论之一，它充分显示出线性规划理论的严谨性和结构的对称性。对 
偶线性规划问题的最优解和原始问题的最优解之间也存在一定的对应关系。有时对偶解也 
称为“影子价格”（shadow price），它是经济学中一个非常重要的概念。学习对偶理论，不 
仅能从另一个视角帮助求解原始线性规划问题，而且能够帮助决策者进行敏感性分析，并 
提供有意义的管理启示。 
3.1 对偶线性规划问题 
我们先回顾第 2 章开始的两个例子。 
例 3-1（生产安排） 某厂在计划期内要安排生产 I、II 两种产品，需要用到劳动力、 
设备以及 A 和 B 两种原材料。已知生产单位产品的利润与所需各种资源的消耗量如表 3-1 
所示。
表 3-1 
产品 I 产品 II 资源限额 
劳动力 8 4 360 工时 
设备 4 5 200 台时 
原材料 A 3 10 250 公斤 
原材料 B 4 6 200 公斤 
单位利润（元） 80 100 
站在该厂（记为厂 A）资源配置的角度，需要确定两种产品的产量。设 x1 和 x2 分别 
为产品 I 和产品 II 的生产数量，则该厂面临的优化模型为
max z = 80x1 + 100x2 
s.t.
8>
>>>>>><>
>>>>>>: 
8x1 + 4x2 . 360 劳动力 
4x1 + 5x2 . 200 设备 
3x1 + 10x2 . 250 原材料A 
4x1 + 6x2 . 200 原材料B 
x1, x2 . 0 非负性 
(3-1) 
该问题的最优决策为：产品 I 的产量为 42.5，产品 II 的产量 5 单位；能实现最优利润 
3900 元。在该生产安排下，劳动力和原材料 B 将刚好消耗完（是紧约束），而设备工时和 
原材料 A 将存在一定的剩余（是非紧约束）。 
现在假设有另外一家企业 B 需要完成某个项目，正好需要厂 A 具备的劳动力、设备 
和两种原材料资源。企业 B 找到厂 A 的老板，想和他商量能否租用其拥有的劳动力和设 
备，并购买其所有原材料资源。厂 A 的老板表示，只要企业 B 支付的价格合适，他是愿意 
出租的。因此，这里最关键的问题是对四种资源的价格（租金）进行谈判。为建模方便，设 
y1 = 企业 B 为劳动力支付的单位租金（元/工时） 
y2 = 企业 B 为设备工时支付的单位租金（元/台时） 
y3 = 企业 B 为原材料 A 支付的单位费用（元/公斤） 
y4 = 企业 B 为原材料 B 支付的单位费用（元/公斤） 
很显然，企业 B 希望支付的总成本越低越好，即他的目标是追求总成本的最小化： 
min w = 360y1 + 200y2 + 250y3 + 200y4 
直观上，对企业 B 而言，最好的状态是四种资源的租金/采购成本都为零（即 y1 = y2 = 
y3 = y4 = 0），这样企业 B 能够免费获得厂 A 的四种资源。然而，当租金过低时，厂 A 
的老板就不愿意停工了。这意味着上述租金/价格应该要满足一定的条件。试想一下，厂 A 
通过 8 单位的劳动力工时、4 单位的设备工时、3 单位的原材料 A 和 4 单位的原材料 B 
能生产出一单位产品 I，从而创造 80 元的利润。于是，为了让厂 A 愿意放弃产品 I 的生 
产，其当量租金总收入（表示为 8y1 + 4y2 + 3y3 + 4y4）不能低于 80 元，用不等式约束来 
表示，即 
8y1 + 4y2 + 3y3 + 4y4 . 80 
同样，为了让厂 A 愿意放弃产品 II 的生产，其当量租金总收入也应该满足 
4y1 + 5y2 + 10y3 + 6y4 . 100 
考虑到单位租金和采购费用的非负性，我们可以得到企业 B 的一个完整的线性规划模 
型，如下： 
min w = 360y1 + 200y2 + 250y3 + 200y4 
s.t.8>
><>
>: 
8y1 + 4y2 + 3y3 + 4y4 . 80 
4y1 + 5y2 + 10y3 + 6y4 . 100 
y1, y2, y3, y4 . 0 
(3-2) 
74
利用 Excel 求解该问题，优化结果如图 3-1 所示。可以看出，企业 B 为劳动力支付的 
单位租金为 2.5 元/小时，采购原材料 B 的单位成本为 15 元/公斤，而设备的单位工时租 
金为零，原材料 A 的单位采购成本也为零。获取所有资源，企业 B 总共支付的费用为 3900 
元，恰好等于厂 A 在资源配置问题中的最优利润收入。 
图 3-1 
对比厂 A 的资源配置模型 (3-1) 和企业 B 的租金模型 (3-2)，我们可以发现这两个线 
性规划模型所有的参数（目标函数系数、工艺矩阵、约束右边项）都是共同的，只是参数 
在不同模型中位置不同而已。我们称这两个模型为互为对偶的线性规划模型。 
例 3-2（混合配方） 养猪专业户小王考虑选择玉米、槽料和苜蓿作为主要饲料科学 
养猪。各种饲料的价格以及对应的碳水化合物和蛋白质含量如表 3-2 所示；表的最后一列 
给出了科学养猪中每头猪每天摄入的最低营养成分。 
表 3-2 
营养成分 玉米 槽料 苜蓿 最小需求量 
碳水化合物 9 2 4 60 
蛋白质 4 8 6 55 
成本（元） 3 2.3 2.5 
从小王的角度，设 y1、y2 和 y3 分别为每天给每头猪喂食的玉米、槽料和苜蓿的量，其 
对应的成本—收益平衡优化模型如下： 
min w= 3y1 + 2.3y2 + 2.5y3 
75
s.t.8>
><>
>: 
9y1 + 2y2 + 4y3 . 60 
4y1 + 8y2 + 6y3 . 55 
y1, y2, y3 . 0 
(3-3) 
该问题的最优决策为 (y.1, y.2, y.3) = (5.78, 3.98, 0)；每头猪每天的饲料成本最低为 z. = 
26.51 元。 
一直从事猪饲料研究工作的老赵看到了一个自认为富有潜力的创业机会。为了更直接 
地让猪吸收生长所需的各营养成分，他认为可以从各种原料提炼出猪生长所需的碳水化合 
物和蛋白质营养素，即可以通过营养素来替代原来的猪饲料。经过半年的努力，老赵将自 
己的想法变为了现实，他面向养猪场的碳水化合物营养素和蛋白质营养素面世了；但是如 
何为两种营养素定价是摆在老赵面前的一大难题。设 
x1 = 每单位碳水化合物营养素的定价 
x2 = 每单位蛋白质营养素的定价 
考虑到每头猪每天的营养素需求，老赵当然希望自己的收入越高越好，即目标函数为 
max z = 60x1+55x2 
如果没有任何约束的限制，那么老赵应该将营养素的定价定得越高越好。但是，当营养素 
价格过高时，养猪场老板（比如小王）从经济性考虑可能依然会选择原来的饲料。因此，两 
种营养素的价格不能定得过高。为了说服小王放弃喂食玉米，其玉米饲料所包含的营养成 
分对应的当量成本（表示为 9x1 + 4x2）不能超过玉米的价格，即 
9x1 + 4x2 . 3 
同样的，为了说服小王放弃喂食槽料和苜蓿，它们各自营养素对应的当量成本也不能超过 
其价格，即： 
2x1 + 8x2 . 2.3 
4x1 + 6x2 . 2.5 
考虑到营养素价格的非负性，我们可以得到老赵的完整线性规划模型： 
max z = 60x1+55x2 
s.t.
8>
>>><>
>>>: 
9x1 + 4x2 . 3 
2x1 + 8x2 . 2.3 
4x1 + 6x2 . 2.5 
x1,x2 . 0 
(3-4) 
利用 Excel 优化求解，优化结果如图 3-2 所示。可以看出，两种营养素的最优定价分别为 
0.2313 和 0.2297 元，对应的每头猪的销售收入为 26.51 元。 
76
图 3-2 
对比小王的混合饲料配方模型 (3-3) 和老赵的营养素定价模型 (3-4) 也不难看出，两者 
之间也存在很好的对称性；它们也构成一组互为对偶的线性规划模型。 
通过上述两个例子可以看出，一个资源配置型线性规划模型，可以找到一个与之对偶 
的成本—收益平衡型线性规划模型；反之亦然。我们考虑一个一般的资源配置模型为原问 
题（Primary Problem，简记为 P）： 
max z = c1x1 + c2x2 + · · · + cnxn 
s.t.
8>
>>>>>><>
>>>>>>: 
a11x1 + a12x2 + · · · + a1nxn . b1 
a21x1 + a22x2 + · · · + a2nxn . b2 
· · · 
am1x1 + am2x2 + · · · + amnxn . bm 
x1, x2, · · · , xn . 0 
那么，其对偶问题（Dual Problem，简记为 D）为 
min w = b1y1 + b2y2 + · · · + bmym 
s.t.
8>
>>>>>><>
>>>>>>: 
a11y1 + a21y2 + · · · + am1ym . c1 
a12y1 + a22y2 + · · · + am2ym . c2 
· · · 
a1ny1 + a2ny2 + · · · + amnym . cn 
y1, y2, · · · , ym . 0 
原问题和对偶问题之间的对称关系体现为： 
·原问题的每个约束对应对偶问题的一个决策变量； 
·原问题为求极大（或极小），则对偶问题为求极小（或极大）； 
77
·原问题的目标函数系数对应于对偶问题约束右边项； 
·原问题的约束右边项对应于对偶问题的目标函数系数； 
·原问题的系数矩阵和对偶问题的系数矩阵互为转置关系； 
·原问题的约束条件方向为小于等于，其对偶问题的约束条件方向为大于等于。 
如果用矩阵形式来表示，上述原问题和对偶问题分别为 
(P) 
max z = CX 
s.t.( AX . b 
X . 0 
(D) 
min w = Y b 
s.t.( Y A . C 
Y . 0 
其中，原问题中 X 为一个列向量，而对偶问题中 Y 为一个行向量。 
以上互为对偶的问题中，原始问题是一个标准型的资源配置问题，其对偶问题是一个 
标准型的成本—收益平衡问题。那么，原问题的约束条件中包含等式约束时，如何写出其 
对应的对偶问题呢？ 
考虑如下带有等式约束条件的线性规划问题： 
max z = 
n Xj=1 
cjxj 
s.t.8>
<>
: 
n Xj=1 
aijxj = bi, i = 1, 2, · · · ,m 
xj . 0, j = 1, 2, · · · , n 
(3-5) 
先将等式约束条件分解为两个不等式约束条件。这时上述线性规划问题可表示为 
max z = 
n Xj=1 
cjxj 
s.t.
8>
>>>>><>
>>>>>: 
n Xj=1 
aijxj . bi, i = 1, 2, · · · ,m . y′i 
. 
n Xj=1 
aijxj . .bi, i = 1, 2, · · · ,m . y′′ i 
xj . 0, j = 1, 2, · · · , n 
(3-6) 
设 y′i
是对应于式 (3-6) 第一组约束的对偶变量，y′′ i 是对应于第二组约束的；这里 i = 
1, 2, · · ·,m。 
从形式上，规划问题式 (3-6) 是一个标准形式的资源配置型问题，我们可以直接写出 
其对偶问题如下：
min w = 
m Xi=1 
biy′i
+ 
m Xi=1 
(.biy′′ i ) 
s.t.8>
<>
: 
m Xi=1 
aijy′i
+ 
m Xi=1 
(.aijy′′ i ) . cj , j = 1, 2, · · · , n 
y′i
, y′′ i . 0, i = 1, 2, · · · ,m 
78
整理可得 
min w = 
m Xi=1 
bi(y′i 
. y′′ i ) 
s.t.8>
<>
: 
m Xi=1 
aij(y′i 
. y′′ i ) . cj , j = 1, 2, · · · , n 
y′i
, y′′ i . 0, i = 1, 2, · · · ,m 
令 yi = (y′i 
. y′′ i ) , y′i
, y′′ i . 0。由此可见，yi 不受正负值的限制，为“自由”身份。将 
yi 代入上述规划问题，便得到原问题的对偶问题，如下： 
min w = 
m Xi=1 
biyi 
s.t.8>
<>
: 
m Xi=1 
aijyi . cj , j = 1, 2, · · · , n 
yi 自由, i = 1, 2, · · · ,m 
按照上述思路，可以写出任何线性规划模型所对应的对偶问题，如下例所示。 
例 3-3（对偶问题） 写出下面问题的对偶问题： 
max z = 5x1+6x2 
s.t.
8>
>>><>
>>>: 
3 x1.2 x2 = 7 
3 x1+ x2 . 8 
5 x1+6 x2 . 30 
x1, x2 . 0 
解 该问题中，第 1 个约束和第 3 个约束不符合前文的小于等于形式，因此我们先对 
约束条件进行等价变换，如下： 
max z = 5x1+6x2 
s.t.
8>
>>>>>><>
>>>>>>: 
3 x1.2 x2 . 7 . y′1 
.3 x1+2 x2 . .7 . y′′ 1 
3 x1+ x2 . 8 . y2 
.5 x1.6 x2 . .30. y′3 
x1, x2 . 0 
记各个约束条件对应的对偶变量分别为 y′1
、y′′ 1 、y2 和 y′3
，我们可以直接利用前面的 
对偶关系写出其对偶问题为
min w = 7y′1 
. 7y′′ 1 + 8y2 . 30y′3 
s.t.8>
><>
>: 
3 y′1 
. 3 y′′ 1 + 3 y2 . 5 y′3
. 5 
.2 y′1
+ 2 y′′ 1 + y2 . 6 y′3
. 6 
y′1
, y′′ 1 , y2,y′3
. 0 
进一步做变量替换，令 y1 = y′1 
. y′′ 1 ，y3 = .y′3
，则上述对偶问题变为 
79
min w = 7y1 + 8y2 + 30y3 
s.t.8>
><>
>: 
3 y1 + 3 y2 + 5 y3 . 5 
.2 y1 + y2 + 6 y3 . 6 
y1自由, y2 . 0, y3 . 0 
观察上述例子： 
·对偶变量 y1 对应于等式约束 3x1 . 2x2 = 7，它可正可负，是一个自由变量； 
·对偶变量 y3 对应于 . 型约束 5x1+6x2 . 30（该约束方向与标准资源配置型线性规 
划的约束方向相反），因此 y3 . 0。 
原问题与对偶问题之间的对应关系可以总结为表 3-3，今后利用该对应关系可以直接 
写出任何线性规划问题对应的对偶问题。 
表 3-3 
原问题（或对偶问题） 对偶问题（或原问题） 
目标函数 max z 
变量
..
........
....... 
n个 
. 0 
. 0 
无约束 
目标函数 min w 
n个 
. 0 
. 0 
= 
..........
....... 
约
束
条
件 
约
束
条
件
..
........
....... 
m个 
.
.
= 
m个 
. 0 
. 0 
无约束
..
........
....... 
变
量 
约束条件右端项 
目标函数变量的系数 
目标函数变量的系数 
约束条件右端项 
例 3-4（对偶问题） 请直接写出下述线性规划原问题的对偶问题 
min w = 2x1 + 3x2 . 5x3 + x4 
s.t.
8>
>>><>
>>>: 
x1+ x2 . 3 x3+ x4 . 5 . y1 
2 x1+ 2 x3. x4 . 4 . y2 
x2+ x3+ x4 = 6 . y3 
x1 .0, x2, x3 . 0, x4 无约束 
解 设对应于三个约束条件的对偶变量分别为 y1，y2，y3。由表 3-3 中原问题和对偶 
问题的对应关系，可以直接写出上述问题的对偶问题，即 
80
max z = 5y1 + 4y2 + 6y3 
s.t.
8>
>>>>>><>
>>>>>>: 
y1+ 2y2 . 2 
y1+ y3 . 3 
.3 y1+ 2y2+ y3 . .5 
y1. y2+ y3 = 1 
y1 .0, y2 .0, y3无约束 
3.2 对偶问题的基本性质 
例 3-1 和例 3-2 表明，对偶线性规划问题的最优目标函数值和原问题的最优目标函数 
值相等。本节我们探讨线性规划对偶问题的基本性质；先利用单纯形法求解线性规划模型 
(3-1) 及其对偶问题 (3-2)。 
线性规划模型 (3-1) 的标准型如下： 
max z = 80x1 + 100x2 
s.t.
8>
>>>>>><>
>>>>>>: 
8x1 + 4x2 + x3 = 360 
4x1 + 5x2 + x4 = 200 
3x1 + 10x2 + x5 = 250 
4x1 + 6x2 + x6 = 200 
x1, x2, · · · , x6 . 0 
其对应的单纯形表计算过程如下： 
因此，最优解为 (x.1
, x.2
, x.3
, x.4
, x.5
, x.6
) = (42.5, 5, 0, 5, 72.5, 0)，对应的最优目标函数 
值 z. = 3900。 
我们考虑其对偶问题： 
min w = 360y1 + 200y2 + 250y3 + 200y4 
s.t.8>><>>: 
8y1 + 4y2 + 3y3 + 4y4. 80 
4y1 + 5y2 + 10y3 + 6y4. 100 
y1, y2, y3, y4 . 0 
为了利用单纯形法求解，增加松弛变量 y5、y6 和人工变量 y7、y8，对偶问题改写为 
min w = 360y1 + 200y2 + 250y3 + 200y4 +My7 +My8 
s.t.8>
><>
>: 
8y1 + 4y2 + 3y3 + 4y4 . y5 + y7= 80 
4y1 + 5y2 + 10y3 + 6y4 . y6 + y8= 100 
y1, y2, · · · , y8 . 0 
其对应的单纯形表计算过程如下： 
因此，对偶问题的最优解为 (y.1, y.2, y.3, y.4, y.5, y.6) =(2.5, 0, 0, 15, 0, 0)，对应的最优目 
标函数值 w. = 3900。 
81
对比原问题和其对偶问题最终单纯形表，也不难发现一些对应关系，如表 3-4 与表 3-5 
所示。
表 3-4 
cj→ 80 100 0 0 0 0 
CB 基 b x1 x2 x3 x4 x5 x6 θi 
0 x3 360 8 4 1 0 0 0 90 
0 x4 200 4 5 0 1 0 0 40 
0 x5 250 3 [10] 0 0 1 0 25 
0 x6 200 4 6 0 0 0 1 33.33 
80 100 0 0 0 0 
0 x3 260 6.8 0 1 0 .0.4 0 38.24 
0 x4 75 2.5 0 0 1 .0.5 0 30.00 
100 x2 25 0.3 1 0 0 0.1 0 83.33 
0 x6 50 [2.2] 0 0 0 .0.6 1 22.73 
50 0 0 0 .10 0 
0 x3 105.4545 0 0 1 0 [1.4545] .3.0909 72.5 
0 x4 18.1818 0 0 0 1 0.1818 .1.1364 100 
100 x2 18.1818 0 1 0 0 0.1818 .0.1364 100 
80 x1 22.7273 1 0 0 0 .0.2727 0.4545 
0 0 0 0 3.6364 .22.7273 
0 x5 72.5 0 0 0.6875 0 1 .2.125 
0 x4 5 0 0 .0.125 1 0 .0.75 
100 x2 5 0 1 .0.125 0 0 0.25 
80 x1 42.5 1 0 0.1875 0 0 .0.125 
0 0 .2.5 0 0 .15 
表 3-5 
cj→ 360 200 250 200 0 0 M M 
CB 基 b y1 y2 y3 y4 y5 y6 y7 y8 θi 
M y7 80 8 4 3 4 .1 0 1 0 80/3 
M y8 100 4 5 [10] 6 0 .1 0 1 10 
360.12M 200.9M 250.13M 200.10M M M 0 0 
M y7 50 [6.8] 2.5 0 2.2 .1 0.3 1 .0.3 7.353 
250 y3 10 0.4 0.5 1 0.6 0 .0.1 0 0.1 25 
260.6.8M 75.2.5M 0 50.2.2M M 25.0.3M 0 1.3M.25 
360 y1 7.353 1.000 0.368 0.000 0.324 .0.147 0.044 0.147 .0.044 22.727 
250 y3 7.059 0.000 0.353 1.000 [0.471] 0.059 .0.118 .0.059 0.118 15.000 
0 .20.588 0 .34.118 38.235 13.529 
360 y1 2.5 1 0.125 .0.6875 0 .0.1875 0.125 
200 y4 15 0 0.75 2.125 1 0.125 .0.25 
0 5 72.5 0 42.5 5 
82