可行解、基本解、基本可行解

可行解

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

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

基本解与基本可行解

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

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

基本解

线性规划的标准形式为： \[ \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} \]

其中, \(\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\) 。

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

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

可实际情况往往是 \(n>m\) 的。这种情况怎么做呢? 很简单，想办法让 \(n=m\) ，这就用到了基 \(\boldsymbol{B}\) 的概念。把 \(\boldsymbol{A}\) 分成 \(n\) 个列向量，从中任意取出了 \(m\) 个，当然这 \(m\) 个列向量必须是线性无关的，就是说不能有哪一个可以用剩下的 \(m-1\) 个表示出来，要不相当于少取了一个。这 \(m\) 个列向量就是一个基 \(\boldsymbol{B}\) ，也叫作基矩阵 。从 \(\boldsymbol{A}\) 中去除 \(\boldsymbol{B}\) ，剩下的 \(n-m\) 个列向量组成的矩阵就是非基 \(\boldsymbol{N}\) ，或者叫非基矩阵。基 \(\boldsymbol{B}\) 对应的变量 \(\boldsymbol{x_B}\) 叫作基变量 ，非基 \(\boldsymbol{N}\) 对应的变量 \(\boldsymbol{x_N}\) 叫作非基变量 。第一个约束条件也就写成了: \[ [\boldsymbol{B}, \boldsymbol{N}]\left[\begin{array}{l} \boldsymbol{x_B} \\ \boldsymbol{x_N} \end{array}\right]=\boldsymbol{b} \] 只要把 \(\boldsymbol{x_N}\) 中的变量都设为 \(0\) 上式就变成了 \(\boldsymbol{B}\boldsymbol{x_B}=\boldsymbol{b}\) , 这是 \(m\) 个线性无关的 \(m\) 元一次方程组，消元法就可以解出来 \(\boldsymbol{x_B}\) , 再带上 \(\boldsymbol{x_N}=\boldsymbol{0}\) 得出的 \([\boldsymbol{B}^{-1}\boldsymbol{b},\boldsymbol{0}]^{\top}\) 就是原约束条件 \(\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}\) 的解，这个解就是一个基本解。

基本可行解

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