2. 整数规划建模基础

整数规划建模的核心难点不在“列公式”，而在于把现实决策中的离散性、逻辑条件和数量关系准确翻译成变量、目标与约束。一个模型能否被求解器高效求解，往往在建模阶段就已决定。本节围绕决策变量的整数化表达、0-1变量与一般整数变量的分工、建模步骤以及常见陷阱展开，并用一个生产计划示例贯穿说明。

一、决策变量：先确定“决策什么”，再确定“取什么值”

决策变量是模型中由求解器决定的量，必须直接对应一个可执行的决策。例如“本周生产A产品多少件”对应一般整数变量 x_A ∈ ℤ₊；“是否启用2号产线”对应0-1变量 y₂ ∈ {0,1}。变量定义要写清三件事：含义、单位、取值范围。缺少单位会导致目标函数系数与约束右端项量纲混乱，例如把“小时”和“件”直接相加。

整数化表达的关键是区分“物理上不可分割”和“管理上要求取整”。前者如设备台数、车辆数、人员数，天然是整数；后者如产量，若允许小数则不应强行取整，否则会人为收紧可行域、抬高最优值。只有当业务规则明确“按整批生产”时，才把产量设为整数变量。

二、0-1变量与一般整数变量的使用场景

0-1变量擅长表达“是/否”型逻辑：是否建厂、是否选择某供应商、是否在某时段开机。它也是处理逻辑约束的桥梁，常用三种表达：互斥选择（y₁+y₂ ≤ 1）、条件约束（用大M法把“若y=1则x≤b”写成 x ≤ b + M(1−y)）、固定成本（目标中加入 c·y）。一般整数变量则用于计数型决策，如生产批量、分配人数、采购箱数，其取值上界应由产能、库存或需求给出，避免无界变量导致模型不可解或求解困难。

大M的取值是常见失分点。M应取该约束在业务上可能出现的最大差值，而不是随意取一个巨大数。M过大会削弱线性松弛的紧致性，使分支定界变慢；M过小则会误删可行解。例如“若开机则产量不超过产能”中，M取“产能上限减去最小产量”即可，而非10⁶。

三、目标函数与约束的整数化表达

目标函数通常写成线性加权和：max Σ p_ix_i − Σ f_jy_j，其中 p 为单位收益，f 为启用固定成本。约束分为资源约束（Σ a_ijx_i ≤ b_j）、需求约束（Σ x_i ≥ d）、逻辑约束（互斥、蕴含、覆盖）和变量界约束。整数化表达要求所有约束对变量的整数取值仍然成立，不能出现“x为整数时约束才等价”的隐性假设。

下面用一个示例说明变量与约束的配合。某车间可生产A、B两种产品，A每件耗工时2小时、收益30元；B每件耗工时3小时、收益40元；本周可用工时120小时。若启用1号产线（固定成本200元），A的产量上限为30件；若启用2号产线（固定成本150元），B的产量上限为25件。至少启用一条产线。设 x_A、x_B 为整数产量，y₁、y₂ 为0-1启用变量，则模型可写为：

max  30x_A + 40x_B − 200y_1 − 150y_2
s.t. 2x_A + 3x_B ≤ 120
     x_A ≤ 30y_1
     x_B ≤ 25y_2
     y_1 + y_2 ≥ 1
     x_A, x_B ∈ Z_+,  y_1, y_2 ∈ {0,1}

这里 x_A ≤ 30y₁ 同时表达了“未启用则不能生产”和“启用后产量不超过上限”两层含义，比额外写大M约束更紧致。该示例参数为教学假设，实际建模时应替换为真实工时、收益与产能数据。

四、建模步骤：从问题到可求解模型

建议按六步推进。第一步，明确决策周期与决策对象，列出所有需要“拍板”的量。第二步，为每个量选择变量类型并写明单位与上下界。第三步，写出目标，确认是最大化收益还是最小化成本，固定成本是否随启用发生。第四步，逐条列出资源、需求、逻辑约束，每条约束注明来源。第五步，检查量纲与符号方向，统一“≤”或“≥”的书写习惯。第六步，用小规模数据手算或代入验证，确认模型在边界情形下仍合理。

验证时不要只看最优值。应构造三个测试：全部变量取下界时约束是否成立；只启用一条产线时另一条产量是否被正确压为0；把某条约束右端项放宽后目标是否单调不变差。若出现“放宽约束反而变差”，说明符号或逻辑写反了。

五、常见陷阱与规避

第一类陷阱是“整数性滥用”。把本可连续的产量设为整数，会让模型规模膨胀且最优值偏高。规避方法是问一句：这个量在业务上真的不可分割吗？第二类是大M失控，前文已述，应优先用变量界与0-1变量直接表达，而非依赖大M。第三类是无界变量，例如产量没有上界，求解器可能返回无界解，应结合产能补上界。第四类是指标量纲混用，如把“元”和“千元”混在同一目标中。第五类是逻辑约束遗漏，例如写了“启用才可生产”，却忘了写“至少启用一条”，导致全不启用成为可行解。

把上述要点落到示例中：若把 x_A、x_B 改为连续变量，模型变成混合整数规划中的“连续产量+0-1启用”，这在实际中更常见，也更易求解；若业务要求“按整箱出货”，才应改为整数并补充箱规约束。变量类型的选择应服务业务规则，而不是服务公式好看。