基于表上作业法确定货物运输的最优调配方案

李国蓉

(渤海大学数学科学学院 辽宁锦州 121013)

随着经济的深入发展，运输业致力于打造“绿色、节约”的运输环境。而在铁路运输中，不乏出现运输成本高、货物运输物流繁琐的问题[1]，并且在各地方之间存在着货物运输和调配问题。如何有效地减小运输成本并提高货物运输效率，从而更好地实现经济全球化、利益最大化是一个值得研究的课题。

上述的货物调配问题很明显可以看成是一个线性规划模型。一般地，将物资运输问题描述如下：某物资有n个产地Ai，i=1，2，…，n，产地Ai的产量为ai，i=1，2，…，n；有m个销地Bj，j=1，2，…，m，销地Bj的需求量为bj，j=1，2，…，m；从各产地到各销地的单位物资运费为cij，寻求从产地运往销地总运费最小的运输方案，数学模型如下：

设xij为产地i送往销地j的运输量，则满足：

在运输问题的模型上，可采用一种更简便的算法——表上作业法[2]。

1 表上作业法

表上作业法[3]是求解运输问题的一种有效方法，算法如下：

步骤1：列出产销平衡表和运价表(见表1，表2)

表1 产销平衡表

表2 产销运价表

步骤2：确定初始运输方案。

确定初始运输方案有以下几种方法：

方法一：西北角法

优先考虑产销平衡表左上角的产地，销地从左到右进行调配。若产地满足该销地的需求，并且有多余，则考虑下一个销地。若产地不足该销地的需求，则从下一个产地进行调配，以满足该销地的需求，由此可得出初始调配方案。

方法二：最小元素法

从单位运价表中依次找出最小运价所在地优先供给，比较产量和销量，以判断划去行或列。在未划线的运价元素中再挑出最小的运价元素，重复上述过程。由此可得出初始调配方案。

方法三：行伏格尔法

在单位运价表中，比较同一产地到各销地的最小和次小运费之间的差额，找出最大差额的那一行，将尽可能多的物资从该产地运到运费最小的销地，划去没有剩余的产地和满足需求的销地，再重复上述过程，由此得出初始调配方案。

方法四：行列伏格尔法

在单位运价表中，比较同一产地到各销地的最小和次小运费之间的差额和同一销地到各产地的最小和次小运费之间的差额，找出最大差额的那一行或列，将尽可能多的物资从该产地运到运费最小的销地，划去没有剩余的产地和满足需求的销地，再重复上述过程，由此得出初始调配方案。

在以上方法中，行列伏格尔法是最接近最优方案的方法。

步骤3：计算检验数，若最优解已得，则计算停止，否则继续。

对于计算检验数，可采用最简单的运价矩阵法。对运价矩阵做变换即行加列减，将所有对应数字格的运价变为0。此时，运价矩阵中对应空格的矩阵元素值，即所求的检验数。

步骤4：调整方案，转步骤3。

2 案例分析

假设某货物共有4个供应地，供应量分别为7箱、8箱、5箱和10箱；有5个需求地，需求量分别为5箱、6箱、4箱、7箱和8箱。通过产销平衡表确定最优运输方案，各供应地到各需求地的单位运价如表3所示。

表3 各供应地到各需求地的单位运价表

根据单位运价表可以得出数学模型为：

2.1 确定初始运输方案

本题运用最好的行列伏格尔法来确定初始调配方案，结果如表4所示。

表4 初始运输方案

由此可得，出初始运输方案为A1运4箱给B3，A1运3箱给B4，A2运5箱给B1，A2运3箱给B5，A3运5箱给B5，A4运6箱给B2，A4运4箱给B4。

2.2 计算检验数

计算检验数进行变换时，优先考虑数字格多的那一列，即第4列和第5列，要使每一列数字格相等，即第三行每个数加2，第四行每个数加2，再将每一列减去每列的数字格，剩下的数字则为检验数。

由此可以发现，所有检验数为0是非负数，因此最优方案已经得出。最优调拨方案为A1运4箱给B3，A1运3箱给B4，A2运5箱给B1，A2运3箱给B5，A3运5箱给B5，A4运6箱给B2，A4运4箱给B4。

此时的总运费最小为4*7+3*10+5*4+3*7+5*5+6*7+4*8=198元

3 案例改进

当求解产销不平衡问题时，可将此类问题通过方法转换成产销平衡问题，再利用表上作业法进行求解。

注意：当运用表上作业法来确定初始运输方案时，运价全为0的那一列或行，可不考虑[5]。

上述为目标函数极小化问题，当问题改为极大化问题时，也可使用表上作业法进行求解。运用行列伏格尔法时，应按“最大”和“次大”元素之差的大小优先考虑，并且当所有检验数全为负时，即为最优方案。

当遇到无运输路线情况时，即将对应的运价改为M(M＞1)。

下面通过简单的案例进一步理解产销不平衡问题。

问题：假设某种物资共有3个供应地，4个需求地，各供应地到各需求地的单位运价如表5所示，通过产销平衡表确定最优运输方案。

表5 运价表

解：该问题的总供应量为50箱，总销量为40箱，属于产销不平衡问题。由此通过增加一列虚拟销地B5，将问题转换为产销平衡问题，虚拟销地B5需求量为50-40为10箱，任何产地对该虚拟销地的单位运价为0。

3.1 运用行列伏格尔法确定初始运输方案

初始运输方案如表6所示。

表6 初始运输方案

3.2 计算检验数

检验数全为非负，最优方案已求得。最优运输方案为A1运7箱给B1，A1运10箱给B2，A1运3箱给B4，A2运15箱给B3，A3运5箱给B4。

4 结语

本文以货物运输为案例，用表上作业法来处理产销平衡问题，后以增加虚拟产地或销地来处理产销不平衡问题。表上作业法是处理此类问题的有效方法，简单实用，能有效实现效益最大化。