2.1单纯形法的矩阵描述
一, 为什麽要研究单纯形法的矩阵描述？
&进一步讨论修正单纯形法
&便于理论推导 （ 如对偶定理的证明 ）
二, 怎样进行矩阵描述？
关键 —— 写出两个基本的表达式 。
第二章 线性规划的进一步研究
1,准备工作：
（ 1）标准型的矩阵形式 ——
?
?
?
?
?
?
0
..
X
bAX
ts
CXM a x Z
（ 2）将式中矩阵写成分块矩阵形式
)( NB CCC ?? )( NB XXX ??
)(),,,( 21 NBPPPA n ??
?
??
2,将分块形式代入 矩阵形式标准
型, 得出两个基本表达式：
（ 1）由约束条件
bNXBX
X
X
NBAX NB
N
B
???
?
?
?
?
?
?
?
?
?
?
? ?? )(
可得 用非基变量表示基变量的表达式：
NNB NXBbBNXbBX
111 )( ??? ????
（ 2-1）
）（
得令
22
)(
)(
)(
1
111
11
11
???
?????
???
???
??
?
?
?
?
?
?
?
?
?
?
??
?
???
??
??
NNB
BNNNBNB
NNNBB
NNNB
NNBB
N
B
NB
XbBCZ
NBCCXNBCCbBC
XCNXBCbBC
XCNXBbBC
XCXC
X
X
CCCXZ
?
?
??
（ 2） 将式 （ 2-1） 代入目标函数的表
达式, 可得：
用非基变量表示目标函数的表达式：
（ 3） 借助一个恒等式推出用非基变量表
示目标函数的另一个等价表达式：
0)( 1 ?? ? BBB XBBCC 01 ?? ? BBBB BXBCXC
代入式（ 2-2），并令 1?? BC
B?
XACb
BXBCXCXNBCCbBCZ BBBBNBNB
)(
)( 111
?? ???
????? ??? （ 2-4）
单纯形乘子
三、单纯形表格的矩阵形式：
cj
j?
TBX T
NX
TBC BX bB 1? BB 1? NB 1?
Z? bBC B 1?? NBCC BN 1??
CB XB
xj
b
CB CN
0
一、对偶问题的提出
1,对偶思想举例
周长一定的矩形中, 以正方形面积
最大；面积一定的矩形中, 以正方形
周长最小；
2,2 对偶原理
2,换个角度审视生产计划问题
?
?
?
?
?
?
???
???
???
0,,
974
3
..
332
321
321
321
321
xxx
xxx
xxx
ts
xxxM a x Z
例 2-1要求制定一个生产计划方案，在劳动
力和原材料可能供应的范围内，使得产品
的总利润最大 。
它的 对偶问题 就是一个 价格系统,
使 在平衡了劳动力和原材料的直接成本
后, 所确定的 价格系统最具有竞争力：
?
?
?
?
?
?
?
?
??
??
??
??
0,
37
34
2
..
93
21
21
21
21
21
yy
yy
yy
yy
ts
yyM in W
（ 用于生产第 i种产品的资
源转让收益不小于生产该
种产品时获得的利润 ）
对偶变量的经济意义可以解释为对工时
及原材料的单位定价 ；
若工厂自己不生产产品 A,B和 C,将现
有的工时及原材料转而接受外来加工时，
那么 上述的价格系统能保证不亏本又最富
有竞争力 （包工及原材料的总价格最低）
当原问题和对偶问题都取得最优解时，这
一对线性规划对应的目标函数值是相等的：
Zmax=Wmin=8
考察原问题和对偶问题的解，给作决
策的管理者另一个自由度；
?怎样通过增加更多的资源来增加利润？
?怎样使用不同类型的资源来增加利润？
3、饮食与营养问题
例 2-2 采购甲、乙、丙、丁 4种食品量分别
为 x1,x2,x3,x4,在保证人体所需维生素
A,B,C前提下，使总的花费最小。
?
?
?
?
?
?
?
?
???
????
????
????
0,,,
)(30305.75.17
13.068.027.06.0
)(40003250175015001000
..
5.19.05.08.0
4321
421
4321
4321
4321
xxxx
Cxxx
Bxxxx
Axxxx
ts
xxxxMin Z
毫克维生素
）（毫克维生素
国际单位维生素
构建的 线性规划模型：
换一个角度，生产营养药丸的制药公司力图
使营养师相信，各种营养药丸勿须通过多种食
品的转换就能供营养师调剂。
制药公司面对的问题是 为营养药丸
确定单价,以 获得最大的收益,同
时 与真正的食品竞争 。
于是，营养药丸的单位成本 不能超过
相应食品的市价。
?
?
?
?
??
?
?
?
?
????
????
????
????
???
0,,
)(5.1303.03 2 5 0
)(9.0068.01 7 5 0
)(5.05.727.01 5 0 0
)(8.05.176.01 0 0 0
..
304 0 0 0
321
321
321
321
321
321
yyy
IVyyy
IIIyyy
IIyyy
Iyyy
ts
yyyM a x W
丁食品市价的成本合成药丸
丙食品市价的成本合成药丸
乙食品市价的成本合成药丸
甲食品市价的成本合成药丸
由此得到下面的对偶问题：
二, 原问题和对偶问题的关系
1,对称形式的对偶关系
（ 1）定义：若原问题是
?
?
?
?
?
?
?
?
?
?
????
????
????
????
0,,,
..
21
2211
22222112
11212111
2211
n
mnmnmm
nn
nn
nn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
ts
xcxcxcM a x Z
?
?
???
?
?
?
则定义其对偶问题为
?
?
?
?
?
?
?
?
?
?
????
????
????
????
0,,,
..
21
2211
22222112
11221111
2211
m
nnmnnn
nm
mm
mm
yyy
cyayaya
cyayaya
cyayaya
ts
ybybybM i n W
?
?
???
?
?
?
这两个式子之间的变换关系称为
,对称形式的对偶关系, 。
（ 2） 对称形式的对偶关系的矩阵描述
?
?
?
?
?
?
0
..
Y
CYA
ts
bYM in W
（ D）
?
?
?
?
?
?
0
..
X
bAX
ts
CXM a x Z
（ L）
（ 3） 怎样从原始问题写出其对偶问题？
? 按照定义； ?记忆法则：
,上, 下, 交换,, 左, 右, 换位,
不等式变号,, 极大, 变, 极小,
例 2-3 写出下面线性规划的对偶问题：
?
?
?
?
?
?
??
??
??
0,
1025
1543
..
2
21
21
21
21
xx
xx
xx
ts
xxM a x Z
?
?
?
?
?
?
??
??
??
0,
124
253
..
1015
21
21
21
21
yy
yy
yy
ts
yyM in W
2,非对称形式的对偶关系：
?
?
?
?
?
??
??
?
?
?
?
?
njx
mibxa
ts
xcM a x Z
j
n
j
ijij
n
j
jj
,,2,10
,,2,1
..
1
1
?
?
?
?
?
?
?
?
??
?
?
?
?
?
miy
njcya
ts
xbM in W
i
m
i
jiij
m
i
ii
,,2,1
,,2,1
..
1
1
?
?
符号不限，
（ 1） 原问题 对偶问题
（ 特点：对偶变量
符号 不限, 系数阵
转置 ）
(特点：等式约束 )
（ 2） 怎样写出非对称形式的对偶问题？
?把一个等式约束写成两个不等式约束,
再根据对称形式的对偶关系定义写出；
?按照原始 -对偶表直接写出 ；
（ 3） 原始 -对偶表
原问题（或对偶问题） 对偶问题（或原问题）
目标函数 MaxZ 目标函数 MinW
约束条件数,m个
第 i个约束条件类型为, ≤”
第 i个约束条件类型为, ≥”
第 i个约束条件类型为,=”
对偶变量数,m个
第 i个变量 ≥0
第 i个变量 ≤0
第 i个变量是自由变量
决策变量数,n个
第 j个变量 ≥0
第 j个变量 ≤0
第 j个变量是自由变量
约束条件数,n
第 i个约束条件类型为, ≥”
第 i个约束条件类型为, ≤”
第 i个约束条件类型为,=”
课堂练习：写出下面线性规划的对偶规划：
?
?
?
?
?
?
?
??
??
???
???
???
0,,0
141312
111098
7654
..
324
321
21
321
321
321
xxx
xx
xxx
xxx
ts
xxxM i n Z
符号不限
下面的答案哪一个是正确的？为什麽？
?
?
?
?
?
?
?
??
???
???
???
???
0,0,
3106
21395
41284
..
14117
321
21
321
321
321
yyy
yy
yyy
yyy
ts
yyyM a x W
符号不限 ?
?
?
?
?
?
?
??
???
???
???
???
0,0,
3106
21395
41284
..
14117
321
21
321
321
321
yyy
yy
yyy
yyy
ts
yyyM a x W
符号不限
（ 原问题是极小化问题, 因此 应从原始对偶
表的 右边 往 左边 查 ！ ）
√ ×
三, 对偶定理
对偶定理是揭示
原始问题的解与对偶问题的解之间重
要关系 的
一系列定理 。
定理 2-1 对称性定理 ——
对偶问题的对偶是原问题 。
定理 2-2 弱对偶定理 —— 若一对对称形
式的对偶线性规划
?
?
?
?
?
?
0
..
X
bAX
ts
CXM a x Z
（ L）
?
?
?
?
?
?
0
..
Y
CYA
ts
bYM in W
和 （ D）
均有可行解, 分别为 和, 则 C ≤ b。X~ X~Y~ Y~
证
明
思
路
：
由（ L） bXA ?~ 左乘,得 bYXAY ~~~ ?Y~
由（ D） CAY ?~ 右乘,得X~ XCXAY ~~~ ?
bYXC ~~ ?
该结论对非对称形式的对偶问题同样成立 。
（ 教材上的证明,对一般情况, 分三类 并 用
简缩形式 加以证明 ）
由该定理可以得到什麽附带结果？
? 关于, 界, 的结果；
问：
极小化问题有下界 ——
推论 1 极大化问题的任意一个可行解所对应的
目标函数值是其对偶问题最优目标函数值的一
个下界 。
?极大化问题有上界 ——
推论 2 极小化问题的任意一个可行解所对
应的目标函数值是其对偶问题最优目标函
数值的一个上界。
?关于最优解无界情况与对偶问题的关系；
原始问题可行, 则 目标函数值上无界
<==>对偶问题不可行 ——
对偶问题可行, 则目标函数值下无界
<==>原始问题不可行 ——
推论 4 若对偶问题可行, 则其目标函数
无界的充要条件是原始问题没有可行解 。
推论 3 若原始问题可行，则其目标函数
无界的充要条件是对偶问题没有可行解。
定理 2-3 最优性准则定理 若, 分
别为对称形式对偶线性规划的可行解，
且两者目标函数的相应值相等，即
C =b, 则, 分别为原始问题
和对偶问题的最优解。
X~
X~X~
Y~
Y~Y~
C = bY~X~
CX≤ Yb
弱对偶
定 理
已 知
结论
最优解定义X=
X~
CX≤ bY~Y=
Y~
特别取
b≤ YbY~
CX≤C X~
C ≤ YbX~
证明思路
定理 2-4 主对偶定理 若原始问题和对
偶问题两者均可行，则两者均有最优
解，且此时目标函数值相同。
证明要点：
第一部分 —— 证明两者均有最优解 。
由于原始问题和对偶问题 均可行,根据弱对
偶定理知两者 均有界,于是 均有最优解 。
第二部分 —— 证明在达到最优时, 两个
问题的目标函数值相等 。
证明思路：利用单纯形法的特征, 就 非
对称形式的对偶问题 给出
第一步：给出原始问题形式和对偶问题形式；
?
?
? ?
?
的符号无限制Y
CYA
ts
YbM in W
..
(D)
?
?
?
?
?
?
0
..
X
bAX
ts
CXM a x Z
(L)
NB CNBC ??
? 1
设原始问题有对应于最优基 B的最优基本
可行解 X=（ XB,0） T,则有 XB=B-1b。
第二步：利用单纯形法的矩阵描述, 由单纯形
法最优性判别定理得出重要结论,
并引出, 单纯形乘子, 的定义 ；
NNB CBBC ?? 1
1?? BC B?
令 A=（ B,N）,所以对应于最优基 B的检
验数满足
01 ??? ? NBCC BNN?
（最优单纯形乘子）1?? BC B?定义
第四步：进一步证明 是对偶问题的最优解，并
验证两个问题的目标函数值相等。
?
第三步：证明最优单纯形乘子就是对偶问题的
可行解；
CCCNBCCNBA NBBB ???? ? ),(),(),( 1???
所以,是对偶问题的可行解。?
CXXCbBCb BBB ??? ? 1?又
根据最优性准则定理, 这时的 正是对偶问
题的最优解 。
?
四、对偶最优解（影子价格）
的经济含义
1,对偶最优解的经济解释
讨论例 1-1的图解法时, 提出了它的对
偶规划, 并用图解法求出了最优解 。 同时
提到, 影子价格,, 确切的定义是,一个
线性规划对偶问题的最优解 （ 简称为, 对
偶最优解, ） 。 在经济上可以解释 为 约束
条件所付出的代价 。
回忆例 1-1及其对偶规划的求解结果,
当 原问题和对偶问题都取得最优解时, 这
一对线性规划对应的目标函数值相等, 即
有 Zmax=CX*=2x*1+3x*2
=Wmin=y*b=y*1+3y*2=8
其中 X*是原问题的最优解, y*是对偶问
题最优解 。
即有
X*=(x1,x2)T=(1,2)T，
Y*=(y1,y2)=(5,1)
若原材料供应量能增加一个单位, 即右端常
数向量 b=(b1,b2)T=(1,3)T中的 b2从 3个单位
增加到 4个单位, 则目标函数值的变化量为
（ y*1+4y*2)-(y*1+3y*2)=y*2=1
说明 目标函数值增加一个单位,
这就是 放宽 一个约束条件所产生的
附加贡献 。
就是说, 影子价格 确定了 为得到
一个附加单位的约束因素所应花费
的 成本上限 。
2,在单纯形表中如何观察到对偶最优解？
例 1-1扩展为案例 1（增加一个变量）
后，用单纯形法求解得到最终表：
Basis c(j) x1 x2 x3 s1 s2 B(i) B(i)/A(i,j)
2.000 3.000 1.000 0 0
x1 2.000 1.000 0 -1 4.000 -1.00 1.000 0
x2 3.000 0 1.000 2.000 -1.000 1.000 2.000 0
C(j)-Z(j)
*BigM
0
0
0
0
-3.000
0
-5.000
0
-1.00
0
8.001
0
(Max.)Optimal OBJ value = 8.006
原问题 的 最优解 和 目标函数最优值,
X*=(x1*,x2*,x3*,s1*,s2*)Τ
=(1.000,2.000,0,0,0)T
Zmax=8.001
从 检验数行 可得 对偶问题的最优解 和 目标函
数最优值 ——
将 所有非基变量的检验数变号, 得到,
Y*=(y*1,y*2,s1,s2,s3)T
=(5.00,1.00,0,0,3.00)T
Wmin=8.001
原问题两个 约束条件 对应 对偶问题两个变量 。
表中 S1,S2分别表示两个约束条件中的剩余资
源量, 其检验数的相反数就是对应的两个对偶
变量, Y*1=5.00,Y*2=1.00，
x1,x2,x3 检验数的相反数 分别对应着 对偶
问题 中三个 约束条件的剩余变量,
即 s1=0,s2=0,s3=3.00。
3,Y*的各分量与 X*的对应关系
因为 s3是 X3对应的检验数的相反数，则 X3
对应的检验数是 -3！
4,进一步的分析
y*1=5.00表示如果 总工时比例增加 1
个单位 （ 即总工时翻一番 ）, 则 产品总利
润将增加 5千元, y*2=1.00则表明 若原材
料增加 1吨, 产品总利润将增加 1千元 。
而 （ 对偶 问题 约束 3的剩 余变 量 ）
s3=3.00则说明 如果生产一个单位的产品 C，
将使 产品总利润 下降 3千元 。 为什麽？
劳动工时 ！
因为它的变化对产品总利润的影响最
大, 因此 劳动力 是 最关键的生产环节,
若能采取有力措施增加劳动总工时, 则
产品总利润将得到较大的提高 。
在计算机求解结果中将约束条件的影
子价格和变量的机会成本统称为 机会成
本 （ opportunity cost）。
当前最敏感的资源是什麽？
求解结果总表
Summarized Resulted for Case1
Variables
No,Names
Opportuni
ty Cost
Variables
No.Names Opportunity CostSolution Solution
1 x1 1.0003 0.0000 4 s1 0.0000 5.0006
2 x2 2.0000 0.0000 5 s2 0.0000 1.0000
3 x3 0.0000 3.0000
Maximum Value of the OBJ = 8.0006 Iters.=2
综上, 影子价格 是灵敏度分析的一
种形式, 它 通过 获取 一个单位 的追
加的产品因素, 去 测量 放宽一个约
束条件的价值, 比较 追加资源的价
值和资源的实际成本, 就能比较有
把握地作出各种可行的决策 。
课后小组讨论 3
（ 可以作为小组小实践选题 ）
适当查阅参考书, 讨论总结对偶定理
的应用 。
参考练习,1,考察原始线性规划：
?
?
?
?
?
?
????
????
????
0,,,
20232
20322
..
432
4321
4221
3321
4321
xxxx
xxxx
xxxx
ts
xxxxM a x Z
写出其对偶问题，然后讨论：
如果知道是原问题的可行解（用什麽办法可
以较方便地寻找一个可行解？），能否对对偶
问题的目标函数值做出估计？
以此为启发，能否对原问题目标函数值作出
估计？
2、下面的问题是某线性规划的对偶问题，请
写出其原始问题。
可以观察到 是原始问题的可行
解 。 不要使用单纯形法求解, 能否说明原
始问题最优解无界？
?
?
?
?
?
?
?
?
??
??
???
??
0,
1
1
12
..
2
21
21
21
21
21
yy
yy
yy
yy
ts
yyM i n W
TX )0,0,0(~ ?
一, 为什麽要研究单纯形法的矩阵描述？
&进一步讨论修正单纯形法
&便于理论推导 （ 如对偶定理的证明 ）
二, 怎样进行矩阵描述？
关键 —— 写出两个基本的表达式 。
第二章 线性规划的进一步研究
1,准备工作：
（ 1）标准型的矩阵形式 ——
?
?
?
?
?
?
0
..
X
bAX
ts
CXM a x Z
（ 2）将式中矩阵写成分块矩阵形式
)( NB CCC ?? )( NB XXX ??
)(),,,( 21 NBPPPA n ??
?
??
2,将分块形式代入 矩阵形式标准
型, 得出两个基本表达式：
（ 1）由约束条件
bNXBX
X
X
NBAX NB
N
B
???
?
?
?
?
?
?
?
?
?
?
? ?? )(
可得 用非基变量表示基变量的表达式：
NNB NXBbBNXbBX
111 )( ??? ????
（ 2-1）
）（
得令
22
)(
)(
)(
1
111
11
11
???
?????
???
???
??
?
?
?
?
?
?
?
?
?
?
??
?
???
??
??
NNB
BNNNBNB
NNNBB
NNNB
NNBB
N
B
NB
XbBCZ
NBCCXNBCCbBC
XCNXBCbBC
XCNXBbBC
XCXC
X
X
CCCXZ
?
?
??
（ 2） 将式 （ 2-1） 代入目标函数的表
达式, 可得：
用非基变量表示目标函数的表达式：
（ 3） 借助一个恒等式推出用非基变量表
示目标函数的另一个等价表达式：
0)( 1 ?? ? BBB XBBCC 01 ?? ? BBBB BXBCXC
代入式（ 2-2），并令 1?? BC
B?
XACb
BXBCXCXNBCCbBCZ BBBBNBNB
)(
)( 111
?? ???
????? ??? （ 2-4）
单纯形乘子
三、单纯形表格的矩阵形式：
cj
j?
TBX T
NX
TBC BX bB 1? BB 1? NB 1?
Z? bBC B 1?? NBCC BN 1??
CB XB
xj
b
CB CN
0
一、对偶问题的提出
1,对偶思想举例
周长一定的矩形中, 以正方形面积
最大；面积一定的矩形中, 以正方形
周长最小；
2,2 对偶原理
2,换个角度审视生产计划问题
?
?
?
?
?
?
???
???
???
0,,
974
3
..
332
321
321
321
321
xxx
xxx
xxx
ts
xxxM a x Z
例 2-1要求制定一个生产计划方案，在劳动
力和原材料可能供应的范围内，使得产品
的总利润最大 。
它的 对偶问题 就是一个 价格系统,
使 在平衡了劳动力和原材料的直接成本
后, 所确定的 价格系统最具有竞争力：
?
?
?
?
?
?
?
?
??
??
??
??
0,
37
34
2
..
93
21
21
21
21
21
yy
yy
yy
yy
ts
yyM in W
（ 用于生产第 i种产品的资
源转让收益不小于生产该
种产品时获得的利润 ）
对偶变量的经济意义可以解释为对工时
及原材料的单位定价 ；
若工厂自己不生产产品 A,B和 C,将现
有的工时及原材料转而接受外来加工时，
那么 上述的价格系统能保证不亏本又最富
有竞争力 （包工及原材料的总价格最低）
当原问题和对偶问题都取得最优解时，这
一对线性规划对应的目标函数值是相等的：
Zmax=Wmin=8
考察原问题和对偶问题的解，给作决
策的管理者另一个自由度；
?怎样通过增加更多的资源来增加利润？
?怎样使用不同类型的资源来增加利润？
3、饮食与营养问题
例 2-2 采购甲、乙、丙、丁 4种食品量分别
为 x1,x2,x3,x4,在保证人体所需维生素
A,B,C前提下，使总的花费最小。
?
?
?
?
?
?
?
?
???
????
????
????
0,,,
)(30305.75.17
13.068.027.06.0
)(40003250175015001000
..
5.19.05.08.0
4321
421
4321
4321
4321
xxxx
Cxxx
Bxxxx
Axxxx
ts
xxxxMin Z
毫克维生素
）（毫克维生素
国际单位维生素
构建的 线性规划模型：
换一个角度，生产营养药丸的制药公司力图
使营养师相信，各种营养药丸勿须通过多种食
品的转换就能供营养师调剂。
制药公司面对的问题是 为营养药丸
确定单价,以 获得最大的收益,同
时 与真正的食品竞争 。
于是，营养药丸的单位成本 不能超过
相应食品的市价。
?
?
?
?
??
?
?
?
?
????
????
????
????
???
0,,
)(5.1303.03 2 5 0
)(9.0068.01 7 5 0
)(5.05.727.01 5 0 0
)(8.05.176.01 0 0 0
..
304 0 0 0
321
321
321
321
321
321
yyy
IVyyy
IIIyyy
IIyyy
Iyyy
ts
yyyM a x W
丁食品市价的成本合成药丸
丙食品市价的成本合成药丸
乙食品市价的成本合成药丸
甲食品市价的成本合成药丸
由此得到下面的对偶问题：
二, 原问题和对偶问题的关系
1,对称形式的对偶关系
（ 1）定义：若原问题是
?
?
?
?
?
?
?
?
?
?
????
????
????
????
0,,,
..
21
2211
22222112
11212111
2211
n
mnmnmm
nn
nn
nn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
ts
xcxcxcM a x Z
?
?
???
?
?
?
则定义其对偶问题为
?
?
?
?
?
?
?
?
?
?
????
????
????
????
0,,,
..
21
2211
22222112
11221111
2211
m
nnmnnn
nm
mm
mm
yyy
cyayaya
cyayaya
cyayaya
ts
ybybybM i n W
?
?
???
?
?
?
这两个式子之间的变换关系称为
,对称形式的对偶关系, 。
（ 2） 对称形式的对偶关系的矩阵描述
?
?
?
?
?
?
0
..
Y
CYA
ts
bYM in W
（ D）
?
?
?
?
?
?
0
..
X
bAX
ts
CXM a x Z
（ L）
（ 3） 怎样从原始问题写出其对偶问题？
? 按照定义； ?记忆法则：
,上, 下, 交换,, 左, 右, 换位,
不等式变号,, 极大, 变, 极小,
例 2-3 写出下面线性规划的对偶问题：
?
?
?
?
?
?
??
??
??
0,
1025
1543
..
2
21
21
21
21
xx
xx
xx
ts
xxM a x Z
?
?
?
?
?
?
??
??
??
0,
124
253
..
1015
21
21
21
21
yy
yy
yy
ts
yyM in W
2,非对称形式的对偶关系：
?
?
?
?
?
??
??
?
?
?
?
?
njx
mibxa
ts
xcM a x Z
j
n
j
ijij
n
j
jj
,,2,10
,,2,1
..
1
1
?
?
?
?
?
?
?
?
??
?
?
?
?
?
miy
njcya
ts
xbM in W
i
m
i
jiij
m
i
ii
,,2,1
,,2,1
..
1
1
?
?
符号不限，
（ 1） 原问题 对偶问题
（ 特点：对偶变量
符号 不限, 系数阵
转置 ）
(特点：等式约束 )
（ 2） 怎样写出非对称形式的对偶问题？
?把一个等式约束写成两个不等式约束,
再根据对称形式的对偶关系定义写出；
?按照原始 -对偶表直接写出 ；
（ 3） 原始 -对偶表
原问题（或对偶问题） 对偶问题（或原问题）
目标函数 MaxZ 目标函数 MinW
约束条件数,m个
第 i个约束条件类型为, ≤”
第 i个约束条件类型为, ≥”
第 i个约束条件类型为,=”
对偶变量数,m个
第 i个变量 ≥0
第 i个变量 ≤0
第 i个变量是自由变量
决策变量数,n个
第 j个变量 ≥0
第 j个变量 ≤0
第 j个变量是自由变量
约束条件数,n
第 i个约束条件类型为, ≥”
第 i个约束条件类型为, ≤”
第 i个约束条件类型为,=”
课堂练习：写出下面线性规划的对偶规划：
?
?
?
?
?
?
?
??
??
???
???
???
0,,0
141312
111098
7654
..
324
321
21
321
321
321
xxx
xx
xxx
xxx
ts
xxxM i n Z
符号不限
下面的答案哪一个是正确的？为什麽？
?
?
?
?
?
?
?
??
???
???
???
???
0,0,
3106
21395
41284
..
14117
321
21
321
321
321
yyy
yy
yyy
yyy
ts
yyyM a x W
符号不限 ?
?
?
?
?
?
?
??
???
???
???
???
0,0,
3106
21395
41284
..
14117
321
21
321
321
321
yyy
yy
yyy
yyy
ts
yyyM a x W
符号不限
（ 原问题是极小化问题, 因此 应从原始对偶
表的 右边 往 左边 查 ！ ）
√ ×
三, 对偶定理
对偶定理是揭示
原始问题的解与对偶问题的解之间重
要关系 的
一系列定理 。
定理 2-1 对称性定理 ——
对偶问题的对偶是原问题 。
定理 2-2 弱对偶定理 —— 若一对对称形
式的对偶线性规划
?
?
?
?
?
?
0
..
X
bAX
ts
CXM a x Z
（ L）
?
?
?
?
?
?
0
..
Y
CYA
ts
bYM in W
和 （ D）
均有可行解, 分别为 和, 则 C ≤ b。X~ X~Y~ Y~
证
明
思
路
：
由（ L） bXA ?~ 左乘,得 bYXAY ~~~ ?Y~
由（ D） CAY ?~ 右乘,得X~ XCXAY ~~~ ?
bYXC ~~ ?
该结论对非对称形式的对偶问题同样成立 。
（ 教材上的证明,对一般情况, 分三类 并 用
简缩形式 加以证明 ）
由该定理可以得到什麽附带结果？
? 关于, 界, 的结果；
问：
极小化问题有下界 ——
推论 1 极大化问题的任意一个可行解所对应的
目标函数值是其对偶问题最优目标函数值的一
个下界 。
?极大化问题有上界 ——
推论 2 极小化问题的任意一个可行解所对
应的目标函数值是其对偶问题最优目标函
数值的一个上界。
?关于最优解无界情况与对偶问题的关系；
原始问题可行, 则 目标函数值上无界
<==>对偶问题不可行 ——
对偶问题可行, 则目标函数值下无界
<==>原始问题不可行 ——
推论 4 若对偶问题可行, 则其目标函数
无界的充要条件是原始问题没有可行解 。
推论 3 若原始问题可行，则其目标函数
无界的充要条件是对偶问题没有可行解。
定理 2-3 最优性准则定理 若, 分
别为对称形式对偶线性规划的可行解，
且两者目标函数的相应值相等，即
C =b, 则, 分别为原始问题
和对偶问题的最优解。
X~
X~X~
Y~
Y~Y~
C = bY~X~
CX≤ Yb
弱对偶
定 理
已 知
结论
最优解定义X=
X~
CX≤ bY~Y=
Y~
特别取
b≤ YbY~
CX≤C X~
C ≤ YbX~
证明思路
定理 2-4 主对偶定理 若原始问题和对
偶问题两者均可行，则两者均有最优
解，且此时目标函数值相同。
证明要点：
第一部分 —— 证明两者均有最优解 。
由于原始问题和对偶问题 均可行,根据弱对
偶定理知两者 均有界,于是 均有最优解 。
第二部分 —— 证明在达到最优时, 两个
问题的目标函数值相等 。
证明思路：利用单纯形法的特征, 就 非
对称形式的对偶问题 给出
第一步：给出原始问题形式和对偶问题形式；
?
?
? ?
?
的符号无限制Y
CYA
ts
YbM in W
..
(D)
?
?
?
?
?
?
0
..
X
bAX
ts
CXM a x Z
(L)
NB CNBC ??
? 1
设原始问题有对应于最优基 B的最优基本
可行解 X=（ XB,0） T,则有 XB=B-1b。
第二步：利用单纯形法的矩阵描述, 由单纯形
法最优性判别定理得出重要结论,
并引出, 单纯形乘子, 的定义 ；
NNB CBBC ?? 1
1?? BC B?
令 A=（ B,N）,所以对应于最优基 B的检
验数满足
01 ??? ? NBCC BNN?
（最优单纯形乘子）1?? BC B?定义
第四步：进一步证明 是对偶问题的最优解，并
验证两个问题的目标函数值相等。
?
第三步：证明最优单纯形乘子就是对偶问题的
可行解；
CCCNBCCNBA NBBB ???? ? ),(),(),( 1???
所以,是对偶问题的可行解。?
CXXCbBCb BBB ??? ? 1?又
根据最优性准则定理, 这时的 正是对偶问
题的最优解 。
?
四、对偶最优解（影子价格）
的经济含义
1,对偶最优解的经济解释
讨论例 1-1的图解法时, 提出了它的对
偶规划, 并用图解法求出了最优解 。 同时
提到, 影子价格,, 确切的定义是,一个
线性规划对偶问题的最优解 （ 简称为, 对
偶最优解, ） 。 在经济上可以解释 为 约束
条件所付出的代价 。
回忆例 1-1及其对偶规划的求解结果,
当 原问题和对偶问题都取得最优解时, 这
一对线性规划对应的目标函数值相等, 即
有 Zmax=CX*=2x*1+3x*2
=Wmin=y*b=y*1+3y*2=8
其中 X*是原问题的最优解, y*是对偶问
题最优解 。
即有
X*=(x1,x2)T=(1,2)T，
Y*=(y1,y2)=(5,1)
若原材料供应量能增加一个单位, 即右端常
数向量 b=(b1,b2)T=(1,3)T中的 b2从 3个单位
增加到 4个单位, 则目标函数值的变化量为
（ y*1+4y*2)-(y*1+3y*2)=y*2=1
说明 目标函数值增加一个单位,
这就是 放宽 一个约束条件所产生的
附加贡献 。
就是说, 影子价格 确定了 为得到
一个附加单位的约束因素所应花费
的 成本上限 。
2,在单纯形表中如何观察到对偶最优解？
例 1-1扩展为案例 1（增加一个变量）
后，用单纯形法求解得到最终表：
Basis c(j) x1 x2 x3 s1 s2 B(i) B(i)/A(i,j)
2.000 3.000 1.000 0 0
x1 2.000 1.000 0 -1 4.000 -1.00 1.000 0
x2 3.000 0 1.000 2.000 -1.000 1.000 2.000 0
C(j)-Z(j)
*BigM
0
0
0
0
-3.000
0
-5.000
0
-1.00
0
8.001
0
(Max.)Optimal OBJ value = 8.006
原问题 的 最优解 和 目标函数最优值,
X*=(x1*,x2*,x3*,s1*,s2*)Τ
=(1.000,2.000,0,0,0)T
Zmax=8.001
从 检验数行 可得 对偶问题的最优解 和 目标函
数最优值 ——
将 所有非基变量的检验数变号, 得到,
Y*=(y*1,y*2,s1,s2,s3)T
=(5.00,1.00,0,0,3.00)T
Wmin=8.001
原问题两个 约束条件 对应 对偶问题两个变量 。
表中 S1,S2分别表示两个约束条件中的剩余资
源量, 其检验数的相反数就是对应的两个对偶
变量, Y*1=5.00,Y*2=1.00，
x1,x2,x3 检验数的相反数 分别对应着 对偶
问题 中三个 约束条件的剩余变量,
即 s1=0,s2=0,s3=3.00。
3,Y*的各分量与 X*的对应关系
因为 s3是 X3对应的检验数的相反数，则 X3
对应的检验数是 -3！
4,进一步的分析
y*1=5.00表示如果 总工时比例增加 1
个单位 （ 即总工时翻一番 ）, 则 产品总利
润将增加 5千元, y*2=1.00则表明 若原材
料增加 1吨, 产品总利润将增加 1千元 。
而 （ 对偶 问题 约束 3的剩 余变 量 ）
s3=3.00则说明 如果生产一个单位的产品 C，
将使 产品总利润 下降 3千元 。 为什麽？
劳动工时 ！
因为它的变化对产品总利润的影响最
大, 因此 劳动力 是 最关键的生产环节,
若能采取有力措施增加劳动总工时, 则
产品总利润将得到较大的提高 。
在计算机求解结果中将约束条件的影
子价格和变量的机会成本统称为 机会成
本 （ opportunity cost）。
当前最敏感的资源是什麽？
求解结果总表
Summarized Resulted for Case1
Variables
No,Names
Opportuni
ty Cost
Variables
No.Names Opportunity CostSolution Solution
1 x1 1.0003 0.0000 4 s1 0.0000 5.0006
2 x2 2.0000 0.0000 5 s2 0.0000 1.0000
3 x3 0.0000 3.0000
Maximum Value of the OBJ = 8.0006 Iters.=2
综上, 影子价格 是灵敏度分析的一
种形式, 它 通过 获取 一个单位 的追
加的产品因素, 去 测量 放宽一个约
束条件的价值, 比较 追加资源的价
值和资源的实际成本, 就能比较有
把握地作出各种可行的决策 。
课后小组讨论 3
（ 可以作为小组小实践选题 ）
适当查阅参考书, 讨论总结对偶定理
的应用 。
参考练习,1,考察原始线性规划：
?
?
?
?
?
?
????
????
????
0,,,
20232
20322
..
432
4321
4221
3321
4321
xxxx
xxxx
xxxx
ts
xxxxM a x Z
写出其对偶问题，然后讨论：
如果知道是原问题的可行解（用什麽办法可
以较方便地寻找一个可行解？），能否对对偶
问题的目标函数值做出估计？
以此为启发，能否对原问题目标函数值作出
估计？
2、下面的问题是某线性规划的对偶问题，请
写出其原始问题。
可以观察到 是原始问题的可行
解 。 不要使用单纯形法求解, 能否说明原
始问题最优解无界？
?
?
?
?
?
?
?
?
??
??
???
??
0,
1
1
12
..
2
21
21
21
21
21
yy
yy
yy
yy
ts
yyM i n W
TX )0,0,0(~ ?
