§1.3 单纯形法

迄今为止，单纯形法仍然是求解线性规划问题最有效的方法。根据线性规划问题解的性质，如果存在最优解，则一定存在一个基可行解是最优解。因此单纯形法的基本思想是：先找一个可行基及其对应的基可行解，判断其是否为最优解，如果不为最优解，则从该基可行解转换到相邻的基可行解，并且使目标函数值不断增大（单调不减），经过有限步转换（迭代）必能找到线性规划问题的最优解，或者判定线性规划问题为无界解。

1.3.1 单纯形表的矩阵结构

一般的线性规划问题转化为如下的标准型：

不妨设矩阵A的秩为m，在矩阵A中必会存在一个m阶非奇异子矩阵B，若以B为基矩阵，则B中列向量所对应的变量X_B为基变量。如果令，其中，不妨设

则非基变量所对应的系数矩阵为，相应的非基变量记为X_N。系数矩阵可分块写成A=（B，N），决策变量也可写成分块形式。此时，约束条件AX= b可以写成：

同时，目标函数的系数也可分块写成C=（C_B，C_N），目标函数可以写为

由式（1.3.2）和式（1.3.3），线性规划问题可以表示为

目标函数：

约束条件：

非负约束：

将式（1.3.5）两边左乘B^-1，得，即

式（1.3.7）表示基变量可以由非基变量来表达。将式（1.3.7）代入式（1.3.4），可得

令非基变量全取零，即，由式（1.3.7）得到基B对应的基解，它对应的目标函数值为。如果，则为对应于基B的基可行解。

如果，则由式（1.3.8）得

因此，当，时，就得到线性规划问题的最优解，此时称B为最优基。实际上，

因此等价于。

由此得到最优解的判别准则：

对于基B，如果，，则对应于基B的基可行解即为基最优解。

式（1.3.7）和式（1.3.8）可改写成：和，再将以上两式改写为矩阵形式：

其中I为单位矩阵。

原线性规划问题可以写成等价的形式：

若记，

则线性规划问题也可写成：

在实际的线性规划求解过程中，为了书写规范和便于计算，对单纯形法的计算专门设计了一种表格，称为单纯形表。若记，其中，根据式（1.3.9），对应于基B的单纯形表的结构如表1.3所示。

表1.3 基B 所对应的单纯形表

根据上述最优解的判别规则，对于单纯形表（表1.3），如果，，则基B对应的基可行解为最优解。值得注意的是基变量对应的检验数。

特别是在线性规划问题中，若矩阵A中含有一个m阶单位矩阵，因右端的常数项b≥0，这时以这个单位矩阵为基，可以立即得到这个基所对应的单纯形表。对如下的线性规划问题

则直接可得到基所对应的单纯形表（如表1.4所示）。

表1.4 基B=（P₃，P₄，P₅）所对应的单纯形表

一般来说，对于基B所对应的单纯形表，利用单纯形方法就可经有限步迭代求得线性规划问题的最优解，或者判定线性规划问题无解。

1.3.2 单纯形法的基本原理和步骤

单纯形法是一个迭代运算，主要分三步组成，下面分别介绍。

1.确定一个初始基可行解，列初始单纯形表

线性规划问题化为标准型后，总可在系数矩阵中找到一个单位矩阵，以此作为初始基B，并求出相对应的基可行解。当线性规划的约束条件均为“≤”时，通过添加松弛变量，松弛变量的系数矩阵即为单位阵。对于约束条件为“≥”和“=”的情况，可通过加入人工变量的方法（人工变量法在1.4节讨论），人为产生一个单位矩阵。

含初始基可行解的单纯形表称为初始单纯形表，如表1.5所示。在基可行解的转换（迭代）过程中，每找出一个新的基可行解，就重画一张单纯形表。

事实上，不妨设

为单位阵，因此，可知初始单纯形表中检验数：

因此我们有。

表1.5 初始单纯形表

例1.6 对于线性规划问题

加入松弛变量，转化为标准形式，即

此时，是单位矩阵，构成一个基，对应是基变量。令非基变量，即找到一个初始基可行解，列出初始单纯形表，如表1.6所示。

表1.6 初始单纯形表

2.基可行解的最优性检验

根据最优解的判别准则，在单纯形表（表1.5）中，如果所有检验数，且基变量中不含人工变量，表中的基可行解即为最优解。对于基变量中含人工变量时的解的最优性检验将在下一节中进行讨论。

对于非基变量的检验数大于零的情况，不能判定基B为最优基，分以下两种情况。

（1）对于基B所对应的单纯形表中，若存在某个检验数，且所有非基变量所对应的系数列向量均有正分量，那么不能判定基B为最优基，这时需要对可行基B进行换基迭代，以便求出最优解。

（2）如果非基变量所对应的列向量均小于0时，有如下定理。

定理1.3.1 对于基B所对应的单纯形表（表1.3）中，若存在某个非基变量的检验数，非基变量所对应的列向量满足，则该线性规划问题为无界解，即。

证明 记基B所对应的基可行解为。在此基础上构造一个新的解，它的分量为

易知满足模型[式（1.3.10）]的约束条件。将代入目标函数，有

由于，故当时，目标函数的值。

通过表1.6可看出，σ1=7，σ2=12两个非基变量的检验数均大于零，且它们对应的列向量均存在正分量，故表中基可行解不是最优解，需要进行换基迭代。

3.换基迭代

换基迭代的目的是从一个基可行解，转换到相邻的能使目标函数值更大的基可行解，并列出新的单纯形表。在单纯形表（表1.5）的基础上，进行换基迭代步骤如下。

（1）确定换入的基变量，也称进基变量（换入变量）。只要有检验数，对应的变量x_j，就可作为换入的基变量，当有一个以上检验数大于零时，一般从中选择最大的检验数对应的变量x_k作为换入的基变量。

（2）确定换出基的变量，也称出基变量（换出变量）。将常数项列b除以对应的进基变量x_k所在列的正分量，选择比值最小者对应行的基变量为出基变量，即如果

则确定变量lx为出基变量。元素lka决定了从一个基可行解到另一个基可行解的去向，称之为主元素。

（3）用换入变量x_k替换基变量中的换出变量x_l，原来的基转换得到一个新的基。根据如下方法，将初始的单纯形表进行初等变换，得到一个新的基可行解，画出新的单纯形表，过程如下。

① 将主元素所在的第l行数字除以主元素a_lk，即

② 将主元素所在行的-a_ika_lk倍加到第i行上（使得第k列的其他元素均化为零）。即

从而得到新的单纯形表，如表1.7所示。换基迭代后，x_l的检验数变为，x_j的检验数变为。

定理1.3.2 单纯形表经过换基迭代后，新基具有以下两条性质：

（1）新基仍为一个可行基；

（2）经过换基迭代后，目标函数的值不降（上升），只有当b_l =0时，目标函数值不变。

表1.7 换基迭代后的单纯形表

证明 设基B所对应的单纯形表中的变量系数为，常数列为；B₁所对应的单纯形表中的变量系数为，常数列为。只须证明对，都有，即可证明B₁也是线性规划问题的可行基。

分两种情况：当i=l时，；

当i≠l时，若a_ij >0，由于，则；若，则。

因此，B₁也是线性规划问题的可行基。

将基B对应的基可行解和对应的基可行解代入目标函数得

由于，换基迭代前非基变量x_k的检验数，所以，且当b_l =0时，（。

定理1.3.3 设某线性规划问题中基B对应的基可行解为，对一切非基变量的检验数有，若存在某个非基变量的检验数，则该线性规划问题有无穷多最优解。

证明 只须将非基变量x_k换入基变量中，得到新基可行解X(1)，由于，根据式（1.3.12）可知，，故X⁽¹⁾也为最优解。根据线性规划解的性质，X(1)和X⁽⁰⁾的任意凸组合均为最优解，所以该线性规划问题有无穷多最优解。

4.重复2、3两个步骤，直到计算结束为止

在表1.6中，由于两个非基变量的检验数σ1<σ2，故确定x₂为进基变量。常数项列除以对应的进基变量x₂所在列的正分量，得

如表1.8所示，因此选择x₅为出基变量，由此10为主元素，作为标志对主元素10加方括号[ ]。

在单纯形表（表1.8）中，换入变量x₂替换基变量中的换出变量x₅，得到一个新的基，按照上述方法进行初等变换，即第3行数字除以10，同时将第3行的-0.4倍和-0.5倍分别加到第1行和第2行，并列出新的单纯形表（表1.9），得到新的基可行解。由于表1.9中还存在大于零的检验数，故重复上述步骤。

表1.8 单纯形表中主元素的确定

表1.9 单纯形表的第一次迭代

在表1.9中，由于非基变量的检验数σ1>0，故确定x₁为进基变量。常数项列除以对应的进基变量x₁所在列的正分量，得

因此选择x₄为出基变量，由此2.5为主元素。换入变量x₁替换基变量中的换出变量x₄，经过初等变换，得到新的单纯形表（表1.10）。由此确定新的基可行解。

表1.10 单纯形表的第二次迭代

由于表1.10中，所有非基变量的检验数均小于零，且基变量中不含人工变量，故表1.10中得到的新基可行解为最优解，代入目标函数得

图1.7 图解法

例1.6的线性规划问题是二维的，通过图解法对例1.6进行求解，最优解对应图1.7中的B点。现在将表1.8至表1.10每步迭代的结果与图解法进行对比，初始基可行解相当于点O（0，0），表1.9对应的基可行解相当于点A（0，30），最优解相当于点B（20，24）。从初始基可行解X(0)进行迭代，依次得到X(1)和X⁽²⁾。相当于目标函数平移时，从O点开始，首先碰到A点，再碰到B点。

例1.7 Breadco面包厂烤制法式面包和发酵面包，一块法式面包的售价是36元，一块发酵面包的售价是30元。每烤制一块法式面包需要1包发酵粉和6盎司面粉，一块发酵面包需要1包发酵粉和5盎司面粉。目前有5包发酵粉和10盎司面粉，另外还可分别以每包3元和每盎司4元的价格购进发酵粉和面粉。建立线性规划模型，做出决策使得该面包厂的利润最大化。

解 设1x为烤制的法式面包的块数，2x为烤制的发酵面包的块数，3x为购买的发酵粉数量，4x为购买的面粉数量。考虑到发酵粉数量和面粉数量的限制，以利润最大为目标，建立如下线性规划模型：

加入松弛变量x₅和x₆，将线性规划化为标准型，并列出初始单纯形表（表1.11），根据单纯形法的步骤，利用单纯形表进行运算（见表1.12至表1.13）。

表1.11 初始单纯形表中主元素的确定

表1.12 单纯形表的第一次迭代

表1.13 单纯形表的第二次迭代

至表1.13，可以看出非基变量x₃的检验数σ3=9大于零，且其所对应的列向量均小于0，根据最优解的判别规则可知，该规划问题为无界解。

在该问题中，允许面包厂以3+ 6× 4=27（元）的成本购买法式面包的配料，以36元的价格进行销售。因此，每块法式面包的利润为9元，由于允许无限制的购买配料，且没考虑现实中面包厂生产能力的限制，以及社会对面包的实际需求量，从而使得赚取的利润可以无限大。