第四节 0—1规划与隐枚举法

0−1规划是一种特殊的纯整数规划，它的变量只取0或者1，称为0−1变量或二进制变量。0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件，因此0-1规划非常适合描述和解决如线路设计、工厂选址、生产计划安排、旅行购物、背包问题、人员安排、代码选取、可靠性等人们所关心的多种问题。实际上，凡是有界变量的整数规划都可以转化为0-1规划来处理。由于0-1规划具有广泛的应用，几十年来一直受到人们的重视。

求解0-1规划问题最简明直观的方法是穷举法，即检查变量取0或者1的各种组合，逐一比较相应的目标函数值以求得最优解，但这需要比较2个结果，但是当较大时，采用穷举法求解不太现实。目前求解0-1规划问题最常用的是隐枚举法，对一些特殊问题还有一些更加有效的方法，例如对指派问题，用匈牙利法求解更显方便有效。隐枚举法基本思路是从所有变量等于零出发，依次指定一些变量为1，直至得到一个可行解，并将它作为目前最好的可行解。此后，依次检查变量等于0或1的某些组合，以便使目前最好的可行解不断加以改进，最终获得最优解。隐枚举法不同于枚举法，它不需要将所有可行的变量组合一一列表。它通过分析、判断排除了许多变量组合作为最优解的可能性。

隐枚举法的求解步骤如下：

(1)列表。将0-1整数规划的相关信息填入表中。表格的第一列按规律列出决策变量的取值组合，从组合(0,0,…,0)开始,从最后一个变量开始,依次将变量由0变为1,最后一个组合为(1,1,…,1)；表格第二列为第一列对应的目标函数值；第三列到倒数第二列为约束条件列，每列代表一个约束条件；最后一列为最优值列，即目前为止的最优目标函数值。

(2)填表。对决策变量的每一个取值组合，先求出其目标函数值，若目标函数值不优于最后一列的数值，则不再考虑此行，转入下一行；若目标函数值优于最后一列的数值，再考虑是否满足各个约束条件，若不满足某约束条件，在相应的格子里划“×”，并不再考虑后面的约束条件，转入下一个行；若满足某约束条件，在相应的格子里划“√”并接着考虑下一个约束条件，若满足所有的约束条件，再在该行的最后一列中填入试目标函数值。当表中所有行都考虑完了后，将最后一个最优目标函数值作为所求规划问题的最优目标函数值，第一列中对应的组合为最优解。

下面举例说明隐枚举法的求解过程。

【例3.3】求解下列整数规划。

解：采用隐枚举法解该0-1整数规划，求解过程可用表3-6表示。

表3-6 枚举法解过程

从表3-5可知，最优目标函数值=2，最优解为：。

采用这种方法，共运算了21次。

为了进一步减少运算量，一般按照以下规则重新排列0-1整数规划模型中决策变量的系数：

(1)对“”型的0-1整数规划，重新排列的系数，使目标函数中的系数是递增的，同时将约束条件中按目标函数中的顺序重新排列；

(2)对“min”型的0-1整数规划，重新排列的系数，使目标函数中的系数是递减的，同时将约束条件中按目标函数中的顺序重新排列。

对于重新排列过决策变量的0-1整数规划，一定要注意将表格中第一列的决策变量顺序作相应的排序。

例如，对例3.3，可按下列步骤进行：

先对模型中的决策变量按目标函数中系数递减的顺序重新排列，得如下整数规划：

再对上述0-1整数规划列表计算如表3-7。

表3-7隐枚举法解过程

从表3-6可知，最优目标函数值=2，最优解为，即：

采用这种方法，共运算了13次，比未排序前少运算了8次。