分支定界法 max 2=40x,+90x 不是问题A解 9x1+7x2≤56 7x1+20x2≤70 6 x2≥0 4.81 B 1:x1≤4 3 X 1.82 B 356 B 2:x1≥5 0 2345678910 z=0 2=356
、 、 、 、 、 、 、 、 、 、 、 0 1 2 3 4 5 6 7 8 9 10 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - B 356 1 .82 4 .81 021 === zxx 不是问题A解 z但 £ z * : 4 B1 x 1 £ : 5 B 2 x 1 ³ z = 0 , z = 356 ïîïíì ³ + £ + £ = + , 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
分支定界法 4.81 x1<4x 1.82 B,:x,=4.00 zo=356 2=2.10 349 x,≥5 B2:x1=5.00 1.57 341 0 349 01234567
0 1 2 3 4 5 6 7 4 3 2 1 B1 349 2 . 10 : 4 . 00 1 2 1 1 = = = z x B x 341 1 .57 : 5 .00 2 2 2 1 = = = z x B x z = 0 z = 349 B 2 356 1 .82 4 .81 0 2 1 = = = z x x 5 x 1 ³ 4 x 1 £
分 不是问题A解 2 4.00 剪枝 x,=2.10 B4:x1=1.42 z,=349 x,=3.00x x2≥3 zA=327 B,:x,=4.00 z=340 2.00 z=341 z3=340 是问题A解 但< 01234567
4 3 2 1 340 2 .00 : 4 .00 3 2 3 1 = = = z x B x 327 3 .00 : 1 .42 4 2 4 1 = = = z x B x 0 1 2 3 4 5 6 7 是问题A解 z 但 z 3 349 2 . 10 : 4 . 00 1 2 1 1 = = = z x B x x2 £ 2 x2 ³ 3 B 4 B 3 不是问题A解 而 剪枝 z £ z 4
分支定界法 B X 5.00 x,=1.57 z=340 341 z,=341 x2≤1 B =5.44B x2=1.00无可行解 308 0 234567
0 1 2 3 4 5 6 7 4321 308 1 .00 : 5 .44 52 5 1 === zx B x 无可行解 : B 6 341 1 .57 : 5 .00 22 2 1 === zx B x x 2 £ 1 x2 ³ 2 B 5
分支定界法 B 4.81 82 2=0,z=356 <4 z0=356 x,≥5 B,1:x,=4.00 B2:x=5.00三=0 x2=2.10 x2=1.572=349 349 z=340 =341 x2<2 ≥3 341 < x,≥2 B3:x1=400B:x1=142B5:x1=5.44B行解 x2=2.00 3.00 x2=1.00无可行 3=340 4=327 308 z=z=340
356 1 . 82 : 4 . 81 0 2 1 = = = z x B x 349 2.10 : 4.00 1 2 1 1 = = = z x B x 341 1.57 : 5.00 2 2 2 1 = = = z x B x 340 2.00 : 4.00 3 2 3 1 = = = z x B x 327 3.00 : 1.42 4 2 4 1 = = = z x B x z = 0 , z = 356 349 0 = = z z 341 340 = = z z x1 £ 4 5 x1 ³ 2 x 2 £ 3 x 2 ³ 308 1 .00 : 5 .44 5 2 5 1 = = = z x B x 无可行解 : B 6 x2 £ 1 x 2 ³ 2 340 * z = z =