运输问题，一类具有特殊结构的线性规划问题。由于运输问题约束方程组的系数矩阵是完全么模的，即所有的子行列式为0或±1，存在着比单纯形法更简单的特殊解法。

中文名：运输问题

外文名：Transportation problem

别名：运输型问题

学科归属：交通科学、运筹学

现已发现的运输型问题有以下6类：

一般运输问题，又称希契科克运输问题，简称H问题。2.

网络运输问题，又称图上运输问题，简称T问题。3.

最大流量问题,简称F问题。4.

最短路径问题，简称S问题。5.

任务分配问题，又称指派问题,简称A问题。6.

生产计划问题，又称日程计划问题，简称CPS问题。

如把产地称为源（发点），销地称为汇(收点)，则任务分配问题、生产计划问题等运输型问题的模型也可以归纳成类似上述形式。本词条的运输问题指的是一般类型的运输问题。

问题提出

图1.问题举例

运输问题的典型情况是研究单一品种物质的运输调度问题：设某种物品有m个产地A1，A2，···，Am，各产地的产量分别是a1，a2，···，am；有n个销地B1，B2，···，Bn，各个销地的销量分别为b1，b2，···，bn。假定从产地Ai(i=1,2,···,m)向销地Bj(j=1,2,···,n)运输单位物品的运价为cij，问怎么调运这些物品才能使总运费最小？

数学模型

产销平衡运输问题的数学模型可表示如下：

如果运输问题的总产量等于总销量，即有

以上模型是一种线性规划模型，单纯形法师求解线性规划问题十分有效的一般方法，因而单纯形法也可以求解运输问题。但是采用线性规划的单纯形法求解运输问题时，先得在每个约束条件中引入一个人工变量，即使求解3个产地，4个销地(m=3,n=4)这样的简单运输问题，在不考虑去掉多余约束条件的情况下，变量数目也会达到19个之多，因而需要寻求更简便的解法。

系数矩阵

将约束条件的结构加以整理，可知运输模型约束方程组的系数矩阵具有下述比较松散且特殊的形式：

图2.运输模型约束方程组的系数矩阵

其系数列向量的结构式：Aij=(0,···,0,1（第i个）,0,···,0,1（第m+j个）,0,···,0)T，即除第i个和第(m+j)个分量为1外，其他分量全等于0。这是(m+n)×mn的矩阵，每一列的元素中只有2个1，其余均为0。可以证明A的秩=(m+n－1)，所以运输问题的任一基本可行解都有(m+n-1)个基变量，这(m+n-1)个基变量的值就对应一个调运方案。

由此可知，运输问题的约束条件具有下述特点：

1.

运输问题的有m×n个变量，(m+n)个约束方程，(m+n-1)个基变量。2.

约束条件系数矩阵的元素等于0或1。3.

约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程出现一次，在后n个方程中也出现一次。

对产销平衡运输问题，除上述两个特点外，还有以下特点：

1.

所有结构约束条件都是等式约束。2.

各产地产量之和等于各销地销量之和。

有限最优解

对产销平衡的运输问题，可以找到一个可行解：其变量

%20是运输问题的一个可行解，其中，

%20，目标函数有下界0，目标函数值不会趋于

%20。由此可知，运输问题必存在有限最优解。

运输表

这是有多个产地供应多个销地的单一品种物资运输问题。为直观清楚起见，可列出该问题的运输表，如下表所示。

图3.运输表

表中的变量xij(i=1,2,···,m;j=1,2,···,m)为产地Ai运往销地Bj的物品数量，cij为Ai到Bj的单位运价。有时，仅简单地将单位运价单独列入另一个表中，称其为运价表，如下表所示。

图4.运价表

求解思路

根据运输问题的数学模型求出的运输问题的解X=(xij)，代表着一个运输方案，其中每一个变量xij的值表示由Ai调运数量为xij的物品给Bj。前已指出运输问题是一种线性规划问题，可设想用迭代法进行求解，即先找出它的某一个基可行解，在进行解的最优性检验，若它不是最优解，就进行迭代调整，以得到一个新的更好的解，继续检验和调整改进，直到得到最优解为止。

为了能按照上述思路求解运输问题，要求每步得到的解X=(xij)都必须是其基可行解，这意味着：

解X必须满足模型中的所有约束条件；2.

基变量对应的约束方程组的系数列向量线性无关；3.

解中非基变量的个数不能大于(m+n-1)个，原因是运输问题虽有(m+n)个结构约束条件，但是由于总产量等于总销量，故只有(m+n-1)个结构约束条件是线性独立的；4.

为使迭代顺利进行，基变量的个数在迭代过程中应该始终保持为(m+n-1)个。因为可以证明(m+n-1)基变量所对应的约束方程的系数列向量线性无关。

表上作业法

当采用一般单纯形法求解运输问题时，应去掉一个多余的约束等式，任何一个约束等式均可。但运输问题是的特殊性，人们将单纯性法简化用表格来处理，采用表上作业法求解时，因为在运输表上进行，不必写出上述的数学模型。

运输问题解的每一个分量，都唯一对应其运输表中的一个格。得出运输问题的一个基可行解后，就将即便基变量的值xij填入运输表相应的格子(Ai,Bj)内，并将这种格子称为填有数字的格，含填数字0的格，这时的解为退化解，退化需要补0；对非基变量对应的格不填入数字，称为空格。

表上作业法是求解运输问题的一种简便而有效的方法，其求解工作在运输表上进行，它是一种迭代法，可以满足上述的要求，迭代步骤为：先按照某种规则找出一个初始调运方案；再对现行解做最优性判别；若这个解不是最优解，就在运输表上对它进行调整改进，得出一个新的解；再判别，再改进；直到得到运输问题的最优解为止。

表上作业法的第一步就是找出一个初始解，初始基本可行解的求法介绍三种。

左上角法

西北角法，它的基本思想是给运输表中左上角的变量分配运输量以确定产销关系。

最小元素法

最小元素法，或最小成本法。它的基本思想是就近供应，即从运输表中运价最小的格子开始分配运输量以确定产销关系。

元素差额法

又称沃格尔近似法，简称VAM法。它是从运输表中各行和各列的最小元素和次小元素的差额来确定产销关系。

得到了运输问题的初始基可行解之后，即对应这个解进行最优性判别，看它是不是最优解。改进初始基本可行解有两种最常用的方法：闭回路法和对偶变量法（位势法）。

闭回路法

这种方法需要对每一个空格寻找一条闭回路，并根据闭回路求出每个空格的检验数。当运输问题中m和n较大时，计算检验数的工作量很大。

位势法

或乘数法。先对初始调运方案求出位势，然后求各空格的检验数。当所有的检验数均为非负时，就得到最优方案。如果出现负的检验数，则从检验数为负的空格出发，作闭回路，重新计算检验数，作进一步调整。用位势法求检验数就是对偶问题的表上作业法。