基本思想:Р设有最大化的整型优化问题A,相应有松弛问题B,从解松弛问题РB开始,若其最优解不符合A的整数条件,那么B的最优目标函数Р必是A的最优目标函数x米的上界,记作7;而A任意可行解Р的目标函数值将是x*的一个下界,记作又。Р分枝定界法就是将B的可行域分成子区域(称为分枝)的方法,Р逐步减小了,增大又,最终求到x。Р≤冰≤РРР三个基本操作:Р(1)分枝Р在松弛问题B的最优解中任选一个不符合整数条件的变量x,其Р值为b,以表示小于b的最大整数。构造两个约束条件Рx≤[1和x≥b+1Р将这两个约束条件,分别加入问题B,求两个后继规划问题B1和B2,Р不考虑整数条件求解这两个后继问题РРР(2)定界Р以每个后继问题为一分枝标明求解结果.在解的结果中,找出最优Р目标函数值最大者作为新的上界.从已符合整数条件的各分支中Р找出目标函数值为最大者作为新的下界,若无,则下界为0Р(3)比较与剪枝Р各分支的最优目标函数中若有小于,则剪掉这枝:;若大于Р且不符合整数条件,则重复前两步,直到找到最优解。РРР分枝定界法计算过程:Р上界Р讨论松弛问题L0:Р1、L无最优解,则IP)无最优解结束Р2、最优解X*=(x*0,x*m,…,x*n),最优值zoР(1)X*为整数解,则X*为(P的最优解结束Р(2)X米中至少有一个是分数,设x是分数:分枝Р,sXoРx14X*+1Р子问题LР子问题L2Р1、L无最优解,剪枝Р2、最优解X*=(x米1,x+1,…,x)Р最优值x1Р(1)X*为整数解,x为下界关闭Р(2)X*中至少有一个是分数:Р继续分枝РРР设已找到下界ZР讨论子问题LР若k的最优值zk≤2o,剪枝Р若1的最优值Zk>z0;Р(1)最优解X*是整数解Р将下界改为Z,关闭LkР(2)最优解X*不是整数解Р继续对L分枝Р当所有的子问题均被关闭或剪枝后Р目标函数值最大的整数解既为所求的最优解
全文预览
