In the theory of linear programming, a basic feasible solution (BFS) is a solution with a minimal set 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 simplex algorithm, which essentially travels from one BFS to another until an optimal solution is found.^[1]

Definitions

Properties

1. A BFS is determined only by the constraints of the LP (the matrix ${\displaystyle A}$ and the vector ${\displaystyle \mathbf {b} }$); it does not depend on the optimization objective.

2. By definition, a BFS has at most m non-zero variables and at least n-m zero variables. A BFS can have less than m non-zero variables; in that case, it can have many different bases, all of which contain the indices of its non-zero variables.

3. A feasible solution ${\displaystyle \mathbf {x} }$ is basic if-and-only-if the columns of the matrix ${\displaystyle A_{K}}$ are linearly independent, where K is the set of indices of the non-zero elements of ${\displaystyle \mathbf {x} }$.^[1]: 45

4. Each basis determines a unique BFS: for each basis B of m indices, there is at most one BFS ${\displaystyle \mathbf {x_{B}} }$ with basis B. This is because ${\displaystyle \mathbf {x_{B}} }$ must satisfy the constraint ${\displaystyle A_{B}\mathbf {x_{B}} =b}$, and by definition of basis the matrix ${\displaystyle A_{B}}$ is non-singular, so the constraint has a unique solution:

${\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}$

The opposite is not true: each BFS can come from many different bases. If the unique solution of ${\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}$ satisfies the non-negativity constraints ${\displaystyle \mathbf {x_{B}} \geq 0}$, then B is called a feasible basis.

5. If a linear program has an optimal solution (i.e., it has a feasible solution, and the set of feasible solutions is bounded), then it has an optimal BFS. This is a consequence of the Bauer maximum principle: the objective of a linear program is convex; the set of feasible solutions is convex (it is an intersection of hyperspaces); therefore the objective attains its maximum in an extreme point of the set of feasible solutions.

Since the number of BFS-s is finite and bounded by ${\displaystyle {\binom {n}{m}}}$, an optimal solution to any LP can be found in finite time by just evaluating the objective function in all ${\displaystyle {\binom {n}{m}}}$BFS-s. This is not the most efficient way to solve an LP; the simplex algorithm examines the BFS-s in a much more efficient way.

Examples

Consider a linear program with the following constraints:

${\displaystyle {\begin{aligned}x_{1}+5x_{2}+3x_{3}+4x_{4}+6x_{5}&=14\\x_{2}+3x_{3}+5x_{4}+6x_{5}&=7\\\forall i\in \{1,\ldots ,5\}:x_{i}&\geq 0\end{aligned}}}$

The matrix A is:

${\displaystyle A={\begin{pmatrix}1&5&3&4&6\\0&1&3&5&6\end{pmatrix}}~~~~~\mathbf {b} =(14~~7)}$

Here, m=2 and there are 10 subsets of 2 indices, however, not all of them are bases: the set {3,5} is not a basis since columns 3 and 5 are linearly dependent.

The set B={2,4} is a basis, since the matrix ${\displaystyle A_{B}={\begin{pmatrix}5&4\\1&5\end{pmatrix}}}$ is non-singular.

The unique BFS corresponding to this basis is ${\displaystyle x_{B}=(0~~2~~0~~1~~0)}$.

Geometric interpretation

The set of all feasible solutions is an intersection of hyperspaces. Therefore, it is a convex polyhedron. If it is bounded, then it is a convex polytope. Each BFS corresponds to a vertex of this polytope.^{[1]: 53–56}

Basic feasible solutions for the dual problem

As mentioned above, every basis B defines a unique basic feasible solution ${\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}$ . In a similar way, each basis defines a solution to the dual linear program:

minimize ${\textstyle \mathbf {b^{T}} \mathbf {y} }$

subject to ${\displaystyle A^{T}\mathbf {y} \geq \mathbf {c} }$.

The solution is ${\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c}$.

Finding an optimal BFS

There are several methods for finding a BFS that is also optimal.

Using the simplex algorithm

In practice, the easiest way to find an optimal BFS is to use the simplex algorithm. It keeps, at each point of its execution, a "current basis" B (a subset of m out of n variables), a "current BFS", and a "current tableau". The tableau is a representation of the linear program where the basic variables are expressed in terms of the non-basic ones:^[1]: 65

$${\displaystyle {\begin{aligned}x_{B}&=p+Qx_{N}\\z&=z_{0}+r^{T}x_{N}\end{aligned}}}$$

where ${\displaystyle x_{B}}$ is the vector of m basic variables, ${\displaystyle x_{N}}$ is the vector of n non-basic variables, and ${\displaystyle z}$ is the maximization objective. Since non-basic variables equal 0, the current BFS is ${\displaystyle p}$, and the current maximization objective is ${\displaystyle z_{0}}$.

If all coefficients in ${\displaystyle r}$ are negative, then ${\displaystyle z_{0}}$ is an optimal solution, since all variables (including all non-basic variables) must be at least 0, so the second line implies ${\displaystyle z\leq z_{0}}$.

If some coefficients in ${\displaystyle r}$ are positive, then it may be possible to increase the maximization target. For example, if ${\displaystyle x_{5}}$ is non-basic and its coefficient in ${\displaystyle r}$ is positive, then increasing it above 0 may make ${\displaystyle z}$ larger. If it is possible to do so without violating other constraints, then the increased variable becomes basic (it "enters the basis"), while some basic variable is decreased to 0 to keep the equality constraints and thus becomes non-basic (it "exits the basis").

If this process is done carefully, then it is possible to guarantee that ${\displaystyle z}$ increases until it reaches an optimal BFS.

External links

• How to move from an optimal feasible solution to an optimal basic feasible solution. Paul Robin, Operations Research Stack Exchange.

References