1. 概述
在本教程中，我们将深入探讨整数线性规划（Integer Linear Programming, ILP），并介绍如何在 ILP 中建模和处理涉及最小值（min）和最大值（max）的优化问题。我们会结合具体实例，展示如何将这些非线性逻辑转换为 ILP 可处理的形式。
2. 整数线性规划（ILP）简介
整数线性规划是一种在满足线性等式或不等式约束条件下，对线性目标函数进行优化的方法。与普通线性规划不同的是，ILP 要求所有决策变量取整数值。
我们可以用如下数学形式定义一个 ILP 问题：
最大化或最小化： $$ c_1y_1 + c_2y_2 + \cdots + c_ny_n $$
约束条件为： $$ \begin{aligned} b_{11}y_1 + b_{12}y_2 + \cdots + b_{1n}y_n &\leq d_1 \ b_{21}y_1 + b_{22}y_2 + \cdots + b_{2n}y_n &\leq d_2 \ \vdots \ b_{m1}y_1 + b_{m2}y_2 + \cdots + b_{mn}y_n &\leq d_m \ y_i &\geq 0,\quad y_i \in \mathbb{Z},\quad i = 1,2,\dots,n \end{aligned} $$
也可以用矩阵形式表示为：
最大化或最小化： $$ C^T Y $$
约束条件： $$ \begin{aligned} BY &\leq D \ Y &\geq 0 \ Y &\in \mathbb{Z} \end{aligned} $$
其中：
- $ C $：目标函数的系数向量（成本向量）
- $ B $：约束条件的系数矩阵
- $ D $：资源上限向量
- $ Y $：决策变量向量，且取整数
3. 最大化 ILP 示例
我们来看一个最大化收入的 ILP 示例：
Rob 有两份兼职工作，每周最多工作 16 小时。他在 A 工作每小时赚 $40，在 B 工作每小时赚 $60。他希望最大化总收入。
我们设：
- $ y_a $：A 工作的小时数
- $ y_b $：B 工作的小时数
目标函数为： $$ \text{最大化 } E = 40y_a + 60y_b $$
约束条件为： $$ \begin{aligned} y_a + y_b &\leq 16 \ y_a, y_b &\in \mathbb{Z^+} \end{aligned} $$
4. 最小化 ILP 示例
现在我们来看一个最小化摄入胆固醇的例子：
Alex 想通过吃豆腐和意大利面来满足每天至少摄入 150g 蛋白质的需求，同时尽量减少胆固醇摄入。
设：
- $ y_p $：吃意大利面的天数
- $ y_t $：吃豆腐的天数
已知：
- 意大利面：每份 8g 蛋白质、60mg 胆固醇
- 豆腐：每份 16g 蛋白质、50mg 胆固醇
目标函数为： $$ \text{最小化 } I = 60y_p + 50y_t $$
约束条件为： $$ \begin{aligned} 8y_p + 16y_t &\geq 150 \ y_p, y_t &\in \mathbb{Z^+} \end{aligned} $$
5. Maximin ILP（最大化最小值）
当问题要求我们最大化多个决策变量中的最小值时，我们称之为 Maximin ILP。
比如我们要最大化三个整数中的最小值，且它们的总和为 100：
原始目标函数： $$ \text{最大化 } \min{ y_1, y_2, y_3 } $$
约束条件： $$ y_1 + y_2 + y_3 = 100 $$
我们可以引入一个辅助变量 $ z $，将其转化为标准 ILP 形式：
目标函数： $$ \text{最大化 } z $$
约束条件： $$ \begin{aligned} y_1 + y_2 + y_3 &= 100 \ z &\leq y_1 \ z &\leq y_2 \ z &\leq y_3 \ y_1, y_2, y_3, z &\in \mathbb{Z^+} \end{aligned} $$
✅ 这样就能通过 ILP 求解器求解。
6. Minimax ILP（最小化最大值）
当问题要求我们最小化多个决策变量中的最大值时，我们称之为 Minimax ILP。
比如我们要最小化四个整数中的最大值，且它们的总和为 120：
原始目标函数： $$ \text{最小化 } \max{ y_1, y_2, y_3, y_4 } $$
约束条件： $$ y_1 + y_2 + y_3 + y_4 = 120 $$
同样，我们引入辅助变量 $ z $：
目标函数： $$ \text{最小化 } z $$
约束条件： $$ \begin{aligned} y_1 + y_2 + y_3 + y_4 &= 120 \ z &\geq y_1 \ z &\geq y_2 \ z &\geq y_3 \ z &\geq y_4 \ y_1, y_2, y_3, y_4, z &\in \mathbb{Z^+} \end{aligned} $$
✅ 这种建模方式非常实用，常用于任务调度、负载均衡等场景。
7. 总结
在本教程中，我们介绍了：
- ILP 的基本定义和数学表达形式
- 如何建模最大化和最小化问题
- Maximin ILP：最大化最小值的建模方法
- Minimax ILP：最小化最大值的建模方法
这些技巧在实际业务场景中非常有用，例如资源分配、排班调度、组合优化等领域。掌握这些建模方式，有助于你更灵活地使用 ILP 解决复杂的优化问题。