整数规划的定义

当模型中的变量 (部分或全部) 被限制为整数时，称为整数规划。

[math]\text{整数规划}\begin{cases}\text{整数线性规划(线性规划 + 变量取整)} \\ \text{整数非线性规划(无求解算法，只能模拟，如蒙特卡洛算法、智能算法)}\end{cases}[/math]

问题：把线性规划的最优解的自变量取整就是整数规划的最优解吗？

1. [math]\min z = x_1 + x_2, \ \text {s.t.} \begin {cases} 2x_1 + 4x_2 = 5 \\ x_1 \geqslant 0, x_2 \geqslant 0 \end {cases}[/math]，此时最优解 [math] x_1 = 0, x_2 = \min \ z = \dfrac {5}{4}[/math]，此时整数规划无解。
2. [math]\min z = x_1 + x_2, \ \text {s.t.} \begin {cases} 2x_1 + 4x_2 = 6 \\ x_1 \geqslant 0, x_2 \geqslant 0 \end {cases}[/math]，此时最优解 [math] x_1 = 0, x_2 = \dfrac {3}{2}, \min z = \dfrac {3}{2}[/math]，若限制为整数 [math] x_1 = 1, x_2 = 1, \min z = 2 [/math]，有解。

整数规划的例题

相互排斥的约束条件/01背包问题

例 1. 某市为方便小学生上学，拟在新建的 8 个居民小区 [math] A_1, A_2, \dots, A_8 [/math] 增设若干所小学，经过论证，知备选校址有 [math] B_1, B_2, \dots, B_6 [/math]，它们能覆盖的居民小区如表所示。

解题思路

设 [math] x_i = \begin {cases} 1, & \text {在备选校址 } B_i \text { 建学校}, \\ 0, & \text {在备选校址 } B_i \text { 不建学校}. \end {cases}[/math]

目标是让覆盖所有小区，且校区数量最少，即 [math]\min \sum_{i = 1}^{6} x_i [/math]。

对于[math]A_1[/math]到[math]A_7[/math]，分别找出包含它们的备选校址，可以得到约束条件：

[math]\text {s. t.}\begin {cases}x_1 + x_2 + x_3 \geqslant 1 \\x_4 + x_6 \geqslant 1 \\x_3 + x_5 \geqslant 1 \\x_2 + x_4 \geqslant 1 \\x_5 + x_6 \geqslant 1 \\x_1 \geqslant 1 \\x_2 + x_4 + x_6 \geqslant 1\end {cases}[/math]

指派问题

例 2. 某公司新购置了某种设备 6 台，欲分配给下属的 4 个企业，已知各个企业获得这种设备后创年利润如表所示，每个企业至少分配 1 台设备，问应该如何分配这些设备才能使年创总利润最大，最大为多少？

解题思路

用 [math] j = 1, 2, 3, 4 [/math] 分别表示甲、乙、丙、丁四个企业，[math] c_{ij}[/math] 表示第 [math] i (i = 1, …, 6)[/math] 台设备分配给第 [math] j [/math] 个企业创造的利润，设：[math]
x_{ij} =
\begin {cases}
1, & \text {第} i\text {台设备分配给第} j\text {个企业} \\
0, & \text {第} i\text {台设备不分配给第} j\text {个企业}
\end {cases},
i = 1, \cdots, 6; j = 1, 2, 3, 4.
[/math]

目标函数为：[math]\max \sum_{i = 1}^{6} \sum_{j = 1}^{4} c_{ij} x_{ij}[/math]

约束条件（s.t.）：[math]
\begin {cases}
\sum_{i = 1}^{6} x_{ij} \geqslant 1, & j = 1, 2, 3, 4, \\
\sum_{j = 1}^{4} x_{ij} = 1, & i = 1, \cdots, 6, \\
x_{ij} = 0 \text { 或 } 1, & i = 1, \cdots, 6; j = 1, 2, 3, 4.
\end {cases}
[/math]