整数规划

约 499 个字 预计阅读时间 2 分钟

整数规划（Integer Programming, IP）是数学规划的一个重要分支，研究在变量需取整数值（如0、1、2等）的约束下，求解优化问题的方法。其核心思想是通过数学建模和算法，在离散决策场景中找到最优解。

核心特点

1. 变量离散性：至少有一个决策变量必须为整数，而普通线性规划（LP）允许变量取实数。
2. 挑战性：整数规划属于NP难问题，计算复杂度随问题规模急剧增加。

主要分类

1. 纯整数规划（Pure IP）
   所有决策变量均为整数。
   例：生产调度中确定工人数量。

2. 混合整数规划（Mixed IP, MIP）
   部分变量为整数，部分为实数。
   例：投资组合优化中选择是否投资（0-1变量）与资金分配（实数变量）。

3. 0-1整数规划
   变量仅取0或1，用于“是否选择”类决策。
   例：项目选择、路径规划。

经典解法

1. 分支定界法（Branch and Bound）
2. 松弛：先解对应的线性规划问题，若解为整数则终止。
3. 分支：若解非整数，选择变量分裂为两个子问题（如x≤3和x≥4）。

4. 定界：通过子问题的最优值逐步缩小可行解范围。

5. 割平面法（Cutting Plane）
   通过添加线性约束（“割平面”）逐步逼近整数解。

应用场景

• 资源分配：预算限制下选择最优项目组合。
• 生产调度：安排机器、人力的时间与任务分配。
• 网络优化：最短路径、设施选址问题。
• 金融风控：投资组合优化、信用评分模型。

挑战与应对

1. 计算复杂性：大规模问题需借助启发式算法（如遗传算法、模拟退火）或商业求解器（CPLEX、Gurobi）。
2. 模型构建：需将实际问题抽象为整数规划模型，可能涉及非线性约束的线性化处理。