表423分枝问题的松弛解 问题I 问题I 2 3 9/4 21 问题Ⅲ的解即原整数问题的最优解 可能存在两个分枝都是非整数解的情况,则需要两边同时 继续分枝,直到有整数解出现,就可以进行定界过程 当存在很多变量有整数约束时,分枝即广又深,在最坏情 况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题,NP- complete 只有少数特殊问题有好的算法,如任务分配问题、匹配问题6 表4.2.3 分枝问题的松弛解 问 题 I 问 题 I I x1 2 3 x2 9/4 1 f(x) 2 1 2 2 问题II的解即原整数问题的最优解 可能存在两个分枝都是非整数解的情况，则需要两边同时 继续分枝，直到有整数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即广又深，在最坏情 况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题，NP-complete， 只有少数特殊问题有好的算法，如任务分配问题、匹配问题