本文介绍如何将经典运输问题扩展为考虑6吨卡车整数装载限制的混合整数线性规划（milp）问题，并利用分支定界法自动求解最优运输方案与卡车调度计划。
本文介绍如何将经典运输问题扩展为考虑6吨卡车整数装载限制的混合整数线性规划（milp）问题，并利用分支定界法自动求解最优运输方案与卡车调度计划。
在标准运输问题中，决策变量是连续的运量（如“从供应点1向需求点2运送10吨货物”），目标是最小化总运费（单位运价 × 运量）。但当实际物流受限于固定载重卡车（如6吨/车）时，运量不再自由可分——必须按整数车次调度，每车最多装6吨，且即使只运1吨也需占用1整车资源。这使问题本质从线性规划（LP）升级为混合整数线性规划（MILP），而分支定界（Branch-and-Bound）正是求解MILP的标准算法框架。
关键建模思想是：引入整数变量 trucks[i][j] 表示从供应点 i 到需求点 j 所需的卡车数量，并建立其与实际运量 flow[i][j] 的逻辑耦合关系：
- 每辆卡车最多运6吨 → 约束：flow[i][j] ≤ 6 × trucks[i][j]
- 运量非负且满足供需平衡 → 原始约束保留（但需求须严格等于，而非≥）
- 总成本变为：∑(i,j) (6 × cost[i][j] × trucks[i][j])（因每车满载6吨，单位车成本 = 6 × 单位吨价）
以下为完整可运行的 PuLP 实现（更易读、轻量，适合教学）：
import pandas as pd
import pulp
# 参数定义
truck_capacity = 6
suppliers = pd.RangeIndex(name='supplier', stop=4) # 4个供应点
consumers = pd.RangeIndex(name='consumer', stop=5) # 5个需求点
supply = pd.Series([17, 8, 10, 9], index=suppliers, name='supply')
demand = pd.Series([6, 15, 7, 8, 8], index=consumers, name='demand')
# 单位吨运费矩阵（4×5）
price_per_tonne = pd.DataFrame([
[10, 8, 5, 9, 16],
[ 4, 3, 4, 11, 12],
[ 5, 10, 29, 7, 6],
[ 9, 2, 4, 1, 3]
], index=suppliers, columns=consumers)
# 决策变量：连续运量 flow[i][j] ≥ 0；整数卡车数 trucks[i][j] ∈ ℤ⁺
flow = pd.DataFrame(
pulp.LpVariable.matrix('flow_s%d_c%d', (suppliers, consumers), cat='Continuous', lowBound=0)
).stack().rename('flow')
trucks = pd.DataFrame(
pulp.LpVariable.matrix('trucks_s%d_c%d', (suppliers, consumers), cat='Integer', lowBound=0)
).stack().rename('trucks')
# 目标函数：最小化总卡车成本（每车运6吨，故单辆车成本 = 6 × 单位吨价）
objective = pulp.lpDot(price_per_tonne.stack() * truck_capacity, trucks)
prob = pulp.LpProblem("Transportation_with_Trucks", pulp.LpMinimize)
prob.setObjective(objective)
# 约束1：各供应点总运量 ≤ 其供应量
for i in suppliers:
prob.addConstraint(pulp.lpSum(flow.xs(i, level='supplier')) <p>运行后得到最优解：<strong>总成本276元</strong>，对应卡车调度如下（行=供应点，列=需求点）：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/ai/2006" title="AI大学堂"><img
src="https://img.php.cn/upload/ai_manual/000/000/000/175679966594209.png" alt="AI大学堂" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/ai/2006" title="AI大学堂" class="overflowclass">AI大学堂</a>
<p class="overflowclass">一个面向AI学习与应用实践的在线平台，提供人工智能相关课程和学习资源，帮助用户了解和掌握AI工具及技术。</p>
</div>
<a rel="nofollow" href="/ai/2006" title="AI大学堂" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div><pre class="brush:php;toolbar:false;">consumer 0 1 2 3 4
supplier
0 0 1 1 1 0
1 0 1 1 0 0
2 1 0 0 0 1
3 0 1 0 1 1对应运量矩阵（吨）：
consumer 0 1 2 3 4 supplier 0 0.0 6.0 5.0 6.0 0.0 1 0.0 6.0 2.0 0.0 0.0 2 6.0 0.0 0.0 0.0 4.0 3 0.0 3.0 0.0 2.0 4.0
⚠️ 注意事项与最佳实践：
- 不要手动实现分支定界：现代求解器（如CBC、Gurobi、CPLEX）已内置高效B&B引擎，用户只需正确建模为MILP即可；
- 避免“四舍五入”启发式：对LP松弛解直接向上取整（如10吨→2车）通常非最优，本例中原始LP解成本为245元，但强制整数化后实际最小成本为276元；
- 约束紧致性：flow[i][j] ≤ 6 × trucks[i][j] 是关键，它确保卡车数足够支撑运量，同时不引入冗余变量；
- 扩展性提示：若需考虑不同车型（如6吨/10吨混用），可引入多类型整数变量及互斥约束，仍属MILP范畴。
该建模范式可无缝迁移至Gurobi等商业求解器——只需将 pulp.LpVariable 替换为 gp.Model.addVar，其余逻辑完全一致。掌握此方法，即掌握了将现实物流约束（车辆、集装箱、航班舱位等）嵌入优化模型的核心能力。
