任务三　0—1规划及其求解方法

3.1　0—1规划问题

0—1规划是变量只取0或1的一种特殊形式的整数规划。在实际问题中，诸如开与关、取与舍、有或无等逻辑现象都可以用0—1变量来描述。由于0—1整数规划在实践中有着广泛的应用和独特的建模技巧，所以在此单独介绍。

例3-3-1　投资问题　某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用如表3-3-1所示。假定每一项已选定的工程要在三年内完成，试确定应该上马哪些工程，方能使该部门可能期望收益最大？

解：这是工程上马的决策问题，对于任一给定的工程而言，它只有两种可能，要么上马，要么不上马，这两种情况分别令它对应二进制中的0和1。大凡这样的实际背景所对应的工程问题，大都可以考虑用0—1规划建立其相应的模型。

因为每一年的投资不能超过所能提供的资金18千元，因此该0—1规划的约束条件为

由于期望收益尽可能大，所以目标函数为

maxz＝20x1＋40x2＋20x3＋30x4

3.2　0—1规划的求解

由于0—1规划的决策变量只取0、1两个值，除了能用一般整数规划的求解方法，例如分支定界法来求解之外，还有其特殊的解法。下面介绍求解0—1规划的完全枚举法和隐枚举法。

3.2.1　完全枚举法

解0—1规划时，一种最自然的思路是检查变量的每一个取值，比较目标函数值的大小，以求得最优解。这种方法称为完全枚举法。

例3-3-2　用完全枚举法求解下列0—1规划问题。

（x1，x2，x3）共有8种不同的组合，把各种组合下目标函数和约束条件左端的值列入表3-3-2中。

由表可知，该问题的可行解为（0，0，0）、（0，0，1）、（0，1，0）、（1，0，0）、（1，0，1），最优解为（1，0，1），最优值为8。

3.2.2　隐枚举法

枚举法可以解决一些0—1规划问题，可是当变量个数比较多的时候，枚举法的计算量明显增大。这时，我们需要找到一种方法，只检查变量取值的部分组合，就能求得问题的最优解。这种方法称为隐枚举法。

用隐枚举法来求解例3-3-2。

解：先用试探的方法，找到一个满足所有约束条件的解，如（0，0，1），算出其z值等于5。也就是说，要求的最优值一定不会小于5。所以，可以增加一个约束条件3x1-2x2＋5x3≥5，凡是目标函数值小于5的组合不必讨论，这时就得到了一个更简单的表3-3-3。

从表3-3-3可以看出，最优解为（1，0，1），最优值为8。隐枚举法是对枚举法的一种简化，而这两种方法的主导思想是趋于一致的。