-1/3
0 -1
2/3
η=0
两阶段法
第二阶段：将解（4/3，1/3，0，0，1/3） 作为原始线性规划问题的可行解，并将第 一阶段得到的约束条件一起进行运算
Page 19
cj CB -2 -1 0 xB x1 X2 X5
-2 x1 1 0 0
-1 x2 0 1 0
0 x3 -2/3 1/3 -1/3
首先：转化为标准形式，增加松弛变量、剩余 变量和人工变量
max z 3x1 2 x2 0 x3 0 x4 Mx5 2 x1 x2 x3 2 s.t. 3x1 4 x2 x4 x5 12 x ,x ,x ,x ,x 0 4 1 2 3 Page 95
max z 3x1 x2 x3
3x1 x4 2 x5 12 x x5 1 2 2 x1 x3 1 x j 0, j 1,...,5
Page 27
cj
CB 0 xB X4
3
x1 3
-1
x2 0
-1
x3 0
0
x4 1
0
x5 -2 b 12 Ө 4
x5 0 b 2 Ө 2
-1
x5
sacj impj
3
-3
3
4
-4
4
0
0
0
-1
1
-1
1
-1
0
12
η=-12 2 4 η=-4
3
0 -1
x2 x5 sacj impj
2 -5
5 -5
1 0 0
0
1 -4 4 -4
Page 22
0 -1
0 1
-1 0
1
-1
得到最优解（0，2，0，0，4），此时 x 依然在基中，所以原问题没有最优解。
Page 12
两阶段法
第一阶段的目的：是设法把人工变量从基 内调出来，寻找原问题（未加人工变量前 的线性规划问题）的一个基本可行解。具 体作法如下：
不考虑原问题的目标函数，构造一个辅助目标 函数，使所有人工变量的和最小。设有L个人 工变量，构造如下的辅助目标函数：
min w xn 1 xn 2 xn L
X3 sacj impj
0
-2 0 0
1
0 -1
1
0
1 0 0
0
0 0 0
-1
0 1 -1
1
0 -1 0
0
1 0
-1
1
1 z=-1
1
-
0
0
X4
X2
3
0
0
1
0
0
1
0
-2
-1
2
1
-1
0
12
1
0
X3
sacj impj
-2
0 0
0
0
0
1
0 0
0
0 0
Page 26
0
0 0
0
0 -1
1
0
1
z=0
-1
进入第二阶段：带入初始可行解（0，1，1， 12，0）和上一阶段的约束条件
第二章 线性规划的单纯形法
本章重点
单纯形法的基本概念和思想
单纯形法的计算步骤
大M法和两阶段法 退化问题
Page 2
单纯形法的基本思想
不容易
寻找一组初始基本变量
直接观察，在线性规划中存在m个基本变量 如果约束条件都是≤约束，将增加的松弛变量 作为基本变量，得到一组基本可行解
a x
0
0
1
0
0
1/3
0
-2/3
-1
4
1
-1
x3
sacj impj
0
3 0
0
-1
0
1
-1 0
2/3
1/3 -1/3
Page 8
-4/3
1/3 -1/3
9
η=2
大M法
例：用大M法求解线性规划问题
max z 3x1 2 x2 2 x1 x2 2 s.t. 3 x1 4 x2 12 x ,x 0 1 2
-M
-1
x6
x3 sacj impj
0
-2 2 1
1
0 -M
M-1
0
1 -1 0
0
0 0 0
-1
0 M -M
1
0 -M 0
-2
1
2M-1
-3M-1
1
1
1
— η=-M-1
0
-1
x4
x2
3
0
0
1
0
0
1
0
-2
-1
2
1
-5
-2
12
1
4
-
-1
x3
sacj impj
-2
2 1
0
-1
0
1
-1 0
0
0 0
Page 7
max z 3 x1 x2 x3 x1 2 x2 x3 11 4 x x 2 x 3 1 2 3 s.t. 2 x1 x3 1 xi 0
Page 4
大M法
转化为标准形式
基变量？？
max z 3 x1 x2 x3 x1 2 x2 x3 s1 11 4 x x 2 x s 3 1 2 3 2 M是任意大的正数，所以目标 s.t. x3 1 2 x1 函数取得最大值时 6 7 xi 0
Page 5
cj
CB 0 xB x4
3
x1 1
-1
x2 -2
-1
x3 1
0
x4 1
0
x5 0
-M
x6 0
-M
x7 0 b 11 Ө 11
-M
-M
x6
x7 sacj impj
-4
-2 6M
3-6M
1
0 -M
-1+M
2
1 -3M
3M-1
0
0 0
0
-1
0 M
-M
1
0 -M
0
0
1 -M
0
3
1
1.5
1 η=-4M
s.t.
max w x5
2 x1 x2 x3 2 3 x1 4 x2 x4 x5 12 x ,x ,x ,x ,x 0 1 2 3 4 5
Page 21
cj
CB 0 xB X3
0
x1 2
0
x2 1
0
x3 1
0
x4 0
2 x1 x2 x3 2 3 x1 4 x2 x4 x5 12 x ,x ,x ,x ,x 0 1 2 3 4 5 -1
-1
-1
X2
0
0 0
2
3
1 -3
1
1
0 -1
-1
-1
0 1
-1
0
1 0
0
-1
0 1
0
1
0
-1 0
1
1ቤተ መጻሕፍቲ ባይዱ
1/3
1 η=-1
0
0
x1
X2
1
0
0
1
-2/3
1/3
-1/3
-1/3
0
0
2/3
-1/3
1/3
1/3
4/3
1/3
0
X5
sacj impj
0
0 0
0
0 0
-1/3
0 0
1/3
0 0
Page 18
1
0 0
1/3
0 -1
cj
CB 0 xB X3
3
x1 2
2
x2 1
0
x3 1
0
x4 0
-M
x5 0 b 2 Ө 2
-M
x5
sacj impj
3
-3M
3+3M
4
-4M
2+4M
0
0
0
-1
M
-M
1
-M
0
12
3
η=-12M 10 4 η=-4M+20
2 -M
x2 x5 sacj impj
2 -5
4+5M 1-5M
1 0 2
0
1 -4
0
-M
x4
x6
3
0
-2
1
0
0
1
0
0
-1
0
1
-1
-2
10
1
1
-1
x3
sacj impj
-2
2 1
0
-M
M-1
1
-1 0
0
0 0
Page 6
0
M -M
0
-M 0
1
2M-1
1
—
η=-M-1
-3M-1
cj
CB 0 xB x4
3
x1 3
-1
x2 -2
-1
x3 0
0
x4 1
0
x5 0
-M
x6 0
-M
x7 -1 b 10 Ө -
第二阶段：以第一阶段求得最优解作为初始基本 可行解，求原问题的最优解。
以第一阶段求得最优解作为初始基本可行解，再用第 一阶段求得最优解时的约束条件和原问题的目标函数 进行迭代，直到求出最优解。