4. 经典整数规划模型

整数规划之所以在运筹学与工程优化中占据核心地位，很大程度上源于四类经典模型：背包问题、指派问题、选址问题和旅行商问题。它们各自刻画了一类现实决策结构，又分别对应不同的变量设计思路与求解难度。理解这四类模型，等于掌握了整数规划建模的“基本语汇”——后续大量复杂问题，往往都是它们的组合、扩展或变形。

一、背包问题：0-1变量的最简原型

背包问题描述的是在容量约束下从若干物品中选择子集，使总价值最大。设物品集合为 i=1,…,n，物品 i 的重量为 w_i、价值为 v_i，背包容量为 C。引入 0-1 决策变量 x_i：取 1 表示装入，取 0 表示不装。模型为：

max  Σ v_i · x_i
s.t. Σ w_i · x_i ≤ C
     x_i ∈ {0, 1},  i = 1,…,n

变量设计的要点在于“选择即 0-1”。若物品可重复选取，则变量改为非负整数 x_i ∈ ℤ₊，成为完全背包；若每类物品有数量上限 u_i，则加约束 x_i ≤ u_i，成为有界背包。背包问题的规模由物品数 n 决定，约束只有一条容量约束，结构极简，但它是 NP 难的——这正是“约束少不等于容易解”的典型例证。

二、指派问题：排列型 0-1 结构

指派问题把 n 项任务分配给 n 个执行者，每人恰好承担一项、每项恰好由一人完成，目标是最小化总成本。设成本矩阵为 c_ij，决策变量 x_ij ∈ {0,1} 表示任务 j 是否指派给执行者 i。模型为：

min  Σ_i Σ_j c_ij · x_ij
s.t. Σ_j x_ij = 1,  ∀i   （每人一项）
     Σ_i x_ij = 1,  ∀j   （每项一人）
     x_ij ∈ {0, 1}

指派问题的特殊之处在于：其约束矩阵是全幺模的，线性松弛的最优解天然为整数，因此可用匈牙利算法在多项式时间内求解。这一点与背包问题形成鲜明对照——同样是 0-1 变量，结构不同，难度天差地别。变量设计时需注意“双等式约束”是保证排列性质的关键，缺一不可。

三、选址问题：两层决策与固定成本

设施选址在指派结构上叠加了“是否启用设施”的决策。设候选设施集合 i、客户集合 j，启用设施 i 的固定成本为 f_i、容量为 Q_i，客户 j 的需求为 d_j，从 i 到 j 的单位运输成本为 c_ij。需要两层变量：y_i ∈ {0,1} 表示是否启用设施 i；x_ij ≥ 0 表示设施 i 服务客户 j 的货量。核心约束是“未启用的设施不能供货”：

min  Σ f_i·y_i + Σ Σ c_ij·x_ij
s.t. Σ_i x_ij = d_j,           ∀j
     Σ_j x_ij ≤ Q_i · y_i,     ∀i   （容量与启用联动）
     x_ij ≥ 0,  y_i ∈ {0, 1}

这里 Q_i·y_i 是典型的“大 M”式联动约束：当 y_i=0 时右侧为 0，强制 x_ij=0；当 y_i=1 时退化为容量约束。选址问题的难度来自固定成本带来的非凸性，线性松弛会倾向于把 y_i 取成小数以“分摊”固定成本，导致松弛界偏松，分支定界需要更多节点。

四、旅行商问题：排列与子回路消除

旅行商问题（TSP）要求访问 n 个城市各一次并回到起点，使总路程最短。设 c_ij 为城市 i 到 j 的距离，x_ij ∈ {0,1} 表示是否走边 (i,j)。基础模型为：

min  Σ_i Σ_j c_ij · x_ij
s.t. Σ_j x_ij = 1,  ∀i   （每个城市出度 1）
     Σ_i x_ij = 1,  ∀j   （每个城市入度 1）
     x_ij ∈ {0, 1}

仅有出入度约束会允许“多个不相连的子回路”，因此必须加入子回路消除约束。常用做法是引入辅助变量 u_i（访问次序），对 i,j ≠ 1 加 MTZ 约束：u_i − u_j + n·x_ij ≤ n−1。TSP 的变量数为 n(n−1)，约束数随 n 平方增长，且子回路约束数量指数级，通常采用割平面法按需生成。

五、模型规模与求解难度的关系

把四类模型放在一起比较，可以得到一个关键认识：规模（变量与约束数量）并不直接决定难度，结构才是决定性的。指派问题变量数达 n²，却因约束矩阵全幺模而多项式可解；背包问题只有一条约束，却是 NP 难的。选址问题在指派结构上加入固定成本，破坏了全幺模性，线性松弛解出现小数 y_i，分支定界树显著变大。TSP 的变量数 n(n−1) 与子回路约束的指数级数量，使其成为四者中最难的一类。

实际建模时，可据此选择策略：指派类问题优先用匈牙利算法或直接 LP 求解；背包类问题规模小时用动态规划，规模大时用分支定界配合贪心上界；选址问题应尽量收紧大 M 取值（用 Q_i 而非任意大数），并考虑加入有效不等式强化松弛；TSP 则必须依赖割平面与启发式初始解。变量设计上，0-1 变量用于“是否选择/启用/走边”，连续或整数变量用于“数量/流量”，两层变量之间的联动约束是建模正确性的关键。