我们将单纯形法归纳如下：

①选定初始基B（它对应的基本解是（LP）的一个可行解，称此基为原有可行基），确定指标集IB，ID，作单纯形表T（B）；

②T（B）中rj≥0对j∈ID是否均成立？

若是，则得（LP）的一个基本最优解

最优值f＊＝f0，算法终止.

若否，则定指标t：

转步骤③.

③在T（B）中yit≤0对i＝1，…，m是否均成立？

若是，则（LP）的目标函数值f在可行域内无下界，算法终止；

若否，则按最小比值准则定指标k，使

以ykt为枢轴元素进行转轴，得新的原有可行基B′及指标集IB′，ID′以及相应的单纯形表T（B′）；将B′，IB′，ID′视为B，IB，ID，转步骤②.

例1－5　给出（LP）与表1－4、表1－5如下，分析表1－4与表1－5的有关信息：

表1－4

表1－5

解　（LP）中的两个等式方程已经是典型方程，所以可以非常方便地取x4与x3为初始基本变量，将相关的信息列成表1－4.将表1－4看作T（B），相应的IB＝｛4，3｝，B1＝4，B2＝3，对应的基B为

因为r1＝－2＜0，所以基本可行解X0＝（0，0，20，8）T不是最优解，取t＝1，k＝2（Bk＝B2＝3），x1为进基变量，xB2＝x3为出基变量，y21＝5为枢轴元素，在表1－4中用括号给以标出.

将表1－5看作T（B′），相应的IB′＝｛4，1｝，＝4，＝1，对应的基为

我们当然可以通过转轴公式（1－26）至（1－29）由T（B）来得到T（B′）（利用电子计算机进行计算就是按照此方法进行的），但在进行手工计算时，我们可以直接通过消元法由T（B）来得到T（B′）.

在T（B）表1－4中，将第二行除以枢轴元素y21＝5，便得到表1－5的第二行；用表1－4的第一行减去表1－5的第二行乘以表1－4中的y11（值为－1），便得到表1－5的第一行；用表1－4的第三行减去表1－5的第三行乘以表1－4中的r1（值为－2），便得到表1－5的第三行.

表1－5中的检验数rj都非负，所以X＊＝（4，0，0，12）T为最优解，最优值f＊＝－8.

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

解　首先把它化成标准型：

执行步骤①：选取初始指标集IB＝｛4，5，6｝，ID＝｛1，2，3｝，这时B为单位阵，故｜B｜≠0，易知，关于B的基本解（0，0，0，3，6，7）T是一个可行解，其单纯形表如表1－6.

表1－6

执行步骤②：现min｛rj｜rj＜0，j∈ID｝＝－4＝r3，故取t＝3.(www.daowen.com)

执行步骤③：现y1t＝y13＝3，y3t＝y33＝1均大于零，因而

执行步骤④，以ykt＝y13＝3为枢轴元素对表1－6进行转轴，得表1－7，继续迭代得表1－8.

表1－7

表1－8

由于表1－8中rj≥0对j＝1，…，6均已成立，故算法终止.原规划最优解X＊和最优值分别为

例1－7　证明下列线性规划：

在其可行域内无下界，并给出一个可行解，有f（）＜－3 000.

证　现取初始指标集IB＝｛3，4｝.由于目标函数中x3及x4的系数不为零，而由约束条件可知：

于是，有初始单纯形表如表1－9.

在表1－9中，r2＝－1＜0，又y12＝－1＜0，y22＝－2＜0，最小比值准则失效，所以（LP）的目标函数值在可行域内无下界.

取

表1－9

由式（1－34）得

为使f（）＜－3 000，取ε＝3 110，即得（LP）的一个可行解

单纯形法的产生，当年被认为是数学界的一大突破，难度也比较大，而在本节介绍的单纯形法，我们可以看到，它不过是方程组的一系列等价变换，只要应用初等数学知识就可以了.

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

代入模型并引进松弛变量x6，x7，得到标准模型（LP），用单纯形法求得最优解：

因而，原有问题的最优解为：

最优值为f＊＝－9.

仿照此例，如果一个线性规划问题中有k个自由变量，变换≥0）将使对应的非负变量个数加倍.我们可以用k＋1个非负变量来代替k个自由变量，即令

感兴趣的读者可以用图解法来求解这道变量为自由变量的例题.