整数线性规划（简称整数规划）是数学规划的一个分枝，它的目标函数和约束条件都是线性的，与线性规划不同的是整数规划要求其全部或部分决策变量必须是非负整数。根据决策变量是否全部要求为整数，可将整数规划划分为两类，即要求部分决策变量为整数的混合整数规划和要求全部决策变量均为整数的纯整数规划（或称完全整数规划）。在整数规划中，有些问题要求变量只能取0或1，称之为0—1规划，它是整数规划的一种特殊情形。整数规划求解的方法主要有图解法、枚举法、圆整法、分枝定界法和割平面法等[17]。
分枝定界法是A.H.Land和A.G.Doig于1958年提出的，它可以用于求解纯整数或混合的整数规划问题，由于该方法灵活且便于用计算机求解，它是求解整数规划的重要方法之一，因此，下面将简要介绍该方法的计算步骤。
若某整数规划问题的标准形式表示为
则应用分枝定界法求解整数规划问题的步骤如下[16]：
（1）假设称求解的整数规划问题为问题A，而称其与之对应的线性规划问题为问题B。
（2）求解问题B，可能得到以下情况之一：
1）问题B没有可行解，这时问题A也没有可行解，则停止计算。(https://www.xing528.com)
2）问题B有最优解，并符合问题A的整数条件，则问题B的最优解即为问题A的最优解，求解过程结束。
3）问题B有最优解，但不符合问题A的整数条件，记相应的目标函数值为Z。
（4）分枝。在问题B的最优解中任选一个不符合整数条件的变量xj，其相应的值为bj，以[bj]表示小于bj的最大整数，构造两个新的约束条件xj≤[bj]和xj≥[bj]+1，并将这两个约束条件分别加入问题B，分别得到两个后继规划问题B1和B2，在不考虑整数约束条件的前提下分别求解后继规划问题B1和B2。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
