整数规划

---

是一类待求变量的全部或一部分必须取整数值的特殊数学规划。

在线性规划数学模型中，有些变量是连续的，即取值可以是分数或小数。例如，亩产粮食1012．25斤等。

还有些变量是不连续的，即取值必须是整数。

例如，运输中需要的火车车箱数等。

凡有一部分变量或所有变量限制为整数的线性规划，称为整数线性规划或叫整数规划。

这其中：若只是部分变量限制为整数时，称为混合整数线性规划；若全部变量限制为整数时，则称为纯整数线性规划或全整数线性规划。在有些实际应用问题中，整数变量仅限制在0或1之间取值，则称为0－1规划或双态整数线性规划(参阅《0－1规划》)。

整数规划模型中若舍去变量的整数限制，即为一般的线性规划，称为与原整数规划相应的线性规划或原整数规划的松驰线性规划。

整数规划的解法是多种多样的，而且至今尚缺乏严密的统一性，但大多数方法的思路是这样的：先从某一个有关问题(起初就是原向问题IP)出发，称之为母向问题，“继传”产生一系列子问题，其中至少有一个子问题的最优解属于其问题的最优解。

对于每一个子问题，这时又称之为原问题，在把它的可行解扩大之后，就派生得一个松驰问题，它必须比原问题容易求解。然后，根据松驰问题的求解结果来确定：抛弃它的原问题或者用它的原问题去代替母问题。依此类推，直到不存在新的问题，或者说，继传终结为止。

现在人们总结出的一些整数规划的具体解法，如分支定界法、割平面法等等，主要差别在于产生子问题或继传方法上的不同，或者派生松驰问题方法上的不同，或者选取子问题作为新的母问题方法上的不同。