2.4 单纯形法的矩阵描述

用矩阵来描述单纯形法的计算过程，有助于加深我们对单纯形法的理解。

对于线性规划问题：

加入松弛变量Xs＝（X _n＋1 ，X _n＋2 ，…，X _n＋m ） ^T 以后，得到标准型：

这里 I 是 m × m 单位矩阵。

设 B 是一个可行基，也称基矩阵。将系数矩阵（ A ， I ）分为（ B ， N ）两块，这里 N 是非基变量的系数矩阵。

对应于 B 的变量 X _{B 1} ， X _{B 2} ，…， X _BM 是基变量，用向量 X _B 表示。其他为非基变量，用向量 X _N 表示，则 。

同时将 C 也分为两块（ C _B ， C _N ）。 C _B 是目标函数中基变量 X _B 的系数行向量； C _N 是目标函数中非基变量 X _N 的系数行向量。于是约束条件可以转化为：

这时可以将原问题改写为：

将约束条件进行等价转换后得到：

将上式代入目标函数得到：

令非基变量 X _N ＝ 0 ，可以得到一个基可行解 。

对应目标函数值为 z ^（1） ＝ C _B B ^－1 b 。

从以上分析可以看出：

（1）非基变量的系数 C _N － C _B B ^－1 N 就是单纯形法中的检验数。

（2）用矩阵描述时， θ 规则的表达式是：

这里（ B ^－1 b ） _i 是向量（ B ^－1 b ）中第 i 个元素，（ B ^－1 P _j ） _i 是向量（ B ^－1 P _j ）中第 i 个元素。这里 θ 的表达式的形式与之前有所不同，但是其含义完全相同。

为了方便于在单纯形表中找到 B ^－1 所在位置，将 z ＝ C _B X _B ＋ C _N X _N 改写为－ z ＋ C _B X _B ＋ C _N′ X _N′ ＋0 X _s ＝0，约束条件 BX _B ＋ NX _N ＝ b 也改写为 BX _B ＋ N′X _N′ ＋ IX _s ＝ b 。

X _s 是当前的基本变量， X _N′ 为其他的非基本变量，当确定 X _B 为新的基变量时，经过基变换，可以得到：

上述两式用矩阵关系式表示为：

这些分块的系数矩阵可以用表格形式表示（见表2.10）。

在分块的系数矩阵中，（0，1） ^T 这一列不参加运算，所以表格中不填这些数字。表2.10即为迭代后的计算表，各部分数字都可以用矩阵的运算求得。此外可见在初始单位矩阵的位置，在各个运算表中就是 B ^－1 的所在位置。

由于单纯形法的迭代过程中基矩阵的逆矩阵 B ^－1 求出后，单纯形表上的其他行和列的数字也随之可以确定。按这一分析对单纯形法进行改进，计算步骤为：

（1）根据给出的线性规划问题，在加入松弛变量或人工变量后，得到初始基变量。求初始基矩阵 B 的逆矩阵 B ^－1 。

求出初始解：

然后计算单纯形乘子 Y ＝ C _B B ^－1 。

（2）计算非基变量 X _N 的检验数 σ _N ， σ _N ＝ C _N － C _B B ^－1 N 。若 σ _N ≤0，已经得到最优解，可以停止计算；若不是，转下一步。

（3）根据max（ σ _j ｜ σ _j ＞0）＝ σ _k 所对应的非基变量 X _k 为换入变量计算 B ^－1 P _k ，若 B ^－1 P _k ≤0，那么问题无解，停止计算；否则进入下一步。

（4）根据 θ 规则，求出：

它对应的基变量 X _l 为换出变量。是可以给出一组新的基变量以及新的基矩阵 B ₁ 。

（5）计算新的基矩阵 B ₁ 的逆矩阵 ，求出 和 。重复（2）～（5）。

单纯形法的迭代过程中，上一步迭代的基 B 与下一步迭代的基 B ₁ 之间只差了一个变量。如何只根据 B ^－1 和换入变量 X _k 的系数列向量 P _k 来计算出 ，而不是直接求出 ，其计算过程为：

①把 m × m 单位矩阵 I _m 表示为 I _m ＝（ e ₁ ， e ₂ ，…， e _m ）。 e _i 表示第 i 个位置的元素是1，其他元素均为0的单位列向量。

②设 X _k 为换入变量， X _l 为换出变量，则有 。

其中：

例2.7 用改进单纯形法求解。

解：初始基 B ₀ ＝（ P ₃ ， P ₄ ， P ₅ ）是单位阵，基变量 。相应地， （0，0，0）， ， 。计算非基变量检验数 （2，3），由此可以确定 x ₂ 为换入变量，计算：

对应的换出变量为 x ₅ 。

于是得到新的基 B ₁ ＝（ P ₃ ， P ₄ ， P ₂ ）， ， （2，0）。

下面进行基转换， ， ：

非基变量检验数：

所以下一步换入变量为 x ₁ ，计算：

换出变量为第一基本变量 x ₃ 。于是得到新的基 B ₂ ＝（ P ₁ ， P ₄ ， P ₂ ）， ， ，

第二步迭代计算：

所以， 。

非基变量检验数：

x ₅ 为换入变量，再确定换出变量：

所以对应的换出变量为 x ₄ 。再重复之前的步骤，最后得到最优解：

X ^＊ ＝（4，2，0，0，4） ^T

习题

2.1 用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解？

2.2 将下列线性规划问题化为标准形式。

2.3 用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步得到的基可行解对应与图解法可行域中的哪个点。

2.4 对下列线性规划问题，找出所有基本解，判断哪些是基可行解，并用图解法说明。

2.5 求解下列线性规划问题。