maxz=10x1+15x2-50000y1-80000 ≤500+Mv +≤700+(1-M)y The lP model of this problem is . 40 25 x1≤M1 x,≤My y,y,y2 are binary 4. Use the BIP branch-and-bound algorithm to solve the following problem interactively(15 z=8x1+2x2-4x3-7x4-5 3x1+3x,+x2+2x1+3x。≤4 s15x1+3x2-2x3-x4+x5≤4 Solution: we set x, 1-y, x2=1-y2, x3=y3, x4= y4, xs =ys, the model is changed into Max z=10-8y1 3y1-3y2+y2+2y4+3 s1-5y1-3y2-2y3-4y4+y 2 No feasible soluti So, the optimal solution is y1=0, y2=1, y3=1,y4=0, y5=0, that is x1=1, x2=0, x3=1, X 4=0, x5=0, the optimal 5. Solving the following game model. (10 points)3 The IP model of this problem is ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ ≤ ≤ + ≤ + − + ≤ + = + − − , 0 , , 700 (1 ) 40 25 500 50 40 . . max 10 15 50000 80000 1 2 1 2 2 2 1 1 1 2 1 2 1 2 1 2 x x y y y are binary x My x My M y x x My x x st Z x x y y 4. Use the BIP branch-and-bound algorithm to solve the following problem interactively. (15 points) ⎪ ⎩ ⎪ ⎨ ⎧ + − − + ≤ + + + + ≤ = + − − − x is binary x x x x x x x x x x st Max Z x x x x x j 5 3 2 4 3 3 2 3 4 . . 8 2 4 7 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 Solution: we set 1 1 2 2 3 3 4 4 5 5 x = 1− y , x = 1− y , x = y , x = y , x = y , the model is changed into ⎪ ⎩ ⎪ ⎨ ⎧ − − − − + ≤ − − − + + + ≤ − = − − − − − y is binary y y y y y y y y y y st Max Z y y y y y j 5 3 2 4 4 3 3 2 3 2 . . 10 8 2 4 7 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 So, the optimal solution is y1=0,y2=1,y3=1,y4=0,y5=0, that is x1=1,x2=0,x3=1,x4=0,x5=0, the optimal value is z=4 5. Solving the following game model. (10 points) 1 y1=1 y1=0 3 z=2 2 y2=1 y2=0 4 y3=1 y3=0 z=4 5 6 No feasible solution 7 No feasible solution