3. 混合整数规划建模要素

混合整数规划（MIP）之所以强大，在于它允许模型中同时存在两类决策：一类是可以取任意实数的连续变量，另一类是被限制为整数的离散变量。真正决定模型质量与求解效率的，往往不是目标函数写得多漂亮，而是这三件事处理得是否得当：连续量与整数量的分工、逻辑条件的线性化方式、以及指示变量与半连续变量的表达。本节围绕这三项建模要素展开，并给出可直接套用的写法。

一、连续变量与整数变量的混合建模

先明确两类变量的角色。连续变量通常表示数量、流量、时间、比例等可细分的量，例如生产量 x ≥ 0、运输量、投资金额；整数变量表示不可分割或只能取离散档位的决策，例如是否建厂、设备台数、班次数、车辆数。二者混合的典型结构是“整数决定结构，连续决定规模”：整数变量控制某条产线是否启用，连续变量表示启用后的产量。

这里最容易犯的错误是漏掉“联动约束”。若只用 y ∈ {0,1} 表示是否生产、x ≥ 0 表示产量，而不写任何连接，求解器会给出 y=0 但 x 很大的荒谬解。正确写法是引入产能上界 U，加上

x ≤ U · y
x ≥ 0,  y ∈ {0,1}

当 y=0 时强制 x=0；当 y=1 时 x 最多取到 U。这条约束同时承担了“逻辑开关”和“上界收紧”两个作用，是混合建模的基本功。需要提醒的是，U 应取紧上界（如该产线的实际最大产能），而不是随意取一个很大的数，否则线性松弛会过松，分支定界效率明显下降。

另一个常见结构是固定成本：启用即付一笔固定费用 f，再按单位变动成本 c 计费，目标中写 f·y + c·x。此时 y 与 x 的联动约束同样不可省，否则模型会“只付变动成本、不付固定成本”。

二、逻辑约束的线性化：大M法的正确用法

MIP 只能处理线性（或已线性化的）约束，而现实决策常带“如果……则……”的逻辑。大M法的本质，是用一个足够大的常数把“条件不成立时该约束自动失效”翻译成线性不等式。设 y ∈ {0,1}，要表达“若 y=1，则 a·x ≤ b”，标准写法为

a·x ≤ b + M · (1 − y)

当 y=1 时右端为 b，约束生效；当 y=0 时右端为 b+M，只要 M 足够大，该约束对可行域不再起作用。反向条件“若 y=1，则 a·x ≥ b”则写成 a·x ≥ b − M·(1−y)。若要表达两个条件二选一（析取），可引入两个 0-1 变量 y₁+y₂=1，分别配上两条大M约束。

举个可核算的例子：某设备开机才可生产，产量 x ∈ [0, 120]，工艺要求“开机时产量不低于 30”。条件为 x ≥ 30 − M(1−y)。取 M = 120 − 30 = 90 即可：y=1 时 x ≥ 30；y=0 时 x ≥ −60，对 x ≥ 0 无约束。若误取 M=1000，虽然逻辑仍正确，但松弛变松，求解时间通常上升。

三、指示变量与半连续变量建模

指示变量是把“某个逻辑状态”显式化为 0-1 变量，再由它去触发一组约束或成本。它与大M法是一体两面：指示变量是“因”，大M约束是“果”的线性表达。在多产品、多时段、多工厂模型中，指示变量常成组出现，例如 y_{i,t} 表示第 i 条线在第 t 期是否开机。

半连续变量是工程中极常见却常被忽略的一类：某量要么取 0，要么落在区间 [L, U] 内，不允许取 (0, L) 之间的小值。典型场景是最小起订量、最小批量、最小开机负荷。其标准建模为

L · y ≤ x ≤ U · y
x ≥ 0,  y ∈ {0,1}

当 y=0 时 x=0；当 y=1 时 L ≤ x ≤ U。注意这里 L·y ≤ x 与 x ≤ U·y 缺一不可：前者防止“开机却产量过小”，后者防止“关机却仍在生产”。若只写后者，模型会允许 y=1 时 x 取 0 到 L 之间的小值，最小批量约束形同虚设。

下面用一张结构图把三类要素的关系串起来：整数/指示变量作为“开关”，通过大M或联动约束去控制连续变量的可行区间，最终共同进入目标函数。

把三类要素落到一个可执行的小例子上：某车间有两条产线，产量 x₁, x₂，单线产能上界 120，最小批量 30，开机固定成本分别为 200 与 150，单位变动成本 3 与 4，总需求至少 100。模型可写为

min  200·y₁ + 150·y₂ + 3·x₁ + 4·x₂
s.t. x₁ + x₂ ≥ 100
     30·y₁ ≤ x₁ ≤ 120·y₁
     30·y₂ ≤ x₂ ≤ 120·y₂
     y₁, y₂ ∈ {0,1},  x₁, x₂ ≥ 0

求解后若得到 y₁=1, x₁=100, y₂=0, x₂=0，总成本为 200+300=500，说明单开一线即可满足需求且更经济；若需求提高到 150，则需两线同开或单线满产加另一线最小批量，此时半连续约束会强制第二条线至少生产 30，模型不会给出“第二条线只产 10”的不可行方案。判断结果是否合理，重点看三点：开机变量与产量是否同为零或同为正、产量是否落在 [L,U] 内、固定成本是否只在开机时计入。

最后强调一个易被忽视的实践细节：大M与半连续约束都会显著影响线性松弛的紧致程度。建模完成后，建议先查看松弛解中 0-1 变量是否大量取分数值、连续变量是否贴着上界，这往往是 M 过大或上界过松的信号。把 M 收紧、把 U 设为真实产能、把不必要的整数变量放宽为连续变量（若业务允许），通常比换求解器更能缩短求解时间。