线性规划的约束条件定义了可行区域。如下图所示，可行区域是连续的，其中可行解有无穷多个。那么最优解适否存在。如果存在，如何找到它呢。因此，有必要研究一下最优解的性质。
可以证明如下结论。
info定理 最优解是可行区域的一个顶点。注意，顶点的数量是有限的。这样一来，最优解一定存在。可以枚举所有顶点，找到目标函数值最优的顶点。当然，枚举的效率太低，需要设计更好的算法。
但是，有一个概念没讲清楚。那就是，什么是顶点。从几何视角来看，顶点不难理解。接下里，需要从代数角度进行定义，这样才方便计算。
标准形 link考虑线性规划的标准形式：
$$
\begin{aligned}
\min~ & c^T x\\
\text{s.t.}~ & Ax=b\\
& x\geq 0
\end{aligned}
$$其中 $c, x \in \mathbb{R}^n$，$A\in\mathbb{R}^{m\times n}$，$b\in\mathbb{R}^m \geq \mathbf{0}$，$n\geq m$。
基矩阵 link注意 $A$ 是一个 $m$ 行 $n$ 列的矩阵，可以把它看成 $n$ 个 $m$ 维的列向量。
$$
A = [a_1, a_2, …, a_n]
$$
其中 $a_j \in \mathbb{R}^m$，$j=1,2,…n$。
接下来把 $A$ 拆成两个部分：
$$
A = [B \quad N]
$$
其中 $B$ 包含前 $m$ 列，因此 $B$ 是一个方阵，即 $B\in \mathbb{R}^{m\times m}$；而 $N$ 包含剩下的 $n-m$ 列，因此 $N \in \mathbb{R}^{m \times (n-m)}$。
假设 $A$ 是满秩矩阵，由于 $m\leq n$，那么它的秩是 $m$。考虑 $A$ 的列向量，它有一组基 (Basis)，即 $m$ 个线性无关的列向量。
如果 $B$ 不满秩，就把这组基换到前 $m$ 列，因此 $B$ 也是满秩的，或者说可逆的。我们称 $B$ 为基矩阵 (Basic Matrix)，称 $N$ 为非基矩阵 (Non-basic Matrix)。
基变量 link相应地，把 $x$ 拆成两个部分，即
$$
x = \begin{bmatrix}
x_B \\
x_N
\end{bmatrix}
$$
其中
$$
x_B = \begin{bmatrix}
x_1 \\
\vdots\\
x_m
\end{bmatrix}\quad
x_N = \begin{bmatrix}
x_{m+1} \\
\vdots\\
x_n
\end{bmatrix}
$$把 $x_B$ 对应的变量称为基变量， $x_N$ 对应的变量称为非基变量。
例子 link需要注意， $x_B$ 的下标与 $B$ 中的列一一对应。同理，$x_N$ 的下标与 $N$ 中的列一一对应。
举例说明。
$$
A = \begin{bmatrix}
1 & 0 & 0 & 4 & 0\\
0 & 2 & 0 & 0 & 5\\
0 & 0 & 3 & 0 & 0\\
\end{bmatrix}\quad
x = \begin{bmatrix}
x_1\\
x_2\\
\vdots\\
x_5
\end{bmatrix}
$$接下来划分 $B$ 和 $N$。
从 $A$ 的列中，任选三个线性无关的列作为 $B$。例如，选最后三列。
$$
B = \begin{bmatrix}
0 & 0 & 0\\
0 & 4 & 5 \\
3 & 0 & 0\\
\end{bmatrix}
$$那么 $N$ 就是剩下的两列。
$$
N = \begin{bmatrix}
1 & 0 \\
0 & 2 \\
0 & 0 \\
\end{bmatrix}
$$对应的 $x_B$ 和 $x_N$ 如下：
$$
x_B = \begin{bmatrix}
x_3 \\
x_4\\
x_5
\end{bmatrix}\quad
x_N = \begin{bmatrix}
x_1 \\
x_2
\end{bmatrix}
$$基本解 link考虑约束条件。把 $Ax=b$ 用分块矩阵来表示。
$$
\begin{aligned}
A x & =
[B \quad N]
\begin{bmatrix}
x_B\\
x_N
\end{bmatrix}\\
& = Bx_B + N x_N\\
& = b
\end{aligned}
$$即
$$
Bx_B + N x_N = b
$$
由于 $B$ 可逆，我们得到
$$
x_B = B^{-1}b - B^{-1}Nx_N
$$
令 $x_N = \mathbf{0}$，那么 $x_B = B^{-1}b$，于是
$$
z:= \begin{bmatrix}
x_B\\
x_N
\end{bmatrix} = \begin{bmatrix}
B^{-1}b\\
\mathbf{0}
\end{bmatrix}
$$
满足方程 $Az = b$。那么 $z$ 就称为基本解 (Basic Solution)。
基本可行解 link如果基本解 $z\geq \mathbb{0}$，那么它就是 基本可行解 (Basic Feasible Solution)。
可以证明，可行区域的顶点就是基本可行解。这两个概念是等价的。也就是说，要在基本可行解中找最优解。