线性规划的对偶理论
对偶的定义
对偶问题的性质
对偶的经济解释
SUES
XB XN XS b
XB B N I b
C CB CN 0 0
了解了解--------单纯形的矩阵描述单纯形的矩阵描述
XXSS为松弛变量为松弛变量
XB XN XS b
XB I B－1N B－1 B－1b
N 0 CN－CBB－1N －CBB－1 －CBB－1b
单纯性法计算时，总选取单位矩阵单纯性法计算时，总选取单位矩阵 II 为初始基，为初始基，
对应基变量为对应基变量为XXSS, , 设迭代若干步后，基变量变为设迭代若干步后，基变量变为
XXBB, , XXB B 在初始单纯性表中的系数矩阵为在初始单纯性表中的系数矩阵为 BB。则该。则该
步的单纯性表中由步的单纯性表中由 XXBB 系数组成的矩阵为单位矩系数组成的矩阵为单位矩
阵阵 II ，对应，对应XXSS 的系数矩阵在新表中应为的系数矩阵在新表中应为BB-1-1
Y=C Y=CBBBB-1
-1 称为单纯形乘子（称为单纯形乘子（对偶变量对偶变量））
对偶原理
对偶问题概念：
任何一个线性规划问题都有一个与之相对应
的线性规划问题，如果前者称为原始问题，后者
就称为“对偶”问题。
对偶问题是对原问题从另一角度进行的描述
其最优解与原问题的最优解有着密切的联系，在
求得一个线性规划最优解的同时也就得到对偶线
性规划的最优解，反之亦然。
对偶理论就是研究线性规划及其对偶问题的
理论，是线性规划理论的重要内容之一。
问题的导出
A B C 拥有量
工 时 1 1 1 3
材 料 1 4 7 9
单件利润 2 3 3
A B C 拥有量
工 时 1 1 1 3
材 料 1 4 7 9
单件利润 2 3 3
假设有客户提出要求，购买工厂所拥有的
工时和材料，为客户加工别的产品，由客
户支付工时费和材料费。那么工厂给工时
和材料制订的最低价格应是多少，才值得
出卖工时和材料 ?
A B C 拥有量
工 时 1 1 1 3
材 料 1 4 7 9
单件利润 2 3 3
•出卖资源获利应不少于生产产品的获利;
约束
•价格应该尽量低，这样，才能有竞争力;
目标
•价格应该是非负的
A B C 拥有量
工 时 1 1 1 3
材 料 1 4 7 9
单件利润 2 3 3
用y1和y2分别表示工时和材料的出售价格
总利润最小 min W=3y1+9y2
保证A产品利润 y1+y2≥2
保证B产品利润 y1+4y2≥3
保证C产品利润 y1+7y2≥3
售价非负 y1≥0 y2≥0
A B C 拥有量
工 时 1 1 1 3
材 料 1 4 7 9
单件利润 2 3 3
对
偶
问
题
的
定
义
对
称
形
式
的
对
偶
问
题
对偶的定义
原始问题
min f(x)=CTX
. AX≥b
X ≥0
对偶问题
max z(y)=bTy
. ATy≤C
y ≥0
≥
min
bA
CT
CAT
bT
≤
max
m
n
m
n
对偶问题的特点
（1）目标函数在一个问题中是求最大值在
另一问题中则为求最小值
（2）一个问题中目标函数的系数是另一个
问题中约束条件的右端项
（3）一个问题中的约束条件个数等于另一
个问题中的变量数
（4）原问题的约束系数矩阵与对偶问题的
约束系数矩阵互为转置矩阵
一 般
线性规
划问题
的对偶
问题
对偶问题对应表
原问题（对偶问题） 对偶问题（原问题）
目标函数min 目标函数max
约束条件： m个
第i个约束类型为“≥”
第i个约束类型为“≤”
第i个约束类型为“＝”
变量数： m个
第i个变量≥0
第i个变量≤0
第i个变量是自由变量
变量数：n个
第j个变量≤ 0
第j个变量≥ 0
第j个变量是自由变量
约束条件：n个
第j个约束类型为“≥”
第j个约束类型为“≤”
第j个约束类型为“＝”
例 写出如下LP问题的对偶问题
对偶问题
对偶问题的性质
1、对偶的对偶就是原始问题
max z’=-CTX
. -AX≤-b
X ≥0
min y=-bTW
. -ATW≥-C
W ≥0
max y=bTW
. ATW≤C
W ≥0
min z=CTX
. AX≥b
X
≥0
对偶的定义
对偶的定义
2、对偶问题的性质
（1）弱对偶性（可行解的目标函数值之间的关系）
设X、Y分别是原始问题和对偶问题的可行解
∑cjxj≤∑biyi
（3）最优性
（2）无界性
如果原问题（对偶问题）具有无界解，
则其对偶问题（原问题）无可行解。
无界性 在一对对偶问
题，若其中一个问题可行
但目标函数无界，则另一
个问题不可行；反之不成
立。这也是对偶问题的无
界性。
关于无界性有如下结论：
问题无界
无可
行解
无可行解
无可行解
问题无界
对偶问题原问题
无界
如：
（原）
无可
行解
（对）
已知
试用对偶理论证明原问题无界。
解： =（）是 原问题的一个可行解，而 对偶
问题 的第一个约束条件不能成立（因为y1 , y2 ≥0)。因此
，对偶问题不可行，可知，原问题无界。
（4）强对偶性（最优解的目标函数之间的关系）
如果原问题有最优解，则其对偶问题也一定有
最优解，且两者的目标函数值相等
在线性规划问题的最优解中，
如果对应某一约束条件的对偶变量值为非零，
则该约束条件取严格等式；
反之如果约束条件取严格不等式，
3、互补松弛性
则其对应的对偶变量一定为零。
即
解：先写出它的对偶问题
练习
已知线性规划问题
影子价格－对偶的经济解释
1、原始问题是利润最大化的生产计划问题
单位产品的利润
产品产量
总利润
资源限量单位产品消耗的资源 剩余的资源
消耗的资源
2、对偶问题
资源限量
资源价格
总利润
对偶问题是资源定价问题，对偶问题的最优解w1、w2、
...、wm称为m种资源的影子价格（Shadow Price）
原始和对偶问题都取得最优解时，最大利润 max z=min y
3、资源影子价格的性质
■影子价格越大，说明这种资源越是相对紧缺
■影子价格越小，说明这种资源相对不紧缺
■如果最优生产计划下某种资源有剩余，这种资源
的影子价格一定等于0
w1
w2
wm
4、产品的机会成本
机会成本
表示减少一件产品所节省的资源可以增加的利润
增加单位资源可以增加的利润
减少一件产品可以节省的资源
THE END
对偶单纯形法
对偶单纯形法的原理
对偶单纯形法的应用步骤
对偶单纯形法举例
对偶单纯形法的应用条件
对偶单纯形法的优点和缺点
对偶单纯形法原理
对偶单纯形法并不是求解对偶问题解的方法，
而是利用对偶理论求解原问题的解的方法。
单纯形法是在原问题可行的基础上，通过迭
代使对偶问题达到可行，从而得到最优解。
根据对偶问题的对称性，若原问题不可行而
对偶问题可行，那么在保持对偶问题可行的
基础上，逐步迭代使原问题达到可行，也可
得到最优解。
对于标准线性规划问题：
可行基B 若B对应的基本解是可行解
最优基B 若B对应的基本解是最优解
对偶可行基B 若CBB
-1是对偶问题可行解
即 C-CBB
-1A≥0 或 检验数≥0
最优基B 可行基B
对偶可行基B
单纯形法
可行基B 保持可行性 对偶可行基B
对偶单纯形法
可行基B 保持对偶可行性 对偶可行基B
对偶单纯形法应用条件
应用前提：
有一个基，其对应的基满足:
① 单纯形表的检验数行全部非正（对偶
可行）；
② 变量取值可有负数（非可行解）。
对偶单纯形法步骤
找一个基（可以不是可行的），建立初始对偶
单纯形表，检验数全部非负；
若b列元素非负，则已经是最优基。反之，则
取相应行的基变量为出基变量；
为保证能对基的可行性有所改进，则将来的主
元应该为负数；为保证下一个基还能是对偶可
行基，应使检验数仍为非负的。
主元变换
例题:用对偶单纯形法求解
解:将上述模型转化为
cj -9 -12 -15 0 0 0
cB xB b x1 x2 x3 x4 x5 x6
0 x4 -10 -2 -2 -1 1 0 0
0 x5 -12 -2 -3 -1 0 1 0
0 x6 -14 -1 -1 -5 0 0 1 (-9/-1.-12/-1.
-15/-5)
cj
-Z′
0 -9 -12 -15 0 0 0
列初始单纯形表，取b中比较小的行对应的变量为
换出基变量。
cj -9 -12 -15 0 0 0
cB xB b x1 x2 x3 x4 x5 x6
0 x4 -36/5 -9/5 -9/5 0 1 0 -1/5
0 x5 -46/5 -9/5 -14/5 0 0 1 -1/5
-15 x3 14/5 1/5 1/5 1 0 0 -1/5 (-30/-9.-45/-14
.-15/-1)
-Z′ 42 -6 -9 0 0 0 -3
cj -9 -12 -15 0 0 0
cB xB b x1 x2 x3 x4 x5 x6
0 x4 -9/7 -
9/14
0 0 1 -9/14 -1/14
-12 x2 23/7 9/14 1 0 0 -5/14 1/14
(-3/-9.-45/-9.
-33/-
1)
-15 x3 15/7 1/14 0 1 0 1/14 -3/14
-Z′ 501/7 -
3/14
0 0 0 -
45/14
-
33/14
cj -9 -12 -15 0 0 0
cB xB b x1 x2 x3 x4 x5 x6
-9 x1 2 1 0 0 -14/9 1 1/9
-12 x2 2 0 1 0 1 -1 0
-15 x3 2 0 0 1 1/9 0 -
2/9
-Z′ 72 0 0 0 -1/3 -3 -
7/3
所以， X*=（2 . 2 . 2 . 0 . 0 . 0）
Z′* =－72，
原问题 Z* =72
其对偶问题的最优解为：
Y*= (1/3 . 3 . 7/3)，W*= 72
对偶单纯形法的优点和缺点
优点：
初始解可以是非可行解，当检验数都为负数时，就
可以进行基的变换，不需要加入人工变量。
当变量多于约束条件，用对偶单纯形法计算可以减
少计算工作量，因此对于变量较少，而约束条件很多
的线性规划问题，可以首先将它变换成为对偶问题，
然后用对偶单纯形法来求解。
在灵敏度分析中，有时需要使用对偶单纯形法，这
样可以使问题处理简化。
缺点：对于大多数的线性规划问题，很
难找到一个初始可行基，因而这个方法
在求解线性规划问题时很少单独应用。
单纯形法是在基本可行解中寻找满足最优性
条件（简约价值系数非负）的最优解
对偶单纯形法则是在所有满足最优性条件
（简约价值系数非负）的最优解中寻找满足
可行的最优解
单纯形法与对偶单纯形法
对偶单纯形法与单纯形法的区别补充
是是
是是
否否
否否
所有 所有
得到
最优解
计算 计算
典式对应原规划的
基本解是可行的
典式对应原规划的基
本解的检验数
所有 所有
计算计算
以为中心元素进行迭代 以为中心元素进行迭代
停
没
有
最
优
解
没
有
最
优
解
单纯形法 对偶单纯形法
