Basic feasible solution

In the theory of linear programming, a basic feasible solution (BFS) is, intuitively, a solution with a minimal number of non-zero variables. Geometrically, each BFS corresponds to a corner of the polyhedron of feasible solutions. If there exists an optimal solution, then there exists an optimal BFS. Hence, to find an optimal solution, it is sufficient to consider the BFS-s. This fact is used by the the simplex algorithm, which essentially travels from some BFS to another until an optimal one is found.

Definition

To define a BFS, we first present the linear program in the so-called equational form:

maximize ${\textstyle \mathbf {c^{T}} \cdot \mathbf {x} }$

subject to $A\mathbf {x} =\mathbf {b}$ and $\mathbf {x} \geq 0$

where:

• $\mathbf {c^{T}}$ and $\mathbf {x}$ are vectors of size n (the number of variables);
• $\mathbf {b}$ is a vector of size m (the number of constraints);
• $A$ is an m-by-n matrix;
• $\mathbf {x} \geq 0$ means that all variables are non-negative.

Any linear program can be converted into an equational form by adding slack variables.

As a preliminary clean-up step, we verify that:

• The system $A\mathbf {x} =\mathbf {b}$ has at least one solution (otherwise the whole LP has no solution and there is nothing more to do);
• All m rows of the matrix $A$ are linearly independent, i.e., its rank is m (otherwise we can just delete redundant rows without changing the LP).

Typically m < n, so the system $A\mathbf {x} =\mathbf {b}$ has many solutions; each such solution is called a feasible solution of the LP.

A basic feasible solution of the LP is a feasible solution $\mathbf {x}$ that satisfies the following properties: