吴振华 贵文龙 智国建

（桂林电子科技大学商学院，广西 桂林 540114）

1 引言

在整数规划中，隐枚举法（Implicit enumeration algorithm）是用于求解“0-1整数规划问题”的常见方法，其基本思想是通过增加“过滤约束”舍弃一定不最优解的解组合以求得最优解[1]。在教学过程中发现，许多学生存在这样的疑问：过滤约束应如何添加？作用何在？为此，本文通过实例阐述隐枚举法的求解步骤、过滤约束的作用及“隐”字的含义，帮助学生更好地掌握隐枚举法。

2 目标函数求max的0-1规划问题求解

[例1] 求以下0-1整数规划问题的最优解？

求解步骤[2]：

（1）寻找目标函数值下界。可以判断，当可行解X = (0,1, 0)T时，该问题的目标函数值（－2）最小，因此可以确定目标函数值下界，即3x1-2x2+ 5x3≥－2。

（2）构造过滤约束，并将其加入到原约束条件中。

因函数函数值大于等于“－2”，因此可能是0[X =(0, 0,0)T）]、3[X =(1,0,0)T）]和 5[X =(0,0,1)T）]等，可先构造过滤约束“3x1-2x2+ 5x3≥0”，则原模型变为：

（3）写出所有解组合，比较目标函数值 Z，并检查是否满足约束条件和过滤条件，得出最优解。过滤约束为“3x1-2x2+ 5x3≥0”的求解过程如表1所示：

当X =(0,0,0)T时，满足所有约束条件（包括过滤约束），因此在表中对应位置添入“√”，此时目标函数值Z为“0”。当X =(0,0,1)T时，满足所有约束条件，因此在表中对应位置添入“√”，此时目标函数值Z为“5”。当X =(0,1,0)T、(0,1,1)T和(1,0,0)T时，Z值分别为“－2”、“3”和“3”，均小于“5”，由于目标函数求最大值，因此无须再去考虑 X是否满足约束条件。当X =(1,0,1)T时，满足所有约束条件，因此在表中对应位置添入“√”，此时目标函数值Z为“8”。当X=(1,1,0)T和(1,1,1)T时，Z值分别为“1”和“6”，均小于“8”，因此可求得该问题的最优解为：X*=(1,0,1)T，Z*=8。

可见，添加过滤约束可以加快筛选过程，“隐”去不可能成为最优解的解组合（见表1加粗部分，下同），以简化求解过程。……