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

第五章 整数规划的探讨

第五章 整数规划的探讨

第一节 整数规划的概述

一、整数规划的定义

当数学规划中的变量被限定为必须取整数值时，这样的规划问题便被称为整
数规划（Integer Programming, IP），其是数学优化或运筹学中的一个分支，它涉
及在满足一系列线性约束条件的情况下最大化或最小化一个线性目标函数，其中

决策变量被要求取整数值。其可以视为线性规划的一个特例，但求解过程通常更
加复杂，因为解空间不是连续的，而是离散的。整数规划问题根据变量是否必须
为整数，又分为纯整数规划（所有变量都必须为整数）和混合整数规划（部分变
量可以为实数，部分变量必须为整数）。如果是在线性规划模型的基础上进一步

要求所有或部分变量必须为整数，这便特指为整数线性规划。现阶段流行的解决
整数规划问题的技术，大多数仅限于处理整数线性规划类型的问题。至今尚未发
现一种通用且高效的方法，能够应对所有类型的整数规划挑战。
整数规划作为运筹学的一个重要分支，其发展历史可以追溯到 20 世纪中叶。

尽管线性规划的概念早在 20 世纪初就已出现，但直到计算机技术的进步和相关
算法的发展，整数规划才逐渐成为解决实际问题的有效工具。在 20 世纪 30 年代
至 40 年代，线性规划理论开始形成。George Dantzig 在 1947 年发明了单纯形法，
这是解决线性规划问题的第一个有效算法。然而，单纯形法并不能直接应用于整

数规划问题，因为它的解通常是分数值。在 1950 年代，随着对线性规划研究的
深入，人们开始意识到许多实际问题中决策变量必须取整数值。这促使研究人员
探索新的方法来处理这类问题。1958 年，Ralph E. Gomory 提出了第一个针对纯

整数规划问题的切割平面算法，这是整数规划领域的重要突破之一。
其关键发展阶段主要包括：1. 分支定界法：1960 年代，A.H. Land 和 A.G.
Doig 提出了分支定界法（Branch and Bound），这是一种系统地搜索整数解的方
法。这种方法通过将原问题分解成若干子问题，并对每个子问题进行评估，逐步

123