1. Indicate which of the following is an all-integer linear program, and which is a mixed integer linear program. Write the LP Relaxation for the problem but do not attempt to solve. (8 marks)

1. Max 30x₁ + 25x₂ subject to

4x₁ + 2.5x₂ 400

3.5x₁ + 5x₂ 250

2x₁ + 1.5x₂ 150

x₁, x₂ 0 and x₂ to be integer

2. Min 3x₁ + 4x₂ subject to

4 x₁ + 2x₂ 8

5 x₁ + 4x₂ 12

x₁, x₂ 0 and both to be integer

2. Consider the following all-integer linear program:

Max 1 x + 1 y subject to

4x + 6y 22

x + 5y 15

2x + y 9

x, y 0 and both integers

1. Graph the constraints for this problem. Use dots to indicate all feasible integer solutions. (3 marks)

2. Solve the LP Relaxation of this problem. (3 marks)

3. Find the optimal integer solution including all the calculations and all steps. (3 marks)