分枝定界法的基本思路: 通过对松弛问题的分枝, 不断降低(P)最优值的上界,提高下界, 当上界等于下界时,得到最优解
分枝定界法的基本思路： 不断降低（IP）最优值的上界，提高下界， 当上界等于下界时，得到最优解 通过对松弛问题的分枝
分枝定界法计算过程: 上界 讨论松弛问题L 1、L无最优解,则俨)无最优解结東 2、最优解X*=(x*01,x*m2…,x*n)最优值z0 (1)X*为整数解,则X*为)的最优解结束 (2)X*中至少有一个是分数,设x*01是分数:分枝 Xy 子问题L1 子问题L2 L无最优解,剪枝 2、最优解X*=( x11 最优值 (1)X*1为整数解,1为下界关闭 (2)X*中至少有一个是分数 继续分枝
分枝定界法计算过程： : 讨论松弛问题L0 1、L0无最优解，则(IP)无最优解 结束 0 0 1 0 2 0 2 X * (x * x * , , x * ), z 、最优解 = ， o n 最优值 (1)X * 0 为整数解 ，则X * 0 为(IP)的最优解 (2)X * 0 中至少有一个是分数， 结束 设x * 01 是分数 ：分枝 上界 : 子问题L1 : 子问题L2 1、L1无最优解，剪枝,z1 为下界 关闭 继续分枝 1 1 11 12 1 2 * ( * * , , * ), z X x x x n 最优值 、最优解 = ， (1)X * 1 为整数解 (2)X * 1中至少有一个是分数：