Consider the following all-integer linear program:
Max 10x1 + 3x2
s.t.
6x1 + 7x2 ≤ 40
3x1 + 1x2 ≤ 11
x1, x2 ≥ 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 3x1 + 6x2. Repeat parts (a) and (b).