标准0-1整数规划的隐枚举法求解步骤及原理解析

通过上面这个简单的例子可以看出，隐枚举法的基本思想是尽量减少求解过程中对0-1变量组合的检验计算。那么如何才能有规律地构建过滤条件，使检验计算量达到最低呢？以下针对标准的0-1 整数规划问题给出隐枚举法的求解步骤。

标准的0-1 整数规划要求：上式中的目标函数值求最小值；目标函数的系数0C ≥；在目标函数中，变量按系数值从小到大排列，同时约束条件中的变量顺序也作相应改变；所有约束条件必须是“≥”的形式。

隐枚举法的求解思路与分枝定界法相似，利用变量只能取0 或1 这两个值的特征，进行分枝。首先，令所有变量取值为0，检验解是否可行：若可行，则0z=，已得最优解；若不可行，则根据另一个变量取值为0 或1（此变量为固定变量），将问题分为两个子域，其余未被指定取值的变量为自由变量。由于这些自由变量在目标函数中的系数都是正数，因此，令自由变量为0 且与固定变量组成的子域的解可使目标函数值达到最小。经过此检验，或者停止分枝，或者将第二个自由变量转为固定变量，令其值为0 或1，将此子域再分成两个子域。如此不断往下进行，直至没有自由变量或者全部子域停止分枝为止，就求出最优解。

具体求解步骤如下：

第一步：令全部jx 都是自由变量且取值为0，检验解是否可行。

（1）若可行，已得最优解；

（2）若不可行，进行第二步。

第二步：将某一变量转为固定变量，令其取值为1 或0，使问题分成两个子域，令一个子域中的自由变量取值为0，加上固定变量取值，组成此子域的解。

第三步：计算此解的目标函数值，并将其与已求出的可行解的最小目标值比较。

（1）如果前者大，则不必检验是否可行而停止分枝（因继续分枝即使得到可行解，其目标函数值也较大，不会是最优解）：

① 若子域都检验过，转到第七步；

② 否则，转到第六步；

（2）如果前者小，转到第四步；

（3）对第一次算出的目标函数值，不必进行比较，直接转到第四步。

第四步：检验解是否可行。

（1）如果可行，已得一个可行解，计算并记下它的z值，停止分枝（因继续分枝，即使得到可行解，由于目标函数的系数均为非负数，所以目标函数值也比记下的z值大，不会是最优解）：

① 若子域都检验过，转到第七步；(www.xing528.com)

② 否则，转到第六步；

（2）若不可行，转到第五步；

第五步：将子域中固定变量的值代入第一个不等式约束条件方程，并令不等式左端的自由变量当系数为负时取值为1，系数为正时取值为0，这就是左端所能取得的最小值。

（1）若此最小值大于右端值，则此子域成为不可行子域，不再往下分枝：

① 若子域都检验过，转到第七步；

② 否则，转到第六步；

（2）若此最小值小于右端值，则依次检验下一个不等式约束方程，直至所有的不等式约束方程都能通过：

① 若子域都检验过，转到第七步；

② 否则，转到第六步。

第六步：定出尚未检验过的另一个子域的解，重复第三步至第五步的过程。

（1）若所有子域都停止分枝，则计算停止，目标函数值最小的可行解就是最优解；

（2）否则，转到第七步。

第七步：检查有无自由变量。

（1）若有，则转到第二步；

（2）若没有，则计算停止，目标函数值最小的可行解就是最优解。

由于第三步至第五步中均有停止分枝的情况，对于这些子域中的自由变量取0 或1的一切可能组合都被隐含地考虑过了，不必再一一列举，所以这种方法称为隐枚举法。它与完全枚举法相比较，计算量大大减少了。