第六节人造基下的单纯形法

前面讨论了对于系数矩阵有单位子矩阵或者约束条件为“”型不等式的线性规划模型，转化为标准型后，系数矩阵有单位子矩阵，可将其作为初始基，易确定初始基可行解。对约束条件含有“”形式的不等式和等式，转化为标准型后，不存在单位子矩阵时，就可通过添加人工变量，构造人造基的方法确定初始基变量。具体构造初始基的方法前已讲述，本节讨论含人造基的线性规划模型的求解方法法：大M法和两阶段法。

设线性规划问题的约束条件是：

(若约束条件含有“”形式的不等式，先转化为等式)分别给每一个约束方程加入人工变量，得到：

系数矩阵为：

将其中单位子矩阵作为初始基，对应的变量为基变量。令非基变量为零，便可得到一个初始基可行解：。

因为人工变量是后加入到原约束条件中的虚拟变量，要求经过基变换将它们从基变量中逐个替换出来。基变量中不再含有非零的人工变量，这表示原问题有解。若在最终表中当所有(目标函数极小化时，)，而在其中还有某个非零人工变量，这表示无可行解。

1.6.1大M法

加进人工变量后，为限制人工变量取值，假定人工变量在目标函数中的系数为(-)(为任意大的正数，目标函数极小化时，系数为)，只要人工变量不取零，目标函数就不可能实现最大化，即目标函数要实现最大化时，必须把人工变量从基变量中换出。

【例1.7】试用大法求解以下线性规划问题。

解：引入松弛变量，剩余变量，将线性规划模型转化为标准型：

松弛变量的列向量为，可作为初始基变量，为得到初始基，在第二、三个约束条件中引入人工变量，，得到：

这里是一个任意大的正数。

再用前面介绍的单纯形表法进行求解，见表1-9。表1-9中的最终表表明得到最优解是：

目标函数：

表1-9 最终单纯形表

1.6.2两阶段法

为将人工变量从基变量中换出，对添加人工变量后的线性规划问题分为两个阶段来计算。

第一阶段：先构造一个目标函数中只含人工变量的线性规划问题，即令目标函数中其它变量的系数为零，人工变量的系数取某个正数(一般取1)，原约束条件不变的情况下使该目标函数极小化。然后用单纯形法求解上述模型。求解结果中，当人工变量取零时，目标函数也为零，这时候的最优解是原线性规划问题的一个基可行解；当目标函数不为零时，即最优解中的基变量中含有非零的人工变量，表明原线性规划问题无可靠解。

第二阶段：将第一阶段计算得到的最终表，除去人工变量。将目标函数行的系数换原问题的目标函数系数，作为第二阶段计算的初始表，继续用单纯形法计算。

各阶段的计算方法及步骤与第3节单纯形法相同，下面举例说明。

【例1.8】试用两阶段法求解下列线性规划问题

解：先在上述线性规划问题的约束方程中加入人工变量，构造第一阶段的数学模型为：

这里是人工变量。用单纯形法求解，见表1-10。第一阶段求得的结果是，得到最优解是：

因人工变量，所以是这线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消填入原问题的目标函数的系数。进行第二阶段计算，见表1-11。

表1-10 单纯形法求解

表1-11 第二阶段计算过程

从表1-11中得到最优解为，目标函数值=-2。

1.6.3单纯形法小结

(1)根据实际问题给出数学模型，列出初始单纯形表。进行标准化，见表1-12。

表1-12 标准化过程

分别以每个约束条件中的松弛变量或人工变量为基变量，列出初始单纯形表。

(2)对目标函数求的线性规划问题，用单纯形法计算步骤的框图见图1-6。

图1-6 单纯形法计算步骤