分支定界法的选择原则与方法
分支变量选择原则:
①按目标函数系数,选系数绝对值最大的变量先分。因为价值系数的绝对值大,对目标函数的值升降影响最大;
②选与整数值相差最大的非整数变量先分支;
③按使用者经验,对各整数变量排定重要性的优先顺序。因为在实际生产管理中,有可能决策变量有上百个,保证每一个都为整数没有必要,只要保证主要变量为整,次要的变量采用舍入化整法处理就可以了。
分支结点选择方法为:
①深探法(后进先出法)。最后打开的结点最先选,可以尽快找到整数解。整数解质量可能不高,但适合计算机编程,因为计算机中的栈正好和这种思维结合使计算机的内存占用较小。
②广探法。选目标函数当前最大值结点,找到的整数解质量高,但是求解速度慢,而且用计算机求解时非常占用内存。