Computing a Basic Feasible Solution from a Basis

A linear program in standard form is

$$A\mathbf{x} = \mathbf{b}, \qquad \mathbf{x} \geq \mathbf{0},$$

where $A$ is an $m \times n$ matrix with $m \leq n$, and $\mathbf{b} \in \mathbb{R}^m$. A basis is a set of $m$ column indices $\mathcal{B} = \{j_1, j_2, \ldots, j_m\}$ whose corresponding columns of $A$ form an invertible $m \times m$ matrix $B$. The variables $x_{j_1}, \ldots, x_{j_m}$ are the basic variables, collected into the vector $\mathbf{x}_B$, and the remaining $n - m$ variables are non-basic.

To compute the basic solution associated with $\mathcal{B}$:

1. Set every non-basic variable to $0$.
2. Solve

$$B\, \mathbf{x}_B = \mathbf{b}$$

for the values of the basic variables.

For example, consider

$$A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}, \qquad \mathbf{b} = \begin{bmatrix} 4 \\ 5 \end{bmatrix}$$

with basis $\mathcal{B} = \{1, 2\}$. The non-basic variable is $x_3$, so $x_3 = 0$. The basic-variable system is

$$\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 4 \\ 5 \end{bmatrix},$$

which gives $x_1 = 4$ and $x_2 = 5$. The basic solution is $\mathbf{x} = (4, 5, 0)$.