运筹学分支定界法-0-1整数规划课件.ppt

运筹学教程第三节第三节 分支定界法分支定界法（ Branch and Bound， 简称 BMIN,上界）；上界）；求极小问题时， LP问题的解是 IP问题的下界。每次分 支支 后的子问题最优解的目标函数值都大于或等于分 支支 前的最优值。如分支支 中得到整数解，则最小的整数解为上界。如分 支支 的目标函数值大于上界，则停止分 支支 。运筹学教程AX1=3/2,X2=10/3Z=29/6BX1=2,X2=23/9Z=41/9CX1=1,X2=7/3Z=10/3无可行解DX1=33/14,X2=2Z=61/14FX1=2,X2=2Z=4EX1=3,X2=1Z=4x1 1 x1 2x2 2 x2 3x1 2 x1 3