Question

2. Consider the following all-integer linear program: ***(I NEED to solve this with HAVE EXCEL SPREAD SHEET AND Sensitivity Report) ***

Max 5x1 + 8x2

S.T

6x1 + 5x2 <= 30

9x1 +4x2 <= 36

1x1 + 2x2 <=10

x1, x2 >=and integer

a. Graph the constraints for this problem. Use dots to indicate all feasible integer solutions.

b. Find the optimal solution to the LP Relaxation. Round down to find a feasible integer solution.

c. Find the optimal integer solution. Is it the same as the solution obtained in part (b) by rounding down?

Answer 1

(a)

Series 1 : 6x1+5x2 <= 30

Series 2 : 9x1+4x2 <= 36

Series 3 : 1x1+2x2 <= 10

The constraints for the problem are (0,0), (0,5) ,(4,0) ,(1.42,4.28) , (2.85, 2.57)

integer solutions

(4,0) (0,1) (0,0) (0,2) (0,3) (0,4) (0,5) (1,0) (1,1) (1,2) (1,3) (1,4) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2)

Please refer the image :

(b) LP relaxation

Please refer image below:

The intersection of series 1 and 3 is the LP relaxation point i.e (1.42, 4.28)

And now the optimal solution to LP relaxation after rounding off is (1,4)

(c)

The optimal integer solution after I solved in solver excel is (0,5).

No, it is not same as the solution obtained in part (b) by rounding down

(Please refer image below)

Please refer the sensitivity analysis below done in excel

41.34 is the relaxation point where x1 and x2 are given