剩下的是整数松弛整数线性规划

整数线性规划（Integer Linear Programming, ILP）是一种优化问题，其中目标函数和约束条件都是线性的，并且某些或所有变量必须取整数值。整数松弛（Integer Relaxation）是指将整数线性规划中的整数约束放宽，使得变量可以取实数值，从而形成一个线性规划（Linear Programming, LP）问题。

整数线性规划的基本形式

一个标准的整数线性规划问题可以表示为：

最大化cTx最大化cTx

满足Ax≤b满足Ax≤b

xi∈Z或xi∈Z+xi​∈Z或xi​∈Z+

其中：

• cc 是目标函数的系数向量。
• xx 是决策变量向量。
• AA 是约束条件的系数矩阵。
• bb 是约束条件的右侧常数向量。
• xixi​ 是需要取整数的变量。

整数松弛

在整数松弛中，我们将整数约束放宽为实数约束：

xi∈R或xi∈R+xi​∈R或xi​∈R+

这样，问题变为一个线性规划问题，可以使用标准的线性规划求解方法（如单纯形法或内点法）来求解。

整数松弛的步骤

1. 构建整数线性规划模型：定义目标函数、约束条件和变量的类型（整数或实数）。
2. 松弛整数约束：将所有整数约束放宽为实数约束。
3. 求解松弛后的线性规划：使用线性规划求解器（如 CPLEX、Gurobi、GLPK 等）求解松弛后的问题。
4. 分析结果：
   • 如果松弛后的解是整数解，则该解也是原整数线性规划的最优解。
   • 如果松弛后的解不是整数解，则需要进一步处理，通常使用分支定界法（Branch and Bound）或割平面法（Cutting Plane）等方法来寻找整数解。

示例

假设我们有以下整数线性规划问题：

最大化3x1+2x2最大化3x1​+2x2​

满足x1+2x2≤43x1+x2≤6x1,x2≥0x1,x2∈Z+满足x1​+2x2​3x1​+x2​x1​,x2​x1​,x2​​≤4≤6≥0∈Z+​

步骤：

1. 松弛整数约束：将 x1x1​ 和 x2x2​ 的约束改为 x1,x2∈R+x1​,x2​∈R+。
2. 求解松弛后的问题：使用线性规划求解器求解。
3. 分析结果：假设得到的解为 x1=1.5x1​=1.5 和 x2=1.75x2​=1.75，这不是整数解。
4. 进一步处理：使用分支定界法等方法来寻找最优的整数解。