5.换基运算： 1 1
1 1
0 0
min Z 4x1 x2 3x3
x1 x2 x3 x4 5 x1 x2 4x3 x5 3 x1 , x2 , x3 , x4 , x5 0
单
x1 x2 x3 x4 x5 常数列
纯 形
x42 -1 -1
-1 -1
0
-5 (1)
表
x5 -1 1
式，可 用两阶 段法求
x1 , x2 , x3 , x4 , x5 0 解，麻
烦！
min Z 4x1 x2 3x3
x1 x2 x3 x4 5 x1 x2 4x3 x5 3 x1 , x2 , x3 , x4 , x5 0
注：对偶单纯形法适用于目标函数系数都 0，不等 式约束都 0 的问题。
单
x1 x2 x3 x4 x5 常数列
纯 形
x2 1
1
1 -1 0
5 (1)
表
x5 -2 0
3
11
-8
检验数 34 01
23
10 0
-05
二.对偶单纯形法的迭代步骤： 例2-8
2.最优性检验：
若当前常数列 0，则得到最
优表。否则转下一步。
min Z 4x1 x2 3x3
x1 x2 x3 x4 5 x1 x2 4x3 x5 3 x1 , x2 , x3 , x4 , x5 0
优 表
检验数
0
x4
x5 常数 min Z 2x1 2x2 x4
0
x1 x2 x3 5
x1 x2 x4 6 6x1 2x2 x5 21
x1, x2 , x3 , x4 , x5 0
一.对偶单纯形法与单纯形法的区别： 不同之处：
单纯形法：在迭代过程中，始终保持常数列 0 ，而 检验数行由有负检验数逐步变为全部 0
00
x4 x5 常数列
1 0 -5
01 00
-3
0 0
有负分量
注：检验数行 0 ，因此可以用对偶单纯形法求解，
否则不能用。
二.对偶单纯形法的迭代步骤： 例2-8
2.最优性检验：
min Z 4x1 x2 3x3
若当前常数列 0，则得
x1 x2 x3 x4 5
到最优表。否则转下一步。 x1 x2 4x3 x5 3
x1 , x2 , x3 , x4 , x5 0
单
x1 x2 x3 x4 x5 常数列
纯 形
x4 -1 -1 -1
10
-5
表
x5 -1 1
4
01
-3
检验数 4 1
3
00
0 0
有负分量
二.对偶单纯形法的迭代步骤： 例2-8
3.确定出基变量：
min Z 4x1 x2 3x3
将常数列中最负分量所在的
检验数
0
二.对偶单纯形法的迭ห้องสมุดไป่ตู้步骤： 求解例2-8
min Z 4x1 x2 3x3
x1 x2 x3 5 标准形 x1 x2 4x3 3 x1, x2 , x3 0
min Z 4x1 x2 3x3 不是典
x1 x2 x3 x4 5 x1 x2 4x3 x5 3
对偶单纯形法：在迭代过程中，始终保持检验数行 0 ， 而常数列由有负分量逐步变为全部 0
最
x1 x2
x3
x4
x5 常数 min Z 2x1 2x2 x4
优
x1 x2 x3 5
表
0
x1 x2 x4 6 6x1 2x2 x5 21
x1, x2 , x3 , x4 , x5 0
4
01
-3
检验数 4 1
3
00
0 0
二.对偶单纯形法的迭代步骤： 例2-8
5.换基运算： 1 1
1 1
0 0
min Z 4x1 x2 3x3
x1 x2 x3 x4 5 x1 x2 4x3 x5 3 x1 , x2 , x3 , x4 , x5 0
单
x1 x2 x3 x4 x5 常数列
二.对偶单纯形法的迭代步骤： 例2-8
1.建立初始单纯形表
j cj CBB1 pj
CB B1b
cj 4 1
3
单 CB
x1 x2 x3
纯0
形 表
0
x4 x5
-1 -1
-1 1
-1 4
检验数 4 1
3
min Z 4x1 x2 3x3
x1 x2 x3 x4 5 x1 x2 4x3 x5 3 x1 , x2 , x3 , x4 , x5 0
纯 形
x2 1
1
1 -1 0
5 (1)
表
x5 --21 10
43
01 1
--38
检验数 4 1
3
00
0 0
二.对偶单纯形法的迭代步骤： 例2-8
5.换基运算： 1 1
1 1
0 0
min Z 4x1 x2 3x3
x1 x2 x3 x4 5 x1 x2 4x3 x5 3 x1 , x2 , x3 , x4 , x5 0
基。
单
x1 x2 x3 x4 x5 常数列
纯 形
x4 -1 -1 -1
10
-5
表
x5 -1 1
4
01
-3
检验数 4 1
3
00
0 0
min{ 4 , 1 , 3 } 1 1 1 1 1
x2为进基变量。若出基变量所在的行中，
所有元素都 0 ，则原问题无可行解。停止计算。
二.对偶单纯形法的迭代步骤： 例2-8
00
0 0
有负分量
二.对偶单纯形法的迭代步骤： 例2-8
4.确定进基变量：
min Z 4x1 x2 3x3
在出基变量所在的行中，找出非基变 量列中的负系数，用相应的检验数分 别除以这些负系数，再取绝对值，所
x1 x2 x3 x4 5 x1 x2 4x3 x5 3
得正比值中最小者相应的非基变量进 x1, x2 , x3 , x4 , x5 0
第二章 线性规划的对偶理论
2.1 对偶线性规划模型 2.2 对偶问题的性质 2.3 对偶单纯形法 2.4 灵敏度分析与参数分析
一.对偶单纯形法与单纯形法的区别：
相同之处：对偶单纯形法与单纯形法都是对单纯形表 进行迭代计算。
当常数列 0，而检验数行都 0 时，单
纯形表是最优表。
最 x1 x2 x3
x1 x2 x3 x4 5
行相应的基变量出基。
x1 x2 4x3 x5 3
min{5, 3} 5 x4为出基变量 x1, x2 , x3 , x4 , x5 0
单
x1 x2 x3 x4 x5 常数列
纯 形
x4 -1 -1 -1
10
-5
表
x5 -1 1
4
01
-3
检验数 4 1
3
单
x1 x2 x3 x4 x5