运输问题求解全解析：从线性规划模型到表上作业法实践

1. 项目概述：从一道经典例题，看透运输问题的本质

最近在后台和社群里，看到不少朋友在啃运筹学里的运输问题。大家普遍的感觉是，单纯看单纯形法、表上作业法的步骤，好像懂了，但一拿到具体的题目，尤其是数据稍微复杂一点，或者问法灵活一点的，就不知道从何下手，怎么把那些表格、数字和理论对应起来。这太正常了，运输问题作为线性规划的一个特例，它的魅力就在于用一套非常直观的“表格”来隐藏了背后复杂的数学结构。今天，我就想借一道被无数教材引用的经典例题，带大家走一遍完整的解题流程。我们的目标不是仅仅算出答案，而是通过这道题，彻底搞明白：面对一个运输问题，我们应该如何思考，如何把实际问题转化为数学模型，又如何选择最高效的求解路径，以及最终如何解读结果背后的管理意义。

这道题是这样的：某公司有三个工厂 A1, A2, A3，生产同一种产品，其月产量分别是 7吨、4吨、9吨。这些产品需要运往四个销售地 B1, B2, B3, B4，其月销量分别是 3吨、6吨、5吨、6吨。已知从每个工厂到每个销售地的单位运价（元/吨）如下表所示。问：应如何调运，才能使总运费最少？

运价	B1	B2	B3	B4	产量
A1	3	11	3	10	7
A2	1	9	2	8	4
A3	7	4	10	5	9
销量	3	6	5	6

这就是一个最标准的、产销平衡的运输问题。所谓“经典”，就在于它要素齐全：多个供应地、多个需求地、明确的供应量与需求量、以及差异化的运输成本。它几乎涵盖了运输问题模型的所有核心概念。接下来，我们不求快，但求透。我会把自己十多年处理这类问题，从教学到实际项目建模的经验，揉碎了分享给你。你会发现，只要思路清晰，运输问题的求解就像完成一个结构化的拼图，每一步都有其必然的逻辑。

2. 问题拆解与模型建立：把文字翻译成数学语言

很多初学者卡在第一步，看到题目描述和一堆数字就发懵。我的经验是，永远不要直接扎进数字里，先花两分钟做好“翻译”工作。这一步做扎实了，后面求解会顺利得多。

2.1 识别问题要素与建立运价表

首先，我们要把题目中的文字信息，整理成我们熟悉的“运输表”形式。这本身就是建模的第一步。

1. 供应地（发点）与供应量（产量）：A1(7), A2(4), A3(9)。记住，在表中，我们通常把供应量放在每一行的最右边。
2. 需求地（收点）与需求量（销量）：B1(3), B2(6), B3(5), B4(6)。需求量放在每一列的最下边。
3. 决策变量：这是我们要求解的核心。设 ( x_{ij} ) 表示从工厂 i 运往销售地 j 的产品数量（吨）。例如，( x_{12} ) 就是从A1运到B2的数量。我们最终要找的就是所有 ( x_{ij} ) 的值。
4. 目标函数系数（单位运价）：题目给出的3x4表格，中间那12个数字（3, 11, 3, 10; 1, 9, 2, 8; 7, 4, 10, 5）就是运价 ( c_{ij} )。它们直接决定了我们的目标——总运费。

把以上信息整合，就得到了我们在概述中列出的那张完整的运输表。这张表是后续所有操作的基础载体。这里有个关键检查点：计算总产量和总销量。7+4+9=20，3+6+5+6=20。两者相等，这是一个产销平衡问题。这是最理想的情况，意味着我们的模型约束都是等式，所有产品都能运出去，所有需求都能被满足。如果不等，就需要先通过引入“虚设产地”或“虚设销地”来化为平衡问题，这是后话，但在这个经典例题中我们很幸运。

2.2 构建线性规划模型

有了运输表，我们就可以用严谨的数学语言来描述这个问题了。这一步虽然看似理论化，但它能帮你从根本上理解表上作业法每一步在做什么。

• 决策变量：( x_{ij} \geq 0 ), (i=1,2,3; j=1,2,3,4)。共12个变量。
• 目标函数（最小化总运费）： [ Min , Z = 3x_{11} + 11x_{12} + 3x_{13} + 10x_{14} + 1x_{21} + 9x_{22} + 2x_{23} + 8x_{24} + 7x_{31} + 4x_{32} + 10x_{33} + 5x_{34} ] 这个式子就是运价表中每个格子运价与其运输量的乘积之和。
• 约束条件：
  1. 供应约束（每个工厂运出的不能超过其产量）：对于每个工厂i，运往所有销地的总和等于其产量。 [ \begin{aligned} & x_{11} + x_{12} + x_{13} + x_{14} = 7 \quad (A1) \ & x_{21} + x_{22} + x_{23} + x_{24} = 4 \quad (A2) \ & x_{31} + x_{32} + x_{33} + x_{34} = 9 \quad (A3) \end{aligned} ]
  2. 需求约束（每个销地收到的等于其需求量）：对于每个销地j，所有工厂运来的总和等于其销量。 [ \begin{aligned} & x_{11} + x_{21} + x_{31} = 3 \quad (B1) \ & x_{12} + x_{22} + x_{32} = 6 \quad (B2) \ & x_{13} + x_{23} + x_{33} = 5 \quad (B3) \ & x_{14} + x_{24} + x_{34} = 6 \quad (B4) \end{aligned} ]
  3. 非负约束：( x_{ij} \geq 0 )。

看到这里，你应该能理解为什么说运输问题是线性规划的特例了。它的约束矩阵非常特殊，全是0和1，并且具有“每行每列之和为定值”的结构。这个结构正是“表上作业法”能够成立的基础。表上作业法本质上就是在运输表这个直观的界面上，执行单纯形法的迭代优化，只不过我们操作的是“格子”和“数字”，而不是抽象的矩阵和向量。

注意：在实际考试或快速分析时，我们通常跳过写出完整数学模型这一步，直接画表操作。但我强烈建议初学者，尤其是感到困惑的时候，一定要亲手写一遍这个模型。它能帮你建立“表格操作”与“数学原理”之间的桥梁，理解更深。

3. 求解流程详解：表上作业法三步走

模型建立好了，现在进入核心的求解阶段——表上作业法。这是运输问题的专属解法，比通用的单纯形法更高效、更直观。整个过程分为三步：寻找初始基可行解 -> 最优性检验 -> 方案调整（闭回路调整）。我们一步一步来。

3.1 第一步：寻找初始基可行解

初始解的好坏直接影响迭代次数。我们有多种方法，如最小元素法、伏格尔法（Vogel‘s Approximation Method, VAM）、西北角法等。对于这道题，为了展示效果并兼顾效率，我们先用最小元素法，再对比一下伏格尔法。

最小元素法（就近供应思想）： 核心思路：优先满足单位运价最小的那个运输路线。

1. 从运价表中找到最小的运价。全局最小是 ( c_{21} = 1 )（A2到B1）。
2. 尽可能多地满足它。A2产量4，B1销量3，取最小值 min(4,3)=3。所以令 ( x_{21} = 3 )。
3. 由于B1的需求3已被完全满足，划去B1这一列。A2的产量剩余 4-3=1。
4. 在剩余的格子中找最小运价。此时最小是 ( c_{23} = 2 )（A2到B3）。
5. A2剩余产量1，B3需求5，取 min(1,5)=1。令 ( x_{23} = 1 )。
6. A2产量已耗尽，划去A2这一行。B3需求剩余 5-1=4。
7. 继续在剩余格子中找最小。现在是 ( c_{13} = 3 )（A1到B3）和 ( c_{32} = 4 )（A3到B2）并列。通常任选一个，比如选 ( c_{13}=3 )。
8. A1产量7，B3剩余需求4，取 min(7,4)=4。令 ( x_{13} = 4 )。
9. B3需求已满足，划去B3列。A1产量剩余 7-4=3。
10. 剩余最小运价是 ( c_{32}=4 )。A3产量9，B2需求6，取 min(9,6)=6。令 ( x_{32} = 6 )。
11. B2需求满足，划去B2列。A3产量剩余 9-6=3。
12. 只剩A1和A3行，B4列。运价分别是 ( c_{14}=10 ), ( c_{34}=5 )。选较小的 ( c_{34}=5 )。
13. A3剩余产量3，B4需求6，取 min(3,6)=3。令 ( x_{34} = 3 )。
14. A3产量耗尽，划去A3行。B4需求剩余 6-3=3。
15. 最后只剩A1行和B4列。A1剩余产量3，B4剩余需求3，令 ( x_{14} = 3 )。

至此，所有产量和需求分配完毕。我们得到了一个初始调运方案。填入表格如下（括号内为运量）：

运价/运量	B1	B2	B3	B4	产量
A1	3	11	3 (4)	10 (3)	7
A2	1 (3)	9	2 (1)	8	4
A3	7	4 (6)	10	5 (3)	9
销量	3	6	5	6

计算当前总运费：( Z = 34 + 103 + 13 + 21 + 46 + 53 = 12 + 30 + 3 + 2 + 24 + 15 = 86 ) 元。

伏格尔法（考虑机会成本）： VAM法比最小元素法更精细，它考虑的是“次小运价与最小运价的差额”（即罚数），差额越大，说明不在该行/列采用最小运价的代价越高，因此应优先分配。

1. 计算每行、每列的罚数（次小值-最小值）。
   • 行罚数：A1: 3-3=0; A2: 2-1=1; A3: 5-4=1。
   • 列罚数：B1: 3-1=2; B2: 9-4=5; B3: 3-2=1; B4: 8-5=3。
2. 选最大罚数所在的行或列。最大是B2列的罚数5。
3. 在B2列中选最小运价 ( c_{32}=4 )。分配 min(9,6)=6，令 ( x_{32}=6 )。
4. B2列满足，划去。更新A3产量为3。
5. 重新计算剩余行/列罚数（略去计算过程）。后续按同样逻辑进行分配。
   • 接下来可能分配A2到B1（罚数大），然后A1到B3，A3到B4，最后分配剩余量。
   • 伏格尔法得到的初始方案通常更优（更接近最优解）。通过计算，我们可以得到另一个初始方案（过程略），其总运费可能低于86元。这说明了初始解选择的重要性。

实操心得：对于课堂练习或考试，如果题目没有明确要求，使用最小元素法通常足够，因为它简单快捷。但在实际物流优化项目中，如果问题规模较大（几十个产地销地），使用伏格尔法获取一个更好的初始解，可以显著减少后续迭代次数，节省计算时间。这是一个典型的“磨刀不误砍柴工”的场景。

3.2 第二步：最优性检验（位势法）

得到了初始基可行解（我们以最小元素法得到的方案为例），我们需要判断它是不是最优解。这里使用位势法（对偶变量法）。

基变量：在我们的方案中，有数字的格子（( x_{13}, x_{14}, x_{21}, x_{23}, x_{32}, x_{34} )）对应的就是基变量。注意，基变量的个数必须是m+n-1 = 3+4-1 = 6个。我们的方案正好有6个，是非退化的。如果少于6个，就需要在空格中补“0”，使其成为“退化”的基变量，这是另一个需要注意的细节。

位势法步骤：

1. 构造位势表：在运输表的基础上，增加一行 ( v_j )（销地位势）和一列 ( u_i )（产地位势）。
2. 对于每一个基变量格子 ( (i, j) )，满足方程：( u_i + v_j = c_{ij} )。
3. 先令 ( u_1 = 0 )（通常令第一个产地的位势为0，方便计算）。
4. 然后利用基变量格子的运价，像解方程组一样求出所有 ( u_i ) 和 ( v_j )。
   • 由 ( x_{13} ) 是基变量：( u_1 + v_3 = c_{13} = 3 ) => ( 0 + v_3 = 3 ) => ( v_3 = 3 )。
   • 由 ( x_{14} )：( u_1 + v_4 = 10 ) => ( v_4 = 10 )。
   • 由 ( x_{21} )：( u_2 + v_1 = 1 )。
   • 由 ( x_{23} )：( u_2 + v_3 = 2 ) => ( u_2 + 3 = 2 ) => ( u_2 = -1 )。
   • 把 ( u_2 = -1 ) 代入 ( u_2 + v_1 = 1 ) => ( v_1 = 2 )。
   • 由 ( x_{32} )：( u_3 + v_2 = 4 )。
   • 由 ( x_{34} )：( u_3 + v_4 = 5 ) => ( u_3 + 10 = 5 ) => ( u_3 = -5 )。
   • 把 ( u_3 = -5 ) 代入 ( u_3 + v_2 = 4 ) => ( v_2 = 9 )。
5. 计算所有非基变量（空格）的检验数 ( \sigma_{ij} = c_{ij} - (u_i + v_j) )。
   • ( \sigma_{11} = c_{11} - (u_1+v_1) = 3 - (0+2) = 1 )
   • ( \sigma_{12} = 11 - (0+9) = 2 )
   • ( \sigma_{22} = 9 - (-1+9) = 1 )
   • ( \sigma_{24} = 8 - (-1+10) = -1 )
   • ( \sigma_{31} = 7 - (-5+2) = 10 )
   • ( \sigma_{33} = 10 - (-5+3) = 12 )

最优性判定：对于最小化问题，当所有非基变量的检验数 ( \sigma_{ij} \geq 0 ) 时，当前方案为最优。我们发现 ( \sigma_{24} = -1 < 0 )。这说明当前方案不是最优，还可以改进。检验数为负的空格，意味着如果让这个格子参与运输（即让对应的变量进基），每增加一个单位的运量，总运费能降低 ( |\sigma_{ij}| ) 个单位。这里，( \sigma_{24} ) 格子（A2到B4）的潜力最大（负得最多，但这里只有一个负的），我们选择它作为入基变量。

3.3 第三步：方案调整（闭回路法）

确定了入基变量 ( x_{24} )（对应A2-B4这个空格）后，我们需要通过闭回路法来调整方案，找到一个更好的基可行解。

1. 寻找闭回路：以入基变量格子为起点，在保持当前基变量格子（有数字的格子）作为转角点的前提下，寻找一条水平或垂直的闭合路径。这条路径必须且只能以入基变量格子和基变量格子为顶点。

   • 从空格 (2,4) 出发，尝试寻找。一条可行的回路是：(2,4) -> (2,3) -> (1,3) -> (1,4) -> (2,4)。验证：所有转角点 (2,3), (1,3), (1,4) 都是基变量格。

2. 标记调整量：在闭回路的顶点依次交替标记“+”号和“-”号。起点（入基变量格）标记为“+”，表示将要增加运量。

   • (2,4): +
   • (2,3): -
   • (1,3): +
   • (1,4): -

3. 确定调整量 θ：观察所有标记为“-”的格子，其当前的运量。调整量 θ 等于这些“-”号格子的最小运量（为了保证调整后所有运量非负）。

   • “-”号格子只有 (2,3)，其运量为 1。所以 θ = 1。

4. 调整运量：沿着闭回路进行运量调整。

   • “+”号格子运量增加 θ：( x_{24} = 0 + 1 = 1 ), ( x_{13} = 4 + 1 = 5 )。
   • “-”号格子运量减少 θ：( x_{23} = 1 - 1 = 0 ), ( x_{14} = 3 - 1 = 2 )。
   • 调整后，( x_{23} ) 变成了0，它出基，变成了空格。( x_{24} ) 进基，运量为1。

得到新的调运方案如下：

运价/运量	B1	B2	B3	B4	产量
A1	3	11	3 (5)	10 (2)	7
A2	1 (3)	9	2 (0)	8 (1)	4
A3	7	4 (6)	10	5 (3)	9
销量	3	6	5	6

计算新方案总运费：( Z = 35 + 102 + 13 + 81 + 46 + 53 = 15+20+3+8+24+15 = 85 ) 元。比之前的86元减少了1元，正好等于 ( |\sigma_{24}| * \theta = 1 * 1 = 1 )，验证了调整的正确性。

3.4 迭代与最优解确认

得到新方案后，我们需要重复第二步“最优性检验”。

1. 新方案的基变量是：( x_{13}, x_{14}, x_{21}, x_{24}, x_{32}, x_{34} )（注意 ( x_{23} ) 出基，( x_{24} ) 进基）。
2. 重新计算位势。令 ( u_1=0 )。
   • ( x_{13} ): ( 0+v_3=3 ) => ( v_3=3 )
   • ( x_{14} ): ( 0+v_4=10 ) => ( v_4=10 )
   • ( x_{21} ): ( u_2+v_1=1 )
   • ( x_{24} ): ( u_2+v_4=8 ) => ( u_2+10=8 ) => ( u_2=-2 )
   • 代入 ( u_2+v_1=1 ) => ( v_1=3 )
   • ( x_{32} ): ( u_3+v_2=4 )
   • ( x_{34} ): ( u_3+v_4=5 ) => ( u_3+10=5 ) => ( u_3=-5 )
   • 代入 ( u_3+v_2=4 ) => ( v_2=9 )
3. 计算所有空格的检验数：
   • ( \sigma_{11} = 3 - (0+3) = 0 )
   • ( \sigma_{12} = 11 - (0+9) = 2 )
   • ( \sigma_{22} = 9 - (-2+9) = 2 )
   • ( \sigma_{23} = 2 - (-2+3) = 1 )
   • ( \sigma_{31} = 7 - (-5+3) = 9 )
   • ( \sigma_{33} = 10 - (-5+3) = 12 )

判定：此时所有检验数 ( \sigma_{ij} \geq 0 )。根据最优性条件，当前方案即为最优解。

因此，该运输问题的最优调运方案为：

• A1 -> B3: 5吨
• A1 -> B4: 2吨
• A2 -> B1: 3吨
• A2 -> B4: 1吨
• A3 -> B2: 6吨
• A3 -> B4: 3吨最小总运费为 85 元。

4. 结果分析与方案解读

算出最优解和85元这个数字，题目就算解完了吗？对于应试，是的。但对于真正理解运输问题，或者将来把它应用到实际工作中，这才刚刚开始。我们需要学会解读这个方案。

4.1 方案的经济与管理含义

让我们审视这个最优方案：

1. 成本最低的路线被充分利用：单位运价最低的路线是A2->B1（运价1），它承担了B1的全部需求（3吨）。次低的A1->B3（运价3）承担了B3的主要需求（5吨中的5吨）。这符合直观的经济性原则。
2. 运价较高的路线被规避或最小化：运价最高的几条路线，如A1->B2(11)、A3->B3(10)、A3->B1(7)，在最优方案中运量均为0。这说明优化模型成功地“绕开”了这些昂贵路径。
3. “折衷”与“平衡”：A3到B4的运价是5，A1到B4是10。为什么不让A3把全部9吨都运到B4（只需45元）？因为A3还要负责供应单价更优的B2（运价4）。模型在整体上做了权衡：让A3主要服务B2（运价4）和部分B4（运价5），虽然A1服务B4较贵（10），但腾出了A1的产能去服务更便宜的B3（3），同时让A2这个低产能工厂专注于最便宜的两条线路（B1和B4）。这就是全局最优的精髓——不是每个局部都最优，而是整体最优。

4.2 灵敏度分析与方案弹性

在实际物流管理中，知道方案在什么情况下仍然有效，和知道最优方案本身一样重要。这涉及到对检验数的解读。

还记得我们最后得到的所有非基变量（空格）的检验数吗？它们都是非负的。但其中 ( \sigma_{11} = 0 ) 是一个特殊信号。

• ( \sigma_{11} = 0 ) 意味着什么？它表示从A1到B1这条目前未使用的运输路线，其“隐含成本”（由位势决定的影子价格）正好等于其实际运价3。如果这条路的实际运价降低哪怕一点点（比如从3降到2.9），它就会变成负检验数，当前最优方案就不再最优，需要调整，让A1->B1进入方案。
• 管理启示：如果你作为物流经理，正在和运输公司谈判A1到B1这条线路的运价。当前合同价是3元/吨。对方提出降价到2.9元，你是否应该启用这条线路？模型告诉你：应该。因为启用后整体运费会下降。反之，如果其他线路成本发生变化，你也可以通过观察检验数的正负变化，快速判断是否需要重新规划。

其他正检验数（如 ( \sigma_{12}=2, \sigma_{22}=2 )）则更大。这意味着这些路线的实际运价比其“影子价格”高出较多，在目前供需和成本结构下，使用它们非常不经济。只有当它们的运价大幅下降（例如A1->B2从11降到9以下），才可能进入最优方案。

注意事项：在退化（基变量个数少于m+n-1）的情况下，寻找闭回路和计算检验数时需要特别小心，有时需要补“0”基变量来保证位势方程有唯一解。这是表上作业法的一个易错点，解题时要留意基变量个数。

5. 方法延伸与常见问题

通过这道例题，我们完整演练了运输问题的标准解法。但在实际应用中，情况会复杂得多。下面分享几个延伸思考和常见坑点。

5.1 产销不平衡问题的处理

我们的例题是完美的产销平衡。但现实中，更多是产量大于销量（供过于求）或销量大于产量（供不应求）。

• 产大于销：总产量 > 总销量。处理方法是虚设一个销地（库存地），其“销量”等于产销量差额，从各产地到该虚设销地的运价设为0。这相当于把多余的产品就地库存，不计运输成本。
• 销大于产：总销量 > 总产量。处理方法是虚设一个产地，其“产量”等于产销差额，从该虚设产地到各销地的运价设为0。这相当于存在未满足的需求，但因为我们无法生产，所以不计成本（或视为缺货损失，如果运价设为缺货成本单位）。

核心技巧：化为平衡问题后，求解过程一模一样。最后，虚设产地/销地所在的列/行如果有运量，就代表了库存或缺货的数量。

5.2 多种目标与约束的转化

运输问题的模型非常灵活，许多看似不同的问题可以转化为运输问题。

• 最大化问题：例如利润最大。只需将利润表视为“运价表”，但注意是最大化。此时最优性检验准则要反过来：所有非基变量的检验数 ( \sigma_{ij} \leq 0 ) 时为最优。或者更简单的方法：将利润表乘以-1，转化为最小化问题。
• 禁止运输路线：如果某条路线（如A2到B3）由于某些原因不能使用。只需将该格子的运价设为一个充分大的正数M（在计算机求解中）或在表上作业法中直接将该格子划掉，永不选用。
• 需求量弹性（有上下限）：这超出了标准运输问题范围，需要用到更复杂的“转运问题”或“网络流问题”模型。但思想相通：通过添加虚设点和设置适当的成本来模拟。

5.3 手工计算与软件求解的取舍

对于这道3x4的题目，手工计算绰绰有余。但现实中，动辄几十上百个产地销地，手工计算是不可能的。

• Excel规划求解：对于中小规模问题（几十个变量），Excel的“规划求解”插件是绝佳工具。你只需要像我们第一步那样，建立变量区、目标函数单元格和约束条件单元格，然后调用求解器，它能快速给出最优解和灵敏度报告。
• 编程求解：对于大规模问题，需要用到专业的优化库，如Python的PuLP,ortools，或商业软件如LINGO、Gurobi等。这时，你的核心工作就变成了正确建模——将业务问题准确地翻译成目标函数和约束条件，剩下的交给计算机。

一个常见的误解：很多人学会了表上作业法，就以为只能解运输问题。其实，它的思想——利用特殊结构简化计算——是运筹学里非常重要的思想。很多大规模线性规划问题，如果其约束矩阵具有类似“网络流”的结构，都有比通用单纯形法更高效的专用算法。

最后，再分享一个我自己的心得：学习运输问题，乃至整个运筹学，一定要动手画表、计算。看十遍不如算一遍。在计算过程中，你对“位势”、“检验数”、“闭回路”这些抽象概念的理解会瞬间具象化。当你能够不假思索地为一个新问题画出第一张运输表时，你就真正掌握了这个强大的分析工具。这道经典例题就像一把钥匙，希望它能帮你打开运筹优化这扇大门，看到里面更广阔的世界。