运输问题（Transportation Problem）是运筹学中的经典问题之一，其历史可以追溯到19世纪中期。该问题最早由数学家和经济学家提出，目的是解决如何在需求和供给之间分配资源以最小化运输成本的问题。运输问题的数学模型最初由俄国数学家卡尔·库尔肖夫（Karl Kulshov）在19世纪提出，他研究了如何以最优方式将物资从多个供应地点运送到多个需求地点。尽管当时他提出的模型尚未形成完善的理论体系，但这成为了现代运输问题研究的起点。运输问题源于实际中的物流需求。在工业革命时期，随着铁路、船舶等运输方式的快速发展，如何高效地将货物从多个生产地运输到多个需求地成为了企业面临的关键问题。例如，如何将煤炭从矿山运输到工厂，或者将产品从工厂运送到市场，运输成本直接影响了企业的利润和竞争力。因此，如何以最低的成本完成资源的运输任务成为了学者和企业家们关注的重要问题。
一、平衡型运输问题(标准型)的引入
例1：某部门有3个生产同类型产品的产地，生产的产品由4个销售点出售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位运价（元/吨）如下表所示，求最优调运方案？
| 产地\销地 | $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4 $$ | 产量 |
|---|---|---|---|---|---|
| $$ A_1 $$ | 4 | 12 | 4 | 11 | 16 |
| $$ A_1 $$ | 2 | 10 | 3 | 9 | 10 |
| $$ A_1 $$ | 8 | 5 | 11 | 6 | 22 |
| 销量 | 8 | 14 | 12 | 14 | 48 |
各产地的产量和各销售点的销量总和都是48，属产销平衡问题。我们需要将每个产地的产品按适当的量运送到各销售地，以满足需求，同时使总运输成本最小，寻找满足要求的最优调运方案。
明确问题：产销平衡问题，运输问题的标准型
- 产地 \(A_1\), \(A_2\), \(A_3\) 的产量分别为 7, 4, 9
- 销地 \(B_1\), \(B_2\), \(B_3\), \(B_4\) 的销量分别为 3, 6, 5, 6
- 产销平衡：\(7 + 4 + 9 = 3 + 6 + 5 + 6\)
决策变量：
| 销地 | $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4 $$ | 产量 |
|---|---|---|---|---|---|
| 产地\(A_1\) | \(x_{11}\) | 3 | \(x_{12}\) | 11 | \(x_{13}\) | 3 | \(x_{14}\) | 10 | 7 |
| 产地\(A_2\) | \(x_{21}\) | 1 | \(x_{22}\) | 9 | \(x_{23}\) | 2 | \(x_{24}\)| 8 | 4 |
| 产地\(A_3\) | \(x_{31}\) | 7 | \(x_{32}\) | 4 | \(x_{33}\) | 10 | \(x_{34}\) | 5 | 9 |
| 销量 | 3 | 6 | 5 | 6 |
| 调运网络图 | 决策变量 |
|---|---|
 |
 |
符号定义：
- \(x_{ij}\)：表示从产地\(A_i\)向销售地 \(B_j\) 运送的货物量，其中\(i=1, 2, 3\)表示产地 \(A_1, A_2, A_3\)；\(j = 1, 2, 3, 4\)，表示销售地\(B_1, B_2, B_3, B_4\)
- \(c_{ij}\)：表示从产地\(A_i\) 到销售地\(B_j\) 的单位运输成本
模型建立：
- 目标函数为：
- 约束条件：
- 供给约束：
- $ x_{11} + x_{12} + x_{13} + x_{14} = 16$ (A1)
- $ x_{21} + x_{22} + x_{23} + x_{24} = 10$ (A2)
- $ x_{31} + x_{32} + x_{33} + x_{34} = 22$ (A3)
- 需求约束：
- $ x_{11} + x_{21} + x_{31} = 8$ (B1)
- $ x_{12} + x_{22} + x_{32} = 14$ (B2)
- $ x_{13} + x_{23} + x_{33} = 12$ (B3)
- $ x_{14} + x_{24} + x_{34} = 14$ (B4)
- 供给约束：
- 非负约束：
- 所有运输量\(x_{ij} \geq 0\)
二、平衡型运输问题的数学模型
已知有 m个生产地点 \(A_i，i = 1, \cdots, m\)，每个地点的供应量（产量）分别为 \(a_i\)，现有 n个销地\(B_j，j = 1, \cdots, n\)，每个销地的需求量分别为\(b_j\)。用\(c_{ij}\)表示从\(A_i\)运到\(B_j\)的单位物资的运价，如下单位运价表所示。
| 销地/产地 | $$B_1$$ | $$B_2$$ | ... | $$B_n$$ | 产量 |
|---|---|---|---|---|---|
| $$A_1 $$ | $$ c_{11}$$ | $$ c_{12}$$ | ... | $$ c_{1n}$$ | \(a_1\) |
| $$A_2 $$ | $$ c_{21}$$ | $$ c_{22}$$ | ... | $$ c_{2n}$$ | \(a_2\) |
| $$... $$ | ... | ... | ... | ... | ... |
| $$A_m $$ | $$ c_{m1}$$ | $$ c_{m2}$$ | ... | $$ c_{mn}$$ | \(a_m\) |
| ** 销量 ** | \(b_1\) | \(b_2\) | ... | \(b_n\) |
设从\(A_i\)运到\(B_j\)的运输量为\(x_{ij} ( x_{ij} \geq 0 )\)，则其数学模型为：
\[\begin{aligned} &\text{min} \quad Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \\ \text{s.t.} \quad &\begin{cases} \sum_{i=1}^{m} x_{ij} = b_j, \quad j = 1, 2, \cdots, n, \\ \sum_{j=1}^{n} x_{ij} = a_i, \quad i = 1, 2, \cdots, m, \\ x_{ij} \geq 0, \quad i = 1, 2, \cdots, m; \ j = 1, 2, \cdots, n \end{cases} \end{aligned}\]运输问题约束条件的系数矩阵具有下面特征：
将约束条件的结构加以整理，可知运输模型约束的系数矩阵具有下述比较松散且特殊的形式
即除第\(i\)个和第\(m+j\)个分量为1外，其他分量全等于0。这是\((m+n) \times mn\)的矩阵，每一列的元素中只有2个1，其余均为0。
- 注意决策变量的排序规则，以行为主导，这样系数矩阵的每一列\(A_{ij}\)都对应决策变量的系数列
- 运输问题的有 \(m \times n\) 个变量，\(m+n\) 个约束方程，约束条件系数矩阵的元素等于0或1，约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前 \(m\) 个约束方程出现一次，在后 \(n\) 个方程中也出现一次。
- 可以证明\(A\)的秩 $ \text{rank}(A) = m+n-1 $，所以运输问题的任一基本可行解都有 \(m+n-1\) 个基变量，这 \(m+n-1\) 个基变量的值就对应一个调运方案
- 所有约束条件都是等式约束，这是因为各产地产量之和等于各销地销量之和，即运输问题标准型的结构要求
三、不平衡运输问题的标准化
在运输问题中，供求平衡（即供给总量等于需求总量）是标准型问题。标准型问题的求解较为简单，可以直接使用经典的运输问题算法（如西北角法、最小元素法、MODI法）进行优化。然而，在实际应用中，供给和需求往往不完全平衡，可能会出现供给大于需求或需求大于供给的情况。为了使问题统一为标准型，以便采用成熟的求解方法，可以通过引入虚拟需求点或虚拟供给点将非标准型问题转化为标准型问题。
3.1供大于求的运输问题
当供给总量大于需求总量时，意味着部分供应点的货物将无法全部分配到需求点，存在供给过剩的情况。为了将这种情况转化为标准型，可以引入一个虚拟需求点。这个虚拟需求点的需求量设定为供给总量与需求总量的差额，也就是未被需求点吸收的那部分供给。为了避免虚拟需求点对运输成本的影响，虚拟需求点的运输成本一般设为零。通过这种方法，问题中的供给总量与需求总量达到平衡，运输问题即可转化为标准型。
\[\begin{aligned} &\text{min} \quad y = \sum_{i=1}^{3} \sum_{j=1}^{4} c_{ij} x_{ij} \\ &\text{s.t.} \quad \begin{cases} \sum_{j=1}^{4} x_{ij} \leq a_i, & i = 1, 2, 3, \\ \sum_{i=1}^{3} x_{ij} = b_j, & j = 1, 2, 3, 4, \\ x_{ij} \geq 0, & i = 1, 2, 3; \ j = 1, 2, 3, 4 \end{cases} \end{aligned} \]为了将上述的运输问题转化为平衡型运输问题，可以通过添加松弛变量来标准化。引入松弛变量\(x_{15}、x_{25}、x_{35}\)将不等式约束
\[\sum_{j=1}^{4} x_{ij} \leq a_i, \quad i = 1, 2, 3 \]转化为等式约束
\[\sum_{j=1}^{4} x_{ij} + x_{i5} = a_i, \quad i = 1, 2, 3 \]此时所有产地的产量仍然不等于所有销地的销量，为此根据平衡型运输问题的特点引入一个虚拟销地\(j = 5\)，为每个供给点\(i\)将过剩的供给运送到虚拟销地，这样就可以化为平衡型问题：
- 目标函数：
- 约束条件：
-
注意变化整合如下：
- 我们添加了虚拟销地\(j = 5\)，并且相应地为每个供给点\(i\)引入了松弛变量\(x_{i5}\)
- \(c_{i5}\)表示从供给点\(i\)运送到虚拟销地的运输成本（通常设为 0，因为是虚拟的，不实际发生运输）
- 供给约束条件从不等式变为等式，因为通过松弛变量和虚拟销地的引入，实现了供给总量和需求总量的平衡。
-
转换为等价的单位运价表
| 销地/产地 | $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4$$ | $$B_5$$ | 产量 |
|---|---|---|---|---|---|---|
| $$A_1 $$ | $$ c_{11}$$ | $$ c_{12}$$ | $$ c_{13}$$ | $$ c_{14}$$ | $$ c_{15}=0$$ | \(a_1\) |
| $$A_2 $$ | $$ c_{21}$$ | $$ c_{22}$$ | $$ c_{23}$$ | $$ c_{24}$$ | $$ c_{25}=0$$ | \(a_2\) |
| $$A_3 $$ | $$ c_{31}$$ | $$ c_{32}$$ | $$ c_{33}$$ | $$ c_{34}$$ | $$ c_{35}=0$$ | \(a_3\) |
| 销量 | \(b_1\) | \(b_2\) | \(b_3\) | \(b_4\) | \(b_5=\sum_{i=1}^{3}a_i - \sum_{j=1}^{4} b_j\) |
为更好地体现运输问题的意义，一般不写出标准化后的数学模型，而是直接在单位运价表中添加一列将其转化为产销平衡的单位运价表。
**例2:有3个产地,4 个销地的运输规划问题, 表格中的内容是某产地运往某销地的运费。 **
| 产地\销地 | $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4 $$ | 产量 |
|---|---|---|---|---|---|
| $$ A_1 $$ | 3 | 11 | 3 | 10 | 7 |
| $$ A_1 $$ | 1 | 9 | 2 | 8 | 8 |
| $$ A_1 $$ | 7 | 4 | 10 | 5 | 9 |
| 销量 | 3 | 6 | 5 | 6 | 20\24 |
标准化
| 产地\销地 | $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4 $$ | $$B_5 $$ | 产量 |
|---|---|---|---|---|---|---|
| $$ A_1 $$ | 3 | 11 | 3 | 10 | 0 | 7 |
| $$ A_1 $$ | 1 | 9 | 2 | 8 | 0 | 8 |
| $$ A_1 $$ | 7 | 4 | 10 | 5 | 0 | 9 |
| 销量 | 3 | 6 | 5 | 6 | 24-4=4 | 24\24 |
3.2 供不应求的运输问题
当需求总量大于供给总量时，意味着部分需求点将无法获得足够的供给，存在供给不足的情况。为了使问题转化为标准型，可以引入一个虚拟供给点，其供给量等于需求总量与供给总量的差额。这些虚拟供给点的运输成本也设为零。同样地，通过引入虚拟供给点，模型中的供给总量与需求总量保持一致，问题转化为标准型。
\[\begin{aligned} &\text{min} \quad y = \sum_{i=1}^{3} \sum_{j=1}^{4} c_{ij} x_{ij} \\ &\text{s.t.} \quad \begin{cases} \sum_{j=1}^{4} x_{ij} = a_i, & i = 1, 2, 3, \\ \sum_{i=1}^{3} x_{ij} \leq b_j, & j = 1, 2, 3, 4, \\ x_{ij} \geq 0, & i = 1, 2, 3; \ j = 1, 2, 3, 4 \end{cases} \end{aligned} \]为了将上述的运输问题转化为平衡型运输问题，可以通过添加松弛变量来标准化。引入松弛变量\(x_{41}、x_{42}、x_{43}和x_{44}\)将不等式约束
\[\sum_{i=1}^{3}x_{ij} \leq b_j, j = 1, 2, 3, 4 \]转化为等式约束
\[\sum_{i=1}^{3}x_{ij}+x_{4j} = b_j, j = 1, 2, 3, 4 \]此时所有产地的产量仍然不等于所有销地的销量，为此根据平衡型运输问题的特点引入一个虚拟产地\(i =4\)，为每个销售点\(j\)生产供应不足的需求，这样就可转化为平衡型运输问题：
- 目标函数：
- 约束条件：
其中，虚拟产地\(A_4\)的运输成本\(c_{4j}\)为零，表示引入的虚拟产地只是为了平衡供需，实际不进行物理运输，\(a_4=\sum_{j=1}^{4} b_{j} - \sum_{i=1}^{3}a_{i}\)。注意整合变化如下：
- 我们添加了虚拟产地\(i = 4\)，并且相应地为每个销售点\(j\)引入了松弛变量\(x_{4j}\)
- \(c_{4j}\)表示从虚拟产地4运送到销地\(j\)的运输成本（通常设为 0，因为是虚拟的，不实际发生运输）
- 销地约束条件从不等式变为等式，因为通过松弛变量和虚拟产地的引入，实现了供给总量和需求总量的平衡。
- 转换为等价的单位运价表
| 销地/产地 | $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4$$ | 产量 |
|---|---|---|---|---|---|
| $$A_1 $$ | $$ c_{11}$$ | $$ c_{12}$$ | $$ c_{13}$$ | $$ c_{14}$$ | \(a_1\) |
| $$A_2 $$ | $$ c_{21}$$ | $$ c_{22}$$ | $$ c_{23}$$ | $$ c_{24}$$ | \(a_2\) |
| $$A_3 $$ | $$ c_{31}$$ | $$ c_{32}$$ | $$ c_{33}$$ | $$ c_{34}$$ | \(a_3\) |
| $$A_4 $$ | $$ c_{41}=0$$ | $$ c_{42}=0$$ | $$ c_{43}=0$$ | $$ c_{44}=0$$ | \(a_4=\sum_{j=1}^{4}b_j - \sum_{i=1}^{3} a_3\) |
| 销量 | \(b_1\) | \(b_2\) | \(b_3\) | \(b_4\) |
为更好地体现运输问题的意义，一般不写出标准化后的数学模型，而是直接在单位运价表中添加一行将其转化为产销平衡的单位运价表。
例3：某运输问题的单位运价表如下，试确定其是哪一类问题，如果不是平衡型问题，请将其转化为标准型。
| 产地\销地 | $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4 $$ | 产量 |
|---|---|---|---|---|---|
| $$ A_1 $$ | 5 | 9 | 0 | 4 | 28 |
| $$ A_2 $$ | 6 | 10 | 3 | 0 | 32 |
| $$ A_3 $$ | 4 | 2 | 5 | 7 | 60 |
| 销量 | 48 | 29 | 40 | 33 | 150\120 |
标准化
| 产地\销地 | $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4 $$ | 产量 |
|---|---|---|---|---|---|
| $$ A_1 $$ | 5 | 9 | 0 | 4 | 28 |
| $$ A_2 $$ | 6 | 10 | 3 | 0 | 32 |
| $$ A_3 $$ | 4 | 2 | 5 | 7 | 60 |
| $$ A_4 $$ | 0 | 0 | 0 | 0 | 150-120=30 |
| 销量 | 48 | 29 | 40 | 33 | 150\150 |
通过引入虚拟需求点或虚拟供给点，非标准型运输问题可以转化为供求平衡的标准型问题。这种转化方法不仅简化了问题的求解过程，还使得求解算法的适用性更加广泛。标准型问题可以利用经典的线性规划和运输问题算法进行优化，从而在复杂的供需关系中找到最优的运输策略，降低运输成本并提高资源分配效率。
3.3 其他形式的运输问题
在不标准的运输问题中，除了常见的产销不平衡（产大于销或销大于产）外，还涉及到一些更加复杂的情境和约束条件。例如，禁运和封锁问题，通常出现在某些区域或时间段内某些产品无法运输，或者运输路径受到地理、政治等因素的封锁和限制。弹性需求问题则指的是需求量并非固定，而是随着价格、时间、季节等因素的变化而波动，这种情况下的运输决策需要动态调整。运输问题往往会有多种实际的约束条件，以下是一些常见的约束类型：
体积限制：运输工具的空间有限，每批货物的体积不能超过运输工具的最大容积。这对大宗商品的运输尤为重要，例如石油、煤炭等商品的体积可能比重量更具决定性。
重量限制：每辆车的承载重量有上限，尤其是在运输大型或重型物品时，重量限制会成为关键因素，防止运输工具超载以确保运输安全。
时间限制：某些货物有时效性，例如食品、药品等具有保质期，必须在规定的时间内完成运输。另外，紧急运输任务或物流高峰期间的时间要求也很重要。
车型限制：不同类型的货物可能需要特定的运输工具，例如冷藏车、危险品运输车、集装箱车等。车型的选择不仅影响运输效率，还可能受法规限制，某些车型只能在特定路段行驶。
产品归类限制：对于某些特殊商品（如危险品、化学品、易燃易爆物品等），运输时需按照产品归类进行特殊处理，甚至需要专门的运输工具和路线。
卸货点限制：由于仓储空间或装卸能力有限，有些卸货点无法同时接收大量货物，或者对装卸时间、频率有所要求。这会影响运输批次的安排和路径的选择。
产品比例搭配：某些情况下，运输批次中的货物需要按照一定比例进行搭配。例如，不同产品组合的货运策略，可能为了优化运费、仓储费用或保证不同类型产品之间的协调性。
路径规划：要根据不同的运输工具、路况和交通流量选择最优的运输路线。这不仅仅是寻找最短路径，而是综合考虑时间、成本、路况、安全等因素的多目标优化问题。
流量控制：当多条路线同时进行运输时，需要避免某些道路或节点的拥堵，合理分配不同车辆或货物的流量，确保整个运输网络的畅通和高效。
通过加入这些复杂的条件和约束，运输问题的求解更加接近实际情况，通常需要借助运筹学中的线性规划、动态规划、智能算法等方法进行建模和求解，以实现经济效益和资源利用最大化。
四、练习
在现实供应链中，终端需求常常是变化的，所以其产量和销量并不是一个确定的数值，而可能在某个范围内取值。
例4：设有 3 个化肥厂（A）供应 4 个地区（B）的农用化肥，假定等量的化肥在这些地区使用效果相同，已知各化肥厂年产量、各地区的需要量及从各化肥厂到各地区的单位运价表见下表所示，试给出总运费最少的调运方案。
| 产地\销地 | $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4 $$ | 产量 |
|---|---|---|---|---|---|
| $$ A_1 $$ | 16 | 13 | 22 | 17 | 50 |
| $$ A_2 $$ | 14 | 13 | 19 | 15 | 60 |
| $$ A_3 $$ | 4 | 2 | 5 | 7 | 60 |
| 最低需求量 | 30 | 70 | 0 | 10 | |
| 最高需求量 | 50 | 70 | 30 | 不限 |
说明：
- 表中的数字表示从产地到销地的运输量或需求量。
- "供应量" 列表示每个产地的总供应量。
- "最低需求量" 和 "最高需求量" 列表示销地的需求量限制。
- "—" 表示该值不适用或无数据。
地区 \(\mathrm{B}_4\) 的最高需求是当其他地区最低需求被满足时，供应该销地的数量。
地区 \(B_4\) 的最高需求 \(=50+60+50-30-70=60\)
总产量 \(=50+60+50=160\)
最低需求量 \(=30+70+10=110\)
最高需求量 \(=50+70+30+60=210\)
根据上面的计算和 \(\mathrm{A}_3\) 到 \(\mathrm{B}_4\) 不能调运化肥，将其运价改写为 \(M\) ，如下表所示。
| 产地\销地 | $$B_1$$ | $$B_2$$ | $$B_3$$ | $$B_4 $$ | 产量 |
|---|---|---|---|---|---|
| $$ A_1 $$ | 16 | 13 | 22 | 17 | 50 |
| $$ A_2 $$ | 14 | 13 | 19 | 15 | 60 |
| $$ A_3 $$ | 19 | 20 | 23 | M | 50 |
| $$ A_4 $$ | 0 | 0 | 0 | 0 | 50 |
| 最低需求量 | 30 | 70 | 0 | 10 | |
| 最高需求量 | 50 | 70 | 30 | 60 |
这就是具有弹性需求的运输问题, 要将问题转化为产销平衡问题进行求解, 需进行以下几个方面的调整。
(1)将地区划分为刚性需求地区和弹性需求地区。弹性需求地区要求满足该地区的最低需求, 最高需求和最低需求之差应尽可能满足, 运价不变。为此将弹性需求地区的需求按最低需求拆分为刚性需求部分 (最低需求) 和弹性需求部分( 最高需求和最低需求之差), 为简化描述，将它们仍称为刚性需求地区和弹性需求地区。
(2)增加一个虚拟化肥厂 \(A_4\), 使其产销平衡。
(3)刚性需求地区的需求必须满足，因此虚拟化肥厂不能向刚性需求地区运输化肥，即将虚拟化肥厂到刚性需求地区的运费设为无限大 \(M\) 。
因此, 新的产销量及单位运价表如下所示。
| 产地\销地 | $$B_{1}^{'}$$ | $$B_{1}^{''}$$ | $$B_2$$ | $$B_3$$ | $$B_{4}^{'}$$ | $$B_{4}^{''}$$ | 产量 |
|---|---|---|---|---|---|---|---|
| $$ A_1 $$ | 16 | 16 | 13 | 22 | 17 | 17 | 50 |
| $$ A_2 $$ | 14 | 14 | 13 | 19 | 15 | 15 | 60 |
| $$ A_3 $$ | 19 | 19 | 20 | 23 | M | M | 50 |
| $$ A_4 $$ | M | 0 | M | 0 | M | 0 | 50 |
| 需求量 | 30 | 20 | 70 | 30 | 10 | 50 | 210 |
该问题就转化为 4 个产地和 6 个销地的运输问题, 应用表上作业法可得最优调运方案。
总结
运输问题作为运筹学中的经典问题，经过百余年的发展，已经从最初的经验法则转变为复杂的数学模型和算法，广泛应用于物流、交通、公共设施管理等诸多领域。其理论和方法不仅帮助企业降低了运输成本，提高了运营效率，也在资源调配和分配中发挥了重要作用。随着现代技术的发展，运输问题仍然是一个具有广泛研究价值的课题。未来，随着大数据、人工智能等技术的进一步发展，运输问题的解决方案也有望变得更加智能化和高效。
