第五节单纯形法的矩阵描述

设线性规划问题：

其中A是为行列的矩阵。

引入松弛变量，将上述线性规划问题转化为标准型：

这里的是单位矩阵，可作为初始基矩阵，对应的决策变量为基变量，这时可标记成。这时将系数矩阵分为两块。是非基变量的系数矩阵，相应的决策变量被分为，同时目标函数的系数分为和，分别对应于基变量和非基变量，并记作。线性规划问题可表示为：

经过迭代运算后，初始基变量(松驰变量)可能还是基变量或者已经变为非基变量，即在基矩阵中可能还存在松弛变量或全无松弛变量。为了阐述方便起见，设

；

；

；

；

，，分别表示对应基变量、非基变量、松弛变量的系数矩阵。这时线性规划问题可以表示为

                                  (1-16)

将约束条件移项后，得到；然后给等式两边左乘后，得到：

                                (1-17)

将(1-17)式代入(1-16)中的目标函数，因是单位矩阵，得到：

              (1-18)

令非基变量，可得到一个基可行解，这时目标函数。从表达式中可以见到：

(1)非基变量的系数就是前一节中用符号表示的检验数。因为，是单位矩阵，所以的系数实际上是，在(1-17)式中的系数是0，实质上是，因此所有检验数可以用表示。

(2)用矩阵描述时，规则的表达式是：

这里的表示中的第个元素，表示向量中的第个元素。

(3)单纯形表与矩阵表示的关系

先将(1-16)式，(1-17)式改写成：

再将以上两式用矩阵关系式表示为：

        (1-19)

(1-19)式的分块矩阵也可用表1-8表示，因这列不参加运算，所以在表中不填这些数据。

表1-8即为迭代后的单纯形表，各部分的数字都用来计算。此外还可以见到，在初始单位矩阵中初始基(单位矩阵)的位置经过迭代运算后，就是的位置。

表1-8 分块矩阵