Python求解运输问题：从数学模型到代码实现与优化

1. 项目概述：从实际问题到数学模型

运输问题，听起来像是物流公司调度卡车时才会遇到的麻烦事。但如果你仔细想想，这其实是一个无处不在的数学幽灵。从工厂向多个仓库配送产品，从多个发电厂向不同城市输送电力，甚至是在云计算中，如何将计算任务分配到不同的服务器节点以最小化延迟和成本，其底层逻辑都指向同一个数学模型——运输问题。它本质上是一类特殊的线性规划问题，核心目标是在满足供需约束的前提下，找到总运输成本最低的调度方案。

我第一次在数学建模比赛中接触它，是在一个关于区域水资源调配的题目里。题目给了几个水源地、几个需求城市，以及各自的供应量、需求量，还有每单位水从A地运到B地的成本。当时的第一反应是：这不就是个简单的分配问题吗？手动试试看？结果稍微一复杂，比如5个供应点、8个需求点，各种组合方案就多到让人头皮发麻，根本找不到最优的那个。这时才深刻体会到，为什么我们需要数学建模和编程工具。它把我们从繁琐的试错中解放出来，让我们能专注于问题本身的结构和优化逻辑。

用Python来实现运输问题的求解，对于学生、数据分析师甚至运营人员来说，都是一个极具价值的技能。它不仅仅是调用一个库那么简单，而是理解如何将一个模糊的实际业务需求，转化为严谨的数学表达式，再通过代码让计算机自动求出最优解。这个过程锻炼的是结构化思维和问题解决能力。本文将带你一步步拆解运输问题，并用Python的pulp和ortools这两个强大的库来实现求解，同时分享一些我在实际建模和编码中踩过的坑和总结的技巧。

2. 运输问题的数学模型深度解析

2.1 问题定义与核心要素

运输问题可以抽象为这样一个场景：我们有m个供应点（产地、工厂、仓库等）和n个需求点（销地、市场、客户等）。

• 供应量：每个供应点i有一个固定的供应量（或产量）a_i（i = 1, 2, ..., m）。
• 需求量：每个需求点j有一个固定的需求量b_j（j = 1, 2, ..., n）。
• 单位运价：从供应点i运输一个单位货物到需求点j的成本是c_ij。这通常构成一个m x n的运价矩阵。
• 决策变量：我们需要决定从每个供应点i运多少货物到每个需求点j，记作x_ij。

这里有一个重要的前提：总供应量等于总需求量，即Σa_i = Σb_j。这被称为“产销平衡”的运输问题。这是最标准、最简洁的模型。如果不等，则需要先通过引入“虚拟”供应点或需求点，将其转化为平衡问题，这是建模中第一个关键技巧。

注意：在实际比赛中，题目数据往往直接给出平衡条件。但拿到真实业务数据时，第一步永远是检查总供给和总需求。如果供大于求，意味着有货物运不出去，我们需要增加一个“虚拟需求点”（可理解为库存或销毁），其需求量为多余供给，运价通常设为0（库存成本）或一个惩罚值。如果供不应求，则增加一个“虚拟供应点”，其供应量为短缺量，运价设为0（ unmet demand， 可能意味着缺货）或一个极高的惩罚成本（表示不允许缺货）。这个处理是后续正确建模的基础。

2.2 数学模型构建

基于以上要素，我们可以建立运输问题的线性规划模型。

目标函数（最小化总成本）：我们的目标是让总运输成本最低。总成本就是所有运输路线上的运量乘以单位运价之和。Min Z = Σ_i Σ_j c_ij * x_ij（对所有 i=1..m， j=1..n 求和）

约束条件：

1. 供应约束：从每个供应点i运出的货物总量不能超过其供应量a_i。Σ_j x_ij <= a_i（对每个供应点 i） 在平衡问题中，通常取等号=，即所有货物必须运出。
2. 需求约束：运到每个需求点j的货物总量必须满足其需求量b_j。Σ_i x_ij = b_j（对每个需求点 j）
3. 非负约束：运输量不能为负数。x_ij >= 0

这个模型非常简洁优美。它之所以特殊，是因为其约束矩阵的系数全是0或1，并且具有非常规整的结构，这使得存在比单纯形法更高效的专门算法，如表上作业法（包括最小元素法、伏格尔法求初始解，以及位势法检验和闭回路调整）。不过，在Python中，我们通常不手动实现这些算法，而是将其视为普通线性规划问题，交给求解器处理，这样更通用、更不容易出错。

2.3 模型变体与扩展

标准的运输问题只是起点，实际问题往往更复杂：

• 不平衡问题：如前所述，通过虚拟点处理。
• 转运问题：货物可以从A地运到B地，再中转到C地。这需要引入中间节点作为“既是供应点又是需求点”，并定义节点间的运价。
• 容量限制：某条具体路线i->j有最大运输容量限制，即增加约束x_ij <= U_ij。
• 固定成本：除了与运量成比例的可变成本c_ij*x_ij，如果开启一条运输路线，还需要支付一笔固定费用（如车辆调度费）。这会将问题引入整数规划（0-1变量）的领域，复杂度大大增加。
• 多商品运输：同时运输多种不同类型的货物，它们可能共享运力，需要更复杂的约束。

在数学建模竞赛中，能清晰地将一个复杂问题识别并简化为标准的运输问题或其接近的变体，往往就成功了一半。例如，2019年国赛C题“机场的出租车问题”，其中一部分可以抽象为将降落的航班（供应点，供应量为下客人数）匹配到不同蓄车池/排队区域（需求点，需求为车辆容量），目标是最短总行驶距离或最短平均等待时间，这就是一个典型的运输问题建模思路。

3. Python求解工具选型与核心原理

3.1 为什么选择pulp和ortools？

Python中求解线性规划问题有多种选择，对于运输问题这类标准LP，我主要推荐两个库：PuLP和OR-Tools。它们各有优劣。

PuLP： 轻量级建模首选PuLP是一个开源的线性规划建模库，它本身不包含求解器，而是作为一个“外壳”，可以调用多种后端求解器（如CBC、GLPK、Gurobi、CPLEX等）。它的API非常Pythonic，直观易懂，特别适合教学、快速原型开发和中小规模问题。

• 优点：安装简单（pip install pulp），语法简洁，易于学习和调试。对于数学建模竞赛和大多数课堂作业，其默认的CBC求解器完全够用。
• 缺点：处理超大规模问题（变量数十万以上）时，如果使用开源求解器，性能可能不如商业求解器。但这对运输问题建模来说极少遇到。

OR-Tools： 谷歌出品，性能强劲OR-Tools是Google开发的开源优化工具套件，功能极其强大，涵盖了线性规划、整数规划、约束规划、车辆路径问题等。它的线性规划求解器同样高效。

• 优点：求解性能通常优于PuLP默认的CBC，文档和社区支持良好。如果你的问题后续可能扩展到更复杂的优化类型（如VRP），用OR-Tools可以保持技术栈统一。
• 缺点：安装包稍大，API相对于PuLP稍显冗长，但结构清晰。

对于初学者和大多数数学建模场景，我强烈建议从PuLP开始。它让你更专注于模型本身，而不是复杂的求解器配置。下文将主要以PuLP为例进行详解，并在最后给出OR-Tools的等效实现作为对比。

3.2 求解器背后的黑盒：单纯形法与内点法

当我们调用prob.solve()时，背后发生了什么？理解一点基本原理有助于调试和解释结果。

• 单纯形法：这是求解线性规划最经典的算法。它沿着可行域的顶点移动，每次移动都让目标函数值改善，直到找到最优顶点。运输问题的特殊结构使得单纯形法在其上运行效率很高（即表上作业法）。PuLP默认的CBC求解器主要使用单纯形法或其变种。
• 内点法：另一种主流算法，它不是沿着边界移动，而是从可行域内部穿过，直接逼近最优解。对于某些超大规模稀疏问题，内点法可能更有优势。

作为使用者，我们通常不需要指定算法，求解器会自动选择。但知道这些概念后，当你遇到“求解器无可行解”或“无界解”的报错时，就能明白这不是代码语法错误，而是你的模型约束条件可能存在矛盾（无可行域）或缺少限制（目标函数值可以无限优化）。

4. 使用PuLP求解标准运输问题：完整代码实现与逐行解读

让我们用一个经典案例来贯穿整个实现过程。假设有3个工厂（F1， F2， F3）向4个仓库（W1， W2， W3， W4）供应货物。数据如下：

• 供应量：a = [300, 400, 500]（单位：吨）
• 需求量：b = [250, 350, 400, 200]（单位：吨）
• 单位运价表c_ij（单位：元/吨）：

首先检查是否平衡：总供应=300+400+500=1200，总需求=250+350+400+200=1200。完美平衡。

4.1 步骤一：导入库与定义问题

import pulp # 1. 定义问题， ‘LpProblem’ 是PuLP的核心类 # 参数：问题名称， 目标函数方向（LpMinimize 或 LpMaximize）， 指定求解器（默认CBC） prob = pulp.LpProblem('Transportation_Problem', pulp.LpMinimize) # 2. 定义下标集合 factories = ['F1', 'F2', 'F3'] warehouses = ['W1', 'W2', 'W3', 'W4'] # 3. 定义供应量和需求量字典（用下标作为key，便于后续引用） supply = {'F1': 300, 'F2': 400, 'F3': 500} demand = {'W1': 250, 'W2': 350, 'W3': 400, 'W4': 200} # 4. 定义运价表（嵌套字典）， costs[factory][warehouse] costs = { 'F1': {'W1': 4, 'W2': 5, 'W3': 6, 'W4': 8}, 'F2': {'W1': 7, 'W2': 4, 'W3': 3, 'W4': 5}, 'F3': {'W1': 2, 'W2': 6, 'W3': 5, 'W4': 7} }

实操心得：使用字典（dict）来存储数据，比用列表（list）并通过索引访问要直观得多，尤其是在调试和查看结果时。costs['F1']['W3']远比costs[0][2]更容易理解。这是提高代码可读性和可维护性的一个小技巧。

4.2 步骤二：创建决策变量

决策变量x_ij表示从工厂i运到仓库j的数量。

# 5. 创建决策变量字典 # LpVariable.dicts 用于批量创建变量 # 参数：变量名前缀， 下标组合列表（(i， j)）， 下界（lowBound）， 上界（upBound）， 变量类型（LpContinuous， LpInteger， LpBinary） routes = [(i, j) for i in factories for j in warehouses] # 生成所有可能的路线组合 # 变量名格式为 ‘Route_F1_W1‘， 下界为0， 上界不限（None）， 连续变量 x = pulp.LpVariable.dicts('Route', (factories, warehouses), lowBound=0, cat='Continuous')

这里x是一个字典，你可以通过x['F1']['W1']来访问代表从F1到W1运量的变量对象。

4.3 步骤三：构建目标函数

目标是最小化总成本：Σ_i Σ_j c_ij * x_ij。

# 6. 构建目标函数 prob += pulp.lpSum([x[i][j] * costs[i][j] for i in factories for j in warehouses]), "Total_Transportation_Cost"

pulp.lpSum()是PuLP提供的求和函数，比Python内置的sum()更高效，专门用于构建线性表达式。prob +=是向问题中添加目标函数或约束的语法。

4.4 步骤四：添加约束条件

添加供应约束和需求约束。

# 7. 添加供应约束（对每个工厂，运出总量等于其供应量） for i in factories: prob += pulp.lpSum([x[i][j] for j in warehouses]) == supply[i], f"Supply_Constraint_{i}" # 8. 添加需求约束（对每个仓库，运入总量等于其需求量） for j in warehouses: prob += pulp.lpSum([x[i][j] for i in factories]) == demand[j], f"Demand_Constraint_{j}"

注意约束条件后的字符串（如“Supply_Constraint_F1”），这是约束的名称，在输出模型或调试时非常有用，能快速定位是哪个约束出了问题。

4.5 步骤五：求解与结果输出

# 9. 求解问题 prob.solve() # 10. 打印求解状态 print(f"Status: {pulp.LpStatus[prob.status]}") # 11. 打印最优目标函数值 print(f"Optimal Total Cost: {pulp.value(prob.objective)}") # 12. 打印每条路线的最优运输量 print("\nOptimal Transportation Plan:") for i in factories: for j in warehouses: if x[i][j].varValue > 0: # 只打印运量大于0的路线，使结果更清晰 print(f"From {i} to {j}: {x[i][j].varValue} tons")

运行这段代码，你会得到类似下面的输出：

Status: Optimal Optimal Total Cost: 4850.0 Optimal Transportation Plan: From F1 to W2: 300.0 tons From F2 to W3: 400.0 tons From F3 to W1: 250.0 tons From F3 to W3: 150.0 tons From F3 to W4: 100.0 tons

解读：最优总成本为4850元。具体方案是：F1的300吨全部运给W2；F2的400吨全部运给W3；F3的500吨则拆分，250吨给W1，150吨给W3，100吨给W4。这个方案完美满足了所有供需约束，并且总成本最低。

4.6 步骤六：结果分析与可视化（进阶）

为了更直观，我们可以将结果用pandasDataFrame展示，甚至用matplotlib画一个简单的流量图。

import pandas as pd # 将结果整理成DataFrame results = [] for i in factories: for j in warehouses: val = x[i][j].varValue if val > 0: results.append([i, j, val, costs[i][j], val * costs[i][j]]) df_result = pd.DataFrame(results, columns=['From', 'To', 'Quantity', 'Unit_Cost', 'Total_Cost']) print(df_result) print(f"\nSum of Total Cost: {df_result['Total_Cost'].sum()}")

这会产生一个清晰的表格，包含每条活跃路线的明细成本。

5. 处理不平衡问题与模型扩展

5.1 供大于求的情况

假设工厂F3产能扩大，供应量变为[300, 400, 600]，总供应1300 > 总需求1200。我们需要增加一个虚拟仓库W_dummy，其需求量为过剩的100吨。关键是如何设定到虚拟仓库的运价？

• 如果过剩产品可以零成本库存：则运价设为0。这意味着多余的100吨会“运往”虚拟仓库，即留在产地不作为有效供应，在解中体现为某个工厂的运出量小于其供应量。
• 如果过剩产品有库存成本：则运价设为单位库存成本。
• 如果过剩产品必须销毁且有处理费：则运价设为处理费。

代码调整如下：

# 修改供应量 supply = {'F1': 300, 'F2': 400, 'F3': 600} # F3多了100 demand = {'W1': 250, 'W2': 350, 'W3': 400, 'W4': 200} # 增加虚拟仓库 warehouses.append('W_dummy') demand['W_dummy'] = 100 # 总供应1300 - 总需求1200 = 100 # 设定到虚拟仓库的运价（假设库存成本为1元/吨） for i in factories: costs[i]['W_dummy'] = 1 # 然后重新定义变量、目标函数和约束（注意需求约束对虚拟仓库也是等于） # ... (后续建模代码与标准问题完全相同)

求解后，你会发现有一部分运量指向了W_dummy，这部分就是“未运出”的库存。

5.2 增加运输路线容量限制

现实中的道路或车队可能有运力上限。假设我们从F2到W3的路线最大运力为200吨。我们只需要在标准模型上增加一个约束：

# 在添加完供应需求约束后，添加容量约束 prob += x['F2']['W3'] <= 200, "Capacity_Constraint_F2_W3"

重新求解，求解器会考虑这个额外限制，方案可能会改变，总成本通常会上升。

6. 使用OR-Tools实现对比

为了完整性，这里给出使用OR-Tools的线性规划求解器实现同一标准问题的代码。你会发现其思路一致，但API风格不同。

from ortools.linear_solver import pywraplp def solve_transportation_with_ortools(): # 创建求解器实例，使用GLOP（OR-Tools的线性规划求解器） solver = pywraplp.Solver.CreateSolver('GLOP') if not solver: return # 数据定义（与PuLP示例相同） factories = ['F1', 'F2', 'F3'] warehouses = ['W1', 'W2', 'W3', 'W4'] supply = {'F1': 300, 'F2': 400, 'F3': 500} demand = {'W1': 250, 'W2': 350, 'W3': 400, 'W4': 200} costs = { 'F1': {'W1': 4, 'W2': 5, 'W3': 6, 'W4': 8}, 'F2': {'W1': 7, 'W2': 4, 'W3': 3, 'W4': 5}, 'F3': {'W1': 2, 'W2': 6, 'W3': 5, 'W4': 7} } # 创建变量字典 x = {} for i in factories: for j in warehouses: x[i, j] = solver.NumVar(0, solver.infinity(), f'x_{i}_{j}') # 添加供应约束 for i in factories: constraint = solver.Constraint(supply[i], supply[i]) # 等式约束，下界=上界 for j in warehouses: constraint.SetCoefficient(x[i, j], 1) # 添加需求约束 for j in warehouses: constraint = solver.Constraint(demand[j], demand[j]) for i in factories: constraint.SetCoefficient(x[i, j], 1) # 设置目标函数 objective = solver.Objective() for i in factories: for j in warehouses: objective.SetCoefficient(x[i, j], costs[i][j]) objective.SetMinimization() # 求解 status = solver.Solve() # 输出结果 if status == pywraplp.Solver.OPTIMAL: print('Solution found.') print(f'Optimal Total Cost: {objective.Value()}') total_cost = 0 for i in factories: for j in warehouses: if x[i, j].solution_value() > 0: print(f'{i} -> {j}: {x[i， j].solution_value()} tons') else: print('No optimal solution found.') solve_transportation_with_ortools()

OR-Tools的代码更显“过程式”，需要显式地创建约束对象并设置系数。对于简单模型，PuLP的简洁性优势明显；但对于复杂模型或需要精细控制求解过程时，OR-Tools提供了更底层的接口。

7. 常见问题、调试技巧与实战心得

7.1 求解状态解读与错误排查

调用prob.solve()后，pulp.LpStatus[prob.status]可能返回以下几种状态：

• Optimal：完美，找到了最优解。
• Infeasible：模型无可行解。这是新手最常遇到的问题。
  • 检查1：供需是否平衡？如果不平衡，是否正确地添加了虚拟点？虚拟点的运价设置是否合理（例如，供不应求时，虚拟供应点到真实需求点的运价如果为0，求解器可能会把全部需求分配给零成本的虚拟点，导致真实供应点不发货，这不符合业务逻辑，此时应设为极高的惩罚成本M）。
  • 检查2：约束是否矛盾？例如，某个需求点的需求量大于所有供应点的供应量之和。
  • 检查3：是否有不必要的严格等式约束？尝试将一些==约束放松为<=或>=看看。
• Unbounded：目标函数值可以无限优化（如无限小）。这通常意味着模型缺少必要的约束，比如只规定了供应约束<=，没有规定需求约束，那么求解器可以通过不运输任何货物来让总成本达到负无穷（如果目标是最小化）。
• Not Solved：求解尚未进行或中断。

踩坑记录：在一次建模中，我错误地将一个本应是“小于等于”的产能约束写成了“等于”，同时需求又有硬性要求，导致模型无解。调试时，我使用了prob.writeLP(“model_debug.lp”)将模型输出到一个文本文件，人工检查每一个约束，才发现了这个笔误。这个writeLP方法是非常强大的调试工具。

7.2 处理大规模问题与性能优化

当供应点和需求点成百上千时，变量数量会呈平方增长（m*n）。这时需要注意：

1. 使用稀疏数据结构：如果运价矩阵中很多c_ij是无穷大（表示不可达），在构建目标函数和约束时，可以只遍历有效的(i, j)对，而不是全部组合。
2. 选择更快的求解器：PuLP可以安装并调用商业求解器如Gurobi、CPLEX，它们对于大规模LP问题速度极快。在学术环境下，这些求解器通常有免费许可。
3. 模型简化：思考问题是否具有可聚合的特性。例如，如果多个需求点地理位置接近，是否可以合并为一个“区域”需求点？

7.3 在数学建模竞赛中的应用策略

1. 识别问题：看到“分配”、“调运”、“最小化成本/距离/时间”等关键词，且资源有供给方和需求方，就要联想到运输问题。
2. 大胆假设，小心建模：竞赛题目往往做了大量简化。你需要明确写出你的假设（如“假设单位运价与运量成正比”、“忽略固定成本”等），然后在此简化模型上构建清晰的数学模型。
3. 灵敏度分析：求出最优解后，可以分析一些参数变化对结果的影响。例如，使用PuLP可以计算影子价格（对偶变量），它代表了某个供应量或需求量增加一个单位时，总成本的变化量。这能为决策提供更深层次的洞察。

   # 打印供应约束的影子价格（边际成本） for name, constraint in prob.constraints.items(): if name.startswith('Supply_Constraint'): print(f"{name}: Shadow Price = {constraint.pi}")

4. 可视化结果：将最优运输方案用网络流图或桑基图绘制出来，能为论文增色不少。可以使用networkx和matplotlib或plotly库。

7.4 从运输问题到更复杂的模型

运输问题是网络流问题中最基础的一种。掌握了它，就为学习更复杂的模型打下了坚实基础：

• 指派问题：可以看作是一种特殊的运输问题，其中供应量和需求量都是1，并且m=n，决策变量x_ij是0-1变量（表示是否指派）。
• 转运问题：如前所述，引入中间节点。
• 多商品流问题：每种商品有自己的供需，但共享网络容量。
• 设施选址问题：在运输问题的基础上，增加“是否在某个地点建厂”的0-1决策变量，变成一个混合整数规划问题。

我个人在多次实践中体会到，把运输问题的模型和代码模板化、工具化，能极大提升解决类似优化问题的效率。我通常会准备一个基础的Python脚本，里面包含了数据读取、模型构建、求解和结果导出的函数。遇到新问题时，只需要修改数据输入和少量的约束条件，就能快速得到解决方案。这种“建模即编程”的能力，正是数学建模竞赛和实际工作中所看重的核心技能。最后一个小建议：多读优秀论文，看看别人是如何将千变万化的实际问题，抽象成诸如运输问题这样经典的数学模型，这种化繁为简的功力，需要大量的练习和思考才能获得。