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: Introduction
This question assesses understanding of Linear Programming Problem (LPP) theorems and definitions. We must evaluate four statements for correctness.

Step 2: Statement Analysis
Each statement is now examined:
A. LPPs have a finite number of basic feasible solutions.
A basic solution arises from selecting \(m\) basic variables from \(n\) total variables, where \(m\) is the number of constraints. The maximum combinations possible is \( \binom{n}{m} \), a finite value. Because basic feasible solutions are a subset of basic solutions, their number is also finite. This statement is true.
B. A convex combination of optimal solutions in an LPP yields another optimal solution.
The set of optimal solutions in an LPP forms a convex set. Consequently, a convex combination of points within this set remains within the set. Therefore, a convex combination of optimal solutions is itself an optimal solution. This statement is true.
C. An LPP with a feasible solution possesses a basic feasible solution.
This reflects the Fundamental Theorem of Linear Programming. It assures that if a feasible solution exists (and the feasible region is non-empty), then at least one vertex (a basic feasible solution) also exists. This statement is true.
D. A basic solution to AX = b is degenerate if one or more basic variables equal zero.
This is the definition of a degenerate basic solution. Non-degenerate basic solutions have all \(m\) basic variables strictly positive. If at least one basic variable is zero, the solution is degenerate. This statement is true.
Step 3: Conclusion
All four statements (A, B, C, and D) correctly represent Linear Programming principles.