分支定界法 倒4-2:求解整数规划问题 整数规划问题A 松弛问题B maz=40x1+90x2 maxz=40x+90x 9x1+7x2≤56 9x1+7x,≤56 7x1+20x2≤70 7x+20x,≤70 x,x2≥0且为整数 x,x2≥0 设问题A的最优目标函数值为Z,则问题B的 录优目标函教值必定是问题A的上界,记为Z。例4-2:求解整数规划问题 整数规划问题A 松弛问题B ï î 且为整数 ï í ì ³ + £ + £ = + , 0 7 20 70 9 7 56 max 40 90 1 2 1 2 1 2 1 2 x x x x x x z x x ï î ï í ì ³ + £ + £ = + , 0 7 20 70 9 7 56 max 40 90 1 2 1 2 1 2 1 2 x x x x x x z x x 设问题A的最优目标函数值为Z* ,则问题B的 最优目标函数值必定是问题A的上界，记为Z