第四节线性规划单纯形法与单纯形表

1.4.1线性规划单纯形法的基本思路

单纯形是求解线性规划问题的通用方法。由第二节的定理3可知，如果线性规划问题有最优解，则最优解一定在可行域的某顶点处取得，即最优解一定是某一个基可行解，因此可以从线性规划问题的基可行解中去寻找最优解。单纯形法的基本思路是：先找出一个基可行解，对它进行判断，看是否是最优解；若不是，则按照一定法则转换到另一改进的基可行解，使目标函数值更接近于最优值，对新的基可行解再进行判断，若仍不是，则再转换，按此重复进行，一直到求得最优解或能判断所求线性规划问题无解时为止。以下结合例1.1的求解过程来理解单纯形法的解题思路。

例1.1的标准形为：

模型中的可理解成三种原材料的节余量。前面已经讨论出，约束条件的系数矩阵

中的构成了线性规划问题的初始基，即：

令非基变量，由约束条件可得，由此可得初始基可行解，当前目标函数值=0。

该结果的经济含义是该企业不生产任何产品，原材料全部节余()，产品利润为0，这肯定不是最优结果，因为只要生产产品都可以使利润大于0。

从利润函数也可以看出，因为的系数为正数，中任何一个取比现值()大一点的数，即让其变为基变量，都会使值变大。由于的系数比的系数大，所以变大会使值增加越快，优先让变为基变量(进基)。

由于基变量的固定为3个，进基的同时还要从原来的三个基变量中选出一个使其变为非基变量。进基意味着其取值从0变为一个正数，其经济意义就是生产乙产品，但其产量并不是无限制增加的。分析用非基变量表示基变量的表达式：

为非基变量，取值为0，当乙产品的产量增加时，三种材料的节余量会减少，但这种减少是有限度的，最后的节余量为正数或零，即：

上式中，原材料C对应的节余量最先减少为零，说明它是资源中的薄弱环节，以此确定为出基变量(由基变量换为非基变量)。

到此，新的基变量变为，新的非基变量为，写出用非基变量表示基变量的表达式：

令非基变量为零，可得新的基可行解，新的目标函数值=600。

把上述三个式子代入目标函数可得用非基变量表示的目标函数：

由于非基变量的系数为正数，当它取非零值时(即变为基变量)，目标函数值会变大，所以目前的基可行解不是最优解。于是再利用上述方法，确定进基变量和出基变量，求得新的基可行解，新的目标函数值=840，此时用非基变量表示的目标函数为：

由于非基变量的系数为正数，再进行一次基的变换，求得新的基可行解，新的目标函数值=975，此时用非基变量表示的目标函数为：

上式中，所有的非基变量的系数都为负数，当它们取非零值时(即变为基变量)时，目标函数值会变小。这说明当前的目标函数值为最优值，当前的基可行解是最优解。该企业的最优生产计划方案是：生产甲15吨，生产乙7.5吨，可获得最大利润97.5万元。

1.4.2单纯形法的一般描述和求解步骤

由以上分析可知，单纯形法中的重要步骤为确定初始可行基以得出初始基可行解、对基可行解的判别以及基变换。

(1)确定初始基可行解

最先找出的基可行解称为初始基可行解。基可行解是满足非负条件的基解，而基解是令非基变量为零，利用约束条件解出基变量取值所构成的那组解。所以要确定初始基可行解，首先要确定初始可行基。一般地，找阶系数矩阵中的阶单位子矩阵作为初始可行基，其确定方法如下：

①直接观察法

若线性规划问题：

的系数矩阵中恰好存在个线性无关的列向量，通过调整构成阶单位矩阵，则将其作为初始基，即：

为了方便描述，在上述记法中，对基向量进行了重新排序，它并不对应于系数矩阵A中的前列向量。

②加松弛变量法

对于约束条件(决策变量非负性约束除外)全为“”型的不等式的线性规划问题

当把模型转化为标准型时，在每个约束条件(决策变量非负性约束除外)的左端加上一个非负的松驰变量，则松驰变量的列向量恰好构成阶单位矩阵，将其作为线性规划问题的初始基。

例如下列线性规划问题：

除决策变量非负性约束条件外，其它的约束条件都为“”型的不等式，将其化为标准型：

显然，系数矩阵中

列变量组成的子矩阵是3阶单位矩阵，可将其作为初始基。

③加人工变量法

对约束条件含有“”形式的不等式和等式，且不存在单位子矩阵时，就可通过添加人工变量的方法，构造人造基。对“”形式的不等式，先在不等号的左端减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束在等号的左端加上一个非负的人工变量，总能得到一个单位矩阵。

例如下列线性规划问题

在第一个约束条件的左端加上一个非负的人工变量在第二个约束条件的左端减去一个非负的剩余变量，再加上一个非负的人工变量，在第三个约束条件的左端减去一个非负的剩余变量，再加上一个非负的人工变量，则约束条件转化为：

显然，系数矩阵中

列向量组成的子矩阵是3阶单位矩阵，可将其作为初始基。

若初始基变量为，非基变量为，则初始基可行解，即令非基变量为零时，基变量等于相应的限额系数。

(2)对基可行解的判别

得出基可行解后，就需要判别它是否是线性规划问题的最优解。在单纯形法需要建立对解的判别法则。

线性规划模型：

经过变换后，基变量可用以下式子表示：

代入目标函数得：

令，则有

令，上式可变为：

(1-14)是用非基变量表示的目标函数，称为单纯形法中的检验数，所有基变量的检验数为零。根据检验数的符号可作出如下判别：

①当所有变量的检验数小于或等于零时，线性规划问题得到最优解。

②当所有变量的检验数小于或等于零，且存在某个非基变量的检验数等于零时，线性规划问题存在多重最优解。

③当所有非基变量的检验数小于零时，线性规划问题得到最优解，且最优解唯一。

⑤若有一个非基变量的检验数大于零，且对应的技术系数全部小于或等于零，则线性规划问题具无界解(或称无最优解)。

⑥若有非基变量的检验数大于零，且对应的技术系数有大于零的，则线性规划问题解的情况不确定，需进行换基，继续计算。

以上判别法则适用于目标函数极大化的线性规划问题。当求目标函数极小化时，将其化为标准型。如果不化为标准型，将①、②中“小于或等于零”改成“大于或等于零”，将③、④、⑤中的“检验数小于零”改成“检验数大于零”。

(3)基变换

由单纯形法解的判别法则可知，若有非基变量的检验数大于零，且对应的技术系数有大于零的，则目标函数值还有增加的可能性，需进行基变换，将其中某个非基变量换到基变量中去(称为进基变量)，同时，某个基变量要换成非基变量(称为出基变量)，随之会得到一个新的基可行解。从一个基可行解到另一个基可行解的变换，就是进行一次基变换。从几何意义上讲，就是从可行域的一个顶点转向另一个顶点。

确定进基变量的原则是：为了使目标函数值尽快地增加，通常选检验数中的最大者，即，然后选对应的变量作为进基变量。

确定出基变量的原则是：为保持解的可行性，就是说，要使原基可行解的某一个正分量变成0。同时要保持其余分量均为非负，这时可按“最小比值原则”选换出变量，即若

    (是经过变化后对应于的数值)。

选择对应的基变量为换出变量。

(4)迭代

在确定了进基变量和出基变量之后，要把和的位置进行对换，新的基矩阵中，要把变成原来的形式以取代后者的位置，就是说要把对应的系数列向量变成单位列向量。称为主元列，称为主元素，变换过程中，把主元素化为1，把主元列的其它元素化为0，这可以通过对约束方程组的增广矩阵进行初等行变换来实现，变换结果得一新的基可行解。然后转入(2)。

1.4.3单纯形表

在实际求解过程中，为了便于计算和检查，设计出一种表格，称为单纯形表格来实施计算过程。

(1)计算步骤

①将线性规划数学模型转化为为标准型；

②找出初始可行基，建立初始单纯形表，确定初始基可行解；

③根据判别法则，检验各非基变量的检验数，若，则已得到最优解，停止计算；若在大于零的检验数中，有某个对应的系数列向量，则该线性规划具无界解，停止计算；否则转入下一步。

④选择最大的检验数对应的非基变量作为进基变量。计算：

，选择对应的基变量作为出基变量。

⑤在单纯形表中，以为主元素，对约束方程组的增广矩阵进行初等行变换，将化成第行等于1的单位列向量。

重复②到⑤，直到终止。

(2)初始单纯形表

含初始基可行解的单纯形表称为初始单纯形表，迭代过程中，每找出一个新的基可行解时，就重新画一张单纯形表，含最优解的单纯形表称为最终单纯形表。

初始单纯形表中各块数据与线性规划模型一一对应，对于线性规划模型(为描述方便，将个基变量放前面)。

根据各块系数列初始单纯形表，如表1-3。

表1-3 初始单纯形表

表1-3中，第一行填入目标函数中各变量的系数(价值系数)；第一列为填入各基变量的系数；第二列填入各基变量；第三列填入约束方程组右端的常数(限额系数)；第四列分别填入各决策变量对应的系数，每一行对应一个约束方程；第五列是在确定换入变量后，按规则计算后填入相应的数据；最后一行称为检验数行，是对应各变量的检验数，基变量的检验数，非基变量的检验数； 最后一行的第三列为当前基可行解对应的目标函数值：。

现用单纯形表法求解例1.1，其线性规划数学模型的标准形如下：

前面已分析出，初始基变量为，根据标准型中各数据，列单纯形表如下：

表1-4 单纯形表

根据表格中可以看出初始基可行解为，非基变量的检验数计算如下：

因为检验数都大于零，对应的列向量有正分量存在，所以需要进行基变换，以寻找最优解。

，“50”竖着对应的变量为进基变量，再计算。

“12”横着对应的变量为出基变量。所在列与所在行的交叉处2为主元素。

对限额系数及技术系数组成的矩阵进行行初等变换，将主元素化为1，将对应的列向量化成单位列向量，在列中将换成，在列中将相应的价值系数也换过来，得到新表1-5。

表1-5 初等变换过程

根据表1-5中列的数据，新的基可行解，对应的目标函数值=600。

由于还存在正检验数40，且对应的列向量有正分量，需要再次进行基变换。再次按相关法则选择进基变量和出基变量，进行行初等变换，得到新的单纯形表1-6。

表1-6 初等变换过程

根据表1-6中b列的数据，新的基可行解，对应的目标函数值=840。

由于还存在正检验数15，且对应的列向量有正分量，需要再次进行基变换。再次按相关法则选择进基变量和出基变量，进行行初等变换，得到新的单纯形表1-7。

表1-7初等变换过程

根据表1-7中b列的数据，新的基可行解，对应的目标函数值=975。

由于所有的非基变量的检验数均小于零，说明目标函数值=975已达最优，新的基可行解为最优解，且解是唯一的。