Page 135 - 数学建模算法与应用

第五章 整数规划的探讨

二、整数规划的分类

如不加特殊说明，则一般指整数线性规划。整数线性规划模型大致可分为

两类：
变量全限制为整数时，称纯 ( 完全 ) 整数规划
完全整数规划是指在优化问题中，所有决策变量都被要求取整数值的一类

优化问题。特点包括所有决策变量必须取整数值，这使得解空间变得离散，增加
了求解的难度。通常使用分支定界法（Branch and Bound）、割平面法（Cutting
Plane Method）等算法来求解。其应用广泛，例如生产计划、资源分配、网络设计等。
变量部分限制为整数时，称混合整数规划

混合整数规划是指在优化问题中，部分决策变量被要求取整数值，而其他决
策变量可以取实数值的一类优化问题。特点包括：决策变量中既有整数变量也有
实数变量，这使得问题的复杂度介于线性规划和完全整数规划之间。

求解方法通常也是分支定界法、割平面法等，但需要特别处理整数变量和实
数变量之间的关系。其应用非常广泛，例如供应链管理、物流优化、金融投资组
合优化等。
求解方法主要有：1. 分支定界法（Branch and Bound）：通过系统地划分

问题空间，逐步缩小搜索范围，最终找到最优解。2. 割平面法（Cutting Plane
Method）：通过添加额外的约束（割平面）来逐步逼近整数解。3. 启发式算法：
如遗传算法、模拟退火等，适用于大规模问题，虽然不能保证找到全局最优解，

但在实际应用中往往能获得满意的结果。
完全整数规划和混合整数规划都是整数规划的重要类型，在实际应用中均有
着广泛的用途。完全整数规划要求所有变量都取整数值，而混合整数规划则允许
部分变量取实数值。这两种类型的整数规划问题都可以通过多种算法进行求解，

但在实际应用中需要根据问题的具体特点选择合适的求解方法。

三、整数规划特点

（一）原线性规划有最优解，当自变量限制为整数后，其整数规划解出
现下述情况。
1. 原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。

125