本文介绍如何将经典运输问题扩展为考虑6吨卡车整数装载限制的混合整数线性规划（milp）问题，并利用分支定界法（由求解器自动执行）求得全局最优解，重点在于建模技巧与变量耦合设计。
本文介绍如何将经典运输问题扩展为考虑6吨卡车整数装载限制的混合整数线性规划（milp）问题，并利用分支定界法（由求解器自动执行）求得全局最优解，重点在于建模技巧与变量耦合设计。
在标准运输问题中，决策变量通常表示从供应点 $i$ 到需求点 $j$ 的连续运量 $x{ij}$，目标是最小化总运费 $\sum{i,j} c{ij} x{ij}$。但当实际物流受限于固定载重卡车（如本例中每辆卡车仅能运6吨）时，运费不再与运量呈严格线性关系——例如运10吨需2辆卡车，产生费用 $2 \times 6 \times c{ij} = 12c{ij}$，而非 $10c_{ij}$。此时，问题本质变为整数资源调度问题，必须引入整数变量显式刻画卡车使用数量。
核心建模思想是：解耦“运量”与“成本”，通过整数卡车变量 $t{ij} \in \mathbb{Z}+$ 控制成本，并用线性约束强制其与运量 $x_{ij}$ 逻辑一致。具体实现如下：
- 定义连续变量 $x_{ij} \geq 0$ 表示实际运输吨数；
- 定义整数变量 $t_{ij} \in {0,1,2,\dots}$ 表示从 $i$ 到 $j$ 调用的6吨卡车数量；
- 引入容量耦合约束：$x{ij} \leq 6 \cdot t{ij}$，确保卡车数量足以承载运量（注意：该约束不强制“满载”，但结合最小化目标，最优解天然趋向满载以节省卡车）；
- 目标函数改为：$\min \sum{i,j} (6 \cdot c{ij}) \cdot t_{ij}$，即每辆卡车固定承担6吨×单位运费的成本。
此模型构成典型的混合整数线性规划（MILP），其求解依赖分支定界（Branch-and-Bound）框架：求解器首先松弛 $t{ij}$ 为连续变量获得下界；随后对非整数 $t{ij}$ 进行分支（如 $t{12} \leq 1$ 或 $t{12} \geq 2$），递归求解子问题并剪枝，最终收敛至整数最优解。
以下为完整可运行代码（基于 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')
cost_matrix = 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 = 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吨 × 单位运费）
price_per_truck = cost_matrix.stack() * truck_capacity
prob = pulp.LpProblem("Transportation_with_Trucks", pulp.LpMinimize)
prob.setObjective(pulp.lpDot(price_per_truck, trucks))
# 约束：供应上限
for i in suppliers:
prob.addConstraint(pulp.lpSum(flow.xs(i, level='supplier')) <p><strong>关键注意事项：</strong> </p>
- ✅ 必须使用等式约束满足需求（== demand[j]），避免松弛导致欠运；供应端可用
- ⚠️ 避免强整数约束冗余：无需添加 $t{ij} \ge \lceil x{ij}/6 \rceil$ 类非线性约束，x_{ij} \le 6 t_{ij} 已足够，且保持模型线性。
- ? 验证解的合理性：检查每条路径是否满足 $x{ij} > 0 \Rightarrow t{ij} \ge 1$，且 $t{ij} = 0 \Rightarrow x{ij} = 0$（由约束和最优性保证）。
- ? 扩展性提示：若卡车有不同规格，可引入多类型整数变量及对应约束；若存在固定调度成本，需添加 $y{ij} \in {0,1}$ 指示是否启用该路线，并添加 $x{ij} \le M y{ij}$ 和 $t{ij} \le M y_{ij}$。
该方法将现实中的离散资源约束自然融入运筹模型，无需手动实现分支定界算法——现代求解器（如 Gurobi、CPLEX、CBC）均内置高效B&B引擎，用户只需专注正确建模，即可获得理论最优解。
