1.4 单纯形法的进一步讨论

用单纯形法求解线性规划问题时，通常选单位矩阵为初始可行基，但有时标准化后的约束方程系数矩阵不包含单位矩阵的全部列向量。当线性规划方程的约束条件为“=”或“≥”时，标准化后的约束方程系数矩阵不包含单位矩阵全部列向量，为了便于找到初始基可行解，可以引入人工变量，构造人工可行基，人为产生一个单位矩阵，作为初始可行基。

引用人工变量是用单纯形法求解线性规划问题时解决可行解问题的常用方法。人工变量法的基本思路是若原线性规划问题的系数矩阵中没有构成可行基的完整的单位列向量，则在约束方程中加入一个人工变量，便可在系数矩阵中增加一个单位列向量。由于单位矩阵可以作为基阵，因此可选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终的单纯形表中还存在非零的人工变量，则表示线性规划问题无可行解。

对于如下线性规划问题

首先分别对每个约束方程中加入一个人工变量xn+1,xn+2,…,xn+m得到

这样我们就可选xn+1,…,xn+m为基变量，令非基变量x1,x2,…,xn=0，便可以得到一个初始基可行解X(0)=[0,0,…,0,b1,b2,…,bm]T。

下面介绍两种含有人工变量的线性规划求解方法：大M法与两阶段法。

1.4.1 大M法

由于人工变量对相应约束方程的恒等性具有破坏性，只要人工变量取值大于0，原方程的恒等性就会被破坏，目标函数值就不可能是最优，若人工变量取值等于0，原方程的恒等性就不受到影响。大M法下单纯形法的寻优机制会自动将人工变量由基变量转换为非基本量。

当目标函数为max z，对应的人工变量目标函数价值系数为-M;当目标函数为min z，对应的人工变量目标函数价值系数为+M，其中M为充分大的正数。根据最优检验数判别定理进行基的转换，使得人工变量逐渐换出基底，再寻求原问题的最优解。这种方法我们通常称其为大M法，又称惩罚法。

例1-9 用单纯形法求解线性规划问题：

解：将原问题转化为标准型

然后，再添加人工变量x4,x6，将原线性规划问题变为

列出初始单纯形表，在单纯形法迭代运算中，将M当作一个充分大的正数进行运算。检验数中含M符号的，当M的系数为正时，该检验数为正；当M的系数为负时，该项检验数为负。

取基变量为x4, x6，建立单纯形表，迭代计算过程如表1-12～表1-14所示。

在最优单纯形表中，人工变量x4=0，x6=0，所以线性规划问题有最优解，最优解为x1*=45/7，x2*=4/7,x3*=0，目标函数值：z*=102/7。

在最优单纯形表中，如果人工变量仍不为零，则线性规划无最优解。

1.4.2 两阶段法

在用手工计算求解线性规划问题时，用大M法处理人工变量不会有问题。但用电子计算机求解时，对M就只能在计算机内输入一个机器最大字长的数字。如果线性规划问题中的一些参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。

为了克服这个困难，设计分两个阶段来计算添加人工变量的线性规划问题，第一阶段先求原线性规划问题的一个基可行解（人工变量由基变量换出为非基变量）；第二阶段从此可行解出发，继续寻找问题的最优解。这种方法通常称为两阶段法。

原理：当目标函数为max z，对应的人工变量目标系数为-1；当目标函数为min z，对应的人工变量目标系数为+1。

第一阶段将原目标函数系数暂时取零值。根据最优检验数判别定理进行基的转换，使得人工变量逐渐换出基变量。第二阶段再去掉人工变量对应的列，恢复原线性规划问题的目标函数系数，继续迭代找寻原问题的最优解。

例1-10 用单纯形法求解线性规划问题：

解：将原问题转化为标准型

第一阶段。先在以上问题的约束条件中加入人工变量，给出第一阶段的线性规划问题：

这里取基变量为x4,x6，建立单纯形表并迭代运算，可得表1-15～表1-17。

这里x4、x6是人工变量。第一阶段我们已求得ω=0，因人工变量x6=0，x4=0，所以(45/7,4/7,0,0)T是原问题的基本可行解。于是可以进入第二阶段的计算。

第二阶段。将第一阶段的最终计算表中的人工变量所在列取消，并将目标函数系数换成原问题的目标函数系数，重新计算检验数行，可得如下第二阶段的单纯形表，如表1-18所示。

所有检验数σj≤0，所以x1*=45/7，x2*=4/7,x3*=0是原线性规划问题的最优解，目标函数值：z*=102/7。