作者:llhthinker 整数规划是线性规划的特殊情况,即当约束条件是变量为整数时,线性规划就变成了整数规划。若要求所有变量都为整数,即为纯整数规划;若允许存在一部分变量不一定为整数,则称为混合整数规划。而本文要讨论的0-1整数规划则是纯整数规划的特殊情况,即所有变量要么等于0,要么等于1,故这种变量又成为逻辑变量。 0-1整数规划在生活中还是很常见的,通常可以总结为“是”“否”问题。例如,有n个产品销地x1,...,xn可供选择,为使得利润最大,那么每一个销地都面临是否选择的问题,通常还会有一些限制条件,由于销地xi与销地xj距离较近,所以规定若选择xi就不能选择xj等。那么如何求解0-1规划问题?最朴素的方法是枚举,即将所有销地是否被选择的情况都考虑,那么就是从{0, ... ,0}枚举到{1, ... ,1},需要2的n次方的枚举次数。显然,当n较大时,这种方式的效率就非常低。本文要介绍的隐枚举法就可以提高求解出最优解的效率。 所谓隐枚举法,从字面上理解,就是隐去一些不需要枚举的情况,下面从一个例子出发,来给出隐枚举法的步骤。 【例】求解下列规划问题
1. 预处理 首先需要对原问题进行预处理,至于为什么后文将会解释。预处理的步骤如下: 1) 将目标函数统一为求最小值,即'min', 同时将约束条件都化为'>='。
2) 将目标函数中系数为负的变量xi化为系数为正的变量xi',其中 xi = 1 - xi’ (若xi = 0 则 xi' = 1; 若xi = 1则xi' = 0)。 故针对本问题,在目标函数中x1和x2前的系数为负,故令x1 = 1 -x1', x2 = 1 - x2',代入1)中化简得
3) 重新排列变量在目标函数和约束条件的先后顺序,使其在目标函数中的系数递增。
2. 隐枚举 隐枚举的思想是首先枚举找到一个可行解,并得到目标函数值z0,之后的枚举若目标函数值没有z0优,那么就一定不是最优解。 现在说明预处理的作用: 预处理使得目标函数是求最小值,变量的系数都为正且由小到大排列,所以有如下规律:
隐枚举步骤如下: (1) 先忽略除' xi或xi' = 0或1 '以外的约束条件,从xi = 0也就是0...0开始枚举。 (2) 计算出枚举出的目标函数值。
(3) 检查枚举的解是否满足除去的约束条件。(只要检查出一个约束条件不满足就无需再检查)
对于本问题,从xi = 0 (i = 1到5)开始枚举,得到z' = -10,所以-10便是最优解的下界(所以10便是原问题的上界)。枚举过程列表如下('-'代表没有判断): 由表可以看出,我们在第4次枚举得到了一个较优的可行解,其目标函数值z0 = -4,之后的枚举要么是不满足约束条件,要么是函数值大于-4,剪枝。最后我们只枚举了9次就完成了整个过程(比直接枚举的2^5 = 32次快了很多),得到最优解为{0,0,0,1,1},min z' = -4,将其还原成原问题,最优解为{1, 0, 1, 0, 0},max z = 4. 总结: 在解决很多问题的时候,枚举(搜索)似乎是一种直接了当的方式。但是,当解空间较大时,枚举的效率可能就很低,无法达到目的。此时,不妨想想是否在枚举过程中有一些解可以在枚举之前就判断它一定不满足要求,直接不考虑它们(剪枝),这样就可以缩小解空间,提高效率。 |
|