4) Consider the following all-integer linear program:

Max 10x₁+ 3x₂

s.t.

6x₁+ 7x₂ <= 40 3x₁+ 1x₂ <= 11

x_1, x₂ >=0, and integer

a) Formulate and solve the LP Relaxation of the problem. Solve it graphically, and round down to find a feasible solution. Specify an upper bound on the value of the optimal solution.

b) Solve the integer linear program graphically. Compare the value of this solution with the solution obtained in part (a).

c) Suppose the objective function changes to Max 3x₁+ 6x₂. Repeat parts (a) and (b).

6) Consider the following mixed-integer linear program:

Max 1x₁+ 1x₂ s.t.

7x₁+ 9x₂ <= 63 9x₁+ 5x₂ <= 45 3x₁+ 1x₂ <= 12

x_1, x₂ >=0, and x₂ integer

a) Graph the constraints for this problem. Indicate on your graph all feasible mixed-integer solutions.

b) Find the optimal solution to the LP Relaxation. Round the value of down to find a feasible mixed-integer solution. Specify upper and lower bounds on the value of the optimal solution to the mixed-integer linear program.

c) Find the optimal solution to the mixed-integer linear program.