整数规划②的名词解释

【整数规划②名词解释如下】

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

相关阅读：