现给标准型线性规划（LP）：

对第i个等式约束引进一个非负变量xn＋i（i＝1，…，m），我们称它们为人工变量，得到一个线性规划（LPM）：

其中M是一个充分大的正数.为了今后说明问题方便起见，记

显然，用单纯形法求解（LPM）时，我们就取初始指标集IB＝｛n＋1，…，n＋m｝，其相应基B为一个单位阵.

此时，基本解XB＝b，XD＝0是一个可行解.

由于M是一个充分大的惩罚数，（LPM）要实现最优值，随着迭代的进行必然不断地把人工变量从基本变量中置换出去而成为非基本变量.

下面的定理1－3将告诉我们，当（LPM）求解结束时，原有问题（LP）的求解也就同时得到了解决.

定理1－3　应用单纯形法求解（LPM），那么

该定理告诉我们，在用大M法求解（LP）所得的最后一张单纯形表T（B）中，如果基本变量XB中存在值大于零的人工变量，则（LP）不可行；反之，在基本解中，若人工变量的值都为零，则（LP）与（LPM）或者都有最优解，或者都无下界.

在大M法迭代过程中，由公式

可知，单纯形表中rj和f0为M的一次多项式.设它们为

由于M是一个充分大的正数，因此：

例1－13　求解下列线性规划：

解　首先将它化成标准型：

因为松弛变量x5可以作为初始基本变量，所以我们仅对第一、第三个等式约束分别引进人工变量x6及x7，得（LPM）：

用单纯形法求解时，可取初始指标集

这时基B＝I＝B－1，＝（M，0，M）.

对初始单纯形表T（B）的有关元素计算如下：

或者，我们在初始单纯形表T（B）的右边添加一列CB，上端添加一行C，利用公式直接在表上计算rj及f0.

我们得初始单纯形表如表1－19所示.

表1－19(www.daowen.com)

我们取x1为进基变量，x6为出基变量，y11＝2为枢轴元素，进行转轴，得表1－20.

表1－20

继续迭代得表1－21.

表1－21

由表1－21得原规划的最优解和最优值如下：

例1－14　求解下列线性规划问题：

解　上述线性规划问题相应的（LPM）如下：

取初始IB＝｛5，4｝，有B＝I＝B－1，CB＝（M，0）T，整个迭代过程见表1－22和表1－23（初始单纯形表中的信息rj和f0我们利用公式直接在表上计算；转轴过程中的rj和f0我们仍用转轴公式来计算）.

表1－22

表1－23

现在r3＝－，而y13＝－，y23＝－，故（LPM）无下界，又由于人工变量x5＝0，因此原规划无下界.

例1－15　求解下列线性规划：

解　引进人工变量x5和x6，得（LPM）：

现取初始指标集IB＝｛5，6｝，此时基B＝I＝B－1，＝（M，M），因而

由此我们得初始单纯形表如表1－24，转轴后得表1－25.

表1－24

表1－25

现在r2＝＝－1＜0，而y12＝－1＜0，y22＝0，最小比值准则失效，故（LPM）无下界.又由于人工变量x6＝，因此原有规划不可行.