解线性规划的单纯形方法

出处：按学科分类—自然科学总论 山东人民出版社《方法大辞典》第279页（836字）

在一个决策问题中，如果决策者能够把他的决策用n个变量来表示，而这些变量要满足一组线性不等式，并且这个决策问题的优化目标能用一个线性函数来表示，那么这个决策问题就可以写成线性规划形式。

找变量X₁，X₂，…，X_n满足：

并且使目标函数达到极大或极小。

解线性规划问题最常用的方法是单纯形方法。单纯形方法是一种迭代程序。

它从一个初始基可行解开始计算，此时的约束方程组从规范的形式表示，即基变量所对应的列向量组成单位矩阵。

然后从检验数λ_j(j=m+1，…，n)来判断这个基可行解是否为最优解，如果检验数λ_j不符合最伏判别准则，则可以从检验数不符合要求的列中找到能够改进目标函数值的非基变量，设此非基变量为x_k(k=m+1，…，n)，称为进基变量，将其换入下一个基中，替换出某一个基变量，进行换基迭代。换出的变量称为出基变量或换出变量，设为X₁(1=1，2，…，m)。

X_k可以通过以下方法来决定。在每一方程中只考虑该方程的基变量与X_k的关系，当X_k逐渐增加到某个值日时，基变量X_j(j=1，2，…m)中某个变量值首先减小到零，这个基变量就是X_k，然后在X_k这个方程中将X_k的系数化为1，X_k在其余各方程中的系数化为零。

这样，新的基变量系数仍组成一个单位矩阵，这就是第二个基可行解。然后再检查各检验数，如仍然不满足最伏解判别准则，重复上述过程。

如果发现有某个检验数λ_k不符合判别准则，但是当X_k的值增加时，所有的基变量的值都增加，但就是找不到X₁，这表示X_k的值可以无限增加。这就是线性规划无界的情况。

如果所有检验数都满足最伏判别准则，则所得到的基可行解就是最伏解。

如果线性规划问题没有初始基可行解，可以采用人工基，用两阶段法开始迭代。