3.4 单纯形法的理论基础

本节集中说明单纯形法严谨完整的理论基础，主要涉及线性规划问题解的性质、解的分类及最优解的存在性等。本节有较多定义和定理，请读者注意，这些内容都是建立在线性规划问题的标准形式之上的。

考虑线性规划问题的标准形式：

这里，为n维列向量，为n维行向量，为m维列向量，为维系数矩阵。

定义3.1　可行解、最优解

记，若某一决策变量向量，则称是线性规划问题的可行解。设有一，且对任意，有，则称为线性规划问题的最优解。

定义3.2　基、基向量、基变量、非基变量

设系数矩阵A行满秩，即A的秩为，等价于A的所有n个列向量中可以找出m个组成一个线性无关组。记，取其中m个列向量为线性无关组，记为B，则B是一个维的可逆方阵，称B是线性规划问题的一个基。称其中每个向量为基向量，称下标相同的对应决策变量为相应于的基变量，所有决策变量中除基变量外的其他变量称为非基变量。

定义3.3　基解、基可行解、可行基

方便起见，不妨设是一个基（若不然，可以通过调整变量的位置达到此目的），则，有

相应地，将决策变量向量写为

其中，，，则可表示为

进一步，有

因为B是可逆矩阵，故上式两边可左乘得

在式（3-4-1）中令所有非基变量，则基变量部分。显然满足，称之为基解。

此外，如果，则X也满足的条件，X也是可行解，称为基可行解；相应地，称B是可行基。

有关线性规划问题的可行解、基解与基可行解的关系如图3-4-1所示。说明如下：满足所有约束条件的解称为可行解，只满足，且对应了A中一个满秩子矩阵的解称为基解，如果基解同时也满足，则是基可行解。显然，线性规划问题的可行解可能是无穷多个，但基解和基可行解只可能为有限多个。

当线性规划模型确定后，基解的取值仅仅取决于基B的选择，选定一个基，就会有一组基解，那么有多少这样的基解呢？

由于基本身是系数矩阵A的可逆子矩阵，且行数与A一致，故在A中n列里任取m列并不一定是基，那么基解的个数不确定，相应基可行解的个数也不确定。但无论如何，由于基的个数最多为组合数，所以基解个数不超过个，基可行解当然也不超过个。

例3.4.1　找出下面线性规划问题的所有基，说明相应的基向量、基变量和非基变量，求出基解的值，并指出哪些是基可行解。

解：先验证模型形式是否为标准形式，即写出该线性规划问题的系数矩阵：

（1）取，显然其为可逆矩阵，是该线性规划问题的一个基，则相应的基向量是，基变量是，非基变量是。计算基解的取值，有

由于，故不但是基解，还是基可行解，对应基是可行基。

（2）取非奇异，故其也是该线性规划问题的一个基，相应的基向量是，基变量是非基变量是。计算相应基解的取值：

由于存在负分量，故虽是基解，但不是可行解，当然也不是基可行解，对应基不是可行基。

（3）取奇异，说明它不是该线性规划问题的一个基，不存在基变量、基向量等方面的问题。

所以这个线性规划模型所有列的3个组合中有2个可逆，故存在2个基解，但其中只有一个解是基可行解注4。

注4 事实上，在例3.4.1中找到的基可行解X（1）就是它的最优解，为什么？实际上对于线性规划来说，在基可行解中找到最优解是必然的。

定义3.4　权值、凸组合、凸集

设为一组非负实数，如果满足，且（），则称这样的一组数为权值。

进一步，设为一组权值，是n维欧式空间中的k个点，若中一点可表示为

则称X为的一个凸组合，若其中每个权值，则称其为一个严格凸组合。

考虑两个点的情况。设D是n维欧式空间中的一个点集，如果以D中任意两点、为端点的凸组合，均有，则称D是一个凸集。

如图3-4-2所示，左侧两个是凸集，而右侧两个不是凸集。

凸集是对任意凸组合封闭的集合。1个点的凸组合实际上用1个点自我表达；2个点的凸组合表现为2个点之间的1条线段；3个点的凸组合其实是1个三角形。

定义3.5　顶点（极点）

设D是n维欧式空间中的一个点集，若其中一点不能用不同的两个点和的严格凸组合［不存在一个数使得成立］，则称是的一个顶点，也称极点。

注意这里顶点的定义是用“否定”方式给出的，即不能用凸集中另外两点的严格线性组合表示，这和直接观察到的凸集顶点只能“自己表达自己”是一致的。

需要说明的是，上面的凸集、凸组合、顶点等概念是二维空间中相关概念的自然延伸，读者可以借助“几何”图形理解其含义。不过，当这些定义一旦在任意空间给定后，已经具有“代数”上的抽象意义，不再依赖于图形了。

基于上面给出的几组定义，有以下论断：线性规划问题的可行域如果非空，一定是凸集；进而，如果是有界凸集，由于线性规划问题目标函数的连续性，其一定可在可行域的有界凸集上取得极值，也就是存在最优解。最终可以知道，在有界可行域的顶点处，由于目标函数的线性性质（连续性和单调性），一定可以在某一顶点上找到至少一个最优解。

实际上这里完成了一个转化，即将在无限多个可行解中找最优解的过程转化为在有限多个的可行域顶点中寻找。当然，这些论断需要严格的证明，下面给出几个定理。

定理3.1　若线性规划问题的可行域非空，则是凸集。

证明：按照凸集的定义来证明即可。

可行域可写为

对，有

又因为，所以，即证得是凸集。

定理3.2　若和是线性规划问题的两个不同的最优解，则这两点连线上的所有点都是最优解。

请读者参考定理3.1的证明过程自行完成本定理的证明。

定理3.3　线性规划问题的可行解为基可行解的充要条件是的正分量所对应的系数列向量是线性独立的。

证明：（1）先证必要性。因为是基可行解，自然也是基解，其基变量对应的系数列向量是线性独立的。而的正分量一定都是基变量（非基变量在基可行解中取值均为0），所以的正分量所对应的系数列向量也一定是线性独立的。

（2）再证充分性。通过调整变量顺序，可将所有正分量放在所有变量的前面部分。所以可设可行解，其中，由条件可知线性无关，且一定有。

因为是可行解，有，写成向量形式，即

① 如果，取非奇异是线性规划问题的一个基，则有

所以是基可行解。

② 如果，因为A的秩为，一定存在另外个列向量，不妨设为，使得非奇异，则有

所以是基可行解。

基于定理3.2，下面给出单纯形法理论基础中最为重要的论断。

定理3.4　线性规划问题的基可行解X对应于可行域D的顶点。

证明：（1）先证必要性。设是线性规划的基可行解，不妨设。应用反证法，假若X不是D的顶点，根据顶点定义，一定存在D中的两个不同的点及，有

有

因为均为可行解，所以。同时，考虑的取值，有

又因为

所以有

有，又，则中至少有一个取值非零，所以线性相关，

由定理3.3知，线性无关，矛盾！所以一定是D的顶点。

（2）再证充分性。设是D的顶点，同上设。这里为可行解，要证其为基可行解，使用如上必要性证明过程中的反证法，假若其不是基可行解，由定理3.2可知，其正分量对应的系数列向量一定线性相关，故存在不全为0的，使

又因为，即，则对任意的正数，有

可令足够小，满足，这样可使上述两式中所有的系数。

令

则有，这样我们就构造出线性规划问题的两个可行解，且由于不全为0，一定有，同时有

也即可用两个不同的可行解线性表示，这与是的顶点矛盾。故假设不成立，一定是线性规划问题的基可行解。

定理3.5　若线性规划问题有可行解，则必有基可行解。

证明：分情况讨论。

（1）若，则任取一个基，就是基可行解。

（2）若，则0不是可行解。

任取一个可行解，如果正分量相应的列向量线性无关，根据定理3.3得是基可行解，得证。

否则，线性相关，即一定存在不全为0的数，使得

成立，又X是可行解，有，即

考虑上面两个等式，则对于任意有

令

则

同时，只要取

就有，说明这时都是可行解，且满足

若中有一个为基可行解，即找到了基可行解，命题得证。否则设两者都不是基可行解，观察两者的表达形式，由于的取法，可知在的所有分量中，至少有一个为0，说明中至少有一个的非0分量个数比少，不妨设为［如取，以下过程类似］，对实施如上作用在上的过程，它不是基可行解，则非0分量对应系数列向量线性相关，进一步对各分量存在类似式（3-4-3a）和式（3-4-3b）的表达式，对应地找到两个新的可行解，记作，两者是由延伸出来的，如果两者中有一个是基可行解，证明停止。否则同上分析，得知两者中至少有一个的非0分量个数比少，对其再进行如上作用于和的操作，会得到两个新的可行解，如果这两个可行解中仍然没有基可行解，那么其中只要有一个非0分量个数少于，选取其作为新的点，反复下去，可以得到，由于分量总数有限，且0不是可行解，最终一定会终止于某一步，使得延伸出来的可行解为基可行解（顶点），得证。

引理3.1　若函数在有界闭域上连续，则在上有界，且取得最大值与最小值。

这是多元连续函数的基本性质，证明从略，读者可以参阅高等数学相关书籍。由于线性规划问题的目标函数是所有决策变量的线性函数，当然是连续的，同时线性规划问题可行域是有界闭凸集，说明线性规划问题只要可行域非空有界，则目标函数极值一定可以找到。

引理3.2　若是任意有界凸集，则中任何一点都可以表示为的顶点的凸组合。

这是有界凸集的重要性质。实际上，对于有界凸集而言，其中任何一点不但可以为其顶点的凸组合，而且凸组合表示还具有唯一性。读者可以从顶点数较少的情况进行理解，如两个点围成的有限凸集为线段，线段上任何一点可以表示为线段两个端点的唯一凸组合；3个点围成的有限凸集为一个三角形及其内部，其中任何一点可表示为3个顶点的唯一凸组合。

这里不给出这个引理的证明，感兴趣的读者可参考文献［4］。

定理3.6　若线性规划问题的可行域有界非空，则该问题目标函数一定可以在其可行域的顶点上达到最优。

证明：线性规划问题的可行域有界，其目标函数是线性函数，显然在其可行域上连续。

由引理3.1可知，线性规划问题的目标函数在其可行域上有界，能够取得最大值，即线性规划问题的最优解存在。同时，根据定理3.4，其一定也有基可行解（顶点），下面说明，其一定可以在顶点上找到最优解。

不妨任取一个最优解考虑，若其就是顶点，那么定理得证；若其不是顶点，那么根据引理3.2，其可以用顶点的凸组合表示，设共有k个顶点，为，则有

代入目标函数中，有

考虑所有的值，共有k个数值，故一定存在最大值，设为，有

即顶点使得目标函数的取值不小于最优解处的目标函数取值，而已经是最优解，那么一定有

这说明顶点也是最优解，即目标函数在顶点上达到了最优。

回顾例3.4.1，在该例中通过遍历所有的基，找到了该问题的唯一基可行解，由定理3.6知道，该问题的最优解必然可以在基可行解中找到，而基可行解是唯一的，因而可以断定：必然是该问题的最优解。

需要注意的是，定理3.6只证明了线性规划问题可行域有界非空时，一定可以在基可行解（顶点）上找到最优解，而线性规划问题可行域有可能为无界区域，那么会怎么样？

区分为两种情况：第一是可行域无界且问题本身为无界解（目标函数无穷大），那么问题本身无最优解；第二是可行域无界但目标函数存在最优解，这时只需要将可行域朝向无穷的方向做一个裁剪即可，这时不会影响目标函数最优，同时可行域变为有界，符合定理3.6的要求。