一罐可乐

1. 整数规划分类#

• 纯（全）整数线性规划：所有决策变量都限制为非负整数。
• 混合整数线性规划（MILP）：仅有一部分变量限制为整数，其余可取连续实数值。
• 0-1 整数线性规划：所有决策变量只能取 0 或 1。

2. 舍入凑整法的失效性#

通常不能简单地将松弛后的普通线性规划（即舍去“变量为整数”约束后的 LP 问题，称为松弛规划）的最优解进行四舍五入凑整：

• 凑整后的点极有可能超出可行域，变成非可行解。
• 即使凑整后仍是可行解，它往往也不是最优整数解（整数最优解不一定是松弛解邻域内的点）。

1. 算法核心原理#

• 上界与下界： 对于极大化 $\max z$ 整数规划问题，其松弛规划的最优目标值 $z_0$ 构成了整数规划最优解 $z^*$ 的上界（即 $z^* \le z_0$）。任意已知的整数可行解的目标值则构成 $z^*$ 的下界。
• 分支（Branching）： 若当前松弛解中某变量 $x_k = v$ 不是整数，则以两个不重叠的不等式为约束分裂为两个子问题： $x_k \le \lfloor v \rfloor \quad \text{和} \quad x_k \ge \lceil v \rceil$
• 定界（Bounding）与剪支（Pruning）： 对新生成的子问题求解松弛规划：
  • 若子问题的松弛最优值小于等于当前已知的下界，则该支不可能包含更好的整数解，予以剪支（抛弃）。
  • 若子问题无可行解，予以剪支。
  • 若子问题的松弛解刚好全部满足整数约束，则用其更新下界，并对该支进行剪支（因已找到该分支的最优整数解，无需再分）。
  • 否则，用子问题的最优值更新该支的本地上界，继续对其分支。
• 重复上述过程直到所有分支被剪除，当前下界对应的整数解即为最优解。

1. 算法核心思想#

先求解不含整数约束的松弛规划，若最优解为非整数，则通过数学代数关系构造一个割平面约束（Gomory 切割）并添加到模型中。该约束会割去包含当前非整数最优解的部分可行域，但保证不割掉任何整数可行解。新问题求解后通常会得到非可行解（右端项出现负数），需使用对偶单纯形法快速重新求解，重复此过程直至解为整数。

2. 切割方程的代数推导步骤#

在最终单纯形表中，设某个基本变量 $x_i$ 的值为非整数： $x_i + \sum_{k \in N} \alpha_{ik} x_k = b_i$ 将系数和常数项拆分为整数部分 $N$ 与非负真分数部分 $f$（满足 $0 \le f < 1$）： $b_i = N_i + f_i \quad (0 < f_i < 1)$ $\alpha_{ik} = N_{ik} + f_{ik} \quad (0 \le f_{ik} < 1)$ 带入方程移项整理： $x_i + \sum_{k \in N} N_{ik} x_k - N_i = f_i - \sum_{k \in N} f_{ik} x_k$ 由于左侧各项在整数约束下必须是整数，故右侧的值也必须是整数。又因为 $\sum f_{ik} x_k \ge 0$，且 $f_i < 1$，所以右侧的整数最大只能为 0。由此得到切割方程： $-\sum_{k \in N} f_{ik} x_k \le -f_i$ 引入非负松弛变量，使用对偶单纯形法求解，即可在不损失任何整数解的前提下排除非整数最优解。

1. 互斥项目选择（投资场所选定）#

• 从 $A_1, A_2, A_3$ 中至多选两个：$y_1 + y_2 + y_3 \le 2$。
• 从 $A_4, A_5$ 中至少选一个：$y_4 + y_5 \ge 1$。
• 前提条件约束：选择项目 5 的前提是选择项目 1，则有：$y_5 \le y_1$ （若 $y_1=0$，则 $y_5$ 必须为 0；若 $y_1=1$，$y_5$ 可为 0 或 1）。

2. 互斥约束条件建模#

若两个约束条件 $f_1(X) \le b_1$ 与 $f_2(X) \le b_2$ 是互斥的（即只需满足其中一个即可，另一个自动失效）。 引入一个 0-1 变量 $y \in \{0, 1\}$ 和一个极大常数 $M$： $f_1(X) \le b_1 + y M$ $f_2(X) \le b_2 + (1 - y) M$

• 若 $y=0$，第一式有效，第二式由于加上 $M$ 自动失效。若 $y=1$，则反之。
• 推广到 $m$ 个互斥约束中必须满足 $k$ 个： $f_i(X) \le b_i + y_i M \quad (i=1,\dots,m)$ $\sum_{i=1}^m y_i = m - k \quad (y_i \in \{0, 1\})$

3. 固定费用（Fixed Charge）建模#

生产产品 $x_j$ 时，若产量 $x_j > 0$，需支付固定设备成本 $K_j$；若不生产（$x_j = 0$）则不支付。总成本为： $\text{Cost} = \sum_{j} (K_j y_j + c_j x_j)$ 必须建立产量 $x_j$ 与 0-1 状态变量 $y_j$ 的关联约束： $x_j \le y_j M \quad (\forall j)$ 其中 $M$ 为该产品产量的物理上限。

1. 指派问题数学模型#

有 $n$ 项任务指派给 $n$ 个人分别完成，每人只能做一项。设 $x_{ij} \in \{0, 1\}$ 表示是否指派第 $i$ 人做第 $j$ 项任务，效率矩阵为 $C=(c_{ij})$。要求总时间或总成本最小： $\min z = \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij}$ $\text{s.t. } \begin{cases} \sum_{j=1}^n x_{ij} = 1, & i = 1, \dots, n \quad \text{（每人做一项工作）} \\ \sum_{i=1}^n x_{ij} = 1, & j = 1, \dots, n \quad \text{（每项工作由一人做）} \\ x_{ij} \in \{0, 1\} \end{cases}$

2. 匈牙利法求解步骤#

匈牙利法基于的核心矩阵定理是：“在效率矩阵的某行（或列）同加减一个常数，最优解不变”。

1. 矩阵归零：每行减去该行最小值；随后每列减去该列最小值。使各行各列均出现 0 元素。
2. 试指派与独立零元素寻找：
   • 从含 0 元素最少的行（或列）开始，给唯一的 0 加圈（◎），并划去同行、同列的其他 0 元素（标为 $\Phi$）。
   • 重复直至所有 0 被处理。
   • 若圈出的 ◎ 个数 $m = n$，则这些 ◎ 对应的变量为 1，即得最优解。若 $m < n$，进入第 3 步。
3. 覆盖打勾与覆盖线绘制（寻找最少覆盖直线 $l$）：
   • 对没有 ◎ 的行打“$\checkmark$”。
   • 对已打“$\checkmark$”的行中所有含 $\Phi$ 的列打“$\checkmark$”。
   • 对已打“$\checkmark$”的列中含有 ◎ 的行打“$\checkmark$”。
   • 重复上述两步。
   • 划线：对没有打“$\checkmark$”的行画横线，对打“$\checkmark$”的列画纵线。最少直线数即为 $l$。若 $l = n$ 且 $m < n$，说明试指派有误，重新寻找独立零；若 $l < n$，进入第 4 步。
4. 矩阵重构（增加零元素）： 在没有被任何覆盖线压住的元素中找出最小值 $\Delta$。
   • 所有未被覆盖的元素减去 $\Delta$。
   • 线与线交叉点的元素加上 $\Delta$。
   • 其余只被单线压住的元素保持不变。得到新矩阵后返回第 2 步重新试指派。
5. 注：极大化指派问题，可先令 $b_{ij} = M - c_{ij}$（$M$ 为原矩阵中最大元素），转化为极小化问题再用匈牙利法求解。