用表上作业法求解简单物流运输问题

物流管理的本质要求就是求实效，即以最少的消耗，实现最优的服务，达到最佳的经济效益。搞好物流管理，可以通过合理的运输方案，使中间装卸搬运、储存费用降低、损失减少，在其他条件不变的情况下，降低物流成本就意味着扩大了企业的利润空间，提高了利润水平，所以一个合理的运输方案有着重要的意义。

运输问题是线性规划的一种特殊形式，运输问题主要是解决这样的问题：在大宗物资调运时，有若干个产地，根据已知的运输交通网，如何制定一个运输方案，将这些物资运到各个销售地，使得总运费最小。运输问题模型提出后，人们对其求解的方法进行了大量的研究，并有了重大成果，其中Danzig的表上作业法是最简单和最常用的，表上作业法本质就是单纯形法。本文通过对物流运输问题模型的分析，讲解了表上作业法的求解过程，并进行实际操作。

▲▲1 运输问题的提出

运输问题发展于线性规划问题，属于线性函数在约束条件下的最优化问题，在1940年Hitchcock提出运输问题。运输问题属于线性规划问题的特殊情况，既有线性规划问题的共性，也有自身的特点和算法。运输问题提出后，1958年Kantorovich对运输问题做了早期的研究。

1.1运输问题的数学模型

有m个供应点向n个需求点供应某种物资，这m个供应点A1、A2、、…… Am的供应量分别为a1、a2、…… am；n个需求点B1、B2、…… Bn的需求量分别为b1、b2、、…… bn；已知从任一供应点Ai向任一需求点Bj运输一个单位物资的费用为cij。问采取什么样的物资调运方案才能使总运费最省？

表1-1 供求量及单位运价表

销地

产地 B1 B2 … Bn 供应量

A1 c11 c12 … c1n a1

A2 c21 c22 … c2n a2

… … … … … …

Am cm1 cm2 … cmn am

需求量 b1 b2 … bn

建立数学模型为：

（1）当 时，即运输问题的总产量等于其总销量，这样的运输问题称为产销平衡的运输问题。

（2）当时，即运输问题的总产量不等于总销量，这样的运输问题称为产销不平佛山到包头物流衡的运输问题。

1.2产销平衡的运输问题的数学模型

当时，即为产销平衡的运输问题，此时数学模型可化为：

为了方便计算，只考虑产销平衡的情况；产销不平衡时，增加虚拟的产销地及产量使其变为产销平衡的问题进行求解。

1.3运输问题数学模型的特点

（1）数学模型中有mn个决策变量，有（m+n）个约束条件；

（2）数学模型一定有最优解，且有有限个最优解；

（3）数学模型的系数矩阵为：

（4）系数矩阵中元素只有1和0，且前m行有且仅有n个1，其余为0，后n行有且仅有m个1，其余为0；每列有且仅有2个1，其余为0。

▲▲2 表上作业法

表上作业法是指用列表的方法求解运输问题的计算方法，是线性规划一种求解方法，其本质同单纯形法一样。首先要确定一个初始调运方案，不要求是最优的，主要希望求解方法简便可行，最常见的是西北角法、最小元素法和Vogel法。然后采用检验数来验证这个方案，常用的方法是闭回路法和位势法，若是最优方案则计算结束，否则就要用闭合回路法进行调整，直至得到满意的结果。这种列表求解方法就是表上作业法。

2.1表上作业法的求解步骤

（1）建立产销平衡表，确定初始调运方案，常用的方法有最小元素法、西北角法、Vogel法等；

（2）现行方案的最优性检验，常用方法有闭回路法，位势法，计算出检验数，从而判别方案是否最优；

（3）现行方案的调整，即从当前方案出发去寻找另一个更好的调运方案，常用的方法是闭回路法；

（4）重复2）、3）步骤，直到得出最优调运方案为止。

2.2确定初始调运方案

2.2.1西北角法

西北角法是制定运输问题的初始调运方案（即初始基可行解）的基本方法之一。是从产销平衡表的西北角位置开始分配调运量，依次安排m个产地和n个销地之间的运输业务，从而得到一个初始调运方案的方法。西北角法遵循“优先安排产销平衡表上编号最小的产地和销地之间的运输业务”的规则。其操作步骤如下：

（1）建立产销平衡表，取表的西北角方格分配调运量，并使其尽可能的大；

（2）将西北角方格所对应的产销量均减去分配量，得到新的产销量；

（3）当新产销量为0时，划去其所对应的行或者列；

（4）重新选取表的西北角方格分配调运量，直至产销量分配平衡为止。

2.2.2最小元素法

最小元素法是找出产销平衡表中最小的元素（所谓元素就是单位运价）所对应的方格，给此方格分配调运量，并使其尽可能的大，若某行（列）的产量（销量）已满足，则把运价表中该运价所在行（列）划去；找出未划去的产销平衡表中的最小元素所对应的方格，给其分配调运量，按此办法进行下去，直至得到一个分配平衡为止。其操作步骤如下：

（1）建立产销平衡表，取表中最小单位运价的方格分配调运量，并使其尽可能的大；

（2）将最小单位运价方格所对应的产销量均减去分配量，得到新的产销量；

（3）当新产销量为0时，划去其所对应的行或者列；

（4）重新选取表中最小单位运价的方格分配调运量，直至产销量分配平衡为止。

2.2.3Vogel法

最小元素法的缺点是，为了节约一处的费用，有时造成在其他处要多花几倍的运费。伏格尔法又称差额法，该方法考虑到，某产地的产品如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。其操作步骤如下： （1）建立产销平衡表，算出各行各列中最小元素和次小元素的差额，并标出最大的差额（若几个差额同为最大，则可任取其一）；

（2）取最大差额所对应行或列中的最小元素方格开始分配调运量，并使其尽可能的大；

（3）将最小元素方格所对应的产销量均减去分配量，得到新的产销量；

（4）珠海到白山物流当新产销量为0时，划去其所对应的行或者列；

（5）重新计算行差额和列差额，取最大差额所对应行或列中的最小元素方格开始分配调运量，直至产销量分配平衡为止。

2.3现行方案的最优性检验

2.3.1闭回路法

所谓闭回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。

闭回路的特点：

1）每行每列最多只有两个顶点；

2）每一段折线都是水平或者垂直的；

3）回路的转角点必须是一个基变量；

4）每个非基变量有且仅有一条闭回路，与其方向无关。

所谓闭回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为1，由于产销平衡的要求，我们必须对这个空格的闭回路的顶点的调运量加上或减少1。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。

2.3.2位势法

所谓位势法，我们对运输表上的每一行赋予一个数值ui，对每一列赋予一个数值vj，它们的数值是由基变量xij的检验数 所汕头到徐州物流决定的，则非基变量xij的检验数就可以用公式求出。

2.4现行方案的调整

在进行最优解检验时，出现负检验数，表明没有得出最优解，方案需要进行改进，常用的改进方法是闭回路调整法。闭回路调整法的思路是：以负检验数的空格为调入格，当负检验数为两个或两个以上时，一般选最小的负检验数，以它相对应的非基变量为调入变量；以调入格为起点做一条闭回路，在闭回路的偶数顶点方格中选取调运量最小的数格为调出格，以它相对应的基变量为调出变量；以 闭回路中最小的调运量值为调整数，然后进行调整得到新的调运方案。