3. 容量约束的数学表达与处理技巧

容量约束描述的是“资源供给上限”与“任务占用需求”之间的关系。在资源分配问题中，它通常表现为某类资源在某一时段内被占用的总量不得超过其可用量。设资源 r 的容量为 C_r，任务 i 占用资源 r 的量为 a_ir，决策变量 x_i 表示任务是否被选中（0-1 变量），则最基础的容量约束可写为：

∑_i a_ir · x_i ≤ C_r，∀r

这一形式是线性的，可以直接进入混合整数规划（MIP）模型。真正的难点不在于“写出来”，而在于当容量约束带有条件、分段、逻辑组合或非线性特征时，如何把它转化为求解器能够高效处理的线性形式。本节围绕线性化方法、大M法、指示变量与逻辑约束建模展开，并落到 MIP 的实现细节上。

一、线性化的基本思路

线性化的核心是：用辅助变量和线性等式/不等式，替代乘积项、分段函数或“如果……则……”的条件结构。常见情形有三类。

1. 乘积项线性化。当出现 0-1 变量 x 与连续变量 y 的乘积 z = x·y，且 y 有上下界 [L, U] 时，可引入连续变量 z 并添加四条约束：

z ≤ U·x
z ≥ L·x
z ≤ y - L·(1 - x)
z ≥ y - U·(1 - x)

当 x=0 时，前两条迫使 z=0；当 x=1 时，后两条迫使 z=y。这样就把非线性乘积转成了线性约束，代价是引入一个辅助变量和四条不等式。

2. 分段容量线性化。若资源消耗随分配量呈阶梯变化（例如前 100 单位单价低、超出部分单价高），可用 SOS2（特殊有序集）或分段线性函数表达。以两段为例，设分界点 b₁，引入权重变量 λ₀、λ₁、λ₂，满足 λ₀+λ₁+λ₂=1，且至多两个相邻 λ 非零，则分配量与成本均可写成 λ 的线性组合。

3. 绝对值与最大值的线性化。容量偏差常以 |占用−容量| 度量，可通过引入正负偏差变量 d⁺、d⁻，令偏差 = d⁺ − d⁻，且两者均非负，从而把绝对值约束转为线性约束。

二、大M法与指示变量

大M法用于表达“条件成立时才生效”的约束。典型场景是：只有当任务 i 被选中（x_i=1）时，它才占用资源；未选中时不占用。若直接写 ∑a_irx_i ≤ C_r，在 x_i=0 时自然不占用，无需大M。大M真正发挥作用的是“互斥”“开关”“固定成本”一类逻辑。

例如，设备要么运行要么停机，运行时占用容量 q，停机时占用为 0，且运行状态由 0-1 变量 u 表示。若还需表达“运行则至少产出 P_min”，可写：

P ≥ P_min · u
P ≤ P_max · u

这里 P_max 起到了“上界”的作用，本质上就是大M。更一般地，对于约束 f(x) ≤ b 仅在 u=1 时生效，可写成：

f(x) ≤ b + M·(1 - u)

当 u=1 时退化为原约束；当 u=0 时右端放大到 b+M，约束被“松弛”掉。M 的取值必须谨慎：太小会误删可行解，太大会导致松弛过松、数值不稳定、分支定界下界变差。工程上应取“该约束在变量上下界内可能达到的最大违反量”，而不是随意填一个大数。

三、逻辑约束建模

容量问题中经常出现“至多选 k 个”“要么 A 要么 B”“若选 A 则必选 B”等逻辑关系，它们都可以用 0-1 变量加线性不等式表达。

• 至多选 k 个：∑x_i ≤ k。
• 至少选 k 个：∑x_i ≥ k。
• 互斥（A、B 不能同时选）：x_A + x_B ≤ 1。
• 蕴含（选 A 则必选 B）：x_A ≤ x_B。
• 恰好选一个：∑x_i = 1。

当逻辑条件与容量耦合时，例如“若开启产线 A，则其占用容量不得超过预留额度 Q_A”，可写为 ∑a_ix_i ≤ Q_A·u_A，其中 u_A 为产线开启指示变量。这类“容量乘以指示变量”的结构，正是大M法与指示变量配合的典型用法。

四、MIP 中的实现要点

把上述模型交给求解器（如 Gurobi、CPLEX、COIN-OR CBC 或开源 PuLP/OR-Tools）时，需注意以下几点。第一，变量类型要明确：容量约束中的分配量通常是连续变量，选择/开启状态是 0-1 变量，二者不可混用。第二，系数与右端项尽量用整数或规整小数，避免因浮点误差导致可行性判断抖动。第三，优先使用求解器内置的指示约束（indicator constraint），它比手工大M更紧、数值更稳；若求解器不支持，再退回大M。第四，给出合理的变量上界，这既收紧 M，也帮助预处理。

下面给出一个可直接运行的最小示例（PuLP 风格伪代码），演示“两资源、三任务、带开启指示”的容量约束建模：

# 任务 i 占用资源 r 的量 a[i][r]，资源容量 C[r]
# x[i] ∈ {0,1} 是否执行任务；u[r] ∈ {0,1} 资源 r 是否启用
for r in resources:
    prob += lpSum(a[i][r] * x[i] for i in tasks) <= C[r] * u[r]
    prob += lpSum(a[i][r] * x[i] for i in tasks) >= L[r] * u[r]  # 启用则至少占用 L[r]
prob += lpSum(x[i] for i in tasks) <= 2   # 至多执行两个任务

其中 C[r] * u[r] 就是“容量乘以指示变量”的线性写法：资源未启用时右端为 0，任何占用都不允许；启用时恢复为真实容量。下界约束 L[r] * u[r] 则防止“启用了却几乎不用”的退化解，属于常见的建模加固技巧。

最后强调一个实践判断：模型能否高效求解，往往不取决于约束数量，而取决于松弛的紧致程度。大M过大、指示变量与容量耦合过松，都会让分支定界树膨胀。建模完成后，应检查 LP 松弛解与整数解的差距，若差距明显偏大，优先回头收紧 M 和变量上界，而不是急着调求解器参数。