Question

Consider the following LP problem:

Minimize Cost = 3x₁ + 2x₂

s.t.

1x₁ + 2x₂ ≤ 12

2x₁ + 3 x₂ = 12

2 x₁ + x₂ ≥ 8

x₁≥ 0,

x₂ ≥ 0

A) What is the optimal solution of this LP? Give an explanation.

(4,0)

(2,3)

(0,8)

(0,4)

(0,6)

(3,2)

(12,0)

B)Which of the following statements are correct for a linear programming which is feasible and not unbounded?

1)All of the above.

2)Only extreme points may be optimal.

3)One of the extreme points must be optimal.

4)None of the above.

Only one extreme point must be optimal

Answer 1

1) Answer : (3,2)

The value for constraint 2 for the point (4,0) is 2*4+3*0 = 8. This is not equal to 12. Hence this cannot be the correct answer.

The value for constraint 2 for the point (2,3) is 2*2+3*3 = 13. This is not equal to 12. Hence this cannot be the correct answer.

The value for constraint 2 for the point (0,8) is 2*0+3*8 = 24. This is not equal to 12. Hence this cannot be the correct answer.

The value for constraint 3 for the point (0,4) is 2*0+1*4 = 4. This is not greater than 8. Hence this cannot be the correct answer.

The value for constraint 2 for the point (0,6) is 2*0+3*6 = 18. This is not equal to 12. Hence this cannot be the correct answer.

The value for constraint 2 for the point (12,0) is 2*12+3*0 = 24. This is not equal to 12. Hence this cannot be the correct answer.

For the point (3,2) the value of Constraint 1 is 1*3+2*2 = 7. This is less than 12. Hence this meets the constraint. The value of Constraint 2 is 2*3+3*2 = 12. This is equal to 12. Hence this meets the constraint. The value for constraint 3 is 2*3+1*2 = 8. This is greater than or equal to 8. Hence this meets the constraint. Hence this is the correct answer.

Q2) Only one extreme point must be optimal

If the LP is feasible than it means that there exists a solution of the LP problem. If this LP is not unbounded (which means it is bounded) that means the objective function is a finite set of solutions which lie on the polygon made up of constraints. We know that the problem of such LP will always lie on the corner points. Depending on whether the problem is a minimization or maximization, the solution will always lie on one corner point of the feasible region. Hence the correct answer is only one extreme point must be optimal.