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

1. 项目概述从一道经典例题看透运输问题的本质最近在后台和社群里看到不少朋友在啃运筹学里的运输问题。大家普遍的感觉是单纯看单纯形法、表上作业法的步骤好像懂了但一拿到具体的题目尤其是数据稍微复杂一点或者问法灵活一点的就不知道从何下手怎么把那些表格、数字和理论对应起来。这太正常了运输问题作为线性规划的一个特例它的魅力就在于用一套非常直观的“表格”来隐藏了背后复杂的数学结构。今天我就想借一道被无数教材引用的经典例题带大家走一遍完整的解题流程。我们的目标不是仅仅算出答案而是通过这道题彻底搞明白面对一个运输问题我们应该如何思考如何把实际问题转化为数学模型又如何选择最高效的求解路径以及最终如何解读结果背后的管理意义。这道题是这样的某公司有三个工厂 A1, A2, A3生产同一种产品其月产量分别是 7吨、4吨、9吨。这些产品需要运往四个销售地 B1, B2, B3, B4其月销量分别是 3吨、6吨、5吨、6吨。已知从每个工厂到每个销售地的单位运价元/吨如下表所示。问应如何调运才能使总运费最少运价B1B2B3B4产量A13113107A219284A3741059销量3656这就是一个最标准的、产销平衡的运输问题。所谓“经典”就在于它要素齐全多个供应地、多个需求地、明确的供应量与需求量、以及差异化的运输成本。它几乎涵盖了运输问题模型的所有核心概念。接下来我们不求快但求透。我会把自己十多年处理这类问题从教学到实际项目建模的经验揉碎了分享给你。你会发现只要思路清晰运输问题的求解就像完成一个结构化的拼图每一步都有其必然的逻辑。2. 问题拆解与模型建立把文字翻译成数学语言很多初学者卡在第一步看到题目描述和一堆数字就发懵。我的经验是永远不要直接扎进数字里先花两分钟做好“翻译”工作。这一步做扎实了后面求解会顺利得多。2.1 识别问题要素与建立运价表首先我们要把题目中的文字信息整理成我们熟悉的“运输表”形式。这本身就是建模的第一步。供应地发点与供应量产量A1(7), A2(4), A3(9)。记住在表中我们通常把供应量放在每一行的最右边。需求地收点与需求量销量B1(3), B2(6), B3(5), B4(6)。需求量放在每一列的最下边。决策变量这是我们要求解的核心。设 ( x_{ij} ) 表示从工厂 i 运往销售地 j 的产品数量吨。例如( x_{12} ) 就是从A1运到B2的数量。我们最终要找的就是所有 ( x_{ij} ) 的值。目标函数系数单位运价题目给出的3x4表格中间那12个数字3, 11, 3, 10; 1, 9, 2, 8; 7, 4, 10, 5就是运价 ( c_{ij} )。它们直接决定了我们的目标——总运费。把以上信息整合就得到了我们在概述中列出的那张完整的运输表。这张表是后续所有操作的基础载体。这里有个关键检查点计算总产量和总销量。74920365620。两者相等这是一个产销平衡问题。这是最理想的情况意味着我们的模型约束都是等式所有产品都能运出去所有需求都能被满足。如果不等就需要先通过引入“虚设产地”或“虚设销地”来化为平衡问题这是后话但在这个经典例题中我们很幸运。2.2 构建线性规划模型有了运输表我们就可以用严谨的数学语言来描述这个问题了。这一步虽然看似理论化但它能帮你从根本上理解表上作业法每一步在做什么。决策变量( x_{ij} \geq 0 ), (i1,2,3; j1,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} ] 这个式子就是运价表中每个格子运价与其运输量的乘积之和。约束条件供应约束每个工厂运出的不能超过其产量对于每个工厂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} ]需求约束每个销地收到的等于其需求量对于每个销地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} ]非负约束( x_{ij} \geq 0 )。看到这里你应该能理解为什么说运输问题是线性规划的特例了。它的约束矩阵非常特殊全是0和1并且具有“每行每列之和为定值”的结构。这个结构正是“表上作业法”能够成立的基础。表上作业法本质上就是在运输表这个直观的界面上执行单纯形法的迭代优化只不过我们操作的是“格子”和“数字”而不是抽象的矩阵和向量。注意在实际考试或快速分析时我们通常跳过写出完整数学模型这一步直接画表操作。但我强烈建议初学者尤其是感到困惑的时候一定要亲手写一遍这个模型。它能帮你建立“表格操作”与“数学原理”之间的桥梁理解更深。3. 求解流程详解表上作业法三步走模型建立好了现在进入核心的求解阶段——表上作业法。这是运输问题的专属解法比通用的单纯形法更高效、更直观。整个过程分为三步寻找初始基可行解 - 最优性检验 - 方案调整闭回路调整。我们一步一步来。3.1 第一步寻找初始基可行解初始解的好坏直接影响迭代次数。我们有多种方法如最小元素法、伏格尔法Vogel‘s Approximation Method, VAM、西北角法等。对于这道题为了展示效果并兼顾效率我们先用最小元素法再对比一下伏格尔法。最小元素法就近供应思想 核心思路优先满足单位运价最小的那个运输路线。从运价表中找到最小的运价。全局最小是 ( c_{21} 1 )A2到B1。尽可能多地满足它。A2产量4B1销量3取最小值 min(4,3)3。所以令 ( x_{21} 3 )。由于B1的需求3已被完全满足划去B1这一列。A2的产量剩余 4-31。在剩余的格子中找最小运价。此时最小是 ( c_{23} 2 )A2到B3。A2剩余产量1B3需求5取 min(1,5)1。令 ( x_{23} 1 )。A2产量已耗尽划去A2这一行。B3需求剩余 5-14。继续在剩余格子中找最小。现在是 ( c_{13} 3 )A1到B3和 ( c_{32} 4 )A3到B2并列。通常任选一个比如选 ( c_{13}3 )。A1产量7B3剩余需求4取 min(7,4)4。令 ( x_{13} 4 )。B3需求已满足划去B3列。A1产量剩余 7-43。剩余最小运价是 ( c_{32}4 )。A3产量9B2需求6取 min(9,6)6。令 ( x_{32} 6 )。B2需求满足划去B2列。A3产量剩余 9-63。只剩A1和A3行B4列。运价分别是 ( c_{14}10 ), ( c_{34}5 )。选较小的 ( c_{34}5 )。A3剩余产量3B4需求6取 min(3,6)3。令 ( x_{34} 3 )。A3产量耗尽划去A3行。B4需求剩余 6-33。最后只剩A1行和B4列。A1剩余产量3B4剩余需求3令 ( x_{14} 3 )。至此所有产量和需求分配完毕。我们得到了一个初始调运方案。填入表格如下括号内为运量运价/运量B1B2B3B4产量A13113 (4)10 (3)7A21 (3)92 (1)84A374 (6)105 (3)9销量3656计算当前总运费( Z 34 103 13 21 46 53 12 30 3 2 24 15 86 ) 元。伏格尔法考虑机会成本 VAM法比最小元素法更精细它考虑的是“次小运价与最小运价的差额”即罚数差额越大说明不在该行/列采用最小运价的代价越高因此应优先分配。计算每行、每列的罚数次小值-最小值。行罚数A1: 3-30; A2: 2-11; A3: 5-41。列罚数B1: 3-12; B2: 9-45; B3: 3-21; B4: 8-53。选最大罚数所在的行或列。最大是B2列的罚数5。在B2列中选最小运价 ( c_{32}4 )。分配 min(9,6)6令 ( x_{32}6 )。B2列满足划去。更新A3产量为3。重新计算剩余行/列罚数略去计算过程。后续按同样逻辑进行分配。接下来可能分配A2到B1罚数大然后A1到B3A3到B4最后分配剩余量。伏格尔法得到的初始方案通常更优更接近最优解。通过计算我们可以得到另一个初始方案过程略其总运费可能低于86元。这说明了初始解选择的重要性。实操心得对于课堂练习或考试如果题目没有明确要求使用最小元素法通常足够因为它简单快捷。但在实际物流优化项目中如果问题规模较大几十个产地销地使用伏格尔法获取一个更好的初始解可以显著减少后续迭代次数节省计算时间。这是一个典型的“磨刀不误砍柴工”的场景。3.2 第二步最优性检验位势法得到了初始基可行解我们以最小元素法得到的方案为例我们需要判断它是不是最优解。这里使用位势法对偶变量法。基变量在我们的方案中有数字的格子( x_{13}, x_{14}, x_{21}, x_{23}, x_{32}, x_{34} )对应的就是基变量。注意基变量的个数必须是mn-1 34-1 6个。我们的方案正好有6个是非退化的。如果少于6个就需要在空格中补“0”使其成为“退化”的基变量这是另一个需要注意的细节。位势法步骤构造位势表在运输表的基础上增加一行 ( v_j )销地位势和一列 ( u_i )产地位势。对于每一个基变量格子 ( (i, j) )满足方程( u_i v_j c_{ij} )。先令 ( u_1 0 )通常令第一个产地的位势为0方便计算。然后利用基变量格子的运价像解方程组一样求出所有 ( 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 )。计算所有非基变量空格的检验数 ( \sigma_{ij} c_{ij} - (u_i v_j) )。( \sigma_{11} c_{11} - (u_1v_1) 3 - (02) 1 )( \sigma_{12} 11 - (09) 2 )( \sigma_{22} 9 - (-19) 1 )( \sigma_{24} 8 - (-110) -1 )( \sigma_{31} 7 - (-52) 10 )( \sigma_{33} 10 - (-53) 12 )最优性判定对于最小化问题当所有非基变量的检验数 ( \sigma_{ij} \geq 0 ) 时当前方案为最优。我们发现 ( \sigma_{24} -1 0 )。这说明当前方案不是最优还可以改进。检验数为负的空格意味着如果让这个格子参与运输即让对应的变量进基每增加一个单位的运量总运费能降低 ( |\sigma_{ij}| ) 个单位。这里( \sigma_{24} ) 格子A2到B4的潜力最大负得最多但这里只有一个负的我们选择它作为入基变量。3.3 第三步方案调整闭回路法确定了入基变量 ( x_{24} )对应A2-B4这个空格后我们需要通过闭回路法来调整方案找到一个更好的基可行解。寻找闭回路以入基变量格子为起点在保持当前基变量格子有数字的格子作为转角点的前提下寻找一条水平或垂直的闭合路径。这条路径必须且只能以入基变量格子和基变量格子为顶点。从空格 (2,4) 出发尝试寻找。一条可行的回路是(2,4) - (2,3) - (1,3) - (1,4) - (2,4)。验证所有转角点 (2,3), (1,3), (1,4) 都是基变量格。标记调整量在闭回路的顶点依次交替标记“”号和“-”号。起点入基变量格标记为“”表示将要增加运量。(2,4): (2,3): -(1,3): (1,4): -确定调整量 θ观察所有标记为“-”的格子其当前的运量。调整量 θ 等于这些“-”号格子的最小运量为了保证调整后所有运量非负。“-”号格子只有 (2,3)其运量为 1。所以 θ 1。调整运量沿着闭回路进行运量调整。“”号格子运量增加 θ( 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。得到新的调运方案如下运价/运量B1B2B3B4产量A13113 (5)10 (2)7A21 (3)92 (0)8 (1)4A374 (6)105 (3)9销量3656计算新方案总运费( Z 35 102 13 81 46 53 1520382415 85 ) 元。比之前的86元减少了1元正好等于 ( |\sigma_{24}| * \theta 1 * 1 1 )验证了调整的正确性。3.4 迭代与最优解确认得到新方案后我们需要重复第二步“最优性检验”。新方案的基变量是( x_{13}, x_{14}, x_{21}, x_{24}, x_{32}, x_{34} )注意 ( x_{23} ) 出基( x_{24} ) 进基。重新计算位势。令 ( u_10 )。( x_{13} ): ( 0v_33 ) ( v_33 )( x_{14} ): ( 0v_410 ) ( v_410 )( x_{21} ): ( u_2v_11 )( x_{24} ): ( u_2v_48 ) ( u_2108 ) ( u_2-2 )代入 ( u_2v_11 ) ( v_13 )( x_{32} ): ( u_3v_24 )( x_{34} ): ( u_3v_45 ) ( u_3105 ) ( u_3-5 )代入 ( u_3v_24 ) ( v_29 )计算所有空格的检验数( \sigma_{11} 3 - (03) 0 )( \sigma_{12} 11 - (09) 2 )( \sigma_{22} 9 - (-29) 2 )( \sigma_{23} 2 - (-23) 1 )( \sigma_{31} 7 - (-53) 9 )( \sigma_{33} 10 - (-53) 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 方案的经济与管理含义让我们审视这个最优方案成本最低的路线被充分利用单位运价最低的路线是A2-B1运价1它承担了B1的全部需求3吨。次低的A1-B3运价3承担了B3的主要需求5吨中的5吨。这符合直观的经济性原则。运价较高的路线被规避或最小化运价最高的几条路线如A1-B2(11)、A3-B3(10)、A3-B1(7)在最优方案中运量均为0。这说明优化模型成功地“绕开”了这些昂贵路径。“折衷”与“平衡”A3到B4的运价是5A1到B4是10。为什么不让A3把全部9吨都运到B4只需45元因为A3还要负责供应单价更优的B2运价4。模型在整体上做了权衡让A3主要服务B2运价4和部分B4运价5虽然A1服务B4较贵10但腾出了A1的产能去服务更便宜的B33同时让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以下才可能进入最优方案。注意事项在退化基变量个数少于mn-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等。这时你的核心工作就变成了正确建模——将业务问题准确地翻译成目标函数和约束条件剩下的交给计算机。一个常见的误解很多人学会了表上作业法就以为只能解运输问题。其实它的思想——利用特殊结构简化计算——是运筹学里非常重要的思想。很多大规模线性规划问题如果其约束矩阵具有类似“网络流”的结构都有比通用单纯形法更高效的专用算法。最后再分享一个我自己的心得学习运输问题乃至整个运筹学一定要动手画表、计算。看十遍不如算一遍。在计算过程中你对“位势”、“检验数”、“闭回路”这些抽象概念的理解会瞬间具象化。当你能够不假思索地为一个新问题画出第一张运输表时你就真正掌握了这个强大的分析工具。这道经典例题就像一把钥匙希望它能帮你打开运筹优化这扇大门看到里面更广阔的世界。