In linear programming, what defines a basic feasible solution?

In linear programming, what defines a basic feasible solution?

• A. A feasible point where all variables are nonzero
• B. A feasible point where the objective value is maximized
• C. A feasible point where the number of positive variables equals the number of constraints, corresponding to a vertex
• D. A feasible point with all constraints satisfied with equality

Answer: (C)

The idea being tested is how a basic feasible solution (BFS) is formed in linear programming. A BFS corresponds to a corner point (vertex) of the feasible region, created when exactly as many independent constraints are binding as there are decision variables. In practice, you solve the system for a set of basic variables by turning the other variables to zero. If those basic variables come out nonnegative, you have a feasible BFS. When, in a nondegenerate case, all those basic variables are positive, their count equals the number of constraints, and the point sits at a vertex. That matches the described concept: a feasible point where the number of nonzero variables equals the number of constraints, corresponding to a vertex. Note that BFS can still occur with some basic variables equal to zero in degenerate cases, and optimality is about the objective function value, not the BFS definition itself.

The idea being tested is how a basic feasible solution (BFS) is formed in linear programming. A BFS corresponds to a corner point (vertex) of the feasible region, created when exactly as many independent constraints are binding as there are decision variables. In practice, you solve the system for a set of basic variables by turning the other variables to zero. If those basic variables come out nonnegative, you have a feasible BFS. When, in a nondegenerate case, all those basic variables are positive, their count equals the number of constraints, and the point sits at a vertex.

That matches the described concept: a feasible point where the number of nonzero variables equals the number of constraints, corresponding to a vertex. Note that BFS can still occur with some basic variables equal to zero in degenerate cases, and optimality is about the objective function value, not the BFS definition itself.