已知 b x1 x2
b '1

A
bm'
c0m 0cn
xm xn min
— 24/6 5/1
z0
检验数
单纯形表
单纯形表结构
c j
2
CX
B
B
b
x1
c1 x1 b '1

cm xm bm'
c j

z j
z0
基可行解：
X (b1,, bm ,0,,0)
1
0C 0 0
Z c1x1 ... cm xm cm1xm1 ... cn xn 0
单纯形表
- Z x1 基x变2量..X.B xm
0 1
0 1B

基矩....阵...
0
1
1 c1 c20... cm
xm非1基.变..量.XxN n
a1m1 ...a1n
30
xx
2
3
21
00
40
30
0
xx
4
5
0
1
0
0
X 0 (0, 0,8,16,12)T
表1：列初始单纯形表
（单位矩阵对应的变量为基变量）
c j
CX
B
B
b
x x x x x 2
0 1
3
2
00
最小的值对应的行

为主行
3
4
5 min
0
x 3
8
1 21 0
4
0
x 4
16 0 4
0
0
1
—
0
x 5
12
xn min
c1 x1 b '1 Z Z0 j x j

A jm1
cm xm bm'
— 24/6 5/1
z c z
j
求j 0
有时不写
此项
检验数
m
m
令：Z0 cibi' 单纯形表 i1
Z j ciai'j
i 1
n
Z 单Z纯0 形j表m1(结c j 构 Z j )x j
00
4
0
0
3
c z
j
j
12
3 0主元化0为1
0
主列单位向量
正检验数中最大者对应的列 为主列
x5 换出
x2 换入
表2：基变换
（初等行变换，主列化为单位向量，主元为1）
c j
CX
B
B
b
x x x x x 2
0 1
3
2
0 0 最小的值对应的行 为主行

3
45 min0 Nhomakorabeax 3
2
1 0 1 0 -2
0
x 4
16 1/24
3 x2 3 0 0
c z
j
j
1/42
z 33 9
00 1
4
1主元化0为1 0
—
主列单位向量
0 x30换出
-
0 x1 换入 3/4
正检验数中最大者对应的列
X 1 (为0,主3列, 2,16, 0)T
表3：基变换
（初等行变换，主列化为单位向量，主元为1）
c j
CX
x1

x2

a1m1xm1 ..... a1n xn b1 a2m1xm1 ..... a2n xn b2 ...................................

xm amm1xm1 ..... amn xn bm
x2 xmxn min
—
A
24/6 5/1
检验数
单纯形表令：Z0

m
cibi'
i 1
m
Z j ciai'j i 1
n
单纯形表结构Z Z0 (c j Z j )x j
c j
CX
B
B
j m1
b
2令x1：1xj 2
(c
n
j0CZ
j
)
0
xm
0 检验 数
单纯形表结构 i


a
bi'
' imk
a' imk

0


bl' a'
lmk
c j
2
CX
B
B
b
x1
c1 x1 b '1

cm xm bm'
z c z
j
j0
1 0C
x2
A
0 0
xm xn min
a1,mk 主行 —
am ,mk
25求4/1l/6
检验数 mk
B
B
230 0

b
0x x x x
1
2
3
4
x5 min
2 x1
0 3
xx 42
21 8 1/20 3 20
01 0 -4 10
0-—
1
4
0
12
c z
j
j
1/40 0 -2
0
z* 2 2 313/4 13
X 2 (2,3, 0,8, 0)T
表4：最终单纯形表
c j
2
x b C X
...
......
amm1
...
m
cm1 ciai,m1 i 1
xn
a1n a2n
amn
m
cn ciain i 1
b

b1

b2


bm


m i 1
cibi

单纯形表
单纯形表结构
c j
CX
B
B
c1 x1
cm xm
c z
j
j
C 2c1 c1 2 0
令：c j j
(c j

Z
j2)
x n
b ZCB Z0XB j x j 1
c1
x1j m
1
b
'
1

cm xm bm'
1 检验 0C数 0 c j0

x2 xmxn min
a1 j
—
A

24/6
am j
5/1
z c z
j
j0
检验数 求j
单纯形表
min
a2mN1 ...a2n ...非... 基阵
a mm 1 ...a mn cm1 N cn
b
b1
b2


bm 0

单纯形表
-Z x1 x2... xm


0
1
0 1

.......
0
1

1 0 0 ... 0
xm1
....
a1m1
...
a2m1
第四节 单纯形法的计算步骤
单纯 为书写规范和便于计算，对单纯形法的计算设计了 形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯 形表称为初始单纯形表，含最优解的单纯形表称为最 终单纯形表。本节介绍用单纯形表计算线性规划问题的
步骤。
在上一单节纯单纯形形表法迭代原理中可知，每一
次迭代计算只要表示出当前的约束方程组 及目标函数即可。
B
B
x1 2x2 x3
8
s.t.
4
x1

4 x2
x4
16
x5 12
x1, x2 , x3, x4 , x5 0
表1：列初始单纯形表
（单位矩阵对应的变量为基变量）
c j
CX
B
B
b
0
x 3
8
0
x 4
16
0 x 12 5
c z
j
j
z0
2
0x 1
1 04 00 12 0
不妨设此为
主列
单纯形表
单纯形表结构
c j
2
CX
B
B
b
x1
c1 x1 b '1

cm xm bm'
z c z
j
j0
主元
1 0C
x2
A
0 0
xm xn min
a1,mk
—
a l,m k
am ,mk
254/1l/6
检验数 mk
用单纯形表求解例1
max z 2x1 3x2 0x3 0x4 0x5