本文介绍如何将经典运输问题扩展为考虑6吨卡车整数装载限制的混合整数线性规划（milp）问题，并利用分支定界法自动求解最优运输方案——核心是引入整数“卡车数量”变量，通过容量耦合约束将连续运量与离散车辆调度统一建模。
本文介绍如何将经典运输问题扩展为考虑6吨卡车整数装载限制的混合整数线性规划（milp）问题，并利用分支定界法自动求解最优运输方案——核心是引入整数“卡车数量”变量，通过容量耦合约束将连续运量与离散车辆调度统一建模。
在标准运输问题中，决策变量通常表示从供应点 $i$ 到需求点 $j$ 的连续运量 $x{ij}$，目标是最小化总运费 $\sum c{ij} x{ij}$。但当实际物流受限于固定载重（如6吨卡车）时，运费不再与运量呈严格线性关系：运送10吨货物需2辆卡车（即使仅超载4吨），对应成本为 $2 \times 6 \times c{ij} = 12c{ij}$，而非 $10c{ij}$。这种“阶梯式成本”本质是非线性的，但可通过引入整数变量 + 线性约束精确转化为混合整数线性规划（MILP）问题，从而由现代求解器（如Gurobi、CBC、SCIP）内置的分支定界（Branch-and-Bound）算法高效求解。
关键建模思想如下：
- 定义连续变量 flow[i][j] 表示实际运输吨数（$\geq 0$）；
- 定义整数变量 trucks[i][j] 表示该路径上启用的6吨卡车数量（$\in \mathbb{Z}_+$）；
- 添加容量耦合约束：flow[i][j] ≤ trucks[i][j] × 6，确保运量不超出卡车总承载能力；
- 目标函数改为最小化总卡车成本：$\min \sum{i,j} (6 \times c{ij}) \times \text{trucks}[i][j]$；
- 保留原始供需约束：各供应点总运量 ≤ 供应量，各需求点总运量 = 需求量（严格满足，避免短缺）。
以下为使用 PuLP 库实现的完整可运行代码（兼容性强，无需商业许可证）：
import pandas as pd
import pulp
truck_capacity = 6
suppliers = pd.RangeIndex(name='supplier', stop=4)
consumers = pd.RangeIndex(name='consumer', stop=5)
# 数据定义（与问题一致）
supply = pd.Series(name='supply', index=suppliers, data=[17, 8, 10, 9])
demand = pd.Series(name='demand', index=consumers, data=[6, 15, 7, 8, 8])
price_per_tonne = pd.DataFrame(
index=suppliers, columns=consumers,
data=[
[10, 8, 5, 9, 16],
[ 4, 3, 4, 11, 12],
[ 5, 10, 29, 7, 6],
[ 9, 2, 4, 1, 3],
]
).stack()
price_per_tonne.name = 'price'
# 决策变量：连续运量 & 整数卡车数
flow = pd.DataFrame(
index=suppliers, columns=consumers,
data=pulp.LpVariable.matrix('flow_s%d_c%d', cat=pulp.LpContinuous, lowBound=0, indices=(suppliers, consumers))
).stack()
flow.name = 'flow'
trucks = pd.DataFrame(
index=suppliers, columns=consumers,
data=pulp.LpVariable.matrix('trucks_s%d_c%d', cat=pulp.LpInteger, lowBound=0, indices=(suppliers, consumers))
).stack()
trucks.name = 'trucks'
# 目标：最小化总卡车运费（6吨 × 单位吨价 × 卡车数）
price = truck_capacity * pulp.lpDot(price_per_tonne, trucks)
prob = pulp.LpProblem("transportation", pulp.LpMinimize)
prob.setObjective(price)
# 供应约束：每供应点总运量 ≤ 供应量
for s, group in flow.groupby('supplier'):
prob.addConstraint(pulp.lpSum(group) <= supply[s], f"supply_s{s}")
# 需求约束：每需求点总运量 = 需求量（严格满足）
for d, group in flow.groupby('consumer'):
prob.addConstraint(pulp.lpSum(group) == demand[d], f"demand_c{d}")
# 容量耦合约束：运量 ≤ 卡车数 × 单车容量
for (s, d), f_var in flow.items():
prob.addConstraint(f_var <= trucks[(s, d)] * truck_capacity, f"capacity_s{s}_c{d}")
# 求解
prob.solve(pulp.PULP_CBC_CMD(msg=False)) # 使用开源CBC求解器
assert prob.status == pulp.LpStatusOptimal, "No optimal solution found"
# 输出结果
print("Optimal total cost:", pulp.value(prob.objective))
print("\nFlow matrix (tonnes):")
print(flow.apply(pulp.value).unstack(level='consumer').round(1))
print("\nTruck usage matrix (count per route):")
print(trucks.apply(pulp.value).unstack(level='consumer').astype(int))运行后可得最优总成本为 276.0，对应卡车调度方案清晰显示每条路径启用的卡车数量（如 (0,1) 路径运6吨→1辆卡车；(0,3) 运6吨→1辆；(2,0) 运6吨→1辆等）。值得注意的是：
✅ 分支定界自动生效：PuLP调用CBC求解器时，会自动识别整数变量 trucks[i][j]，启动分支定界流程，在可行域中系统搜索整数最优解；
⚠️ 勿手动实现B&B：现代求解器已高度优化，用户只需正确建模（变量类型+约束逻辑），无需干预具体搜索策略；
? 验证可行性：所有需求被精确满足（如第1列需求15吨 = 6+6+3），且无供应超支（如供应点0共发出6+5+6=17吨）；
? 扩展提示：若需最小化卡车总数（而非运费），可将目标改为 min sum(trucks) 并添加权重；若存在空驶成本，可为 trucks[i][j] > 0 引入固定启运费。
综上，将运输问题升级为带车辆容量的MILP模型，是连接运筹理论与现实物流约束的关键一步——其本质不是修改算法，而是精准重构数学描述，让分支定界等通用技术得以发挥最大效力。
