第八章整数规划 §8.3整数规划的分枝定界法(续) 以下进行分枝和定界: stepl分枝与定界: (1)分枝:对于上述x*≠S4找不等于整数的分量x, 构造两个约束条件: CI 把(c1),(c2)分别加入(4)中得到两个子问题(41)(42) 重复上述求解过程
第八章 整数规划 §8.3整数规划的分枝定界法 （续） 重复上述求解过程。 把 分别加入 中得到两个子问题 构造两个约束条件： （）分枝：对于上述 找不等于整数的分量 分枝与定界： 以下进行分枝和定界： ( ),( ) ( ) ( ),( ), [ ] 1 ( ) [ ] ( ) 1 , , 1. 1 2 1 2 2 1 c c A A A x x c x x c x S x step i i i i A i +
第八章整数规划 58.3整数规划的分枝定界法(续) (2)定界(估界):按8.2 ”的方法找到当前 层的上界和下界f step2比较与剪枝 按“8.,2三2”的方法考察剪枝问题 对于未剪枝问题重复述过程进行分枝。当子问题 均得到剪枝时,当前界对应的解即原问题皊优解
第八章 整数规划 §8.3整数规划的分枝定界法 （续） 均得到剪枝时，当前上界对应的解即原问题的最优解。 对于未剪枝问题重复上述过程进行分枝。当全部子问题 按 “ 三 ”的方法考察剪枝问题， 比较与剪枝 层的上界和下界 。 定界（估界）：按“ 三 ”的方法找到当前 8.2 2 2. (2) 8.2 1 step f f
第八章整数规划 §83整数规划的分枝定界法(续) 例刂: mn f 24 (4) )x,+5 45 (B) 为整娄 解:先解(B)得x=(2.857,3.857) f=-29.714记f 找一可行(2,3)得上界f=-22 分枝约東:x1≤[2.8571=2 x1≥[2.8371+1=3
第八章 整数规划 §8.3整数规划的分枝定界法 （续） [2.857] 1 3 ( ) [2.857] 2 ( ) (2,3) 22 29.714 ~ (2.857,3.857) ~ ( ) ( ) , , 0 9 5 45 . . 3 4 24 min 5 4 ( ) 1 2 1 1 1 2 1 2 1 2 1 2 1 2 x c x c f f f B x B x x x x x x st x x f x x A T T + = = = − = − = + + = − − 分枝约束： 找一可行解 得上界 记 解：先解 得 为整数 例：
第八章整数规划 §83整数规划的分枝定界法(续) 两个子问题: mn f=-5x-4x mn f st.3x+4x,≤24 st.3x1+4x2≤24 (A9x+5245(B)(A4)9x1+5 (B2 x1,x,整数 x1,x,整数
第八章 整数规划 §8.3整数规划的分枝定界法 （续） ( ) , , 0 3 9 5 45 . . 3 4 24 min 5 4 ( ) ( ) , , 0 2 9 5 45 . . 3 4 24 min 5 4 ( ) 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 B x x x x x x x st x x f x x B A x x x x x x x st x x f x x A + + = − − + + = − − 整数 整数 两个子问题：
第八章整数规划 x=(2.857,30572至=22 舾(A) f=-29.714 之3 解(A1) f=-2T =(2,4.5) 2)=( 3,3.6) 29.4 (1 28 (2)=-29.4 x2≤4 还25 之4 解〔A11) 解(A12 解(A21) f=-27 11) (2,4) (1.333,5 x(21)=(3.3330每(A22) 无可行解 11) f=-28.665 26 12 26.665 =-28.665 剪枝 王(12)>王剪枝 剪枝 14 ≤3 解(A211) 解(A212) x(211)= 无可行解 最优解x*=(3, 〔211) 最优值f*=-27 剪枝 剪枝 图6.3.1
第八章 整数规划