c. 单纯形表 (a) 单纯形表的形式

设基为B，则与此基对

应的单纯形表为：

注意：

① 单纯形表中行列记数从0开始，分别为第0, 1, …, m行，第0, 1, …, n列。

② 为求基的逆矩阵简便，一般我们希望系数矩阵A中含有单位阵形式的基。因为,单位阵的逆矩阵就是它本身。如果这种情形存在时，那么构造第一张单纯形表（初始单纯形表）时,就可用单位阵形式的基作为初始基。此时，写出第一张单纯形表就非常容易。

③ 若系数矩阵A中不含有单位阵形式的基，一种“笨”的方法是直接任选一个可行基作为初始基，构造第一张单纯形表；但一般为避免烦琐的求基的逆矩阵的过程，我们会采用其它的方法进行，这将在后面予以介绍。

例6 （接例5）

d. 单纯形法计算

(a) 单纯形法的思想：因为可行基有多个，不可能用穷举法逐一验证，得到最优基，故采取换基迭代的方法，从容易计算其逆的初始基对应的单纯形表开始，逐步得到不同的可行基对应的单纯形表，直至找到最优基对应的单纯形表为止。换基迭代的过程实质上是一个不断改进的过程。

(b) 计算步骤例释（接例6）

① 选单位阵形式的基作为初始基，写出初始单纯形表。若检验向量 CBB－1A－C中含负的检验数，则非最优，进行换基迭代。否则，停止，已找到最优解。

② 确定谁入基：负的最小检验数所对应的系数矩阵中的列向量入基； ③ 确定主元素：单纯形表上所选入基列中取正值的元素分别与同行第0列的元素相除，入基列中取得比值最小者的元素作为此表的主元素，并画框标示；

④ 确定谁出基：简单地说，主元素在第几行，就将基中第几个基向量换出；也可由单纯形表中基变量所对应的的列向量是单位坐标向量这一特点，直接观察哪一个单位坐标向量的“1”元素与主元素同行，从基中被换出的基向量就是表中该单位坐标向量列对应的那一个列向量。

⑤ 利用换基迭代公式，得到下一张（新的基）单纯形表。

⑥ 重复上述过程，直至找到最优解

例7（接例6）

选单位阵形式的基B=（P3 P4 P5）作为初始基，写出初始单纯形表。

因检验向量CBBA－C=（-2 -3 0 0 0）中含负的检验数，故非最优，进行第一次换基迭代。

－1

按⑤换基迭代后，得到新基B=（P3 P4 P2）下的单纯形表，执行步骤⑥，从①开始重复操作。因此时检验向量CBB－1A－C=（－2 0 0 0 3/4）存在负的检验数，故非最优，按②、③、④、⑤进行第二次换基迭代。

第二次换基迭代后，得到新基B=（P1 P4 P2）

下的单纯形表，执行步骤⑥，从①开始重复操作。因为此时检验向量 CBB－1A－C=（0 0 2 0 -1/4）存在负的检验数，故非最优，进行第三次换基迭代。换基迭代的步骤同上。

第三次换基迭代后得到新基B=（P1 P5 P2）下的单纯形表为：

此时检验向量 CBB－1A－C=（0 0 3/2 1/8 0）≥0，由第一判别定理知，已取得最优解，最优解为 x*= ( 4 2 0 0 4 )T.

注意：单纯形法换基迭代的实质是初等行变换。

(c) 退化与BLAND法则：当存在退化的基本可行解时，可能会出现死循环的情形。为避免此情形的发生，可运用BLAND法则，即确定谁入基时，若最小负检验数不唯一，则选位置最靠前的检验数处入基；确定主元素时，若最小比值不唯一，则将取得最小比值的入基列中位置最靠前的元素，作为主元素。

(d) 无穷多最优解：当最优单纯形表中，某非基变量的检验数为0时，该线性规划问题有无穷多最优解。

e. 第二判别定理（无最优解的判别）： (a) 线性规划模型的目标为Max Z 时

对某个单纯形表T（B）=( bi j )(m+1)×(n+1)，若有某检验数b0j ＜0, 且bi j≤0（i= 1,2, …,m），则对应的线性规划问题（L）或者无可行解；或者目标函数值 Z 无（上）界。因此，无最优解。