Basic Feasible Solution¶

Definition¶

A basic feasible solution is a basic solution of an equality-form LP with all its variables nonnegative. A basic solution with a negative variable is a basic infeasible solution.

Interpretation¶

A basic feasible solution is a corner point of the feasible region written in algebraic form: a basic solution whose values, slacks included, are all nonnegative. The simplex method keeps this combination of structure and feasibility at every step, so it can improve the objective without leaving the allowed region.

A shaded pentagon of feasible points bounded by three constraint lines and the axes, with its five corners filled as basic feasible solutions and four hollow intersection points outside it as basic but infeasible.

The five filled points $(0,0)$ , $(40,0)$ , $(40,20)$ , $(20,60)$ and $(0,80)$ are the corners of the region of the Giapetto model, and these are its basic feasible solutions. The four hollow points are also intersections of two boundary lines, so they are basic solutions, but they lie outside the region: at $(40,40)$ , for instance, $s_1=100-2\cdot40-40=-20$ $- 20$ .

Two separate tests are involved. A solution is basic when the nonbasic variables are set to zero and the equations are solved for the rest; it is feasible when every resulting value satisfies its nonnegativity constraint. A point strictly inside the region passes the second test but not the first, and a hollow point passes the first but not the second.

For a feasible equality-form LP with nonnegative variables and a finite optimum, corner point optimality guarantees an optimal basic feasible solution. A primal simplex pivot preserves feasibility and does not worsen the objective. In a degenerate pivot, the basis can change without moving the point or improving its value; termination requires a suitable rule to prevent cycling. The optimality test identifies a basis at which no further improvement is needed.

A common slip is to check only the decision variables. The hollow point $(50,0)$ has $x_s,x_t\ge0$ $0$ , yet $s_3=40-50=-10$ $- 10$ , so it is not feasible.

Key Results¶

Nonbasic variables are set to zero; feasibility is checked through the resulting basic values.
A basic variable may be zero in a degenerate solution.
For the course LPs with a finite optimum, an optimal basic feasible solution exists.

Examples¶

The filled points in the illustrated region $F$ are its feasible corners; the hollow boundary intersections violate at least one nonnegativity restriction in the augmented system.

$(x_1,x_2,s_1,s_2)=(0,0,10,15)$ is basic feasible in the main simplex example.
$(0,10,0,-15)$ is basic but infeasible.

Prerequisites¶

Sources¶

OR Modelling · Week 2

Aliases: BFS, BF solution

Last updated: 27 October 2026 11:52