第三节 运输问题的求解方法——表上作业法

一、产销平衡表与单位运价表

运输问题，作为一类特殊的线性规划问题，我们已在本章第一节中介绍其数学模型，对于这类问题，除用线性规划数学模型进行描写之外，还可用产销平衡表和单位运价表进行描述。

假设某种物资有 m 个生产地点 Ai（i=1，2，⋯，m)，其产量（供应量) 分别为 ai（i=1，2，⋯，m)，有 n 个销地 Bj（j=1，2，⋯，n)，其销量（需求量)分别为■bj（j=1，2，⋯，n)。从 Ai 到 Bj 运输单位物资的运价（单价) 为 Cij。将这些数据汇总可以得到产销平衡表（表 3-10)和单位运价表（表3-11)，将表 3-10 和表 3-11 合并，可得表 3-12。

表 3-10 产销平衡表

表 3-11 单位运价表

表 3-12

二、表上作业法

由于运输问题是一类特殊的线性规划问题，其约束方程组的系数矩阵具有特殊的结构，因而可以找到一种比单纯形法更为简便的求解方法，即表上作业法。

表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质仍是单纯形法，只是其具体计算过程和使用的有关术语有所不同。这一方法的计算步骤可以归纳如下：

（1)找出初始基可行解，即在产销平衡表上给出 m+n-1 个数字格。

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

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

（4)重复（2)—（3)，直到求出最优解为止。

下面，我们通过具体例子来说明表上作业法的计算步骤。

例 3：假设某种物资共有三个产地，其日产量分别是：A1 为 7 吨，A2 为 4 吨，A3 为 9 吨，该种物资的四个销售地，其日销售量分别是：B1 为 3 吨，B2 为 6 吨，B3 为 5 吨，B4 为 6 吨；各产地到销售地的单位物资的运价如表 3-13 所示。试问在满足各销售点需要量的前提下，如何调运该种物资，才能使总运费达到最小？

表 3-13 某物资运输的单位运价表

解：首先列出这一问题的产销平衡表，见表 3-14。

表 3-14 某物资运输的产销平衡表

（一)确定初始基可行解

确定初始基可行解的方法很多，一般而言，人们所希望的方法是既简便， 又尽可能地接近最优解。在用表上作业法求解运输问题时，确定初始基可行解的最常用的方法有最小元素法和伏格尔（Vogel)法。

1. 最小元素法 这一方法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后考虑运价次小的，一直到给出初始基可行解为止。以上例 3 为例，这一方法可由以下几个步骤来完成。

第一步：从表 3-13 中找出最小运价为 1，表示应先将 A2 的产品供应 B1。

因为 a2=4＞b1=3，故 A2 除满足 B1 的全部需要外，还可多余 1 吨物资。在表3-14 中（A2，B1)的交叉格处填上 3，得表 3-15。将表 3-13 中的 B1 列运价划去，得表 3-16。

第二步：在表 3-16 未划去的元素中再找出最小运价 2，确定 A2 多余的 1

吨物资供应 B3，得表 3-17。将表 3-16 中 A2 行运价划去，得表 3-18。

表 3-15

表 3-16

表 3-17

表 3-18

第三步：在表 3-18 未划去的元素中再找出最小运价 3，这表示应将 A1 的产品供应给 B3，因为 b3=5，而 A2 已供应给 B31 吨的产品，故 A1 应供应 B34 吨产品。在表 3-17 中（A1，B3)的位置上填上 4。将表 3-18 中 B3 列的运价划去。⋯⋯这样一直下去，直到单位运价表上的所有元素被划去为止。最后在产销平衡表上得到一个调运方案，即初始基可行解，见表 3-19。

表 3—19

1. 伏格尔法

最小元素法的缺点是，为了节省一处的费用，有时造成在其它处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应， 就考虑次小运费，这就有一个差额，差额越大，说明不能按最小运费调运时， 运费增加越多。因而对差额最大处，就应当采用最小运费调运。伏格尔法的步骤是：

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