[拼音]：yunshu wenti

[外文]：transportation problem

一类具有特殊结构的线性规划问题。由于运输问题约束方程组的系数矩阵是完全么模的，即所有的子行列式为0或±1，存在着比单纯形法更简单的特殊解法。对于规模不太大的运输问题可用图上作业法或表上作业法求解。这类问题的典型提法是，为了把某种产品从若干个产地调运到若干个销地，已知每个产地的供应量和每个销地的需求量，如何在许多可行的调运方案中，确定一个总运输费或总运输量最少的方案。

具有上述特点的线性规划问题通常被称为运输型问题。现已发现的运输型问题有以下6类：

（1）一般运输问题,又称希契科克运输问题，简称H问题。

（2）网络运输问题，又称图上运输问题,简称T问题。

（3）最大流量问题,简称F问题。

（4）最短路径问题,简称S问题。

（5）任务分配问题，又称指派问题,简称A问题。

（6）生产计划问题，又称日程计划问题,简称CPS问题。其中一般运输问题、任务分配问题和生产计划问题通常都可以用表上作业法求解，而网络运输问题、最大流量问题和最短路径问题一般可用图上作业法或网络技术求解。

设某种物资有m个产地A₁,A₂，…,A_m，供应量分别为a₁，ɑ₂，…，ɑ_m个单位,联合供应n个销地B₁，B₂,…,B_n,需求量分别为b₁，b₂,…,b_n个单位。从产地A_i向销地B_j运输一个单位物资的费用为c_ij，求怎样调运物资才能使运输费用最少。记从产地A_i到销地B_j的运输量为x_ij，列运输表（见表）。

运输问题的数学模型是：

式中min 表示求极小值，s.t.表示“约束条件为”。当ɑ_i，b_j 满足条件时称为产销平衡的运输问题，否则称为产销不平衡的运输问题。产销不平衡的运输问题可以通过增加一个假想产地或假想销地，化成产销平衡的运输问题。如把产地称为源（发点），销地称为汇(收点)，则任务分配问题、生产计划问题等运输型问题的模型也可以归纳成类似上述形式。运输模型约束方程组的系数矩阵为如下形式：

这是(m＋n)×mn的矩阵，每一列的元素中只有2个1，其余均为0。可以证明A的秩≤(m＋n－1)。

运输问题可用表上作业法求解。图中示出用表上作业法求解运输问题的全过程。初始基本可行解的求法有三种：

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

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

（3）元素差额法,又称沃格尔近似法，简称VAM法。它是从运输表中各行和各列的最小元素和次小元素的差额来确定产销关系。改进初始基本可行解的方法有两种：

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

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

参考书目

1. 林同曾主编:《运筹学》,机械工业出版社,北京,1986。