CB XB 检验数
CB XB I 0
CN XN B N CN-CBB N
8
-1
B b
-1
-1
例：用单纯形表求解
max z 2 x1 3 x2 2 x1 x2 4 s.t. x1 2 x2 5 x , x 0 1 2
画初始单纯形表：
max z 2 x1 3 x2 4 2 x1 x2 x3 s.t. x1 2 x2 x4 5 x , x , x , x 0 1 2 3 4
School of Business ECUST
3.3.2 单纯形表结构
z c1b1 c2b ... cmbm m 1 c2 a2, m 1 ... cm am , m 1 xm 1 cm 1 c1a1, m 2 c2 a2, m 2 ... cm am , m 2 xm 2 cm 2 c1a1, ... n c2 a2 n ... cm amn xn cn c1a1
1-3 线性规划单纯形表、计算步骤与矩阵描述
1
3.3 单纯形法 3.3.1 单纯形法的一般思路+例子 3.3.2 单纯形表结构+例子 3.3.3 单纯形法的计算步骤 3.3.4 单纯形法的矩阵描述 3.4 大M法 3.5 两阶段法 4 几种特殊情况 4.1 无可行解 4.2 无界解 4.3 多重最优解 4.4 进基变量的相持 4.5 出基变量的相持
40 x2 25/8 1 5/8 35/4
0 x3 1 0 0 0
0 x4 0 1 0 0
0 x5 RHS 比值 -3/8 75/2 12 0 20 20 1/8 75/2 60 -25/4
当前基本可行解：(75/2, 0, 75/2, 20, 0) , Z=1875
16
40 0 50
x2 x4 x1 检验数

_ 3/1 8/2 4/1 -
j
1
1 0
2
0 1
0
1 0
0
0 1
0
0 0
0
0 2 1
j
x5
x3 x2 x1
1
1 0 0 1 0
0
0 0 1 0 0
T
0
0 1 0 0 0
-2
-2 2 1 -2 0
1
0 -1 0 1 -1
2
2 3 2
2/1
2/2 3/1 -
j
X 2,3, 2, 0, 0
假定：(1) 该线性规划问题的可行域不为空集； (2) 所有的可行解不退化； (3) 已找到一个初始可行基B(由A的前m个列向量 构成)。
School of Business ECUST
B
N
T
A P , P ,..., P , P ,...., P 1 2 m m 1 n
X x , x ,..., x , x ,..., x 1 2 m m 1 n XB XN
minZ=-x1 -2x 2 x3 4 x1 x2 x4 3 x5 8 x1 2x 2 x j 0 ，j 1,2,3,4,5
解：本题的目标函数是求极小化的线性函数， 可以令 则
Z' = -Z = x1 +2x 2
minZ=-x1 -2x 2 max Z ' x1 +2x 2
b 4 5
cj
CB 0 0 XB x3 x4
2 x1 2 1
3 x2 1 2
0 x3 1 0
0 x4 0 1

4/1 5/2
j
0 3 x3 x2
2
3/2 1/2 1/2 1 0
3
0 1 0 0 1
0
1 0 0 2/3 -1/3
0
-1/2 1/2 -3/2 -1/3 2/3 1 2 3/2 5/2 1 5
（1）找出初始可行基，给出初始基本可行解，建立 初始单纯形表。 （2）检验各非基变量的检验数，如果所有检验数都 大于等于0，则已得到最优解；否则，转下一步。 （3）负检验数最小对应的变量作为换入变量；极小 比值准则决定换出变量；迭代运算。
（4）重复（2）（3）直到得到最优解。
22
练习：求解下列线性规划问题
这两个线性规划问题具有相同的可行域和最优解，
只是目标函数相差一个符号而已。
School of Business ECUST
C CB 0 0 0 0 2 XB x3 x4 x5 x3 x2
1 x1 1 0 1
2 x2 0 1 2
0 x3 1 0 0
0 x4 0 1 0
0 x5 0 0 1 b 4 3 8 4 3
i 1 m
School of Business ECUST
单纯形原理
设标准的线性规划问题为 max z= s.t. CX AX=b X0 矩阵A可以分块记为A=[B，N] 相应地，向量X和C可以记为
XB X , C C B XN CN
6
AX=b可以写成 BXB+NXN=b 即 XB=B-1b-B-1NXN 对于一个确定的基B，目标函数z可以写成
min z x1 2 x2 x1 x2 3 x 2 1 s.t. 3x1 2 x2 1 x1 , x2 0
School of Business ECUST
3.3.4 单纯形法的矩阵描述
考虑标准形式的线性规划问题：
max z CX AX b s.t. X0
maxZ' =8 or minZ=-8
School of Business ECUST
因为非基变量x4的检验数σ4=0，由无穷多最优解判别定理，本例 的线性规划问题存在无穷多最优解。事实上若以x4为换入变量，以x3为 换出变量，再进行一次迭代，可得一下单纯形表：
C CB 0 2 1 XB x4 x2 x1 1 x1 0 0 1 0
x1 x2 : z CX c1, c 2,..., c m, c m 1,..., c n xm C B, C N x CB CN m 1 : xn



50 x1 0 0 1 0
40 x2 1 0 0 0
0 x3 8/25 -8/25 -5/25 -14/5
0 x4 0 1 0 0
0 x5 RHS 比值 -3/25 12 3/25 8 5/25 30 -26/5
当前基本可行解：(30, 12, 0, 8, 0) , Z=1980
17
例: 用单纯形表方法求解线性规划问题
j
2 3 x1 x2
j
0
0
-1/3
-4/3
最优解：x1=1,x2=2,x3=0,x4=0
School of Business ECUST
3.3.3 单纯形法的计算步骤（max）
（1）将线性规划问题转化为标准型，找出初始可行 基，给出初始基本可行解，建立初始单纯形表。 （2）检验各非基变量的检验数，如果所有检验数都 小于等于0，则已得到最优解；否则，转下一步。 （3）正检验数最大对应的变量作为换入变量；极小 比值准则决定换出变量；迭代运算。
（4）重复（2）（3）直到得到最优解。
11
习题
max s.t.
z=
50x1 3x1
+40x2 +5x2 x2 ≤150 ≤ 20
8x1
x1,
+5x2
x2
≤300
≥ 0
12
Байду номын сангаас
X2 60 50 40 30 20 10
A
X1=0
E
X5=0
D C
X4=0 X3=0
B
(2)
X2=0 50
(3) (1)
10
T
2 x2 0 1 0 0
0 x3 1/2 -1/2 1 0
0 x4 1 0 0 0
0 x5 -1/2 1/2 0 -1
b 1 2 4 8

j
最优解 X 4, 2, 0,1, 0 最优解的一般表示式

最优值
T
maxZ' =8 or minZ=-8
T
X (2,3, 2, 0, 0) (1 ) 4, 2, 0,1, 0 , 0 1.
i 1
School of Business ECUST
m
, j 1,2,..., n j c j ci aij
i 1
m
c1 c2 … cm cm+1 … cn
c1 c2 ... cm
m 1 ... a1 n 1 0 ... 0 a1, m 1 ... a2 n 0 1 ... 0 a2, ...... , m 1 ... amn 0 0 ... 1 am
0 0 … 0
cm 1
m i 1
j
….
cn
m i 1
ci ai, m 1 c a i i,n
School of Business ECUST
单纯形表 cj
CB XB
c1
x1
c2 … cm
x2 … xm
cm+1 … cn
xm+1 … xn
b
b1 b2 ... bm
20
30
40
X1
13
标准化
max z= s.t.
50x1 3x1
+40x2 +5x2 x2 ＋x3 +x4 +x5 x3, x4, x5 =150 = 20 =300 ≥ 0 (1) (2) (3)