单纯形法例题讲解
基可行解
单纯形法是针对标准形式的线性规划问题进行演算的，任何线性规划问题都可以化为标准形式。
min cx f = （1） s.t b Ax = （2）
0≥x （3）
其中 T
m mn m m n n T n n b b b b a a a a a a a a a A x x x x c c c c )...,(,............
...
...,
),...,,(),,...,(212
1
22221112
112121=???
???????????=== 假设1≥≥m n ，并设系数矩阵A 的秩为m ，即
设约束方程（2）中没有多余的方程，用j
p 表示A 的第j 列，于是（2可写成
b
p x
m
k j j
=∑=1
（4）
矩阵A 的任意一个m 阶非奇异子方阵为LP 的一个基（或基阵），若
),...,(21jm j j p p p B = （5）
是一个基，则对应变量jm j j x x x ,...,,21，称关于B 的基变量，其余变量成为关于B 的非基变量，若令非基变量都取零值，则（4）变为
b
p x
m
k jk jk
=∑=1
（6）
由于此方程组的系数矩阵B 是满秩方阵，故知（6）有唯一解，记为T
jn j j x x x )
,...,,()0()
0(2)
0(1于是按分量
{}{}),...,,\,...2,1(0)
,....3,2,1(21)
0(m j jk jk j j j n j x m k x x ∈===
所构成的向量)
0(x
是约束方程组b Ax =的一个
解，称此)0(x 为LP 的对应于基B 的基解
（或基本解），也可称为方程组b Ax =的一个基解，如果)
0(x
为一基解，且满足
0)0(≥x 即它的所有分量都非负，则称此)
0(x 是LP 的一个基可行解，基可行解对应的基
称为可行基。
设对应基阵),...,(21m p p p B =，即m x x x ,...,,21为基变量，n m m x x x ,...,,21++ 是非
基变量，记
)
,...,,()
,...,,()
,...,,(212121n m m T
n m m n T
m B p p p N x x x x x x x x ++++===
从而A=（B,N ）,相应地分划),(N B c c c =,约
束方程（2）可以写成
b x x N B n B =???
?
??),( 即b Nx Bx N B =+由此解得
N B Nx B b B x 1
1---= （7）
这是用非基变量表达基变量的公式 在（7）中令 0=N x 而知
()
T
m B
x x x
x b B )
,...,,()0()
0(2)
0(1
01
==-
求解线性规划问题 min 4212x x x f +-=
t s . 223531
=++x x x
22432=+-x x x 5532=++x x x
)5,4,3,2,1(0
=≥j x j 已知初始可行基=0B
于是可列出0
B 对应的单纯形表)(0B T ,如表所示
从表可以看出，检验数中仅有02≥ λ，故取2
x 为进基变量，由于最小比值
12200min 2=?
?????>i i b b b i
在第32行取得，故取第2行对应的基变量4x 为离基变量，于是元素122
=b 是上表的枢元
为求出新基()321
1
p p
p
B=对应的单纯形表，对)(0B T作初等形变换，使2x对应的列变为单位列向量。在上表中枢元