整数规划
是求最优整数解题的方法。 在线性规划中有些最优解可能是整数、分数或小数，但对于某些具体问题，如机器的台数，人员的分配，飞机的架次等，其答案都必须是整数，虽然可以把所得的带分数或小数的解“舍入化整”，但化整后的解不一定是可行解，更不一定是最优解。如何求得最优整数解，就是整数规划要研究的问题。整数规划中所有变数都限制为(非负)整数，属于纯整数规划，如仅一部分变数限制为整数，则称为混合整数规划。 整数规划的解法，最常用的有两种：一种是割平面法，它的基础仍是用解线性规划的方法去求解整数规划问题，首先不考虑变量xi是整数这一条件，但增加约束条件(用几何术语称为割平面)，使得由原可行域中切掉其包含非整数解，保留整数可行解，经多次切割后最终得到这样的可行解域，它有一个整数坐标的极点恰好是问题的最优解。另一种方法是分枝定界法，它是以求相应线性规划的最优解为出发点，如果这个解不合乎整数条件，就将原问题分解成分枝(部分)，每枝(部分)都增加约束条件，分别在不考虑整数条件求解，如仍然没有得到全部整数解，继续对问题进行分解(分枝)，并分别附加约束条件再求解，直至求出原问题的最优整数解为止。 |