2.2　单纯形法

在学习单纯形法之前需要了解以下三个基本概念：

凸集：对于一个点集（或区域），如果连接其中任意两点x1，x2的线段都全部包含在该集合内，就称该点集为凸集，否则为非凸集。

极点：若凸集S中的点x，不能成为S中任何线段的内点，则称x为S的极点。

单纯形：若一个凸集仅包含有限个极点，则称此凸集为单纯形。

单纯形法是求解线性规划问题的有效方法。线性规划问题的可行域是n维向量空间Rn中的多面凸集，如果存在最优解则最优解必在该凸集的某极点处达到。极点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

2.2.1　基本解与基本可行解

在绪论中提到过如果目标函数是一元线性函数f（x），x∈[a，b]，则f（x）的最大值（或最小值）必在x的端点上取得，而对多元线性规划问题来说，这一结论也是成立的，即f（x）的最大值或最小值在由约束条件构成的求解域的顶点上取得。线性规划问题属于有约束优化（规划）问题，约束条件由等式线性约束和变量非负条件构成。基本解是只满足线性约束条件的解，而基本可行解是既满足等式线性约束又满足变量非负要求的解。因此线性规划问题的解可通过求解线性等式约束方程来获得。

下面先通过一个例子来说明单纯性法的基本原理及求解过程。

【例2-1】　用单纯形法求解下面的线性规划问题。

maxf（x）=2x1+x2-2x3

s.t.x1+x2+2x3≤5

x1+3x2-x3≤3

x1，x2，x3≥0

解：

（1）先用Matlab线性规划函数求解，其计算程序如下：

%ch2_li1

clc；

close all；

f=-[21-2]；

A=[1 12；1 3-1]；

b=[5 3]；

xl=[0 0 0]；

[x，fval]=linprog（f，A，b，[]，[]，xl）

计算结果为：

（2）手算求解

引入松弛变量，将所给问题化成线性规划标准形式。

maxf（x）=2x1+x2-2x3+0x4+0x5

s.t.x1+x2+2x3+x4+0x5≤5

x1+3x2-x3+0x4+x5≤3

x1，x2，x3，x4，x5≥0

将上式约束方程用矩阵表示：

由于方程个数少于变量个数，因此有无穷多个解。但若取其中3个变量的解为零，则可得到确定的解，并且按这种取法得到的解是有限的，对本问题来说可有10个不同的解。应用Matlab编程检索这10解的部分结果如下：

从中可以看出，虽然这些解都是基本解，但并不都是基本可行解。并且x1=3.6667，x3=0.6667和x1=3.0，x4=2.0都是最优基本可行解。挑选基本解的程序如下：

下面通过初等变换或消元法求解【例2-1】。如果约束条件中变量的系数组成的矩阵是满秩的，则对应的变量为基本变量，其系数矩阵称为基矩阵。求解时应选择选择基本变量和基矩阵进行初等变换。由式（2-2）可知，选择松弛变量x4，x5为基本变量，对应的系数组成的矩阵为基矩阵将会带来很大方便。

令非基本变量x1，x2，x3均为零，则得到x4=5，x5=3。将该结果带入目标函数中，得

f（x）=2×0+1×0-2×0+0×5+0×3=0

这一结果似乎没有带来什么益处，因为对目标函数没有丝毫影响。但是通过观察可以发现，如果将变量x1由0变成正值，用其替换其中一个基本变量，则目标函数增加最多，因为变量x1的系数最大。这是将非基本变量选进基本变量的一个原则，接下来的问题是将原来的基本变量x4，x5中的那一个换出，使其成为非基本变量。解决这一问题要借助约束条件，如果仍旧保持x2，x3为零，并去掉方程中非基本变量x2，x3及其系数，则约束方程为

分别选x1，x4和x1，x5为基本变量考察解的情况。以x1，x4为基本变量，同时令x5=0，结果为x1=3，x4=2，f=6；再以x1，x5为基本变量，同时令x4=0，结果为x1=5，x5=-2，f=10。第二种方案是不可取的，因为解x1=5，x5=-2不是基本可行解，只是基本解。也就是说应该选择变量x5出基本变量表。为了说明进基变量的系数列向量元素与右端项元素的关系，将x1分别替换x4和x5的情况用下面的模型进行分析。用x1替换x4的约束方程为

选a11为消元主元，结果为

从而得　　 　　（2-4）

用x1替换x4的约束方程为

选a21为消元主元，结果为

从而得　　 　　（2-7）

观察式（2-4）和式（2-7）注意到，当

时，可得到基本可行解，否则x1的取值不能使所有基本变量的取值成为基本可行解，见式（2-4）。出基变量与式（2-8）有着必然的联系。式（2-8）中最小比值对应的右端项元素或系数行下标对应的基本变量就是出基变量，且比值分母系数下标就是进基变量对应的主消元元素。验证式（2-3）可知，变量x5为被替换出的变量，与计算结果一致。由此可见目标函数与约束条件配合，约束方程求解完成后，将基本变量结果带入目标函数中，通过比较非基本变量系数大小决定进基变量（此时认为非基本变量取值不为零）。对求最大值问题，系数较大的非基本变量为进基变量；对于最小值问题，系数较小的非基本变量为进基变量，确定了进基变量后，则计算右端项与进基变量在约束方程中列系数向量对应元素的比值，比值小者的行下标对应的基本变量为出基变量。

下面对单纯形法进行更一般的说明。将式（2-1）中的约束矩阵A按列表示

A=[p1，p2，…，pn]

pi，（i=1，2，…，n）是m×1的向量，pi的分量是各约束方程中与设计变量xi对应的系数。设矩阵A的秩为m，将设计变量x分解为基本变量和非基本变量，即x=[xE，xN]T，相应地系数矩阵A也分解为两部分，一部分为基矩阵，用E表示；另一部分为非基矩阵，用N表示。于是A=[E，N]，E=[p1，p2，…，pm]，N=[pm+1，pm+2，…，pn]。式（2-1）中的约束条件重新表示为

即　　ExE+NxN=b

上式两端左乘E-1并移项，得

xE=E-1b-E-1NxN　　（2-10）

xN的分量为非基本变量，它们取不同的值，就会使方程组得到不同的解。如果令xN=0，则得到解

称解x为方程组Ax=b的一个基本解。如果E-1b≥0，则称

为满足约束条件的基本可行解（非负的基本解）。

2.2.2　基本可行解的转换

基本可行解的转换就是在得到了某组基本可行解后，如何进一步改进获得更好的解，最终达到最优基本可行解。从2.2.1的分析可知，获得改进的解是在满足约束条件的前提下使目标函数值增加（对于最大值问题）或使目标函数减小（对于最小值问题）的解。设已经获得一组基本可行解

其对应的目标函数值记为f0。设是另一组基本可行解，将其代入目标函数中，得

如果每次将一个非基本变量转换为基本变量，并假定求目标函数的最大值，那么由式（2-12）可知，选择求和项中系数cj-zj>0最大者对应的非基本变量进入基本变量，当该变量取正值时，可使目标函数增加最多。如果所有非基本变量的系数cj-zj不再有正值，则说明，非基本变量的进基运算不会再使目标函数增加，此时就终止计算，输出最优结果。非基本变量转换为基本变量后，则要将上一轮迭代中的一个基本变量转换为非基本变量，判断出基本变量表的条件由约束方程的消元计算格式给出。

设xk为进基本变量，不失一般性，认为xk替换xr，在约束方程中相应地用pk替换pr，pk，新的基矩阵为E（1），为表示清楚起见，将pk标记为，其元素相应地表示为。因此基矩阵E（1）表示为

变量xk由零变为正值后，新的方程组的解为

其中基矩阵E（1）的逆阵为

这里认为初始基矩阵为单位阵。在基矩阵中用pk替换pr，就是将pk放在第r列的位置上。对于式（2-14）这样的矩阵，其逆矩阵只有第r列的元素发生变化，对角线上的元素为相应元素的倒数，该列上其他元素等于原来的元素取反再除以对角线上的元素。式（2-13）的解为

由于设计变量非负，并假设设计变量在约束方程中的系数和右端项元素均大于零，因此自然满足；而式（2-16）中变量非负意味着

即　　 　　（2-17）

当　　 　　（2-18）

时，则能保证用xk替换xr使所有基本变量非负。在线性规划中，通常称

σj=cj-zj　　（2-19）

为判别数或检验数。对极小化问题，进基变量xk的下标与 项下标“k”对应，非基本变量xk的引入使目标函数 增加最多（最大值问题），或减少最多（最小值问题）。出基变量 下标与 项下标“r”对应。式（2-18），式（2-19）是单纯形法求解线性规划问题重要的判别式和检验规则。

2.2.3　单纯形法计算步骤

应用单纯形法求解时，首先要了解怎样求得初始基本可行解，又怎样从一个基本可行解转到邻近的另一个基本可行解，又怎样检验得到的基本可行解是不是最优解。下面通过【例2-2】说明这些问题。

【例2-2】　minz=-6x1+3x2-2x3

s.t.2x1+x2+x3≤6

x1+x3≤2

x1，x2，x3≥0

解：首先引入松弛变量x4，x5，把数学模型化为标准形式：

minz=-6x1+3x2-2x3+0·x4+0·x5

s.t.2x1+x2+x3+x4+0·x5=6

x1+0·x2+x3+0·x4+x5=2

x1，x2，x3，x4，x5≥0

引入松弛变量后，变量总数n=5，约束方程数m=2（不含变量大于等于零的约束），因此有n-m=3个非本基变量，并令其为零进行求解。一个简单的做法就是选松弛变量x4，x5为基本变量，因为其系数列向量为单位基向量。将基本变量用右端列向量和非基本变量来表示，得

x4=6-2x1-x2-x3

x5=2-x1-x3

令非基本变量x1=x2=x3=0，则基本解为

x4=6，x5=2

记初始基本解为　　x（0）=（0，0，0，6，2）T

此解又满足式xj≥0，j=1，2，…，5，因此，x（0）是基本可行解，它对应着凸可行域的一个顶点。一般来说，对于约束条件全为“≤bi”形式（i=1，2，…，m）的线性规划问题，通过引入松弛变量，可较容易地找到一个初始基本可行解。

下一步，将初始基本可行解x（0）=（0，0，0，6，2）T代入目标函数表达式中，得

z=-6×0+3×0-2×0+0×6+0×2=0

非基本变量x1=x2=x3=0对应的目标函数值z=0，为找出进基变量，将x4，x5代入原式得

由上式看出，x1增加1个单位，目标函数值z下降6个单位。x2增加1个单位，z增加3个单位，x3增加1个单位，z值下降2个单位。如果使x1和x3成为正值，都能使目标函数向极小方向改善，因此当前解不是最优解。

选择的进基变量应是使目标函数改善最大的非基变量进基。由前面的分析看到，在目标函数中，应选择有负系数，且负系数绝对值最大的非基变量进基。【例2-2】中，目标函数里x1系数为-6，所以x1应选为进基变量。这是因为当x1由当前的零变为正值时，使目标函数下降最大。

出基变量的选择也不是任意的，原则是要保证变量满足非负条件。为此，要考察约束条件式。这两个方程均有变量x1要从0上升为正值，要从x4和x5这两个变量中，选择一个出基（即从当前值下降到0），而另两个非基变量x2和x3还要保持为零。

由式

x4=6-2x1-x2-x3

x5=2-x1-x3

得　　x4=6-2x1

x5=2-x1

x1从0变为正值时，x4和x5可从当前值下降为0，但不能成为负值（因为变量要满足非负条件）。由上式可以看出，x1取时，x4和x5均为非负（x4=2>0，x5=0），且θmin使x5=0，因此选x5为出基变量。

已经确定了进基变量x1和出基变量x5，就可进行新的消元求解，继续求解下面的方程。

0·x5+x2+x3+x4+2x1=6

x5+0·x2+x3+0·x4+x1=2

此时，令非基变量x2=x3=x5=0，求x1和x4的解。为了下面便于说明建立单纯形表的过程，用初等变换（消元）求解上面的方程，结果为

-2x5+x2-x3+x4+0·x1=2

x5+0·x2+x3+0·x4+x1=2

解得：　　x1=2，x4=2

再将x1和x4用约束方程的非基本变量表示，得

x4=2-x2+x3+2x5

x1=2-x3-x5

将其代入目标函数，得

z=-6（2-x3-x5）+3x2-2x3+c4（2-x2+x3+2x5）+c5x5

整理得

z=-6·2+c4·2+（3-c4）x2+（-2+6+c4）x3+（c5+6+2c4）x5

由于所有非基本变量的系数均为非负，没有进一步可使目标函数可以减少的非基本变量，因此迭代结束，最优解为x1=2，x2=0，x3=0，f=-12。

根据本书2.2.2的介绍及上面的计算，单纯形法的一般步骤可归纳为：

（1）把线性规划问题的约束方程组表达成标准形方程组，然后找出一个基本可行解作为初始基本可行解。对等式约束或“≥bi”形式的约束如果不易得出初始基本可行解，则需用辅助方法得出，如大M法、两段法等。

（2）若基本可行解不存在，即约束条件有矛盾，则问题无解。

（3）若基本可行解存在，则从初始基本可行解作为起点，根据判别数σ（式（2-19））及θ规则（式（2-20）），引入非基变量取代某一基变量，找出使目标函数值更优的另一基本可行解。

（4）按步骤3进行迭代，直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。

（5）若迭代过程中发现问题的目标函数值无界，则终止迭代。