max z 2 x1 3 x2 4 x3 0 x4 0 x5 x1 2 x2 x3 x4 1 2 x1 x2 3 x3 x5 4 x 0( j 1, 2 , 3 , 4 , 5 ) j
§3.6 对偶单纯形法
基变量出基，不影响计算结果，只是迭代次数可能不一样。
§3.6 对偶单纯形法
• 利用对偶单纯形法求解以下线性规划问题：
Page 21
max z x1 3 x2 2 x1 x2 x3 3 4 3 x1 2 x2 s.t . 1 x1 2 x2 x1 , x2 , x3 0
cj zj c k zk min alj 0 j a alk lj
§3.6 对偶单纯形法
Page 12
按θ规则所对应的列的非基变量xk为换入变量，这样才能保持 得到的对偶问题解仍为可行解。 Step4 以αlk为主元素，按原单纯形法在表中进行迭代运算，得 到新的计算表。 重复步骤Step1-4。
x5
0 0 1 0

j
cj-zj
-2 -3 -1 -1 1/3 x3 -1/3 0 x1 4/3 1 x5 1/3 0 0
0 0 1 0
0 0 1 0
此时所有的 B-1b均≥0 ， 且所有的cjzj均≤0，此 时已得到最 优解为：
X*=(3/2,0,0, 1/2,1/2)T Z*=-3/2

j
0 -1 0

Page 7
对偶单纯形法原理
对偶单纯形法是求解线性规划的另一个基本方法。它
是根据对偶原理和单纯形法原理而设计出来的。

注意：对偶单纯形法是一种求解线性规划的方法，而不
是去求对偶问题的单纯形法。
§3.6 对偶单纯形法

Page 8
对偶单纯形法的思路： 以保持对偶问题可行为条件，即不论进行何种基
变换，必须保持所有的检验数非正，同时取消原问题必
§3.6 对偶单纯形法
Page 19
(3)当变量多于约束条件的LP问题用对偶单纯形法计算可以
减少计算工作量，因此对变量较少而约束条件很多的LP问题，
可先将它变换成对偶问题，然后用对偶单纯形法求解。 (4)单纯形法的最小比值是min bi aik 0 i aik 其目的是保证下一个原问题的基本解可行。
Page 15
解:（1）将模型化为下列形式，因为对偶问题可行，即全部 检验数≤0（求max问题）。
max Z 9 x1 12 x2 15 x3 10 2 x1 2 x2 x3 x4 2 x 3 x x x5 12 1 2 3 x6 14 x1 x2 5 x3 x1 , , x6 0
§3.6 对偶单纯形法
cj XB x4 x5 x6 -9 x1 -2 -2 -1 -9 -12 x2 -2 -3 -1 -12 -15 x3 -1 -1 -5 -15 0 x4 1 0 0 0 0 x5 0 1 0 0 0 x6 0 0 1 0
Page 16
CB 0 0 0
b -10 -12 -14
22
CB XB b x3 -3 0 0 x4 -4 0 x5 -1 cj-zj
0 -1 0
x1
x2
-1 -2 -2 -3 3/2 1/3 2/3 -4/3 -7/3 -1/2 ½ -3/2 -5/2
x3
1 0 0 0 1 0 0 0 -3/2 -1/2 -1/2 -1/2
x4
0 1 0 0 -2/3 -1/3 -1/3 -1/3 1/2 1 0 0 0
应注意的问题：
Page 18
(1)单纯形法换基顺序：先确定进基变量后确定出基变量； 对偶单纯形法换基顺序：先确定出基变量后确定进基变量。 (2) 初始解可以是非可行解，但初始表中一定要满足对 偶问题可行 ( 即检验数都为负数 ) ， 就可以进行基变换，不 需要加入人工变量，因此对偶单纯形法可以简化计算。
对偶 问题 最优 表
XB
y2 y3
j
b
1/4 1/2
对偶问题的变量 y1 -4/5 15/2 15/2 y2 1 0 0 y3 0 1 0
§3.6 对偶单纯形法
Page 5
由原问题和对偶问题的解之间关系：b列元素是原问题的 基可行解，而检验数行是对偶问题的基解。单纯形法迭代到 对偶问题的解也是可行解（检验数非正）时，则对偶理论知 原问题和对偶问题此时都达到最优解。 单纯形法的求解过程是：在保持原问题可行(b列数字保 持≥０）的前提下，通过逐步迭代实现对偶问题可行（检验 数行≤０）。
-9/7 23/7 15/7
Page 17
-9 x1
-9/14 9/14 1/14 -3/14
-12 x2 0 1 0 0 0 1
-15 x3 0 0 1 0 0 0
0 x4 1 0 -5/14 1/14
0 x6
-1/14 1/14 -3/14
60/3 10/1 20/1
须可行（常数列的非负限制）的要求，通过基变换使原 问题在非可行解的基础上逐步转换成基本可行解，一旦
原问题的基本解可行，则该基本可行解也就是最优解。
§3.6 对偶单纯形法
找出一个DP的可行基
Page 9
LP是否可行 （XB ≥0） 循 环 否
是
最优解
结束
保持DP为可行解情况下转移到LP 的另一个基本解
§3.6 对偶单纯形法


Page 10
单纯形法和对偶单纯形法的思路不同：
单纯形法
在保持原问题可行解的前提下，通过基变换使对偶问题在非可 行解的基础上向可行解的方向迭代。

对偶单纯形法
在保持对偶问题可行解的前提下，通过基变换使原问题在非可 行解基础上向可行解的方向迭代。 单纯形法 保持 最优准则 B-1b ≥0 cj-zj≤0 对偶单纯形法 c j- z j≤ 0 B-1b ≥0
§3.6 对偶单纯形法
例3.8 用对偶单纯形法求解： min w 2 x1 3 x2 4 x3
Page 13
x1 2 x2 x3 1 2 x1 x2 3 x3 4 x 0( j 1, 2 , 3 ) j
解:（1）将模型化为下列形式，因为对偶问题可行，即全部 检验数≤0（求max问题）。
解法
cj
-1 -3 0 0 0
max z x1 3 x2 0 x4 0 x5 2 x1 x2 x3 Page 3 3 x1 2 x2 x4 4 s.t. x1 2 x2 x5 1 0, ( j 1,2,3,4,5) x j
-45/14 -33/14
2 2
1 0
1 -1
1/9
0
-2/9
-7/3
-15
x3
2
0 0
0 0
1 0
1/9
-1/3
0 -3
原问题的最优解为：X*=（2 , 2 , 2 , 0 , 0 , 0），Z* =72
其对偶问题的最优解为：Y*= （1/3 , 3 , 7/3），W*= 72
§3.6 对偶单纯形法
b -1 -4
-2/-2 -4/-3
最优解：x1* = 2，x2* = 0，x3* = 0，x4* = 1，x5* = 0 目标值：w* = -z* = 4
§3.6 对偶单纯形法
例3.9 用对偶单纯形法求解：
min Z 9 x1 12x 2 15x 3 2 x1 2 x 2 x 3 10 2 x1 3 x 2 x 3 12 x1 x 2 5 x 3 14 x j 0( j 1.2.3)
§3.6 对偶单纯形法
3.6.2 对偶单纯形法的计算步骤
Page 11
Step1 列出初始单纯形表。 若b列的数都非负，检验数都非正，则已得最优解，停止 计算。若b列的数至少有一个负分量，检验数保持非正，则 转入下一步。 Step2 确定换出变量。按min｛(B-1b)i｜(B-1b)i＜0}＝(B-1b)l对应 的基变量xl为换出变量。 Step3 确定换入变量。检查xl所在行的系数。 若所有系数都非负，则无可行解，停止计算。 若存在某个系数小于零, 计算
cj XB x4 x5 x4 x1 -2 x1 -1 -2 -2 0 -2 1 2 0 1 0 -3 x2 -2 1 -3 -5/2 -1/2 -4 -4 x3 -1 -3 -4 1/2 3/2 -1 0 x4 1 0 0 1 0 0 0 x5 0 1 0 -1/2 -1/2 -1
Page 14
CB 0 0
cj-zj
x4 x1 x5
½ 3/2 1/2 -3/2
0 1 0 0
小结
学习要点：
Page 23
1.对偶单纯形法
The end,thank you!
Page 3
§3.6 对偶单纯形法
§3.6 对偶单纯形法
原问 题最 优表
Page 4
XB x3
b 15/2
原问题的变量
x1 0 x2 0
原问题的松弛变量
x3 1 x4 5/4 x5 -15/2
x1 x2
7/2 3/2
j
1 0 0
0 1 0
0 0 0
1/4 -1/4
-1/2 3/2
－1/4 －1/2 对偶问题的剩余变量 y4 -1/4 1/2 7/2 y5 1/4 -3/2 3/2
-9/-1 -12/-1 -15/-5
0 0 -15
x4 x5 x3
-36/5 -9/5 -9/5 -46/5 -9/5 -14/5 14/5 1/5 1/5 -6 -9