常设计一些方法,只检查变量取值的组合的一部分,就能求到问题的最优解。这样的方 法称为隐枚举法( Implicit- numeration),分枝定界法也是一种隐枚举法。当然,对有 些问题隐枚举法并不适用,所以有时穷举法还是必要的 下面举例说明一种解0-1型整数规划的隐枚举法。 例6Max2=3x1-2x2+5x3 x+2x2-x3≤2 x1+4x2+x3 <4 x2+x3≤6 x,x2,x3=0或 求解思路及改进措施: (i)先试探性求一个可行解,易看出(x1,x2,x3)=(1,0)满足约束条件,故为 个可行解,且相应的目标函数值为z=3 (ⅱi)因为是求极大值问题,故求最优解时,凡是目标值z<3的解不必检验是否 满足约束条件即可删除,因它肯定不是最优解,于是应增加一个约束条件(目标值下界) 3x1-2x2+53≥3,称该条件为过滤条件( Filtering Contraint)。从而原问题等价于 Ma 3x1-2x2+5x3≥3 x1+2x2-x3≤2 (b) x1+4x+x3≤4 (d) 4x2+x2≤6 x3=0或1 (f) 若用全部枚举法,3个变量共有8种可能的组合,我们将这8种组合依次检验它 是否满足条件(a)-(e),对某个组合,若它不满足(a),即不满足过滤条件,则b)-(e)即 可行性条件不必再检验:若它满足(a)(e)且相应的目标值严格大于3,则进行(i) (ⅲi)改进过滤条件 )由于对每个组合首先计算目标值以验证过滤条件,故应优先计算目标值二大 组合,这样可提前抬高过滤门槛,以减少计算量 按上述思路与方法,例6的求解过程可由下表来表示 x,x2x)目标值约束条件 过滤条件 (0,0,0) 0 (1,0.0) √√√√√3x, (010) (0,0,1) √√√ 小3x1-2x2+5325-16- 常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方 法称为隐枚举法（Implicit Enumeration），分枝定界法也是一种隐枚举法。当然，对有 些问题隐枚举法并不适用，所以有时穷举法还是必要的。 下面举例说明一种解 0−1 型整数规划的隐枚举法。 例 6 Max 3 1 2 2 5 3 z = x − x + x s.t.          = +  +  + +  + −  , , 0 1 4 6 3 4 4 2 2 1 2 3 2 3 1 2 1 2 3 1 2 3 x x x 或 x x x x x x x x x x 求解思路及改进措施： （i） 先试探性求一个可行解，易看出 ( , , ) (1,0,0) x1 x2 x3 = 满足约束条件，故为一 个可行解，且相应的目标函数值为 z = 3。 （ii） 因为是求极大值问题，故求最优解时，凡是目标值 z  3 的解不必检验是否 满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）： 3x1 − 2x2 + 53  3 ，称该条件为过滤条件(Filtering Contraint)。从而原问题等价于： Max 3 1 2 2 5 3 z = x − x + x s.t.            = +  +  + +  + −  − +  , , 0 1 4 6 3 4 4 2 2 3 2 5 3 1 2 3 2 3 1 2 1 2 3 1 2 3 1 2 3 x x x 或 x x x x x x x x x x x x x ( ) ( ) ( ) ( ) ( ) ( ) f e d c b a 若用全部枚举法，3 个变量共有 8 种可能的组合，我们将这 8 种组合依次检验它 是否满足条件(a)—(e)，对某个组合，若它不满足(a)，即不满足过滤条件，则(b)—(e)即 可行性条件不必再检验；若它满足(a)—(e)且相应的目标值严格大于 3，则进行（iii）。 （iii） 改进过滤条件。 （iv）由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值 z 大 的组合，这样可提前抬高过滤门槛，以减少计算量。 按上述思路与方法，例 6 的求解过程可由下表来表示： ( , ) 1 2 3 x ，x x 目标值 约束条件 过滤条件 a b c d e (0,0,0) 0  (1,0,0) 3 √ √ √ √ √ 3x1 − 2x2 + 53  3 (0,1,0) -2  (0,0,1) 5 √ √ √ √ √ 3x1 − 2x2 + 53  5