表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为：

(1)找出初始基可行解。即在产销平衡表上用西北角法或最小元素法，Vogel法给出个数字，称为数字格。它们就是初始基变量的取值。

(2)求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。

(3)确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法或位势法调整。

(4)重复(2)，(3)直到得到最优解为止。

以上运算都可以在表上完成，下面通过例子说明表上作业法的计算步骤。

【例2.9】某公司经销一种产品，下设三个生产点，分别运往四个销售点，每日的产量、各地的销量(单位：吨)及各生产点到各销售点的运价(单位：千元)等信息见表2-20，问该公司如何调运产品，才能使总运费最小。

表2-20 运输信息表

本题属于产销平衡的运输问题。设表示从到的运输量。运输表见表2-21。

表2-21 运输表

求解过程如下：

(1)确定初始基可行解

产销平衡的运输问题总是存在可行解。因有：

必存在：

这就是可行解。又因：

故运输问题必存在最优解。

确定初始基可行解的方法很多，下面介绍两种方法：最小元素法和伏格尔法。

①最小元素法

这方法的基本思想是优先供应运价最低的销地，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基可行解为止。以例2.8为例进行讨论。

第一步：从表3-21中找出最小运价为1，这表示先将的产品全部供应给。因除满足的全部需要外，还可多余4吨产品。在表2-21的的交叉格处的运费量填上3，并将列划去，表示这一列不用再安排运输量了，得表2-22。

表2-22最小元素法计算过程

第二步：在表2-22未划去的元素中再找出最小运价2，确定多余的4吨供应，产地的产品全部被运走，在的交叉格处的运费量填上4，并将表2-22的行划去，表示这一行不用再安排运输量了，得表2-23。

表2-23最小元素法计算过程

第三步：在表3-23未划去的元素中再找出最小运价3；这样一步步地进行下去，直到表上的所有元素划去为止，见表2-24。

表2-24最小元素法计算过程

第四步：表2-24已标数字的格子对应的变量为基变量，所标数字为基变量取值，量未标数字的格子对应的变量为非基变量，取值为零。非基变量取值不需要在表中标出。由此，得到运输模型的初始基可行解，即得到初始调运方案，对应的运费，见表2-25。

表2-25 初始调运方案

②伏格尔法

最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。例如上例中为了使处产品能按最低运价“1”和“2”运出，处产品的运费不能按较低运价“4”运出，只好选择比其高得多的运价“10”。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。伏格尔法的步骤是：

第一步：在表2-21中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表2-26。

表2-26伏格尔法计算过程

第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表2-26中列是最大差额所在列。列中最小元素为4，可确定的产品先供应的需要，在的交叉格处的运费量填上4，同时将运价表中的列数字划去，表示销地的运输量已满，不再安排其它运输量了。如表2-27所示。

表2-27伏格尔法计算过程

第三步：对表2-27中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，如表2-28。表中列和列的差额同时最大，可从中任选一列开始，例如选列。列中最小元素为1，可确定的产品先供应，在的交叉格处的运费量填上3，同时将运价表中的列数字划去，表示销地的运输量已满，不再安排其它运输量了。如表2-28所示。

表2-28伏格尔法计算过程

第三步：对表2-28中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。是差额数最大所在的行，所在行中未被划掉的运价中最小的是3，确定的产品供应，在的交叉格处的运费量填上5，这时所在行的产量和所在列的销量同进被满足了，这种现象称为退化现象，为使基变量的个数保持不变，在所在行和所在列都被划线的同时，在所在行或所在列中未填数字的任一格填上0，见表2-29。

重复第一、二步，直到表上的所有元素划去为止。

表2-29伏格尔法计算过程

第四步：对表2-29中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。选择最大差额所在行或列中的最元素，填运输量、划线，直到表上的所有元素划去为止，见表2-30。

表2-30伏格尔法计算过程

第五步：图2-30已标数字的格子对应的变量为基变量，所标数字为基变量取值，量未标数字的格子对应的变量为非基变量，取值为零。非基变量取值不需要在表中标出。由此，得到运输模型的初始基可行解，即得到初始调运方案，对应的运费，见表2-31。

表2-31伏格尔法计算结果

由以上可见：伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。

(2)最优性检验

检查初始调运方案是不是最优方案的过程就是最优性检验。检查的方法仍然是计算非基变量(在作业表中对应着未填上数值的空格)的检验数，因运输问题的目标函数是要求实现最小化，故当所有的检验数大于等于零时，方案就是最优调运方案，否则就应进行调整。这里给出两种常用的方法——闭回路法和位势法。

①闭回路法

在给出调运方案的计算表上，从每一空格出发找一条闭回路。它是以某空格为起点，用水平或垂直线向前划，当碰到一数字格时可以转90°后，也可以穿过数字格继续前进，直到回到起始空格为止。闭回路如图2-1的(a)，()，(c)等所示。

图2-1 闭回路形式

闭回路的特点是：除了起始顶点为非基变量外，其他顶点均为基变量。如果对闭回路的方向不加区别，从每一空格出发一定存在和可以找到唯一的闭回路。

如果从回路的起始顶点开始从1开始顺序排列，那么该非基变量的检验数=(闭回路上奇数次顶点单位运价之和)−(闭回路上偶数次顶点单位运价之和)。

例如在已给出初始解的表2-25中，计算的检验数时，先以为起点作闭回路，见图2-32，在这表中闭回路各顶点所在格的右上角数字是单位运价。于是非基变量的检验数=(4+2)-(3+1)=2。

闭回路法计算检验数的经济解释为：若给空格增加一单位运输量，即让的产品调运1单位给，为了保持产销平衡，就要依次作调整：在处减少1吨，处增加1吨，处减少1吨，即构成了以空格为起点，其他为数字格的闭回路。如表2-32中的虚线所示。

表2-32 闭回路

奇数次顶点为增加运输量处，偶数次顶点为减少运输量处，可见这调整的方案使运费增加

(+1)×4+(-1)×1+(+1)×2+(-1)×3=2

这说明这样调整运量将使运费增加2个单位。因此检验数的含义就是在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数的改变量。

按以上所述，可找出所有空格的检验数，见表2-33。

表2-33 检验数

算得检验数还存在负数时，说明原方案不是最优解，要继续改进。

②位势法

用闭回路法求检验数时，需给每一空格找一条闭回路。当产销点很多时，这种计算很繁。下面介绍较为简便的方法——位势法。

设是对应运输问题的个约束条件的对偶变量。是含有一个人工变量的初始基矩阵。人工变量在目标函数中的系数，从线性规划的对偶理论可知。

而每个决策变量的系数向量，所以。于是检验数：

由单纯形法得知所有基变量的检验数等于0。即：

因非基变量的检验数：

这就可以从已知的值中求得。这些计算可在表格中进行。

现在用位势法检验以前面已算出的初始调运方案表2-25。

第一步：制表。根据表2-25，做表2-34；即在表2-25去掉产量那一列和销量那一行，然后再增加一行一列，在列中填入，在行中填入，将基变量所在的外格子里去掉基变量取值，填上对应的检验数0。

表2-34位势法

第二步：确定。先令，然后根据基变量处的检验数，按相继地确定。当时，由可得，由可得；在时，由可得，以此类推可确定所有的的数值，见表2-35。

表2-35位势法

第三步：计算所有空格的检验。按计算所有空格的检验数。

，

，

，计算结果填入相应的空格处，见表2-36。

表2-36位势法

表中还有负检验数，说明未得最优解。

(3)方案调整

当表中空格处出现负检验数时，表示表上的方案不是最优方案，需要进行调整。若有两个和两个以上的负检验数时，一般选其中最小的负检验数，以它对应的空格为调入格，即以它对应的非基变量为进基变量。本例中只有(，)格的检验数为负数，以它为调入格。在原运输方案表上，以此格为出发点，作一闭回路，并标出调整量，(该闭回路上偶数次顶点的运输量)，如表2-37所示。

表2-37 闭回路调整

然后按照下面的方法调整运输量：在闭回路上，奇数次顶点的运输量加上，偶数次顶点的运输量减去，闭回路之外的运输量不变。若闭回路的偶数次顶点中最小运输量只有一个顶点，则调整后该点不用标0，这样调整后运输表中的有数字的格子总数不变；若闭回路的偶数次顶点中最小运输量有个顶点，则调整后，要从个顶点中任选顶点，在其对应的格子里标上数字0，这样调整后运输表中的有数字的格子总数保持不变。

表2-36中的闭回路中，偶数次顶点中有两个顶点(，)和(，)同时为最小运输量4，调整量为4，将(，)格和(，)格的运输量加上4，将(，)和(，)格的运输量减去4，从中任选一格填上0，另一格不填数字。这样得到调整后的运输方案表2-38，新的运输费用为：

表2-38 调整后的运输方案

对新求出的解，再用闭回路法或位势法做最优性检验，现采用位势法求各变量的检验数，见表2-39。

表2-39 检验数

从上表可知，所有的检验数都非负，所以表2-38的调运方案为最优方案。