1. 运输问题从理论到实战的“最后一公里”如果你学过运筹学或者正在准备相关考试那么“运输问题”这个词你一定不陌生。它几乎是所有运筹学教材里必讲的章节也是各类考试、面试中的常客。但不知道你有没有这种感觉看教材例题时感觉每一步都懂公式也背得滚瓜烂熟可一旦题目条件稍微变一变或者数据量一大就不知道从何下手了。这感觉就像学开车在驾校里倒库移库练得挺好真上了复杂路况还是手忙脚乱。运输问题本质上就是解决“如何以最低的总成本把货物从多个供应地产地运送到多个需求地销地”的数学规划问题。它听起来特别“接地气”因为物流、供应链、生产调度甚至是一些资源分配的场景底层逻辑都是它。但恰恰是这种看似简单的模型在实际应用中藏着不少“坑”。比如当产销量不平衡时怎么办当运输路线有容量限制时怎么处理当目标不是求最小成本而是求最大利润时模型又该如何调整今天我们就抛开教材上那些高度抽象化的例题来一次深度实战。我会结合几个经典又“狡猾”的例题不仅带你一步步推演求解过程更重要的是拆解题目背后设置的“陷阱”分享我在多年学习和教学中总结出的、那些教材上不会写的“解题心法”。我们的目标很明确不仅要会算更要懂为什么这么算以及遇到变种题目时如何快速找到突破口。2. 夯实基础运输问题模型的核心要素与标准形式在跳进题海之前我们必须把“武器”检查一遍。很多同学解题出错第一步就错在对模型的基本假设和标准形式理解不透彻。2.1 模型的三要素与表格表达一个标准的运输问题离不开三个核心要素供应量Supplym个产地A1, A2, ..., Am每个产地的供应量为a_i(i1,2,...,m)。这代表了“我们有多少货可以发”。需求量Demandn个销地B1, B2, ..., Bn每个销地的需求量为b_j(j1,2,...,n)。这代表了“市场需要多少货”。单位运价Unit Cost从产地Ai到销地Bj运输一个单位货物的成本为c_ij。这构成了模型的“价格表”是目标函数的核心。最直观的表达方式就是运价表与产销平衡表。我们通常画一个m行n列的表格表格中间每个格子填写c_ij右侧增加一列“产量”下方增加一行“销量”。例如一个简单的2产地3销地问题运价/产销销地B1销地B2销地B3产量产地A129109产地A21345销量46414注意这个表格不仅仅是数据的罗列。在后续用表上作业法如最小元素法、伏格尔法求初始解时我们就是在这个表格上直接进行“分配”操作的。养成画表的习惯是解题规范性的第一步。2.2 产销平衡模型的“入场券”标准运输问题有一个黄金前提总产量等于总销量。即∑a_i ∑b_j这是我们能够应用表上作业法包括最小元素法、位势法检验等的基石。如果题目不满足这个条件我们必须先进行“标准化”处理这是第一个易错点。产大于销∑a_i ∑b_j我们虚构一个“虚拟销地”Bn1其销量等于多余的产量∑a_i - ∑b_j。关键点在于运到虚拟销地的单位运价c_i,n1如何设定如果目标是极小化总成本通常设为0。因为把货物“运到”虚拟销地实际意味着货物在产地没运出去不发生运输成本。如果目标是极大化利润则需谨慎通常设为-M一个极大的负数在极大化问题中等价于成本极高迫使模型不选择此路径或根据库存成本具体设定。销大于产∑a_i ∑b_j我们虚构一个“虚拟产地”Am1其产量等于不足的销量∑b_j - ∑a_i。同样从虚拟产地运出的单位运价c_m1,j如何设定极小化成本问题通常设为0。表示需求未被满足但模型允许这种“缺货”且缺货成本为0。如果缺货有惩罚成本则应设为惩罚值。极大化利润问题通常设为-M表示无法从“虚拟”产地获得货物来满足需求除非支付极高成本。很多题目会在这里埋坑比如给出一个明显不平衡的产销数据却不提醒你。第一步没做标准化后面全盘皆输。2.3 数学模型理解决策变量与约束用数学语言表述运输问题的模型如下决策变量x_ij表示从产地i运往销地j的货物量。这是我们要求解的对象。目标函数最小化总成本 Min Z ∑∑ c_ij * x_ij (对 i1..m, j1..n 求和)约束条件供应约束从每个产地运出的总量等于其产量。 ∑ x_ij a_i (对每个产地 i)需求约束运到每个销地的总量等于其销量。 ∑ x_ij b_j (对每个销地 j)非负约束运输量不能为负。 x_ij ≥ 0这个模型是一个特殊的线性规划问题其约束矩阵具有非常特殊的结构每列只有两个1这决定了它必然存在整数解当产量和销量为整数时并且可以用比单纯形法更高效的表上作业法求解。3. 经典例题精讲一平衡型问题与表上作业法全流程我们来看一个最标准的平衡型问题并完整走一遍表上作业法的流程。例题1某公司有3个工厂A1, A2, A3生产同一种产品4个销售点B1, B2, B3, B4销售该产品。各工厂产量、各销售点销量及单位产品运价如下表所示。问应如何调运使总运费最小运价/产销B1B2B3B4产量A13113107A219284A3741059销量365620第一步验证产销平衡总产量 7 4 9 20 总销量 3 6 5 6 20 平衡可直接求解。第二步用最小元素法求初始基可行解最小元素法的思想很直观优先满足单位运价最小的路线。但操作时有严格步骤避免出错。在运价表中找到最小的运价c_ij。这里是c_21 1A2到B1。尽可能多地满足它。A2产量为4B1销量为3取最小值min(4,3)3。将3填入A2, B1格。此时B1销量已满足划去B1列。操作心得在表中直接画掉被满足的行或列并在旁边用小字标注剩余产量/销量可以极大减少错误。划掉B1列后A2行剩余产量为4-31。在未划去的格子中再找最小运价。此时最小的是c_23 2A2到B3。A2剩余产量为1B3销量为5取min(1,5)1。将1填入A2, B3格。此时A2产量已分配完划去A2行。B3列剩余销量为5-14。继续在剩余格子中找最小运价。现在最小的是c_13 3和c_11 3都是3。这里就涉及到一个关键技巧当最小运价不止一个时优先选择能分配更多运量的那个。我们比较一下选A1, B3A1产量7B3剩余需求4可分配min(7,4)4。选A1, B1但B1列已被划去不可选。 所以选A1, B3分配4。划去B3列因为其需求被满足A1行剩余7-43。重复此过程。接下来最小运价是c_32 4A3到B2。分配min(9,6)6划去B2列A3行剩余9-63。然后最小运价是c_34 5A3到B4。分配min(3,6)3划去A3行B4列剩余6-33。最后只剩下A1行和B4列。A1剩余产量3B4剩余销量3正好将3填入A1, B4。得到初始调运方案如下表括号内为运量运价/产销B1B2B3B4产量A13113 (4)10 (3)7A21 (3)92 (1)84A374 (6)105 (3)9销量365620重要检查基变量个数应为mn-1 34-1 6。我们数一下有数字的格子A1,B3、A1,B4、A2,B1、A2,B3、A3,B2、A3,B4正好6个且不存在闭合回路。初始解正确。第三步用位势法对偶变量法检验当前解是否最优这是表上作业法的核心也是难点。位势法的目的是计算每个非基变量空格的检验数σ_ij。如果所有σ_ij ≥ 0对于最小化问题则当前解最优否则需要调整。求位势u_i和v_j对于每个基变量有运量的格x_ij满足方程u_i v_j c_ij。我们有无穷多组解通常令u_1 0来启动计算。基格 (A1,B3):u1 v3 30 v3 3v3 3基格 (A1,B4):u1 v4 100 v4 10v4 10基格 (A2,B1):u2 v1 1v1还不知道。基格 (A2,B3):u2 v3 2u2 3 2u2 -1由u2 -1和 (A2,B1) 格-1 v1 1v1 2基格 (A3,B2):u3 v2 4v2还不知道。基格 (A3,B4):u3 v4 5u3 10 5u3 -5由u3 -5和 (A3,B2) 格-5 v2 4v2 9得到位势u (0, -1, -5),v (2, 9, 3, 10)计算非基变量空格检验数公式σ_ij c_ij - (u_i v_j)。(A1,B1):σ_11 3 - (02) 1(A1,B2):σ_12 11 - (09) 2(A2,B2):σ_22 9 - (-19) 1(A2,B4):σ_24 8 - (-110) -1(A3,B1):σ_31 7 - (-52) 10(A3,B3):σ_33 10 - (-53) 12判断我们发现σ_24 -1 0。根据判别准则检验数出现负值说明当前解不是最优可以让x_24A2到B4进入基变量来改进方案。第四步用闭回路法调整方案寻找闭回路以检验数为负的非基变量格A2,B4为起点寻找一条由水平/垂直直线构成的、转角点均为基变量格的闭合回路。这条回路是唯一的。 回路为(A2,B4) → (A2,B3) → (A1,B3) → (A1,B4) → (A2,B4)。确定调整量 θ在回路的偶数顶点即第二个、第四个转角点中找出运量最小的值。本例中偶数顶点是 (A2,B3) 的1和 (A1,B4) 的3最小值为θ min(1, 3) 1。调整运量在回路的奇数顶点起点为第一个奇数顶点运量加上θ在偶数顶点运量减去θ。(A2,B4)起点原为空0 1 1(A2,B3)1 - 1 0变为空格(A1,B3)4 1 5(A1,B4)3 - 1 2调整后的新方案为运价/产销B1B2B3B4产量A13113 (5)10 (2)7A21 (3)928 (1)4A374 (6)105 (3)9销量365620第五步重复检验与调整对新方案再次用位势法求检验数。令u10。(A1,B3):0v33v33(A1,B4):0v410v410(A2,B1):u2v11(A2,B4):u2108u2-2由u2-2和 (A2,B1):-2v11v13(A3,B2):u3v24(A3,B4):u3105u3-5由u3-5和 (A3,B2):-5v24v29计算非基变量检验数(A1,B1):3-(03)0(A1,B2):11-(09)2(A2,B2):9-(-29)2(A2,B3):2-(-23)1(A3,B1):7-(-53)9(A3,B3):10-(-53)12所有检验数σ_ij ≥ 0。因此当前解为最优解。最优调运方案A1 → B3: 5 单位A1 → B4: 2 单位A2 → B1: 3 单位A2 → B4: 1 单位A3 → B2: 6 单位A3 → B4: 3 单位最小总运费Z 5*3 2*10 3*1 1*8 6*4 3*5 15 20 3 8 24 15 85避坑指南初始解退化在求初始解或调整时如果同时划去一行和一列会导致基变量个数少于mn-1称为“退化”。此时必须在被同时划去的行或列中选择一个空格填入“0”并将其视为基变量有数字的格否则位势法无法计算。这个“0”的选取有讲究最好选在单位运价较小的格子有利于后续迭代。闭回路画法调整时闭回路必须且只能以基变量格为转角点除了起点是空格外。画错回路是调整失败的主要原因。一个检查技巧回路上的每个转角点除起点外都必须是已有运量的格子且回路是闭合的。检验数计算错误这是最常出错的地方。务必先求对位势u_i和v_j。一个快速验证方法是任选一个空格用你求出的u_i和v_j计算c_ij - (u_iv_j)如果结果与你用闭回路法算出的检验数通过沿着该空格的假想回路正负交替加减运价不一致说明位势求错了。4. 经典例题精讲二不平衡问题、最大化问题与复杂约束现实问题很少是标准平衡型。我们来看两个变种。例题2产大于销已知运输问题的产销量及运价如下求最优调运方案。运价/产销B1B2B3产量A129109A21345销量46414第一步识别与标准化总产量 9 5 14 总销量 4 6 4 14等等仔细加一下46414。咦平衡 这里就是第一个陷阱数据看似平衡但其实是“产大于销”。因为总产量14总销量也是14但注意看产量列的数字9和5与销量行的数字4、6、4总和都是14。这没问题啊等等我们重新审视表格这是一个2行3列的问题。m2, n3。总产量a1a29514总销量b1b2b346414。数学上是平衡的。但为什么题目暗示这是“产大于销”的变种呢这可能是一个表述陷阱。原题可能意在考察“产量”和“销量”数字本身不等的情况。我们假设原题销量数据是(4, 5, 4)总和13小于产量14。那么我们就需要引入虚拟销地B4销量为1运价为0。为了演示我们假设销量是 (4, 5, 4)总销量13 总产量14。那么标准化步骤如下增加虚拟销地 B4销量 14 - 13 1。从A1、A2到B4的运价设为0。新的产销平衡表如下运价/产销B1B2B3B4(虚)产量A1291009A213405销量454114第二步求解此时就可以用标准的表上作业法求解了。最优解中分配到虚拟销地B4的运量就代表了对应产地未运出的库存量。例如如果最优解中x_141则表示A1有1单位产品没有运出留在本地。核心要点处理不平衡问题的关键在于准确判断是“产大于销”还是“销大于产”并正确设置虚拟产地/销地的运价。对于最小化成本问题虚拟路线的运价通常设为0表示“不发生运输成本”。但务必注意题目是否有特殊说明比如库存成本、缺货惩罚等这些成本需要体现在虚拟路线的运价上。例题3最大化问题下表给出了一个运输问题的运价表但这里的“运价”实际上是单位利润。求使总利润最大的调运方案。利润/产销B1B2B3产量A163540A247230销量30252075第一步转化对于最大化问题有两种标准处理方法差值法效率法找出全局最大利润M max(c_ij)。然后构造一个新的“损失”矩阵c_ij M - c_ij。将原最大化问题转化为对c_ij的最小化问题。因为最小化总“损失”等价于最大化总利润。本例中M 7。新运价表为损失/产销B1B2B3产量A114240A230530销量30252075然后用表上作业法求这个损失表的最小化解即为原利润表的最大化解。检验数符号反转法直接对利润表c_ij用表上作业法求解但最优性判别准则要反过来所有非基变量的检验数σ_ij ≤ 0时解最优。因为此时让任何非基变量入基增加运量都不会再增加总利润检验数为负或零表示利润会减少或不变。第二步求解以差值法为例验证产销平衡403030252075平衡。 对“损失”表用最小元素法求初始解过程略。最优解经过迭代可能为A1 → B1: 30A1 → B3: 10A2 → B2: 25A2 → B3: 5 注意这是一个可能的解实际需迭代至最优第三步回溯将解代入原利润表计算总利润Z_max 30*6 10*5 25*7 5*2 180 50 175 10 415。避坑指南最大化问题最易错的就是最优性判别。如果用第二种方法直接对利润表做求检验数的公式不变σ_ij c_ij - (u_iv_j)但判断时一定要记住所有σ_ij ≤ 0才是最优。如果看到正的检验数说明让那个非基变量入基还能增加利润需要调整。很多同学会习惯性地套用最小化问题的σ_ij ≥ 0准则导致答案完全错误。差值法中M的选取M必须大于等于原表中所有c_ij。通常直接取最大值即可。但要注意转化后的“损失”表所有元素非负符合运输问题的常规形式。5. 经典例题精讲三含禁止运输路线与中转问题运输路线可能因道路不通、政策限制等原因无法使用这就是“禁止运输”或“断路”问题。另一种常见变体是“中转”或“转运”问题。例题4含禁止路线在例题1的基础上假设从工厂A2到销售点B1的路线因故无法使用求此时的最优调运方案。解法大M法处理禁止路线标准方法是将该路线的单位运价c_ij设为一个极大的正数M。在最小化问题中M意味着成本无限高模型会自动规避该路线除非万不得已在产销平衡且无其他路径可选时才可能被迫使用此时问题可能无可行解。所以我们只需将原题中的c_21从1改为M然后重新求解。求解过程中在最小元素法找最小运价时会自动忽略这个巨大的M。在最终的最优解中x_21必然为0基变量不会选它因为检验数会很大。实操技巧在手工计算时M可以看作一个比表中所有实际数字都大得多的数。在比较运价大小时任何实际数字都小于M。在计算检验数σ_ij c_ij - (u_iv_j)时如果c_ij M那么σ_ij也会是一个很大的正数肯定不会成为入基变量对于最小化问题。例题5中转运输问题这是运输问题一个非常实用的扩展。假设货物不仅可以从产地直接运到销地还可以先运到某个中转站仓库再从中转站运到销地。甚至允许产地之间、销地之间互相转运。这类问题通常的解法是转化为扩大的标准运输问题。将每个地点既视为产地也视为销地。每个地点的“产量”等于其原始产量加上可能的中转容量如果无限则为一个很大的数“销量”等于其原始销量加上可能的中转发出量。构造一个包含所有地点原始产地、原始销地、中转站的扩大的运价表。直接运输的运价已知。中转运输的运价 第一段运价 第二段运价。同一个地点自己到自己的运价为0表示不移动。如果两点间不允许直接运输则运价为M。确定扩大量后的产销量。这是一个关键且易错点。通常设中转站的产量和销量为一个足够大的数大于等于总运输量表示其吞吐能力足够大。原始产地的销量设为0或一个很小的数表示允许自我留存原始销地的产量设为0。例如有产地A1、A2销地B1、B2一个中转站T。原始数据A1产量10A2产量20B1销量15B2销量15。运价A1→T2, A2→T3, T→B14, T→B25, A1→B19, A2→B28其他直接路线不可用或很贵。转化将A1, A2, T, B1, B2 都视为“地点”。构造5x5的运价表。其中A1到T的运价2A2到T3T到B14T到B25A1到B19A2到B28。A1到A1, A2到A2, T到T, B1到B1, B2到B2 运价0。其他不允许或未知的路线运价设为M。产销量设定A1作为产地产量10作为销地销量0或一个很小的数表示它自己可以“消费”自己的产品即不运出。A2作为产地产量20销量0。T作为产地产量总运输量如30或更大表示其可提供的转运货物量来自其他产地作为销地销量总运输量30表示其可接收的待转运货物量。B1作为销地销量15产量0。B2作为销地销量15产量0。总产量 102030 60总销量 00301515 60。平衡。然后对这个扩大的平衡运输问题用表上作业法求解。解中x_A1T表示从A1运到T的量x_TB1表示从T运到B1的量等等。x_A1A1可能非零表示A1的产品留在了A1即未运出这在允许库存的情况下是合理的。深度解析中转问题的转化思想本质上是将“运输网络”拍平成了一个所有节点两两相连的完全图问题。通过设置合理的产销量和运价尤其是自己到自己的0运价和不允许通行的M运价让模型自己去选择是直接运输还是经过中转。这是运输问题模型灵活性的一个绝佳体现。手工计算此类问题非常繁琐但理解其转化原理至关重要因为这是用计算机求解复杂物流网络问题的基础建模思想。6. 软件求解与实战检验从手工到自动化虽然掌握手工计算是理解原理的基础但在实际工作中面对几十上百个产地销地的问题我们必然依赖软件。这里以最通用的Excel Solver规划求解和Python的pulp库为例演示如何将上述理论付诸实践。6.1 使用Excel Solver求解运输问题Excel Solver是一个内置的强大工具非常适合中小规模问题的建模和求解。建立模型区域在一个区域如A1:E4输入运价表、产量和销量与我们的手工表一致。在另一个区域如G1:J4建立同样大小的“决策变量表”存放待求的x_ij初始可设为0或空白。在K列计算每个产地的实际发出量K2 SUM(G2:J2)向下填充。这对应供应约束。在第5行计算每个销地的实际收到量G5 SUM(G2:G4)向右填充。这对应需求约束。在某个单元格如L5计算总成本SUMPRODUCT(G2:J4, A2:D4)。这里G2:J4是运量区域A2:D4是运价区域。配置Solver参数目标单元格$L$5总成本。选择“最小值”。可变单元格$G$2:$J$4决策变量区域。约束条件$G$2:$J$4 0非负约束$K$2:$K$4 $E$2:$E$4供应约束实际发出量 产量$G$5:$J$5 $G$6:$J$6需求约束实际收到量 销量。这里假设第6行存放销量数据。求解方法选择“单纯线性规划”。求解与解读点击“求解”Solver会找到最优解并填入G2:J4区域。L5显示最小总成本。Excel实战技巧整数解运输问题本身有整数解性质但如果你的模型有额外约束破坏了这种性质可以在Solver约束中添加“$G$2:$J$4 整数”。保存模型对于经常要修改数据重新求解的问题可以使用Solver的“保存模型”功能将参数设置保存在一片单元格中以后通过“加载模型”快速恢复。敏感性报告求解后生成敏感性报告可以查看影子价格对偶价格即产量或销量每增加一个单位总成本的变化量这对于商务决策非常有价值。6.2 使用Python PuLP库求解对于更复杂、规模更大或需要集成到自动化流程的问题编程求解是更优选择。PuLP是Python中一个用户友好的线性规划建模库。import pulp # 定义问题最小化总成本 prob pulp.LpProblem(Transportation_Problem, pulp.LpMinimize) # 定义产地和销地 plants [A1, A2, A3] markets [B1, B2, B3, B4] # 供应量和需求量 supply {A1: 7, A2: 4, A3: 9} demand {B1: 3, B2: 6, B3: 5, B4: 6} # 运价表 (字典的字典) costs { A1: {B1: 3, B2: 11, B3: 3, B4: 10}, A2: {B1: 1, B2: 9, B3: 2, B4: 8}, A3: {B1: 7, B2: 4, B3: 10, B4: 5} } # 定义决策变量字典 routes [(i, j) for i in plants for j in markets] vars pulp.LpVariable.dicts(Route, (plants, markets), lowBound0, catContinuous) # 定义目标函数 prob pulp.lpSum([vars[i][j] * costs[i][j] for (i, j) in routes]), Total_Transportation_Cost # 添加供应约束 for i in plants: prob pulp.lpSum([vars[i][j] for j in markets]) supply[i], fSupply_Constraint_{i} # 添加需求约束 for j in markets: prob pulp.lpSum([vars[i][j] for i in plants]) demand[j], fDemand_Constraint_{j} # 求解问题 prob.solve(pulp.PULP_CBC_CMD(msgFalse)) # 使用CBC求解器关闭求解信息 # 打印结果 print(fStatus: {pulp.LpStatus[prob.status]}) print(fTotal Cost {pulp.value(prob.objective)}\n) print(Optimal Transportation Plan:) for i in plants: for j in markets: if vars[i][j].varValue 0: print(f{i} - {j}: {vars[i][j].varValue} units)运行这段代码它会输出与我们在例题1中手工计算一致的最优解和总成本85。编程求解心得灵活性用代码建模可以轻松处理不平衡问题修改supply/demand字典、最大化问题将LpMinimize改为LpMaximize并相应修改costs为利润、禁止路线将对应costs[i][j]设为一个很大的数如1e9。扩展性中转问题虽然建模复杂但用代码构建扩大的产、销、运价字典比手工画表更不易出错。验证工具当你手工求解一个复杂问题后可以用这样一段简单的代码快速验证答案的正确性这是提高学习效率的利器。从手工推演到软件求解我们完成了对运输问题从理论认知到实践落地的闭环。手工计算锻炼的是对模型机理的深刻理解而软件工具则是解决实际规模问题的生产力。两者结合才能真正掌握这个运筹学中的经典模型。