线性规划问题的单纯形法求解

线性规划问题单纯形法的基本思路是由于线性规划问题的最优解存在于可行域的顶点中，因此可以从可行域的某一顶点开始进行搜索，并且在搜索过程中保证目标函数值得到逐步增大，当目标函数达到最大值时，就得到了问题的最优解。下面通过矩阵表述的形式来说明单纯形法求解的基本过程[15]。

假如线性规划问题的矩阵表示有如下形式

引入松弛变量和剩余变量Xs，把原问题化为标准型，即

式中：C＝（c1，c2，…，cn）；X＝（x1，x2，…，xn）T；Xs＝（xn+1，xn+2，…，xn+m）T；P0＝（b1，b2，…，bm）T；A＝（p1，p2，…，pn）＝（a1j，…，aij，…，anj）（j＝1，2，…，m）；O＝（on+1，on+2，…，on+m）T。

在一般情况下n＞m，有无穷多组解，我们最关心的是求得基本可行解，并从中找到最优解。下面将分别叙述。

1.求基本可行解

任选A阵中m个线性无关的列向量Pj（j＝1，2，…，m）为A的基阵B，其余（nm）个列向量Pj（j＝m+1，m+2，…，n）为非基阵，把A阵分成二块，即

式中：B＝（P1，P2，…，Pm）；N＝（Pm+1，Pm+2，…，Pn）。

同样，把变量也分成与之对应的基本向量xB和非基本向量xN两块，即

由于XB＝（x1，x2，…，xm）T，XN＝（xm+1，xm+2，…，xn）T，则式（4-31）约束矩阵可表示为

式（4-34）同乘B-1阵，移项后可求得

式中：B-1为B的逆矩阵。

如令非基本向量XN＝0，则可求出基本向量XB为

如果XB＝B-1 P0≥0，则能满足非负条件及m个约束方程的要求，所以XB为基本可行解。显然n维向量的基本可行解为

2.确定可行域中的最优解(www.xing528.com)

同样，也可将价值系数C分成与基向量XB对应的系数CB和与非基本向量对应的系数CN两个部分，则目标函数式变为

将式（4-35）代入式（4-39），得

如果XN＝0。则式（4-40）可写成

如果把式（4-40）中第二项展开，则可写成如下形式

从式（4-43）可知，若从xj中选出一进入变量使之能增加目标函数值，要求（Zj-Cj）必须小于零。显然（Zj-Cj）值越负，越能更快的增加目标函数植，故应当选（Zj-Cj）为最负的系数。当所有的（Zj-Cj）≥0时，xj中已没有任何变量进入可使目标函数得到增加，则问题达到最优解。由此可见（Zj-Cj）是最优性条件和最优解的重要判别值，故把（Zj-Cj）称为单纯形系数。

3.换出变量的确定

如果xj为进入变量，XN中的其余非基本变量自然保持为零。由式（4-35）可得

式中：Pj为与xj相对应的系数列向量。由非负条件限制XB≥0，所以XB中任意变量（xB）i均应满足

而xj≥0，上式可写成

由式（4-46）的条件限制，xj应选取式（4-46）中右端比值最小，且（B-1 Pj）i＞0行的变量（xB）i进行替换，才能保证xj进入后仍为基本可行解。即满足比值

的条件下，相应的（xB）i为换出变量。式（4-47）即为可行性条件。