【精选整数规划试题】在运筹学与优化理论中，整数规划（Integer Programming, IP）是一个非常重要的分支，广泛应用于生产调度、资源分配、物流运输等多个领域。整数规划问题要求部分或全部变量取整数值，这使得其求解难度远高于一般的线性规划问题。本文将围绕一些典型的整数规划试题进行分析与解答，帮助读者更好地理解该类问题的建模思路与求解方法。
一、基本概念回顾
整数规划可以分为以下几类：
- 纯整数规划（Pure Integer Programming）：所有变量都必须为整数。
- 混合整数规划（Mixed Integer Programming, MIP）：部分变量为整数，其余为实数。
- 0-1整数规划（Binary Integer Programming）：变量只能取0或1，常用于选择型问题。
整数规划问题通常具有非凸的可行域，因此难以使用传统的线性规划方法求解，常用的方法包括分枝定界法（Branch and Bound）、割平面法（Cutting Plane Method）以及启发式算法等。
二、典型试题解析
试题1：生产计划问题
某工厂生产两种产品A和B，每件产品需要不同的原材料和工时。已知如下数据：
| 产品 | 原材料消耗（kg） | 工时（小时） | 利润（元/件） |
|------|------------------|--------------|---------------|
| A| 2| 3| 5 |
| B| 4| 2| 7 |
现有原材料30kg，工时24小时。要求每种产品的产量为整数，求最大利润。
模型建立：
设 $ x_1 $ 为产品A的产量，$ x_2 $ 为产品B的产量。
目标函数：
$$
\text{Maximize } Z = 5x_1 + 7x_2
$$
约束条件：
$$
\begin{cases}
2x_1 + 4x_2 \leq 30 \\
3x_1 + 2x_2 \leq 24 \\
x_1, x_2 \in \mathbb{Z}_+ \\
\end{cases}
$$
求解思路：
可采用枚举法或分枝定界法求解。通过枚举可能的组合，最终得出最优解为 $ x_1 = 4, x_2 = 6 $，此时利润为 $ 5×4 + 7×6 = 62 $ 元。
试题2：选址问题
某连锁超市计划在5个候选地点中选择若干个设立门店，每个地点的建设成本和预计年收益如下表所示：
| 地点 | 成本（万元） | 年收益（万元） |
|------|--------------|----------------|
| 1| 8| 12 |
| 2| 6| 9|
| 3| 7| 10 |
| 4| 5| 7|
| 5| 9| 13 |
预算为20万元，要求最多开设3个门店，求最大年收益。
模型建立：
设 $ y_i = 1 $ 表示在第i个地点建店，否则为0。
目标函数：
$$
\text{Maximize } Z = 12y_1 + 9y_2 + 10y_3 + 7y_4 + 13y_5
$$
约束条件：
$$
\begin{cases}
8y_1 + 6y_2 + 7y_3 + 5y_4 + 9y_5 \leq 20 \\
y_1 + y_2 + y_3 + y_4 + y_5 \leq 3 \\
y_i \in \{0,1\}, i=1,2,3,4,5 \\
\end{cases}
$$
求解思路：
由于变量为0-1变量，可用穷举法或使用MIP求解器求解。经过计算，最优解为选择地点1、2、4，总成本为 $ 8+6+5=19 $ 万元，年收益为 $ 12+9+7=28 $ 万元。
三、总结
整数规划问题因其变量限制而更具现实意义，但也增加了求解的复杂度。在实际应用中，合理地建立数学模型是解决问题的关键。通过对上述典型试题的分析，我们可以看到，整数规划不仅考验数学建模能力，也对算法实现提出了更高要求。
希望本文能为学习整数规划的读者提供一定的参考与帮助。
