3.5 单纯形法的一般步骤

3.4节说明，线形规划问题如果有最优解，一定可以在基可行解（可行域的顶点）上达到，而基可行解的个数有限，于是就可以在有限的基可行解之间求解。单纯形法就是这样的过程：先找一个初始基可行解，按照某种法则判别它是否为最优解，如果不是，再换一个基可行解，并使目标函数值持续改善，不断迭代下去，有限步后必能得到最优基可行解（或者达到终止条件）。实际上这个过程我们已经在3.3.3节中做过一次，这里使用3.2节建立的规范术语重述，也请读者体会3.4节中相关定义和定理在本节中是如何应用的。

对于例3.1.1中的数学模型，第一步先给出一个初始的“基可行解”，也就是进行模型标准化的工作，引入松弛变量，得到

这时系数矩阵为矩阵，其中变量的系数部分显然是一个的单位矩阵，自然是可逆的，可以很方便地将其作为一个基看待，这时初始基、基变量、非基变量为

由于单位矩阵的逆就是自身，容易得到

这样就方便地找到了一个基可行解，即

显然这个解需要改进，要换一个“好”一点的基可行解。根据目标函数表达式可知，每增加1个单位，目标函数增加3个单位，因而希望优先取换入作为基变量。同时，基变量的总数要保持不变（始终是约束条件的总数），那么就要把中的一个基变量变为非基变量，按照3.3节的最小值计算方法取作为换出变量。

经过这样一番操作，用换入，取代的位置，新的基变量为（这里注意顺序不可颠倒，请读者思考原因），新的非基变量为。同时，注意新的基为对应的系数列向量组合：

新的基变量取值为

这样就找到了一个新的基可行解和新的目标函数值，即

这里目标函数由上一步的0增长到9。

这里涉及新基的逆矩阵计算，一般的矩阵求逆往往费时费力，但由于单纯形法中基的形式特殊，求逆可以更方便进行注5。这里对换入变量对应的列向量P2实施，考虑“”，只需要将该行乘以“-2”加到第一行，让“”变为0即可。值得注意的是，这里P3和P4列是单位列向量，实际没有参与计算。

注5 对照线性代数中使用初等行变换求逆矩阵的过程，读者就会明白这里运算的实质，对于基B1，用初等行变换求解逆矩阵的过程中实际上只变换了一列。

下一步，考虑新的基可行解对应的检验数，继续进行迭代运算，最终就会得到最优解。

到这里，细心的读者可能已经发现一些问题，比如第1步中正好有一个单位矩阵存在，后面计算变得简单，这也是得到初始基可行解的基础，如果没有这一单位矩阵存在呢？同时，线性规划问题的解也可以有其他情况，如无可行解、无界解等，如果是那样，在判别时会出现什么情况？下面用一个例子说明更一般的实施过程，并解释其中的原理。

例3.5.1　用单纯形法求解以下线性规划问题。

第1步：确定初始基可行解

对于这个例子来说，读者会发现，利用前面化标准形式的步骤，并不能自然地得到一个单位子矩阵，下面说明更一般的做法。

首先，考虑具有如下特殊标准形式的线性规划模型（如果仅是具有单位列向量的变量位置不同，可以通过调整变量的位置来实现，其中），其中自然地出现了一个单位子矩阵。

显然从其系数矩阵可直接观察得到一个的单位矩阵：

以作为一个基，令，得到一个基可行解，为可行基，将作为初始基可行解。

那么如何得到满足上述要求的标准形式呢？只需要在3.3节中的标准形式转化过程中加入以下两条即可。

（1）若约束条件为“≤”不等式，在不等式左端加入一个非负松弛变量；若约束条件为等式，在等式左端加入一个非负人工变量（Artificial Variable）；若约束条件为“≥”不等式，在不等式左端减去一个非负剩余变量，再加入一个非负人工变量。

（2）在已经实现最大化的目标函数中，加入的松弛变量和剩余变量在目标函数中的系数为0，而令人为加入的人工变量系数为-M（其中M为任意大的正数，也称惩罚性系数）。

按照以上方法，将例3.5.1中线性规划的一般形式模型变换为如下含单位系数子矩阵的标准形式：

显然，x4、x5、x6的系数列向量构成一个3×3的单位矩阵B。以B作为一个基，令x1= x2= x3=0，可得到x4=5，x5=1，x6=1。则基解=(0，0，0，5，1，1)T为基可行解，B为初始可行基。我们可以将作为初始基可行解。转入第2步，建立单纯形表。

第2步：建立单纯形表

根据3.3.3节中单纯形表的形式，对例3.5.1建立其单纯形表，如表3-5-1所示。

此计算表为初始单纯形表，以后每迭代一次构造一个新的单纯形表。转入第3步，对所得基可行解进行判别。

第3步：解的判别

3.3节中已经演示用“当前非基变量的检验数中是否还有大于0的数”这一点来判别当前解是否是最优解。实际上这样的判断方法只是单纯形法中解的判别准则的一部分，这里说明其完整内容。

不失一般性，设为迭代过程中所得的任意一个基可行解。对应的基B为单位矩阵。

根据式（3-5-1），约束条件方程组可写为

把这些解的表达式代入目标函数，整理后得到

令

有

在式（3-5-2）中，是当前解对应的目标函数值，表示对于非基变量来说，每改变单位数量导致目标函数数值的变化量，如果为正值，那么将相应非基变量作为换入变量，下一步成为基变量时目标函数就会增长；反之，如果其为负值，说明相应变量增加，目标函数将减小。也就是说，的正负和大小表征了目标函数的变化趋势，这也是其被称为检验数的原因。

更进一步，如果选取中的最大值，在增加同等数量的变量值的情况下，目标函数在这一步的增长就最快，我们可以把这种确定换入变量的办法称为最大值规则。

由此给出线性规划问题解的判别准则（或称为终止条件）。读者已经知道，线性规划问题解可能有4种情况：唯一最优解、无穷多最优解、无界解和无可行解。下面分别针对这4种情况说明。

（1）唯一最优解判别。设解为对应于基B的基可行解，若对于所有非基变量，检验数都有（），则为唯一最优解。

这个结论是比较直观的。由式（3-5-2）可以看出，目标函数值由两部分组成，第1部分为定值，第2部分取决于检验数与非基变量的取值，而由于所有变量取值必须为非负数，那么目标函数的增长与否取决于检验数的数值，显然当所有的时，目标函数无法再增长，任意的变量取值改变都将导致目标函数降低，说明线性规划问题的当前解已经是最优解，而且是唯一最优解。

（2）无穷多最优解判别。若解为一个基可行解，对于一切非基变量的检验数有，且存在某个非基变量的检验数，则线性规划有无穷多最优解。

如果存在某个非基变量的检验数为0，可以得到这个非基变量对目标函数没有影响，那么意味着在保证是可行解的条件下，这个变量可以任意取值，即线性规划问题有无穷多最优解。实际上，如果某个非基变量检验数，则可以构造出一个新的解注6：

注6 式（2-5-3）也是单纯形法中每步迭代时基可行解变换的一般形式，即如上一步得到的是X的形式，则下一步就是X^的形式，其中的θ就是最小值准则中的θ，为什么？同时，另一个很有意义的事情：如果有无穷多最优解，如何找出多个，甚至所有最优解？这里的式（2-5-3）实际上指明：取检验数为0的非基变量为换入变量强行迭代一次，可以找出一个新的最优解。

可以验证（请读者自行完成），这样得到的满足，若对于所有，均有（不可能全部为0），那么任取即可保证，从而是可行解，否则只要取

同样，保证是可行解。将代入目标函数得到

由于，一定不同于当前解X，即是线性规划问题的另一个最优解。由定理3.2可知，X与两点连线上的所有点都是最优解，即线性规划问题具有无穷多最优解。

（3）无界解判别。若当前解为一个基可行解，有一个非基变量的检验数，且对所有变量对应的系数，则线性规划问题具有无界解。

实际上，和无穷多最优解判别准则中进行同样操作，可以构造出一个新的解，其中

同上可以验证，满足且对于任意有，即是可行解。进一步，将代入目标函数得到

由于及的任意性，有

因而线性规划问题为无界解。

（4）无可行解判别。如果在单纯形法求解过程中，已经满足上述（1）（2）（3）中的迭代终止条件，但存在某一人工变量取非零值，这时线性规划问题无可行解。

根据人工变量的含义（它是在原约束条件已经为等式条件时人为强行加入的变量），其逻辑上最终必须为0，否则不是可行解。如果在求解过程中已经满足了（1）（2）（3）中的终止条件，而同时有人工变量取非零值，则意味着迭代无法找到可行解，说明线性规划本身不存在可行解。

对于例3.5.1在迭代过程中所得的基可行解X(0)，计算其各决策变量的检验数，填入单纯形表中，如表3-5-2所示。

利用判别准则进行判别，发现X(0)不是最优解，并且不满足迭代终止条件的任何一项。转入第4步，进行基变换，寻找新的基可行解。

第4步：基变换

若迭代过程中解不满足任何一条终止条件，则需要继续迭代——找一个新的基可行解。具体的做法是从非基变量中换入一个变量，同时从当前基变量中换出一个变量，得到一个新的基可行解，这一过程称为基变换。由于只涉及一个变量的替换，这一过程也称为相邻顶点（基可行解）间的变换。实际过程包括了确定换入变量和确定换出变量两个小步骤。

1）确定换入变量

选取了非基变量中检验数值最大的那个变量作为换入变量，其意义是保证了在当前解的“局部”，目标函数增长较快。实际上只要选取检验数大于等于0的非基变量，都是可行的，据此运筹学者们给出很多选取方法，下面3种比较常见，可供读者选用。

（1）选取所有检验数大于0的非基变量中的检验数值最大者。如在表3-5-2中，我们应选取检验数值大的作为换入变量。

（2）选取检验数大于0的非基变量中的下标最小者。如在表3-5-2中，下一步不选取检验数值大的而选取同样检验数为正数，且下标更小的作为换入变量。

（3）选取大于0的检验数与相应最小值乘积中数值最大的。实际上每次迭代后，目标函数的实际增量为，那么这两者乘积最大才是实际上的“局部最优”，由此这样的选取方法具有实际意义。但需要注意的是，这样做意味着对所有的检验数为正的非基变量，要计算相应的值及的数值，并从中选取最大的值，这样就比单纯取检验数最大值的方法增加了不少计算量。

需要说明的是，单纯形法迭代中的每步无法保证是全局最优的，在这个意义上，取检验数最大值的方法不一定“差”，同时由于该方法简便易用，所以教材中经常使用这种方法。

2）确定换出变量

换出变量用所谓的“最小值”来确定，为什么可以这样做？这里说明其中的原理。

不妨设为当前基可行解，其中前m个变量为基变量。已经确定非基变量作为换入变量，对应的系数为，则换出变量按以下方法确定：

由此确定为换出变量。此方法称为最小值规则。

首先，说明这样的值一定可以取到。否则对于所有的j均不存在，那么根据上面的无界解判别准则，可以知道线性规划问题无最优解，迭代终止。

其次，还要说明这样确定的新解必然是基可行解，且使目标函数值至少不会减少。

实际上，如上基变换得到的新解的形式与解的判别准则式（3-5-3）中的形式一致［可参见式（3-5-14）］，为注7

注7 实际上，式（2-5-8）也是单纯形法中每一步迭代时基可行解变换的一般形式，即如上一步得到的是X的形式，则下一步就是X^的形式，其中的θ就是θ最小值准则中的θ，为什么？

很容易验证是可行解，且相应目标函数表达式为

比第3步中目标函数值相差，由于和均大于等于0，说明该值必然不会减小。

下面说明这样得到的新解必然是基解。根据定理3.3，只要证明对应系数列向量线性无关即可。用反证法，假设对应系数向量线性相关，注意这里是第3步中基可行解的系数列向量，必然是线性无关组，所以必然存在一组不全为0的数，使得下式成立：

而由于是第3步中基可行解的系数列向量，均为单位向量，有

式（3-5-9）和式（3-5-7）两式相减，得到

由于式（3-5-11）中所有系数至少有一个不为0（主元素），说明线性相关，组矛盾！假设不成立，说明线性无关，因而新的可行解也就基解，即是基可行解。

继续求解例3.5.1，在单纯形表3-5-2中，根据检验数确定非基变量为换入变量，计算的值，确定基变量为换出变量，如表3-5-3所示。

第5步：旋转运算

为了保证每次变换后的新基可行解中所有基变量的系数列向量仍为单位向量，需要在完成基变换后，对新换入变量的系数列向量进行运算，使其变为单位列向量，过程类似于求解线性方程组的高斯消元法，称为旋转运算。设为换入变量，为换出变量后，对应的系数列向量为

要把的系数列向量变为单位向量，首先在单纯形表中把第m+k列和第l行的交叉元素用“[ ]”标记出来，称为主元素，其次以此主元素为中心，进行如下初等行变换：

（1）将单纯形表中对应的行乘以的倒数，将变为1；

（2）将单纯形表中对应的列中除外的各元素均利用高斯消元法，变换为0。

考虑到变换中6列均参与运算，变换后单纯形表中b列系数为

对照式（3-5-7）中的表达式，有

当用换入替换的位置后，变为非基变量取0，取值为，新的基可行解可表示为

写为

可见，基变换只是在原基可行解中更换一个基变量，变换后非零分量的位置仍然不会超过m个。

继续例3.5.1的求解，在表3-5-3中，确定非基变量x3为换入变量，基变量x5为换出变量，则以主元素为中心进行旋转运算，得到表3-5-4。

由表3-5-4得到一个新的基可行解X(1)=(0,0,1,6,0,0)T。

继续下去，重复第3步到第5步，直到达到迭代的终止条件为止。

这里介绍一种联立的单纯形表形式，每次迭代只需要绘制一次表头，可以简化求解过程。对于例3.5.1，联立单纯形表如表3-5-5所示。

根据判别法则，在表3-5-5最终单纯形表中，所有检验数均小于等于0，且所有人工变量（是人工变量）均取0，迭代终止，得到=(0，2，3，0，0，0)T为最优解。

因此，经过两步迭代，原问题得到最优解为X=(0，2，3)T，目标函数最优值为z*=4。

对照本章中例3.3.2，本例的模型形式要复杂一些，但实际上，前者迭代了3次，而本例只迭代了2次。

本节中使用两个例子较为系统地说明了单纯形法的迭代过程及基本原理，这里进行一些总结。

（1）单纯形法是一个迭代算法，是不断重复“判别－变换－判别”的过程，透彻理解和应用判别准则和基变换方法是掌握单纯形法的两个重点，图3-5-1给出了单纯形法计算框架。

（2）单纯形法关心的核心问题是找到最优解（或满足其他终止条件），一旦找到一个最优解，就会停止迭代过程，即使问题本身有很多最优解。

（3）理论上单纯形法会在有限步内得到最优解或达到其他终止条件，这是因为迭代是在基可行解之间进行变换的，而线性规划问题的基可行解数总是有限的。