单纯形法的计算步骤

根据以上讨论的结果，单纯形法的计算步骤归纳如下：

（1）求初始基可行解，列出初始单纯形表。

为了计算上的方便和规格化，对单纯形法的计算设计了一种专门表格，称为单纯形表（见表1-4）。迭代计算中每找出一个新的基可行解时，就构造一个新单纯形表。含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。

表1-4　单纯形表

（2）进行最优性检验。

（3）进行基变换，列出新的单纯形表。

②确定换出变量。根据上一节中确定的θ规则计算

（4）重复第二、三步，一直到计算终止。

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

解：首先给例1-1各约束条件添加松弛变量，将问题化为标准形式。

并据此列出初始单纯形表（见表1-5）。

表　1-5初始单纯形表

为清楚说明计算过程，表1-5中各行分别以（1）、（2）、（3）、（4）标记，表1-6中相应行标以（1）′ 、（2）′、（3）′ 、（4）′ 。

首先将主元素行除以主元素，故有（2）′ = （2）/2，即（2）′行数字由表1-5中第（2）行数字除以主元素2得来。

即表1-6中第（1）′行数字为表1-5中第（2）行数字乘（-1/2）加到表1-6中的第（1）行得来。

类似的有

表　1-6

表　1-7

表1-7中相应各行数字得计算过程如下：

下面对图解法中所介绍的线性规划问题的解的几种特殊情况，用单纯形法进一步求解说明。

例1-11假如例1-1中生产单位产品B1的利润由原来5百元降低至4百元，其他条件不变，应如何安排生产获利最多。

解：所求问题的标准形式为：

表　1-8

续表　1-8

需要注意的是，在最终单纯形表中，除基变量的检验数为零外，非基变量x4的检验数也为零，这表明如果让x4增加不会使目标函数值有所变化，也就是说，如果让x4作为换入变量继续迭代，就会得到另一个基可行解，见表1-9。

表1-9给出的最优解为λj ≤ 0，说明已找到问题的最优解：

表　1-9

其目标函数值也为180。按最优解的定义，是目标函数达到最大值的任一可行解都是一个最优解。所以这个线性规划问题有多个最优解。 由表1-8和表1-9求出的两个最优解为可行域的两个顶点。实际上这两个顶点连线上的所有点都是该线性规划问题的最优解。例如（30，15），其对应的目标函数值也为180。这表明该点虽然不是基可行解，但同样是该线性规划问题的一个最优解。

例1-12利用单纯形表法求解下列线性规划问题。

表　1-10