Question

Given the following all-integer linear program: (COMPLETE YOUR SOLUTION IN EXCEL USING SOLVER AND UPLOAD YOUR FILE. BE SURE THAT EACH WORKSHEET IN THE EXCEL FILE CORRESPONDS TO EACH QUESTION BELOW ) ​

Max 15x₁ + 2x₂​

s. t. 7x₁ + x₂ <= 23

3x₁ - x₂ <= 5

x₁, x₂ >= 0 and integer ​

a. Solve the problem (using SOLVER) as an LP, ignoring the integer constraints. What solution is obtained by rounding up fractions greater than or equal to 1/2? Is this the optimal integer solution?

b. What solution is obtained by rounding down all fractions? Is this the optimal integer solution? Explain.

c. Show that the optimal objective function value for the ILP is lower than that for the optimal LP (Eg. Resolve original problem using SOLVER with the Integer requirement).

d. Why is the optimal objective function value for the ILP problem always less than or equal to the corresponding LP's optimal objective function value? When would they be equal?

Answer 1

Solver model without IP constraint

The MOdel gives value = x1=2.8

x2=3.4

Rounding up

x1=3

x2=3

This is not an optimal solution

b) rounding down

x1= 2

x2= 3

As these are below the optimal region of the model they are not the optimal solution

c) Optimal solution

The optimal solution is

x1=2

x2=9

d) A feasible solution for IP is a feasible solution for LP but ILP sets extra constraint for the integer. This reduces the feasible regions and makes it more constrained so we get lesser value.

When the LP variables also take integer values automatically then IP constraint will not change the solutions and the LP and IP solution will be equal.

Please rate me

Thanks

Answer 2

Solver model without IP constraint

The MOdel gives value = x1=2.8

x2=3.4

Rounding up

x1=3

x2=3

This is not an optimal solution

b) rounding down

x1= 2

x2= 3

As these are below the optimal region of the model they are not the optimal solution

c) Optimal solution

The optimal solution is

x1=2

x2=9

d) A feasible solution for IP is a feasible solution for LP but ILP sets extra constraint for the integer. This reduces the feasible regions and makes it more constrained so we get lesser value.

When the LP variables also take integer values automatically then IP constraint will not change the solutions and the LP and IP solution will be equal.

Please rate me

Thanks