In a linear programming problem with 3 basic variables and 2 non-basic…
2012
In a linear programming problem with 3 basic variables and 2 non-basic variables, what is the maximum possible number of basic solutions?
Answer: C. 10 — ConceptFor a system with m independent constraints and n variables, a basis is formed by choosing m variables as basic and setting the remaining n − m…
- A.
6
- B.
8
- C.
10
- D.
12
Show answer & explanation
Correct answer: C
Concept
For a system with m independent constraints and n variables, a basis is formed by choosing m variables as basic and setting the remaining n − m variables to zero.
Therefore, the maximum number of candidate basic solutions is the binomial coefficient C(n, m), provided each selected basis is nonsingular.
Application
There are 3 basic variables and 2 non-basic variables, so the total number of variables is n = 3 + 2 = 5.
Choose the 3 basic variables from the 5 total variables: C(5, 3) = 5! ÷ (3! × 2!).
Evaluating gives C(5, 3) = (5 × 4) ÷ (2 × 1) = 10.
Cross-check
Equivalently, choose the 2 non-basic variables: C(5, 2) = 10. Both counts agree, so the maximum possible number of basic solutions is 10.