ai1x10

ai2x2

ai
x

bi
使原条件写成
axi
1x110ai
x
x
1bi
f2单纯形法
21单纯形法的基本原理
单纯形法迭代原理：（1）确定初始可行解
①当线性规划问题的所有约束条件均为≤号时，松弛变量对应的系数矩阵即为单位矩阵，以松弛变量为基变量可确定基可行解。
②对约束条件含≥号或号时，可构造人工基，人为产生一个m×m单位矩阵用大M法或两阶段法获得初始基可行解。
（2）最优性检验与解的判别（目标函数极大型）①当所有变量对应的检验数均非正时，现有的基可行解即为最优解。若存在某个非基变量的检验数为零时，线性规划问题有无穷多最优解；当所有非基变量的检验数均严格小于零时，线性规划问题具有唯一最优解。②若存在某个非基变量的检验数大于零，而该非基变量对应的系数均非正，则该线性规划问题具有无界解（无最优解）。③当存在某些非基变量的检验数大于零，需要找一个新的基可行解，基要进行基变换。
21确定初始可行解
确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定，为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m个系数列向量恰好构成一个可行基，即Ａ（ＢＮ），其中Ｂ（Ｐ1，Ｐ2，…Ｐm）为基变量x1，x2，…xm的系数列向量构成的可行基，ＮＰm1，Pm2，…P
为非基变量xm1，xm2，…x
的系数列向量构成的矩阵。
所以约束方程
AXb
就可以表示为
AXBN

XBXN

BXB
NX
N
b
用可行基Ｂ的逆阵Ｂ1左乘等式两端，再通过移项可推得：XBB1bB1NXN
若令所有非基变量XN0，则基变量XBB1b
f由此可得初始的基本可行解
X

B1b

0
22最优性检验
假如已求得一个基本可行解
X

B1b0

，将这一基本可行解代入目标函数，可求得相
应的目标函数值
ZCXCBCN


B1b0

CBB1b
其中CBc1c2cmCNcm1cm2c
分别表示基变量和非基变量所对应的价
值系数子向量。
要判定ZCBB1b是否已经达到最大值，只需将XBB1bB1NXN代入目标函数，使
目标函数用非基变量表示，即：
ZCXCBC
N


XBXN

CBXBCNXNCBB1bB1NXNCNXN
CBB1bσNXNCBB1bσσm1m1
xm1
σ



x
m2

x

其中NCNCBB1Nm1m1
称为非基变量ＸN的检验向量，它的各个分
量称为检验数。若σN的每一个检验数均小于等于0，即σN≤0，那么现在的基本可行解就
是最优解。
23解的判别
定理1：最优解判别定理
对于线性规划问题maxZCXDXR
AXbX0，若某个基本可行解所对
应的检r