A basic feasible solution of a linear programming problem is said to be ______…
2015
A basic feasible solution of a linear programming problem is said to be ______ if at least one of the basic variable is zero.
- A.
generate
- B.
degenerate
- C.
infeasible
- D.
unbounded
Attempted by 19 students.
Show answer & explanation
Correct answer: B
Answer: degenerate.
Definition: A basic feasible solution is called degenerate if at least one of its basic variables is equal to zero.
Why it matters: Degeneracy can create ties when selecting the leaving variable in the simplex method and may cause the algorithm to cycle unless anti-cycling rules (for example, Bland's rule) or perturbation are used.
Distinction from other terms: 'Infeasible' means no solution satisfies all constraints, and 'unbounded' means the objective can improve without bound. Neither describes a basic variable being zero.
Simple example: If x1 + x2 = 1 with x1, x2 ≥ 0 and the basic variables chosen include x1 and a slack variable, a basic feasible solution where x1 = 0 is degenerate because a basic variable (x1) is zero.