湖南科技职业学院 阳志琼

运输问题的解题方法有很多。基本常用方法有线性规划——单纯形法、表上作业法(最小元素法、西北角法、沃格尔法)、图上作业法、逆推法、标号法等。这些方法各有各的优势，各有各的技巧，不同情境下可以选择不同方法，从而保证最快得到最优解。即使同一个问题，往往也能用几种不同的方法来求解，达到异曲同工的效果。

1 问题的提出

为了描述物流运筹方法对于运输问题的巧妙用处，现举例如下。如图1所示，B、D、F、H各有物资80、150、170、100吨，A、C、E、G各需物资110、130、100、160吨，确定车辆调度的最优运输方案。

图1 物流供需点分布及运距图

2 表上作业法求解

从图1可知，这是一个产销平衡的运输问题，笔者首先想到表上作业，运用最小元素法求初始解。计算结果如表1所示，计算过程省略(表1中X所在格(非基变量)表示不安排运量，其余格(基变量)安排运量并保证基变量有m+n-1个，其中m为产地的个数，n为销地的个数)。

表1 最小元素法求初始解

由此可见，用最小元素法确定初始方案很简单。但是，初始方案是否最优方案还需进一步检验。这就需要对每一个非基变量在表中找到有且仅有的一条闭回路，然后计算检验数。检验数有正有负，往往不能一步到位，调运方案就需多次调整(负检验数表示原方案不是最优方案，方案调整后运费还会减少)。方案调整时首先考虑负检验数最大的非基变量闭回路上的运量调整(令非基变量所在格为奇点，顺时针或逆时针方向行进，遇到基变量格旋转90度并依次确定奇偶点，将偶点上最小运量转给对应奇点并保证闭回路上总体运量协调)，得到新的调运方案，再重新计算检验数，直到所有检验数为非负，从而确定最优调运方案。……