单纯形法中的线性无关性

孙秀华

(安徽建筑大学 数理系，安徽 合肥 230022)

单纯形法作为解决线性规划问题的传统方法，已形成相当成熟的理论，并不断改进简化运算。［1，2］近年来，结合计算机并融合数学建模可更大程度应用运筹学，特别是线性规划中的单纯形法。［3］而单纯形法的原理在于通过迭代不断寻求新的基本可行解，从而得到最优解和目标函数的最优值。基本可行解是指当非基变量全取0 值时，基变量取得非负值而形成的一个解。此时的基变量对应的系数列向量线性无关，并构成线性规划标准型中约束方程组系数矩阵的最高阶的非奇异方阵，即这些列向量为约束方程组系数矩阵所有列向量的最大线性无关组，称为线性规划问题的基。事实上，在单纯形法中，正是其中的线性无关性，才可以保证在每一次迭代中都可以求出非基变量的检验数并确定新的进基变量，进而又要保证确定出基变量后的新的基变量组合仍为基本解，即保证新的基变量对应的系数列向量线性无关。由此可见，线性无关性在单纯形法中有着非常重要的作用。

1 基变量、非基变量与线性无关性

设线性规划问题标准型如下:［4］

在此不妨假设假设矩阵A 秩为m。

定理1.1［5］设非齐次线性方程组的系数矩阵Am×n的秩R(A)= r，则对应的n 元齐次线性方程组AX = 0 的解集S 的秩Rs= n－r。

由上述定理易得如下命题:

命题1.2 xk1，xk2，…，xkm为第k 步迭代中基变量当且仅当基变量xk1，xk2，…，xkm可由非基变量xkm+1，xkm+2，…，xkn－m表示，即:对1 i m，有xki= b＇i－(a＇i，m+1xkm+1+ … + a＇i，n－mxkn－m)。

证明:“”如果xk1，xk2，…，xkm为基变量，其对应列向量(pk1pk2… pkm)经过初等行变换可化为单位阵，由定理1.1 知xk1，xk2，…，xkm可由自由向量，也即非基变量表示。……