Problems:
Use LP relaxation to solve Mix Integer programming problem
Consider the following all-integer linear program:
Max 2x1+3x2
s.t.
4x1+9x2<36
7x1+5x2<35
1x1+2x2<10
X1,x2>0 and x1 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 x1 down to find a feasible mixed-integer solutions. Is this solution optimal? Why or why not?
c. Find the optimal solution for the mixed-integer linear program.