分支定界法在最优化问题中的应用.pdf

2007 NO.08 科技咨询导报 Science and Technology Consulting Herald 工 程 技 术 分支定界法在最优化问题中的应用 张勇 （山西太原理工大学 030024） 摘 要:分支定界法是一种应用范围很广的搜索算法，本文在最优化问题中充分体现了分支定界法的应用，投资问题上充分体现了分 支定界法的优越性。 关键词:分支 定界 分支定界法 中图分类号:G424 文献标识码:A 文章编号:1673-0534(2007)03(b)-0061-02 1简介 此是原问题的可行解，其年收益可作为原问 分支定界法是一种应用范围很广的搜索 投资总额I满足 题最优解的一个候选者，即年收益低于2.9亿 算法，它的基本思想是把给定问题分解为若 元的解，不会是最优解。另外x=0对应的解 3 干个较小的子问题，每个子问题又可继续分 预计年投资总收益P满足 ，恰为第一步得到且我们尚未处 解，直到子问题不能再分解或不能产生最优 解。根据问题的特点和不同的策略，把问题 理的解。过程可图示如下，解右侧的数字表 分解为子问题的过程称之为分支。在分支过 所以数学模型就是求 示该解对应的年收益 程，为每一子问题估算其对应的目标值的界 限称之为定界。定界的目的是为了测定界的 趋势，留下有价值的或尚不能判定的分支。 删除肯定不存在的最优解的分支，称之为剪 为便于求解，我们先算出每个项目的收 支，以达到加速收敛、简化运算的目的。对 益率，即单位投资收益，加入表1中得表2 对上图左边的解，我们分别取x=0或 为题进行分解，确定子问题的解值界限，减 然后，放宽约束条件，允许xi取正实 1 x=1，即将约束条件限为x3=0，x1=0或 去非优的子问题，在进行新的分支，这样一 数值，优先选择收益率最高的项目，得两组最 1 x=0，x=1(其余变量不限)，对约束x=0， 个分支到定界到剪支再到分支等反复的过程 3 1 3 优解 是分支定界法的基本算法步骤。不同的分支 x=1,有两组最优解 和 ， 1 规则与定界方法，形成了同一问题的不同分