可行解

可行解按字面意义就可以理解：可行的解。

什么是可行？符合所有约束条件就可行，否则不可行。

基本解与基本可行解

基本解和基本可行解，都可以认为是为了求解线性规划问题而发明的概念。

对于简单的线性规划问题，可以通过做图的方式来进行求解（就像高中的线性规划问题一样）。那线性规划不画图应该怎么求解呢？答案是按多元一次方程组来求。

基本解

线性规划的标准形式为：

min⁡c⊤x s.t. Ax=bx⩾0\begin{aligned} \min \quad& \boldsymbol{c}^{\top} \boldsymbol{x} \\ \text { s.t. }\quad & \boldsymbol{A x}=\boldsymbol{b} \\ & \boldsymbol{x} \geqslant \mathbf{0} \end{aligned}

其中, c∈Rn,b∈Rm,b⩾0,A∈Rm×n,m⩽n\boldsymbol{c} \in \mathbb{R}^n, \boldsymbol{b} \in \mathbb{R}^m, \boldsymbol{b} \geqslant \mathbf{0}, \boldsymbol{A} \in \mathbb{R}^{m \times n}, m \leqslant n 。

线性规划都可以转化为标准型来进行求解（不知道的看这篇文章）

约束条件中 Ax=b\boldsymbol{A x}=\boldsymbol{b} 是资源约束条件，假如有 mm 个约束条件，那 Ax=b\boldsymbol{A x}=\boldsymbol{b} 就有 mm 个方程。为了求 x\boldsymbol{x} 中各未知量的值，我们只要能求解这个方程组就可以了。多元一次方程组用消元法就可以求解，有唯一解的条件是未知量的个数刚好等于方程组的个数 ( n=mn=m )。

可实际情况往往是 n>mn>m 的。这种情况怎么做呢? 很简单，想办法让 n=mn=m ，这就用到了基 B\boldsymbol{B} 的概念。把 A\boldsymbol{A} 分成 nn 个列向量，从中任意取出了 mm 个，当然这 mm 个列向量必须是线性无关的，就是说不能有哪一个可以用剩下的 m−1m-1 个表示出来，要不相当于少取了一个。这 mm 个列向量就是一个基 B\boldsymbol{B} ，也叫作基矩阵 。从 A\boldsymbol{A} 中去除 B\boldsymbol{B} ，剩下的 n−mn-m 个列向量组成的矩阵就是非基 N\boldsymbol{N} ，或者叫非基矩阵。基 B\boldsymbol{B} 对应的变量 xB\boldsymbol{x_B} 叫作基变量 ，非基 N\boldsymbol{N} 对应的变量 xN\boldsymbol{x_N} 叫作非基变量 。第一个约束条件也就写成了:

[B,N][xBxN]=b[\boldsymbol{B}, \boldsymbol{N}]\left[\begin{array}{l} \boldsymbol{x_B} \\ \boldsymbol{x_N} \end{array}\right]=\boldsymbol{b}

只要把 xN\boldsymbol{x_N} 中的变量都设为 00 上式就变成了 BxB=b\boldsymbol{B}\boldsymbol{x_B}=\boldsymbol{b} , 这是 mm 个线性无关的 mm 元一次方程组，消元法就可以解出来 xB\boldsymbol{x_B} , 再带上 xN=0\boldsymbol{x_N}=\boldsymbol{0} 得出的 [B−1b,0]⊤[\boldsymbol{B}^{-1}\boldsymbol{b},\boldsymbol{0}]^{\top} 就是原约束条件 Ax=b\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b} 的解，这个解就是一个基本解。

基本可行解

基本解不一定是可行解，因为它只满足了第一个约束，不一定满足第二个约束。基本解中所有变量均非负（满足第二个约束条件）的才能满足所有约束，这种基本解叫作基本可行解。