Question

For any Linear Programming Problem (LPP), choose the correct statement:
A. There exists only finite number of basic feasible solutions to LPP
B. Any convex combination of k - different optimum solution to a LPP is again an optimum solution to the problem
C. If a LPP has feasible solution, then it also has a basic feasible solution
D. A basic solution to AX = b is degenerate if one or more of the basic variables vanish

• A. A, B and C only
• B. A, C and D only
• C. A, B and D only
• D. A, B, C and D

Hint:

These four statements are pillars of LPP theory. Memorizing them is key: - BFS are finite in number (at most \(\binom{n}{m}\)). - The set of optimal solutions is convex. - If a solution exists, a vertex solution (BFS) exists. - A BFS is degenerate if a basic variable is zero.

Answer 1

The Correct Option is D

Step 1: Understanding the Concept:
This question tests fundamental theorems and definitions related to Linear Programming Problems (LPP). We need to evaluate the correctness of four key statements.

Step 2: Detailed Explanation:
Let's analyze each statement:
A. There exists only finite number of basic feasible solutions to LPP.
A basic solution is found by choosing \(m\) basic variables from \(n\) total variables, where \(m\) is the number of constraints. The maximum number of ways to do this is \( \binom{n}{m} \), which is a finite number. Since the number of basic solutions is finite, the number of basic feasible solutions (which is a subset of the basic solutions) must also be finite. This statement is true.
B. Any convex combination of k - different optimum solution to a LPP is again an optimum solution to the problem.
The set of all optimal solutions to an LPP is a convex set. By definition of a convex set, any convex combination of points within the set is also in the set. Therefore, any convex combination of optimal solutions is also an optimal solution. This statement is true.
C. If a LPP has feasible solution, then it also has a basic feasible solution.
This is a statement of the Fundamental Theorem of Linear Programming. It guarantees that if a feasible solution exists (and the feasible region is non-empty), then at least one vertex (a basic feasible solution) must exist. This statement is true.
D. A basic solution to AX = b is degenerate if one or more of the basic variables vanish.
This is the precise definition of a degenerate basic solution. In a non-degenerate basic solution, all \(m\) basic variables are strictly positive. If at least one of these basic variables is zero, the solution is called degenerate. This statement is true.
Step 3: Final Answer:
All four statements A, B, C, and D are correct principles in the theory of Linear Programming.