2006/3
--第 2章 对偶问题 --
--1--
2006/3
--第 2章 对偶问题 --
--2--
第 2 章 线性规划的对偶理论
Duality 对偶
Dual Problem 对偶问题
Dual Linear Programming
对偶线性规划
Dual Theory 对偶理论
2006/3
--第 2章 对偶问题 --
--3--
2.1 问题的提出
例：某企业计划生产甲、乙两种产品，该两种产品均需要 A,B,C、
D 四种不同的材料，按工艺资料规定，生产一单位甲乙产品需要各
种材料数量及单位产品利润如表中所示。问,如何安排产品的生产计
划,才能使企业获利最大?
设备
产品
A B C D 单位利润
甲产品
乙 产品
2
2
1
2
4
0
0
4
2
3
现有 材料
数量
12 8 16 12
2006/3
--第 2章 对偶问题 --
--4--
1.最大生产利润模型
设 企业生产甲产品为 X1件，
乙产品为 X2件，则
max z= 2 X1 +3 X2
s.t 2 X1 +2 X2 ? 12
X1 +2 X2 ? 8
4 X1 ? 16
4 X2 ? 12
X1 ? 0,X2 ? 0
2.资源最低售价模型
(原问题 ) <========> ( 对偶问题 )
设第 i种资源价格为 yi,（ i=1,2,3,4,）
则有
min w= 12y1 + 8y2 + 16y3 +12 y4
s.t 2y1 + y2 + 4y3 +0 y4 ? 2
2y1 +2y2 + 0y3 +4 y4 ? 3
yi ? 0,(i=1,2,3,4 )
y1
y2
y3
y4
2006/3
--第 2章 对偶问题 --
--5--
2.2 原问题与对偶问题的关系
一般表示式：
原问题,max z = c1 X1 + c2 X2 + ┈ + cn Xn
s.t a11 X1 + a12 X2 + ┈ + a1n Xn ? b1
a21 X1 + a22 X2 + ┈ + a2n Xn ? b2
·······················
am1 X1 + am2 X2 + ┈ + amn Xn ? bm
xj ? 0,j=1,2,┈,n
对偶问题,min w = b1 y1 + b2 y2 + ┈ + b m ym
s.t a11 y1 + a21 y2 + ┈ + a m1 ym ? c1
a12 y1 + a22 y2 + ┈ + a m2 ym ? c2
·························
a1n y1 + a2n y2 + ┈ + a mn ym ? cn
yi ? 0,(i=1,2,···,m )
2006/3
--第 2章 对偶问题 --
--6--
典式模型对应对偶结构矩阵表示
（ 1） max z = C X
s.t AX ? b
X ? 0
min w = Y b
s.t YA ? C
Y ? 0
对偶问题原问题
2006/3
--第 2章 对偶问题 --
--7--
对偶模型其他结构关系
（ 2）若模型为
max z = C X
s.t AX ? b
X ? 0
max z = C X
s.t - AX ? -b
X ? 0
变形
min w = Y b
s.t YA ? C
Y ? 0
Min w=Y ′(-b)
st,Y ′(-A) ? C
Y ′? 0
令 Y=- Y ′
对偶问题
对偶变量 Y?
2006/3
--第 2章 对偶问题 --
--8--
（ 3） max z = C X
s.t AX ? b
X ? 0 变形
设 X= -X′
max = -CX ′
st,-AX′ ? b
X′?0
min w = Y b
s.t YA ? C
Y ? 0
则有min w = Y b
s.t -YA ?- C
Y ?0
2006/3
--第 2章 对偶问题 --
--9--
对偶问题典式：
用矩阵形式表示：
（ 1） max z = C X min w = Y b
s.t AX ? b <========> s.t YA ? C
X ? 0 Y ? 0
（ 2） max z = C X min w = Y b
s.t AX ? b <========> s.t YA ? C
X ? 0 Y ? 0
（ 3） max z = C X min w = Y b
s.t AX ? b <========> s.t YA ? C
X ? 0 Y ? 0
2006/3
--第 2章 对偶问题 --
--10--
原问题与对偶问题关系表
原问题 (对偶问题 ) 对偶问题 (原问题 )
目标函数系数 约束右端项
约束右端项 目标函数系数
约束条件系数列向量 A 约束条件系数行向量 AT
变量个数 约束条件个数
max min
变量 x j, 约束方程 i,
x j ? 0 ?
x j 无约束 =
x j ? 0 ?
约束方程, 变量 y i,
? y i ? 0
= y i 无约束
? y i ? 0
2006/3
--第 2章 对偶问题 --
--11--
2.3 对偶问题的基本性质
Max z = CX Min w = Y b
s t, AX ? b s t, YA ? C
X ? 0 Y ? 0
(1) 弱对偶性：
若 X0—— 原问题可行解,Y0—— 对偶问题可行解
则 CX0 ? Y0 b
证明,∵ Y0 ? 0,AX0 ? b,∴ Y0 AX0 ? Y0 b，
而 Y0 A ? C, ∴ CX0 ? Y0AX0,
∴ CX0 ? Y0 AX0 ? Y0 b
2006/3
--第 2章 对偶问题 --
--12--
（ 2）最优性：
若 X0—— 原问题可行解,Y0—— 对偶问题可行解，且
CX0 = Y0 b
则 X0—— 原问题最优解,Y0—— 对偶问题最优解
证明：设 X* —— 原问题最优解,Y* —— 对偶问题最优解
则 CX0 ? CX* ? Y* b ? Y0 b
但 CX0 = Y0 b,∴ CX0 = CX* = Y* b = Y0 b
∴ X0 = X*, Y0 = Y*
即 X0—— 原问题最优解,Y0—— 对偶问题最优解
证毕。
2006/3
--第 2章 对偶问题 --
--13--
（ 3）无界性
若原问题最优解无界，则对偶问题无可行解
证：有性质 1,C X0 ? Y0 b，当 CX0 ? ∞ 时，则不可
能存在 Y0，使得 C X0 ? Y0 b。
注：逆定理不成立，即
如果原问题（对偶问题）无可行解，那么
对偶问题（或原问题）?解无界?不成立。
2006/3
--第 2章 对偶问题 --
--14--
（ 4）强对偶性（对偶定理）
若原问题有最优解，则对偶问题一定有最优解，
且有 z max = w min
证,由 ?= C- CB B-1 A ? 0 令 CBB-1 = Y*,
得 Y* A ? C
-Y * = -CBB-1 ? 0,Y*?0
因此,Y*是对偶问题的可行解，
又 CX* = CB (B-1 b) = CB B-1b = Y* b
∴ Y*是对偶问题的 最优解。
2006/3
--第 2章 对偶问题 --
--15--
Max z=CX
st,AX ?b
X ? 0
Max z=CX
st,AX +Xs = b
X ? 0
标准形
Max z=CBXB+CNXN+0XS
st,BXB+NXN+IXS=b,
XB,XN,XS ? 0
改写
∴ B-1存在
Max z=CBXB+CNXN+0XS
st,B-1BXB+ B-1NXN+ B-1I XS= B-1 b
XB,XN,XS ? 0
左乘 B-1
LP模型矩阵变换：
|B|≠0，
（ XB+ B-1NXN+ B-1 XS= B-1 b）
2006/3
--第 2章 对偶问题 --
--16--
单纯形法的矩阵描述：
XB XN XS
B N I
I N′ B-1
b
b′
XS
XB
σ CB CN 0
CB CN 0
σ= C- CB B-1 A?0
0 σN σS
xj
cj
pj0
pj′
σj
cj
XB= b ′ = B-1 b
N? = B-1 N
σN = CN -CBB-1 N ? 0
CB
σS = -CB B-1 ? 0
σ
初始表
最终表
2006/3
--第 2章 对偶问题 --
--17--
（ 5）互补松弛性
n
若 y i * >0,则 ? aij xj* = bi
j=1
n
若 ? a ij xj* < bi,则 y i* = 0
j=1
n n m m
证,∵ ? cj x j* = ? ( ? a ij y i* ) xj* = ? bi y i*
j=1 j=1 i =1 i =1
n m m
∴ ? ( ? a ij y i* ) xj* - ? bi y I* =0
j=1 i =1 i =1
m n
? ( ? a ij xj* - bi ） y i* =0
i =1 j=1
∴ 当 y i*>0,? a ij xj* - bi =0,即 ? a ij xj* = bi
当 ? a ij xj* - bi <0,y i*=0
j=1
j=1
j=1
nn
n
2006/3
--第 2章 对偶问题 --
--18--
（ 6）单纯形表中的对应关系
max z= 2 x1 +3 x2 min w= 12y1 + 8y2 + 16y3 +12 y4
s.t 2 x1 +2 x2 ? 12 s.t 2y1 + y2 + 4y3 +0 y4 ? 2
x1 +2 x2 ? 8 2y1 +2y2 + 0y3 +4 y4 ? 3
4 x1 ? 16 yi ? 0,i=1,2,3,4
4 x2 ? 12
x1 ? 0,x2 ? 0
c
j
→ 2 3 0 0 0 0
C
B
X
B
b x
1
x
2
x
3
x
4
x
5
x
6
0 x
3
0
2 x
1
4
0 x
6
4
3 x
2
2
0 0 1 - 1 - 0, 2 5 0
1 0 0 0 0, 2 5 0
0 0 0 - 2 0, 5 1
0 1 0 0, 5 - 0, 1 2 5 0
c
j
-z
j
0 0 0 - 1, 5 - 0, 1 2 5 0
-y5 -y6 -y1 - y2 - y3 - y4
2006/3
--第 2章 对偶问题 --
--19--
2.4 影子价格 (Shadow price)
★ 取决于企业对资源使用的状况，受生产任务、产品结构差异、管
理效率等因素影响。
★ 边际利润的概念：增加单位资源对利润的贡献。
★ 对资源使用决策的参考依据：买进、卖出
★ 对资源使用状况的估算：互补松弛性
★ 机会成本,?j = cj- CB B-1pj = cj- Ypj= cj- ?aijyi，
?aijyi 为生产 xj而放弃其他产品生产的利润。
★ 制定内部结算价格的参考
2006/3
--第 2章 对偶问题 --
--20--
2.5 对偶单纯形法
由于单纯表中同时反映原问题与对偶问题的最优解，故可以从
求对偶问题最优解角度求解 LP模型。
例：
min z=2x1+3x2 max z'=-2x1-3x2+0x3 +0x4
s.t x1+x2?3 标准化 s.t x1+x2-x3=3
x1+2x2 ? 4 ? x1+2x2-x4=4
x1?0,x2?0 xj ?0,(j=1,2,3,4)
max z'=-2x1-3x2+0x3 +0x4
s.t - x1-x2+x3=-3
? - x1-2x2+x4=-4
xj ?0,(j=1,2,3,4)
2006/3
--第 2章 对偶问题 --
--21--
Cj →
x1 x2 x3 x4XB bCB
-1 -1 1 0
-1 -2 0 1
-2 -3 0 0
-3
-4
x3
x4
0
0
cj - zj -2 -3 0 0
-1/2 0 1 -1/2
1/2 1 0 -1/2
x3
x2 -1 2
cj - zj -1/2 0 0 -3/2
0
-3
1 0 -2 1
0 1 1 -1
x1
x2
2
1
cj - zj 0 0 -1 -1
-2
-3
列单纯表计算：
2006/3
--第 2章 对偶问题 --
--22--
对偶单纯形法步骤：
1.列初始单纯形表，使得所有检验数 ?j? 0 ；
2.出基变量：取 min {bi<0 }= bl → x(l)
3.入基变量,min{—— |alk<0}= → xk
4.主元素,[alk]
5.迭代：同单纯形法，新单纯表中 pk化为单位向量
cj-zj
alj
说明：
10 使用对偶单纯形法时，初始表中检验数必须全部为 ?j? 0，即使得
其对偶问题为可行解，
20 为便于说明，这里采取从原问题角度叙述迭代步骤。
2006/3
--第 2章 对偶问题 --
--23--
2.6 灵敏度分析
1．灵敏度分析的概念：
当某一个参数发生变化后，引起最优解如何改变的分
析。
可以改变的参数有：
bi—— 约束右端项的变化，通常称资源的改变；
cj —— 目标函数系数的变化，通常称市场条件的变化；
pj —— 约束条件系数的变化，通常称工艺系数的变化；
其他的变化有：增加一种新产品、增加一道新的工序
等。
2006/3
--第 2章 对偶问题 --
--24--
2．分析原理：
借助最终单纯形表将变化后的结果按下述基本原则反映到最终表
里去。
（ 1） bi变化,（ b+△ b） ′=B-1 （ b+△ b）
= B-1 b+ B-1 △ b = b′+B-1 △ b
（ 2） pj变化：（ pj+△ pj） ′= B-1 （ pj+△ pj ）
= B-1 pj+ B-1 △ pj = pj ′+ B-1 △ pj
（ 3） cj变化：直接反映到最终表中，计算检验数。
（ 4）增加一个约束方程：直接反映到最终表中。
（ 5）增加新产品：仿照 pj变化。
2006/3
--第 2章 对偶问题 --
--25--
3．计算示例：
max z= 2 x1 +3 x2
s.t 2 x1 +2 x2 ? 12
x1 +2 x2 ? 8
4 x1 ? 16
4 x2 ? 12
x1 ? 0,x2 ? 0
例：已知某线性规划模型及最终的单纯表如下：
问：（ 1）若 b2增加 8个单位，最优解如何变化？
（ 2）若 c2还可增加 2个单位，最优解如何改变？
（ 3）若引进一个新变量（产品） y，其目标函
数系数为 cy=5，系数列向量为 py=[3 2 6 3]，问最
优解是否会改变？
cj — ? 2 3 0 0 0 0
CB XB b x1 x2 x3 x4 x5 x6
0 x3 0
2 x1 4
0 x6 4
3 x2 2
0 0 1 -1 -0.25 0
1 0 0 0 0.25 0
0 0 0 -2 0.5 1
0 1 0 0.5 -0.125 0
cj－ zj 0 0 0 -1.5 -0.125 0
2006/3
--第 2章 对偶问题 --
--26--
解：（ 1）
?（ b+△ b） ′=B-1 b+ B-1 △ b = b′+B-1 △ b
=?0 4 4 2?T + ? -8 0 -16 4? T = ?-8 4 -12 6 ? T
B-1 △ b =
1 -1 -0.25 0
0 0 0.25 0
0 -2 0.5 1
0 0.5 -0.125 0
0
8
0
0
=
-8
0
-16
4
?利用对偶单纯形法继续 求最优解。
（ 2）当 cj变化时,?′=C′－ CB′ B-1 A，列出单纯形表，
重新求出检验数,如表中所示：
（ 3）增加 y时,?y= cy- CB B-1 py=5- (0 1.5 0.125 0) [3 2 6 3]T
=1.25>0
?选择 y作入基变量,py′= B-1 py= =?-0.5 1.5 2 0.25?T
继续迭代：
2006/3
--第 2章 对偶问题 --
--27--
cj — ? 2 3 0 0 0 0
CB XB b x1 x2 x3 x4 x5 x6
0 x3 -8
2 x1 4
0 x6 -12
3 x2 6
0 0 1 -1 -0.25 0
1 0 0 0 0.25 0
0 0 0 ?-2 ? 0.5 1
0 1 0 0.5 -0.125 0
cj－ zj 0 0 0 -1.5 -0.125 0
0 x3 -2
2 x1 4
0 x6 6
3 x2 3
0 0 1 0 ? -0.5 ? -0.5
1 0 0 0 0.25 0
0 0 0 1 -0.25 -0.5
0 1 0 0 0 0.25
cj－ zj 0 0 0 0 -0.5 -0.75
0 x3 4
2 x1 3
0 x6 7
3 x2 3
0 0 -2 0 1 1
1 0 0.5 0 0 -0.25
0 0 -0.5 1 0 -0.25
0 1 0 0 0 0.25
cj－ zj 0 0 -1 0 0 -0.25
返回右端项变化分析单纯形表：
2006/3
--第 2章 对偶问题 --
--28--
cj — ? 2 5 0 0 0 0
CB XB b x1 x2 x3 x4 x5 x6
0 x3 0
2 x1 4
0 x6 4
5 x2 2
0 0 1 -1 -0.25 0
1 0 0 0 0.25 0
0 0 0 -2 ? 0.5 ? 1
0 1 0 0.5 -0.125 0
cj－ zj 0 0 0 -2.5 0.125 0
0 x3 2
2 x1 2
0 x6 8
5 x2 3
0 0 1 -2 0 0.5
1 0 0 1 0 -0.5
0 0 0 -4 1 2
0 1 0 0 0 0.25
cj－ zj 0 0 0 -2 0 -0.25
返回
Cj 变化分析单纯形表：
2006/3
--第 2章 对偶问题 --
--29--
cj — ? 2 3 0 0 0 0 5
CB XB b x1 x2 x3 x4 x5 x6 y
0 x3 0
2 x1 4
0 x6 4
3 x2 2
0 0 1 -1 -0.25 0 -0.5
1 0 0 0 0.25 0 1.5
0 0 0 -2 0.5 1 ? 2 ?
0 1 0 0.5 -0.125 0 0.25
cj－ zj 0 0 0 -1.5 -0.125 0 1.25
0 x3 1
2 x1 1
5 y 2
3 x2 1.5
0 0 1 -1.5 -0.125 0.25 0
1 0 0 1.5 -0.125 -0.75 0
0 0 0 -1 0.25 0.5 1
0 1 0 0.75 -0.1875 -0.125 0
cj－ zj 0 0 0 -0.25 -0.4375 -0.625 0
增加新产品（变量 y）变化分析单纯形表：
2006/3
--第 2章 对偶问题 --
--30--
4．程序中的灵敏度分析方法：
(2) 用程序中修改模型的编辑命令，修改原模型，再求解。
命令,ALTER
(1) DO RANGE ANALYSIS? YES
注：可用? PARA‘行号’‘数值’?命令格式对某一
约束方程行右端项数值的变化进行灵敏度分析（参数
规划方式）。但必须是在用? GO”命令求解之后进行 。
2006/3
--第 2章 对偶问题 --
--31--
2.7 参数线性规划
1,概念：研究目标函数值随某一参数变化的规律及最
优解相应的变化。
2,算法：先令变化量 ?=0，再考察随着 ?的增加引起解
的变化情况。
3,最后，画出目标值随 ?的变化所形成的曲线。
2006/3
--第 2章 对偶问题 --
--32--
例：有如下线性规划模型：
max z=2x1+3x2
s.t x1+x2?3
x1+2x2 ? 4 + ?
x1?0,x2?0（ ?? 0 ）
max z=2x1+3x2+0x3 +0x4
s.t x1+x2+x3=3
x1+2x2+x4=4
xj ?0,(j=1,2,3,4)
（ 1）当 ?=0 时的最优解；
（ 2）当 ??0时,z 值的变化规律。
解：先令 ? =0，有下述模型的标准形
利用单纯形法求解：
2006/3
--第 2章 对偶问题 --
--33--
Cj →
x1 x2 x3 x4XB bCB
1 1 1 0
1 2 0 1
2 3 0 0
3
4
x3
x4
0
0
cj - zj 2 3 0 0
1/2 0 1 -1/2
1/2 1 0 1/2
x3
x2 12
cj - zj 1/2 0 0 -3/2
0
3
1 0 2 -1
0 1 -1 1
x1
x2
2
1
cj - zj 0 0 -1 -1
2
3 （ ? =0）
2006/3
--第 2章 对偶问题 --
--34--
Cj →
x1 x2 x3 x4XB bCB
2 3 0 0
3- ?
4+?
x1
x2
0
0
cj - zj
-1 0 -2 1
1 1 1 0
x4
x2
cj - zj -1 0 -3 0
0
3
0 0 -1 -1
1 0 2 -1
0 1 -1 1 （ 0??? 3）
当 ??0时,? b′= B-1·?b= B-1·?b (0 ?)T = (- ? ?)T，继续
迭代如下：（对偶单纯形法）
? -3
7 （ ??3）
其变化曲线如下：
2006/3
--第 2章 对偶问题 --
--35--
?
Z ( ?)
0 3
7
21
2006/3
--第 2章 对偶问题 --
--36--
例：
某大学教授利用部分业余时间从事咨询工作。现有三
个 A,B,C企业欲聘请，各自每小时的咨询费用分别为 10，
12,16元。教授每月可用于外出咨询的时间为 40小时，但
对每个企业而言，用于准备的时间与咨询所花的时间的比
例分别为 0.1,0.5,0.8，教授每月可用于准备的时间应不
超过 24小时。若假定三个企业每月要求的咨询时间可分别
达到 80,60,20小时。现问：教授应作何种决策，才能使
收益最大？
从目前看，教授有许多咨询机会，但可用的外出咨询
时间及准备的时间有限，所以可考虑雇用助手（用于帮助
准备），但要支付每小时 4元的费用，现帮助教授分析一下，
它是否该雇用助手，若需雇用，每月应雇用多少时间？
2006/3
--第 2章 对偶问题 --
--37--
设 用于三个企业咨询的时间分别为 A? x1,B? x2,C? x3，
Max z=10x1+12x2+16x3
s.t,x1+x2+x3?40
0.1x1+0.5x2+0.8x3?24
x1?80
x2 ?60
x3 ?20
x1?0,x2?0,x3?0
+?
- 4?
--第 2章 对偶问题 --
--1--
2006/3
--第 2章 对偶问题 --
--2--
第 2 章 线性规划的对偶理论
Duality 对偶
Dual Problem 对偶问题
Dual Linear Programming
对偶线性规划
Dual Theory 对偶理论
2006/3
--第 2章 对偶问题 --
--3--
2.1 问题的提出
例：某企业计划生产甲、乙两种产品，该两种产品均需要 A,B,C、
D 四种不同的材料，按工艺资料规定，生产一单位甲乙产品需要各
种材料数量及单位产品利润如表中所示。问,如何安排产品的生产计
划,才能使企业获利最大?
设备
产品
A B C D 单位利润
甲产品
乙 产品
2
2
1
2
4
0
0
4
2
3
现有 材料
数量
12 8 16 12
2006/3
--第 2章 对偶问题 --
--4--
1.最大生产利润模型
设 企业生产甲产品为 X1件，
乙产品为 X2件，则
max z= 2 X1 +3 X2
s.t 2 X1 +2 X2 ? 12
X1 +2 X2 ? 8
4 X1 ? 16
4 X2 ? 12
X1 ? 0,X2 ? 0
2.资源最低售价模型
(原问题 ) <========> ( 对偶问题 )
设第 i种资源价格为 yi,（ i=1,2,3,4,）
则有
min w= 12y1 + 8y2 + 16y3 +12 y4
s.t 2y1 + y2 + 4y3 +0 y4 ? 2
2y1 +2y2 + 0y3 +4 y4 ? 3
yi ? 0,(i=1,2,3,4 )
y1
y2
y3
y4
2006/3
--第 2章 对偶问题 --
--5--
2.2 原问题与对偶问题的关系
一般表示式：
原问题,max z = c1 X1 + c2 X2 + ┈ + cn Xn
s.t a11 X1 + a12 X2 + ┈ + a1n Xn ? b1
a21 X1 + a22 X2 + ┈ + a2n Xn ? b2
·······················
am1 X1 + am2 X2 + ┈ + amn Xn ? bm
xj ? 0,j=1,2,┈,n
对偶问题,min w = b1 y1 + b2 y2 + ┈ + b m ym
s.t a11 y1 + a21 y2 + ┈ + a m1 ym ? c1
a12 y1 + a22 y2 + ┈ + a m2 ym ? c2
·························
a1n y1 + a2n y2 + ┈ + a mn ym ? cn
yi ? 0,(i=1,2,···,m )
2006/3
--第 2章 对偶问题 --
--6--
典式模型对应对偶结构矩阵表示
（ 1） max z = C X
s.t AX ? b
X ? 0
min w = Y b
s.t YA ? C
Y ? 0
对偶问题原问题
2006/3
--第 2章 对偶问题 --
--7--
对偶模型其他结构关系
（ 2）若模型为
max z = C X
s.t AX ? b
X ? 0
max z = C X
s.t - AX ? -b
X ? 0
变形
min w = Y b
s.t YA ? C
Y ? 0
Min w=Y ′(-b)
st,Y ′(-A) ? C
Y ′? 0
令 Y=- Y ′
对偶问题
对偶变量 Y?
2006/3
--第 2章 对偶问题 --
--8--
（ 3） max z = C X
s.t AX ? b
X ? 0 变形
设 X= -X′
max = -CX ′
st,-AX′ ? b
X′?0
min w = Y b
s.t YA ? C
Y ? 0
则有min w = Y b
s.t -YA ?- C
Y ?0
2006/3
--第 2章 对偶问题 --
--9--
对偶问题典式：
用矩阵形式表示：
（ 1） max z = C X min w = Y b
s.t AX ? b <========> s.t YA ? C
X ? 0 Y ? 0
（ 2） max z = C X min w = Y b
s.t AX ? b <========> s.t YA ? C
X ? 0 Y ? 0
（ 3） max z = C X min w = Y b
s.t AX ? b <========> s.t YA ? C
X ? 0 Y ? 0
2006/3
--第 2章 对偶问题 --
--10--
原问题与对偶问题关系表
原问题 (对偶问题 ) 对偶问题 (原问题 )
目标函数系数 约束右端项
约束右端项 目标函数系数
约束条件系数列向量 A 约束条件系数行向量 AT
变量个数 约束条件个数
max min
变量 x j, 约束方程 i,
x j ? 0 ?
x j 无约束 =
x j ? 0 ?
约束方程, 变量 y i,
? y i ? 0
= y i 无约束
? y i ? 0
2006/3
--第 2章 对偶问题 --
--11--
2.3 对偶问题的基本性质
Max z = CX Min w = Y b
s t, AX ? b s t, YA ? C
X ? 0 Y ? 0
(1) 弱对偶性：
若 X0—— 原问题可行解,Y0—— 对偶问题可行解
则 CX0 ? Y0 b
证明,∵ Y0 ? 0,AX0 ? b,∴ Y0 AX0 ? Y0 b，
而 Y0 A ? C, ∴ CX0 ? Y0AX0,
∴ CX0 ? Y0 AX0 ? Y0 b
2006/3
--第 2章 对偶问题 --
--12--
（ 2）最优性：
若 X0—— 原问题可行解,Y0—— 对偶问题可行解，且
CX0 = Y0 b
则 X0—— 原问题最优解,Y0—— 对偶问题最优解
证明：设 X* —— 原问题最优解,Y* —— 对偶问题最优解
则 CX0 ? CX* ? Y* b ? Y0 b
但 CX0 = Y0 b,∴ CX0 = CX* = Y* b = Y0 b
∴ X0 = X*, Y0 = Y*
即 X0—— 原问题最优解,Y0—— 对偶问题最优解
证毕。
2006/3
--第 2章 对偶问题 --
--13--
（ 3）无界性
若原问题最优解无界，则对偶问题无可行解
证：有性质 1,C X0 ? Y0 b，当 CX0 ? ∞ 时，则不可
能存在 Y0，使得 C X0 ? Y0 b。
注：逆定理不成立，即
如果原问题（对偶问题）无可行解，那么
对偶问题（或原问题）?解无界?不成立。
2006/3
--第 2章 对偶问题 --
--14--
（ 4）强对偶性（对偶定理）
若原问题有最优解，则对偶问题一定有最优解，
且有 z max = w min
证,由 ?= C- CB B-1 A ? 0 令 CBB-1 = Y*,
得 Y* A ? C
-Y * = -CBB-1 ? 0,Y*?0
因此,Y*是对偶问题的可行解，
又 CX* = CB (B-1 b) = CB B-1b = Y* b
∴ Y*是对偶问题的 最优解。
2006/3
--第 2章 对偶问题 --
--15--
Max z=CX
st,AX ?b
X ? 0
Max z=CX
st,AX +Xs = b
X ? 0
标准形
Max z=CBXB+CNXN+0XS
st,BXB+NXN+IXS=b,
XB,XN,XS ? 0
改写
∴ B-1存在
Max z=CBXB+CNXN+0XS
st,B-1BXB+ B-1NXN+ B-1I XS= B-1 b
XB,XN,XS ? 0
左乘 B-1
LP模型矩阵变换：
|B|≠0，
（ XB+ B-1NXN+ B-1 XS= B-1 b）
2006/3
--第 2章 对偶问题 --
--16--
单纯形法的矩阵描述：
XB XN XS
B N I
I N′ B-1
b
b′
XS
XB
σ CB CN 0
CB CN 0
σ= C- CB B-1 A?0
0 σN σS
xj
cj
pj0
pj′
σj
cj
XB= b ′ = B-1 b
N? = B-1 N
σN = CN -CBB-1 N ? 0
CB
σS = -CB B-1 ? 0
σ
初始表
最终表
2006/3
--第 2章 对偶问题 --
--17--
（ 5）互补松弛性
n
若 y i * >0,则 ? aij xj* = bi
j=1
n
若 ? a ij xj* < bi,则 y i* = 0
j=1
n n m m
证,∵ ? cj x j* = ? ( ? a ij y i* ) xj* = ? bi y i*
j=1 j=1 i =1 i =1
n m m
∴ ? ( ? a ij y i* ) xj* - ? bi y I* =0
j=1 i =1 i =1
m n
? ( ? a ij xj* - bi ） y i* =0
i =1 j=1
∴ 当 y i*>0,? a ij xj* - bi =0,即 ? a ij xj* = bi
当 ? a ij xj* - bi <0,y i*=0
j=1
j=1
j=1
nn
n
2006/3
--第 2章 对偶问题 --
--18--
（ 6）单纯形表中的对应关系
max z= 2 x1 +3 x2 min w= 12y1 + 8y2 + 16y3 +12 y4
s.t 2 x1 +2 x2 ? 12 s.t 2y1 + y2 + 4y3 +0 y4 ? 2
x1 +2 x2 ? 8 2y1 +2y2 + 0y3 +4 y4 ? 3
4 x1 ? 16 yi ? 0,i=1,2,3,4
4 x2 ? 12
x1 ? 0,x2 ? 0
c
j
→ 2 3 0 0 0 0
C
B
X
B
b x
1
x
2
x
3
x
4
x
5
x
6
0 x
3
0
2 x
1
4
0 x
6
4
3 x
2
2
0 0 1 - 1 - 0, 2 5 0
1 0 0 0 0, 2 5 0
0 0 0 - 2 0, 5 1
0 1 0 0, 5 - 0, 1 2 5 0
c
j
-z
j
0 0 0 - 1, 5 - 0, 1 2 5 0
-y5 -y6 -y1 - y2 - y3 - y4
2006/3
--第 2章 对偶问题 --
--19--
2.4 影子价格 (Shadow price)
★ 取决于企业对资源使用的状况，受生产任务、产品结构差异、管
理效率等因素影响。
★ 边际利润的概念：增加单位资源对利润的贡献。
★ 对资源使用决策的参考依据：买进、卖出
★ 对资源使用状况的估算：互补松弛性
★ 机会成本,?j = cj- CB B-1pj = cj- Ypj= cj- ?aijyi，
?aijyi 为生产 xj而放弃其他产品生产的利润。
★ 制定内部结算价格的参考
2006/3
--第 2章 对偶问题 --
--20--
2.5 对偶单纯形法
由于单纯表中同时反映原问题与对偶问题的最优解，故可以从
求对偶问题最优解角度求解 LP模型。
例：
min z=2x1+3x2 max z'=-2x1-3x2+0x3 +0x4
s.t x1+x2?3 标准化 s.t x1+x2-x3=3
x1+2x2 ? 4 ? x1+2x2-x4=4
x1?0,x2?0 xj ?0,(j=1,2,3,4)
max z'=-2x1-3x2+0x3 +0x4
s.t - x1-x2+x3=-3
? - x1-2x2+x4=-4
xj ?0,(j=1,2,3,4)
2006/3
--第 2章 对偶问题 --
--21--
Cj →
x1 x2 x3 x4XB bCB
-1 -1 1 0
-1 -2 0 1
-2 -3 0 0
-3
-4
x3
x4
0
0
cj - zj -2 -3 0 0
-1/2 0 1 -1/2
1/2 1 0 -1/2
x3
x2 -1 2
cj - zj -1/2 0 0 -3/2
0
-3
1 0 -2 1
0 1 1 -1
x1
x2
2
1
cj - zj 0 0 -1 -1
-2
-3
列单纯表计算：
2006/3
--第 2章 对偶问题 --
--22--
对偶单纯形法步骤：
1.列初始单纯形表，使得所有检验数 ?j? 0 ；
2.出基变量：取 min {bi<0 }= bl → x(l)
3.入基变量,min{—— |alk<0}= → xk
4.主元素,[alk]
5.迭代：同单纯形法，新单纯表中 pk化为单位向量
cj-zj
alj
说明：
10 使用对偶单纯形法时，初始表中检验数必须全部为 ?j? 0，即使得
其对偶问题为可行解，
20 为便于说明，这里采取从原问题角度叙述迭代步骤。
2006/3
--第 2章 对偶问题 --
--23--
2.6 灵敏度分析
1．灵敏度分析的概念：
当某一个参数发生变化后，引起最优解如何改变的分
析。
可以改变的参数有：
bi—— 约束右端项的变化，通常称资源的改变；
cj —— 目标函数系数的变化，通常称市场条件的变化；
pj —— 约束条件系数的变化，通常称工艺系数的变化；
其他的变化有：增加一种新产品、增加一道新的工序
等。
2006/3
--第 2章 对偶问题 --
--24--
2．分析原理：
借助最终单纯形表将变化后的结果按下述基本原则反映到最终表
里去。
（ 1） bi变化,（ b+△ b） ′=B-1 （ b+△ b）
= B-1 b+ B-1 △ b = b′+B-1 △ b
（ 2） pj变化：（ pj+△ pj） ′= B-1 （ pj+△ pj ）
= B-1 pj+ B-1 △ pj = pj ′+ B-1 △ pj
（ 3） cj变化：直接反映到最终表中，计算检验数。
（ 4）增加一个约束方程：直接反映到最终表中。
（ 5）增加新产品：仿照 pj变化。
2006/3
--第 2章 对偶问题 --
--25--
3．计算示例：
max z= 2 x1 +3 x2
s.t 2 x1 +2 x2 ? 12
x1 +2 x2 ? 8
4 x1 ? 16
4 x2 ? 12
x1 ? 0,x2 ? 0
例：已知某线性规划模型及最终的单纯表如下：
问：（ 1）若 b2增加 8个单位，最优解如何变化？
（ 2）若 c2还可增加 2个单位，最优解如何改变？
（ 3）若引进一个新变量（产品） y，其目标函
数系数为 cy=5，系数列向量为 py=[3 2 6 3]，问最
优解是否会改变？
cj — ? 2 3 0 0 0 0
CB XB b x1 x2 x3 x4 x5 x6
0 x3 0
2 x1 4
0 x6 4
3 x2 2
0 0 1 -1 -0.25 0
1 0 0 0 0.25 0
0 0 0 -2 0.5 1
0 1 0 0.5 -0.125 0
cj－ zj 0 0 0 -1.5 -0.125 0
2006/3
--第 2章 对偶问题 --
--26--
解：（ 1）
?（ b+△ b） ′=B-1 b+ B-1 △ b = b′+B-1 △ b
=?0 4 4 2?T + ? -8 0 -16 4? T = ?-8 4 -12 6 ? T
B-1 △ b =
1 -1 -0.25 0
0 0 0.25 0
0 -2 0.5 1
0 0.5 -0.125 0
0
8
0
0
=
-8
0
-16
4
?利用对偶单纯形法继续 求最优解。
（ 2）当 cj变化时,?′=C′－ CB′ B-1 A，列出单纯形表，
重新求出检验数,如表中所示：
（ 3）增加 y时,?y= cy- CB B-1 py=5- (0 1.5 0.125 0) [3 2 6 3]T
=1.25>0
?选择 y作入基变量,py′= B-1 py= =?-0.5 1.5 2 0.25?T
继续迭代：
2006/3
--第 2章 对偶问题 --
--27--
cj — ? 2 3 0 0 0 0
CB XB b x1 x2 x3 x4 x5 x6
0 x3 -8
2 x1 4
0 x6 -12
3 x2 6
0 0 1 -1 -0.25 0
1 0 0 0 0.25 0
0 0 0 ?-2 ? 0.5 1
0 1 0 0.5 -0.125 0
cj－ zj 0 0 0 -1.5 -0.125 0
0 x3 -2
2 x1 4
0 x6 6
3 x2 3
0 0 1 0 ? -0.5 ? -0.5
1 0 0 0 0.25 0
0 0 0 1 -0.25 -0.5
0 1 0 0 0 0.25
cj－ zj 0 0 0 0 -0.5 -0.75
0 x3 4
2 x1 3
0 x6 7
3 x2 3
0 0 -2 0 1 1
1 0 0.5 0 0 -0.25
0 0 -0.5 1 0 -0.25
0 1 0 0 0 0.25
cj－ zj 0 0 -1 0 0 -0.25
返回右端项变化分析单纯形表：
2006/3
--第 2章 对偶问题 --
--28--
cj — ? 2 5 0 0 0 0
CB XB b x1 x2 x3 x4 x5 x6
0 x3 0
2 x1 4
0 x6 4
5 x2 2
0 0 1 -1 -0.25 0
1 0 0 0 0.25 0
0 0 0 -2 ? 0.5 ? 1
0 1 0 0.5 -0.125 0
cj－ zj 0 0 0 -2.5 0.125 0
0 x3 2
2 x1 2
0 x6 8
5 x2 3
0 0 1 -2 0 0.5
1 0 0 1 0 -0.5
0 0 0 -4 1 2
0 1 0 0 0 0.25
cj－ zj 0 0 0 -2 0 -0.25
返回
Cj 变化分析单纯形表：
2006/3
--第 2章 对偶问题 --
--29--
cj — ? 2 3 0 0 0 0 5
CB XB b x1 x2 x3 x4 x5 x6 y
0 x3 0
2 x1 4
0 x6 4
3 x2 2
0 0 1 -1 -0.25 0 -0.5
1 0 0 0 0.25 0 1.5
0 0 0 -2 0.5 1 ? 2 ?
0 1 0 0.5 -0.125 0 0.25
cj－ zj 0 0 0 -1.5 -0.125 0 1.25
0 x3 1
2 x1 1
5 y 2
3 x2 1.5
0 0 1 -1.5 -0.125 0.25 0
1 0 0 1.5 -0.125 -0.75 0
0 0 0 -1 0.25 0.5 1
0 1 0 0.75 -0.1875 -0.125 0
cj－ zj 0 0 0 -0.25 -0.4375 -0.625 0
增加新产品（变量 y）变化分析单纯形表：
2006/3
--第 2章 对偶问题 --
--30--
4．程序中的灵敏度分析方法：
(2) 用程序中修改模型的编辑命令，修改原模型，再求解。
命令,ALTER
(1) DO RANGE ANALYSIS? YES
注：可用? PARA‘行号’‘数值’?命令格式对某一
约束方程行右端项数值的变化进行灵敏度分析（参数
规划方式）。但必须是在用? GO”命令求解之后进行 。
2006/3
--第 2章 对偶问题 --
--31--
2.7 参数线性规划
1,概念：研究目标函数值随某一参数变化的规律及最
优解相应的变化。
2,算法：先令变化量 ?=0，再考察随着 ?的增加引起解
的变化情况。
3,最后，画出目标值随 ?的变化所形成的曲线。
2006/3
--第 2章 对偶问题 --
--32--
例：有如下线性规划模型：
max z=2x1+3x2
s.t x1+x2?3
x1+2x2 ? 4 + ?
x1?0,x2?0（ ?? 0 ）
max z=2x1+3x2+0x3 +0x4
s.t x1+x2+x3=3
x1+2x2+x4=4
xj ?0,(j=1,2,3,4)
（ 1）当 ?=0 时的最优解；
（ 2）当 ??0时,z 值的变化规律。
解：先令 ? =0，有下述模型的标准形
利用单纯形法求解：
2006/3
--第 2章 对偶问题 --
--33--
Cj →
x1 x2 x3 x4XB bCB
1 1 1 0
1 2 0 1
2 3 0 0
3
4
x3
x4
0
0
cj - zj 2 3 0 0
1/2 0 1 -1/2
1/2 1 0 1/2
x3
x2 12
cj - zj 1/2 0 0 -3/2
0
3
1 0 2 -1
0 1 -1 1
x1
x2
2
1
cj - zj 0 0 -1 -1
2
3 （ ? =0）
2006/3
--第 2章 对偶问题 --
--34--
Cj →
x1 x2 x3 x4XB bCB
2 3 0 0
3- ?
4+?
x1
x2
0
0
cj - zj
-1 0 -2 1
1 1 1 0
x4
x2
cj - zj -1 0 -3 0
0
3
0 0 -1 -1
1 0 2 -1
0 1 -1 1 （ 0??? 3）
当 ??0时,? b′= B-1·?b= B-1·?b (0 ?)T = (- ? ?)T，继续
迭代如下：（对偶单纯形法）
? -3
7 （ ??3）
其变化曲线如下：
2006/3
--第 2章 对偶问题 --
--35--
?
Z ( ?)
0 3
7
21
2006/3
--第 2章 对偶问题 --
--36--
例：
某大学教授利用部分业余时间从事咨询工作。现有三
个 A,B,C企业欲聘请，各自每小时的咨询费用分别为 10，
12,16元。教授每月可用于外出咨询的时间为 40小时，但
对每个企业而言，用于准备的时间与咨询所花的时间的比
例分别为 0.1,0.5,0.8，教授每月可用于准备的时间应不
超过 24小时。若假定三个企业每月要求的咨询时间可分别
达到 80,60,20小时。现问：教授应作何种决策，才能使
收益最大？
从目前看，教授有许多咨询机会，但可用的外出咨询
时间及准备的时间有限，所以可考虑雇用助手（用于帮助
准备），但要支付每小时 4元的费用，现帮助教授分析一下，
它是否该雇用助手，若需雇用，每月应雇用多少时间？
2006/3
--第 2章 对偶问题 --
--37--
设 用于三个企业咨询的时间分别为 A? x1,B? x2,C? x3，
Max z=10x1+12x2+16x3
s.t,x1+x2+x3?40
0.1x1+0.5x2+0.8x3?24
x1?80
x2 ?60
x3 ?20
x1?0,x2?0,x3?0
+?
- 4?
