的的筛选,也可以解决因穷举法产生的“组合爆炸”问题,同时也考虑了空间利用率最大。因而,求解两阶段装载优化问题最终归结为一个整数规划问题(5-8)其中,T为阈值,根据经验获得,在本文的计算中,T取2。5.3装载优化模型的通用求解算法设计5.3.1求解整数规划的分支定界算法分支定界算法是一种隐枚举法,是整数规划中常用的算法之一[5]。它的主要思想是根据某种策略将原问题松弛问题的可行域分解为越来越小的子域,并检查每个子域内整数解的情况,直到找到最优整数解或证明整数解不存在。分支定界法从求松弛问题开始,将问题可行域分为许多的子域(最通常的分解方式是“两分法”),这一过程称为分支;通过分支找到更好的整数解来不断的修改问题的上下解,这一过程称为定界。定界的目的是为了测定界的趋势,留下有价值的或尚不能判定的分支。删除肯定不存在最优解的分支,称之为剪枝,以达到加速收敛,简化运算的目的。不同的分支定界方法在于分支、定界和剪枝的不同处理手段上,其算法的一般步骤可概括为:Step1:初始化。选择可行域的S的初始松弛集合F,满足;初始可行点集合,上界,令P={F},计算下界,并令。在计算的过程中,若有必要,则更新Q和。Step2:分割。将F分割成有限个子集Fi,(指标集)满足,令。Step3:剪枝。对每个,计算f在子集Fi上的下界,使其满足,利用在计算)的过程中所发现的所有可行点修正集合Q,同时按照合适的删除规则,删除P中所有不包含最优解的Fi或Fi的一部分,剩余集合不妨仍记为P;Step4:定界。令,。Step5:终止判断。若(充分小的正数),则终止算法。否则,从P中挑选合适的子集F,,转入步骤2。5.3.2启发式调整优化启发式算法[3]是一种基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度不一定事先可以预计。
全文预览
