3.3 单纯形法的求解思路

3.2节介绍的图解法显然不是求解线性规划的通用解法。1947年美国空军从事军队建设规划问题研究的学者丹捷格（G.B.Dantzig）提出了一种通用解法——单纯形法。这一方法建立在统一规定好的线性规划模型“标准形式”之上，并以线性代数中求解线性方程组的“主元消去法”为基础，通过“可行解”之间的不断迭代实现对线性规划问题的求解。下面先说明模型的标准形式，然后介绍单纯形法的基本过程。

本节暂不涉及单纯形法的理论分析（在3.4节讨论），也不需要读者有深入的线性代数知识，不过如果读者能够熟悉矩阵的基本概念及线性方程组的求解过程，并且能够跟着书中的例子自己演算，将会大大有助于理解。

3.3.1 数学模型的标准形式

根据3.2节的讨论，我们已经知道线性规划模型有各种不同形式。目标函数有的要求最大化，有的要求最小化；约束条件可以是“”，也可以是“”的不等式，还可以是等式；决策变量一般可以大于0，也可以小于0，甚至可以是无约束的。为便于讨论和寻求通用解法，需要将多种形式的数学模型统一变换为一种规范的形式（称为标准形式），本书中规定，满足以下3个条件的形式为线性规划数学模型的标准形式。

（1）目标函数最大化。规定目标函数求最大值，若为其他形式，需要进行转化；

（2）约束条件等式化。需要将所有不等式转化为等式，且等式右端项必须为非负数；

（3）决策变量非负化。必须是大于或者等于0，如果是其他形式，需要转化。

设线性规划模型中变量数为n个，非负约束条件共m个，标准形式可写为

可简写为

进一步地，可以用向量和矩阵符号表述为

或者

其中，0为n维全0的列向量，其他字母含义为

其中，A称为维系数矩阵，一般且；b称为资源向量，C称为价值向量，称为决策变量向量，称为系数列向量。

显然式（3-3-2）的形式更为简洁，书写也更为方便，本书中会大量使用这种形式，但读者需要注意模型中各符号代表向量的含义以及维度。

实际上，线性规划模型的任何一般形式和标准形式是内在统一的，所有一般形式都可以转化为标准形式，具体通过如下3个步骤进行。

（1）决策变量非负化：若原模型存在取值为负的变量，通过取负转化为非负变量，若存在无约束的变量如，可令，其中。

（2）约束条件等式化：若原模型约束方程为不等式，若为“”不等式，可在不等式的左端加入非负松弛变量；若约束方程为“”不等式，可在不等式的左端减去非负剩余变量（也可称松弛变量）。这样就可以把不等式等价地转化为等式。

（3）目标函数最大化：若原模型目标函数要求实现最小化，形式为，只需要通过两边“取负”变换为目标函数最大化，即令，于是。

下面举例说明这一过程。

例3.3.1　将下述线性规划问题化为标准型。

解：按照上面的3个步骤实施。

（1）不需转化,令，，其中；

（2）检查所有约束条件的右端项是否存在负数,发现第二个约束条件右端为负,该项两边同乘以“-1”,变换为“”。在第一个约束不等式和变换后的第二个约束不等式左端加入松弛变量和；在第三个约束不等式号的左端减去剩余变量；

（3）令，把求改为求，得到该问题的标准形式如下：

在如上操作中，将所有不等式约束转化为等式约束是关键一步，本质是将线性规划的约束条件不等式组变为线性方程组，也就是将线性规划问题的求解转化为在相应的线性方程组的解集中找最优解。

3.3.2 代数法的基本思路

丹捷格给出的通用解法的基础是线性代数中求线性方程组的“主元消去法”，下面以例3.1.1中的数学模型为例来说明它的思路。

例3.1.1的数学模型为

先将上面的模型转化所有约束为等式的标准形式，并写为式（3-3-3a）的形式，其中实质上是不等式左边和右边的差值。

将x1、x2看作线性方程组中的自由变量，很自然想到坐标原点，这时有，得到的取值分别为8、4、3，实际上就是全部的资源总量，意思是全部是剩余量，任何资源都没有使用，那么演习使用炮弹的数量实质上均为0，战斗力指数。

这自然不是我们想要的，观察目标函数表达式，我们只需要将由0变为一个正数就可以得到更大的战斗力指数，而且显然取值越大，战斗力指数增加越多，但显然不能无限大，那么最大取多少呢？为此，我们将所有约束条件表达为的表达式，其中第二个约束条件与无关，不用考虑。得到

这里，那么最大只能取：

相应地有

将它代入目标函数中，得到

同时也将其代入第一个约束条件中，得到

实际上，这样得到了与式（3-3-3a）等价的模型表达形式，即

在式（3-3-4a）中，取，当时，战斗力指数变为9。

对比式（3-3-4a）和式（3-3-3a）就会发现，在所有约束条件中，左端将原来的换出了，而把换入；右端恰好相反，把换出，把换入。变换操作实际是线性方程组求解中的“主元消去”过程，效果是用取代了的位置，其他未发生变化。

这时战斗力指数为9，是否是最大值呢？显然不是，在表达式中，如果增大，由当前为0变成一个正数时，同时保持为0，战斗力指数会变得更大。同样地，为了研究最多能增大多少，将式（3-3-3a）中的约束条件写成的表达式，其中第三个约束条件与无关，不用考虑，得到

同样，这里要求所有变量均大于等于0，在同时保持为0的条件下（不是要换入的变量，仍让其保持为0），最大只能取

这时，有

将它代入目标函数中，得到

同时也将其代入第二个约束条件中，得到

同上得到了与式（3-3-4a）等价的模型表达形式，即

在式（3-3-5a）中，当时，战斗力指数变为13。

对比式（3-3-5a）和式（3-3-4a）会发现，这里是用取代的位置，其他未发生改变。

这时战斗力指数为13，是否仍存在更大的战斗力指数呢？答案是肯定的，在表达式中，如果增大，由当前为0变成一个正数时，战斗力指数会变得更大。和上面两步中操作一样，为了研究最多能增大多少，将式（3-3-5a）中的约束条件写成的表达式，得到

所有变量仍要求大于等于0，在让约束等式右端的变量同时保持为0的条件下，最大只能取

注意这里没考虑第一个约束条件，因为该式中由于的系数为正，意味着只要大于-1即可，实际对其能取多大的正数没有构成约束，无须考虑。取最大值1时对应有

同上操作，得到与式（3-3-5a）等价的表达式为

在式（3-3-6a）中，当，即时，战斗力指数变为14。

对比式（3-3-6a）和式（3-3-5a）会发现，这里其实用取代了的位置，其他未发生改变。

这时目标函数值为14，是否仍存在更大的目标值呢？显然不可能，因为目标函数表达式中，只要不是的取值组合，必然使得目标函数值更小，所以当前解就是线性规划问题的最优解，也就是说演习应使用Ⅰ型炮弹4个基数，Ⅰ型炮弹2个基数，战斗力指数最大为14。这与3.2节图解法的结论一致。

这样经历3步迭代和4次表达形式的变化，在式（3-3-6a）中，读者已经能够直接观察出最优解。回顾以上求解过程，可以得到以下结论。

（1）这一过程开始时就将所有不等式约束条件转化为等式，从而可以将变量相互表达出来。

（2）利用变量在目标函数的系数判断目标函数是否可以增大，并利用约束条件给出相应变量的表达形式，计算出变量可以取的最大变化量。

（3）用变量的表达式更新所有约束条件及目标函数表达式，进而在新的表达式中判别目标函数是否可以继续增大，若是，则重复（2）中操作，直到无法使目标函数变大为止。

（4）在更新表示式时，实际上每次确定一个且只有一个新变量来代替一个旧变量，并确保新变量变成了一个正值，同时使得目标函数增大。

显然，这个过程具有通用性，任何线性规划问题都可以如此操作进行求解（尽管变量数或者约束条件很多时，过程很烦琐）。而部分读者可能已经想到，上面的过程非常固定，可以利用表格进行简化计算，更直观，更简洁。而在一个统一规定的表格上遂行如上计算的方法就是求解线性规划的通用代数解法——单纯形法。

3.3.3 单纯形法的基本过程

将上面示例的求解过程进行规范化，并用一个统一的表格表达相关数据和完成计算过程，即“单纯形法”（Simplex Method或Simplex Algorithm）。总体来说，单纯形法是不同的解之间迭代计算的过程，一般分为5步：第1步寻找一个初始解，第2步构建单纯形表，第3步对解是否是最优解进行判别，第4步变换到一个新解上去（如果第3步判别不是最优解），第5步在单纯形表中计算出新解的数值，然后返回到第3步，反复进行下去，直到得到最优解或达到其他终止条件。

这里用例3.1.1说明这个过程，也是重述3.3.2节的内容。对于单纯形法中更为复杂情况的处理将在3.5节介绍。

例3.3.2　用单纯形法求解例3.1.1中的线性规划问题。

其数学模型为

第1步：找到一个初始解

这一步是通过将数学模型转化为标准形式完成的，对于上面的例子，添加3个松弛变量，得到如下的标准形式：

注意3个新变量的系数列向量为单位向量，按照“主元消去法”的过程，首先考虑这3个变量的表达式，在表达式中直接取其他变量为零，这3个变量取值就是右端项，得到一个初始解，记为。

第2步：建立单纯形表

为便于计算，使用一种格式规范的计算表，称为单纯形表。下面求解过程均在此表上进行。对于本例，构造初始单纯形表如表3-3-1所示。

表中其他部分均为标准形式中的相关数据，下面解释最后一行和最后一列。

在最后一行中，b列对应位置为当前目标函数值，计算方法为

该行其他位置称为各变量的检验数，其中列入表中左侧CB列的变量的检验数为0（总是为0），其他变量检验数的计算方法：

其实，这一步计算，包括“检验数”的计算和上面“主元消去法”过程中的式（3-3-3a）实质上是一样的，各检验数实际上就是式（3-3-3a）中目标函数各变量的系数。

根据计算结果，选取一个检验数为正（很多时候选其中最大的）的变量作为换入变量，如。

最后一列称为准则列 注2，用来确定下一步需要换出的变量，计算方法是对于已经确定的换入变量列的系数，进行如下计算：

注2 这里值的计算方法是确保下一步得到的新解仍是可行解，详见3.4节。

其中列的系数中如果有负值或0，则不用参与计算，直接用“”表示即可。

一般地，表3-3-1中各行（列）的含义如表3-3-2所示。

观察上面的过程，可见这一步与式（3-3-3b）和式（3-3-3c）中的计算过程是相同的。

第3步：解的判别

判断当前的解是否使得目标函数已经达到最优。查看最后一行检验数的计算结果，如果发现所有检验数均小于等于0，那么迭代终止（说明目标函数无法再增加）。如发现某个未选入变量检验数大于0，说明当前解还不是最优解。这里：

说明迭代还需要进行下去，转入下一步。

第4步：解变换

这一步的任务是确定一组新的选入变量，根据3.3.2节的思路，每次确定一个变量换入，同时换出一个变量。根据检验数行的计算结果，这里选取一个检验数大的变量作为换入变量，类似式（3-3-3a）中目标函数系数的判定，确定为换入变量，进一步计算相应的值，得到，由此确定为换出变量，这样得到一组新变量为。

第5步：旋转运算

这一步的任务是计算新变量组的取值，并将变换后得到的新解反映到一个新的单纯形表中。具体做法如下。

首先，在上一步单纯形表的系数矩阵部分确定一个主元素（换入变量对应的系数列和换出变量对应的系数行交叉处的系数称为“主元素”），这里主元素为，方便起见，在单纯形表中用“[ ]”把这一元素圈出。其次，围绕主元素进行“消去法”计算，单纯形称之为旋转运算，使得在主元素所在的列中，主元素位置变为1，同列中的其他位置变为0。通过两种运算来达成这一目的：第1种运算是将某一行同时乘以某一非零数值，第2种运算是将某一行乘以某一数值后加到另一行上去。借助旋转运算就可以等价地把主元素所在的新变量的系数列变为单位列向量，同时不改变其他原有选入变量的系数列向量（仍为单位列向量）。本例中第3行主元素位置系数本身就为1，将该行数值同乘以（-2）然后加到第1行上去，得到如表3-3-3所示的最后结果。最后，在XB列把新的变量写入（用替代），相应地把CB列价值系数更新，准备重新计算检验数。

得到新的单纯形表如表3-3-3所示。

可以看到，该表实际上对应于式（3-3-4a）。这时得到新的变量为，记为，。

对照表3-3-3、表3-3-1和式（3-3-3a）就会发现，实际上新换入的变量取值就是表3-3-1中的，换出变量的取值变为0；而仍留在XB这一组的变量的取值经过一个旋转运算，取值更新了；其他仍为未选入的变量（这里是）取值保持为0。

在这样变换完成后，目标函数由0变为9，这一增加量实际上就是。

对应于式（3-3-4a）、式（3-3-5a），下面重复第3步至第5步，直到目标函数再也无法增加为止，具体过程如下。

第3步，重新计算当前解X(1)的检验数，如表3-3-3所示，其中，存在大于0的正数，说明当前解不是最优解，需要继续迭代。

第4步，选取检验数为正的变量为新的换入变量，计算当前选入变量的值，即

由此确定作为换出变量，确定新的选入变量为，相应主元素为。

第5步，围绕主元素进行旋转运算，由于主元素已经为1，不需要计算，将该行乘以-1加到第2行上去，然后更新相关数值，得到第3张单纯形表，如表3-3-4所示。

这时得到新的可行解，目标函数值。

再回到第3步中，重新计算的检验数，得到未选入变量的检验数仍为正数，说明还未得到最优解，需要进一步迭代。下一步迭代请读者完成，计算结果如表3-3-5所示。

这样经过4张单纯形表的计算，发现最终单纯形表中所有变量检验数取值均为非正，说明找到了最优解，相应最优解为，目标函数值。最终得到，在该问题中，实际应使用Ⅰ型炮弹4个基数，Ⅱ型炮弹2个基数，战斗力指数最大为14。

对照3.2节中图解法的计算过程，发现上面单纯形法的求解过程如图3-3-1所示注3。

注3 观察图3-3-1中的求解过程，值得注意的是，这里最优解在Q3点，如果第一迭代不是从0→Q1，而是从0→Q4，显然会使求解过程变简单，为什么会发生这种情况，同时怎么才能使得迭代第一步从0→Q4呢？更一般地，这个过程为什么能得到最优解呢？能够多快得到最优解呢？

求解过程与结果如表3-3-6所示。

读者会发现，上述求解过程具有普遍性，无论线性规划规模多大，均可以用类似的过程解决。