上节讨论了线性规划问题的约束条件为：
化为标准形式时，在每个不等式左端添加一个松弛变量，由此在约束方程的系数矩阵中包含一个单位矩阵，选这个单位矩阵作为初始基，求初始基可行解和建立初始单纯形表十分简单方便。但当线性规划的约束条件都是等式，而系数矩阵中不含有单位矩阵时，为了迅速地找到一个初始基可行解，往往通过人为添加非负变量（称这种人为引入的变量为人工变量）来构造一个单位基矩阵。当约束条件是“≥”的情况，可以先在不等式左端减去一个非负的剩余变量（也可称为松弛变量）化为等式，然后再添加一个人工变量。设线性规划问题的约束条件是：
1.大M法
在一个线性规划问题的约束条件中加进人工变量后，要求人工变量对目标函数取值不受影响，为此取人工变量在目标函数中的系数为-M（在最小化问题中取M），这里是一个很大的正数，通常称M为惩罚因子，这样目标函数要实现最大化时，必须把人工变量从基变量换出；否则目标函数不可能实现最大化。
例1-13试用大M法求解下列线性规划问题。
利用单纯形法求解，求解过程见表1-11。
表 1-11
2.两阶段法
利用电子计算机求解含有人工变量的线性规划问题时，只能在计算机内输入一个很大的数字来代替M，如果线性规划问题中的aij，bi或ci等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，故称为两阶段法。
两阶段法的第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其他变量的系数为零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束条件不变的情况下求这个目标函数极小值时的解。在第一阶段中，当人工变量取值为0时，目标函数值也为0，这时的最优解是原线性规划问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有人工变量，表明原线性规划问题无可行解。
当第一阶段求解结果表明问题有可行解时，第二阶段是从第一阶段的最终单纯形表出发，去掉人工变量，并按问题原来的目标函数继续寻找问题的最优解。
例1-14试用两阶段法求解下列线性规划问题。
表 1-12
表 1-13
续表 1-13
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
