Basic Feasible Point (BFP)

page=384

---

A vector $x$ is a basic feasible point if

• $x$ is Feasible
• There exists a subset $\mathcal{B}$ of the index set $\{1,2,\dots ,n\}$ such that
  • $\mathcal{B}$ contains exactly $m$ indices
  • $i\notin \mathcal{B}\to x_i=0$ (that is, the bound $x_i\ge 0$ can be inactive only if $i\in \mathcal{B}$).
  • the $m\times m$ matrix $B$ is defined by $B=[A_i{]}_{i\in \mathcal{B}}$, and is nonsingular, and $A_i$ is the $i$‘th column of $A$.

$\mathcal{B}(x)$ is called a basis for the LP, and the indices not in $\mathcal{B}(x)$ are called $\mathcal{N}(x)$.