
58 Introduction to Linear Optimization and Extensions with MATLAB
R
In general, we have the following correspondence, which is a direct conse-
quence of Theorem 2.13.
Corollary 2.16
A vector x ∈ P = {x ∈ R
n
|Ax = b, x ≥ 0} is an extreme point if and only
if there is some matrix B so that x is a basic feasible solution with B as the
basis matrix.
2.3.1 Generating Basic Feasible Solutions
Theorem 2.13 says that any m columns of A that form a submatrix B that
is invertible and whose corresponding variables x
B
are such that Bx
B
= b
and x
B
> 0 will correspond to a basic feasible solution and therefore to an
extreme point. The total number of possible ways to select ...