第2节分支定界解法 令在求解整数线性规划时,如果可行域是有界的,首先容 易想到的方法就是穷举所有可行的整数解,即列出图5-1 中所有标有“+〃的整数点,然后比较它们的目标函数值, 从而确定最优解。 对于规模较小的问题,变量个数很少,可行解的组合数 也较小时,这个方法是可行的,也是有效的。 o如在例1中,变量只有x和x。由条件②,x所能取的整数值为0 为 个。因此所有可能的整数组合(不都是可行的)数是3×5=15个, 穷举法还是勉强可用的。 令对于大型问题,可行的整数组合数会很大 例如在指派问题中,将n项任务指派n个人去完成,不同的指派 方案共有n!种,当n=10时,可能的指派方案数超过300万;当 n=20,超过2×108。显然,穷举法是不可取的。 清华大学出版社清华大学出版社 11 第2节 分支定界解法 ❖ 在求解整数线性规划时，如果可行域是有界的，首先容 易想到的方法就是穷举所有可行的整数解，即列出图5-1 中所有标有“+”的整数点，然后比较它们的目标函数值， 从而确定最优解。 ❖ 对于规模较小的问题，变量个数很少，可行解的组合数 也较小时，这个方法是可行的，也是有效的。  如在例1中，变量只有x1和x2。由条件②，x1所能取的整数值为0、 1、2、3、4共5个；由条件③，x2所能取的整数值为0、1、2共3 个。因此所有可能的整数组合(不都是可行的)数是3×5=15个， 穷举法还是勉强可用的。 ❖ 对于大型问题，可行的整数组合数会很大。  例如在指派问题中，将n项任务指派n个人去完成，不同的指派 方案共有n!种，当n=10时，可能的指派方案数超过300万；当 n=20，超过2×1018。显然，穷举法是不可取的