分枝定界法 (数学模型 设整数规划模型: inz=∑ (P) st ∑ i5 x1≥0且为整数,j=1,2,…,n 记最优解为X”,最优目标值为z 松弛问题: mnz三 ∑ st ≥0,j=1, 记可行域为S0,最优解为X0,最优目标值为z一、分枝定界法 设整数规划模型： （P） = = n j j xj z c 1 mins t a x bi i m n j ij j . , 1,2, , 1  = =  = xj  0 且为整数， j = 1,2,  ,n = = n j j xj z c 1 mins t a x bi i m n j ij j . , 1,2, , 1  = =  =  0, xj j = 1,2,  ,n 记最优解为 ，最优目标值为 。  X  z 松弛问题： （P0） 记可行域为S0 , 最优解为X0 ,最优目标值为z0 。 1 2 3