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$ .

Each intersection of two boundaries corresponds to a basic solution. The feasible ones (filled) are the basic feasible solutions; the hollow ones are basic but infeasible.

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.

Restricting attention to basic feasible solutions loses nothing: by corner point optimality, an LP with a finite optimum has an optimal corner, and simplex moves from one basic feasible solution to a better adjacent one until the optimality test is passed.

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: 20 October 2026 03:02