Which of the following statements are correct about the linear programming problem (LPP)?
A. Every point in the feasible region is a feasible solution of the given LPP.
B. An optimal solution of an LPP, if it exists, occurs at one of the extreme points of the convex set of the feasible solutions.
C. The feasible region for an LPP is always a convex set.
D. If an LPP admits two optimal solutions, it has an infinite number of optimal solutions.
Choose the correct answer from the options given below:
Answer & explanation
Correct answer: option 3
The correct answer is Option (3) → A, B, C and D
A feasible solution is a point that satisfies all the constraints. Each linear constraint gives a half-plane, which is convex, and the intersection of convex sets is convex. By the corner point theorem, an optimal value, if it exists, occurs at a corner (extreme) point of the feasible region.
So the feasible region is convex, its points are the feasible solutions, an optimum occurs at a corner point, and the number of optimal solutions is 0, 1 or infinitely many.
Checking the statements
(A) Every point in the feasible region is a feasible solution of the given LPP. — Correct. This is the definition of a feasible solution.
(B) An optimal solution of an LPP, if it exists, occurs at one of the extreme points of the convex set of the feasible solutions. — Correct. This is the corner point theorem.
(C) The feasible region for an LPP is always a convex set. — Correct. It is an intersection of half-planes, each of which is convex.
(D) If an LPP admits two optimal solutions, it has an infinite number of optimal solutions. — Correct. If P and Q are optimal, the linear objective has the same value at every point of the segment PQ, which lies in the convex feasible region.