2.6 线性规划问题的基本解

通过引入剩余变量或松弛变量，可以把线性规划问题转换为它的标准型，即约束条件为线性等式，决策变量非负．

考虑方程\mathbf A\mathbf{x}=\mathbf b，其中\text{rank}(\mathbf A)=m，为了求解这类问题，可以从\mathbf A中选取m个线性无关的向量组成方阵\mathbf B，对\mathbf A的列向量重新排序，可以使\mathbf B中的列向量位于\mathbf A的前m列，即\mathbf A可以写为分块矩阵\mathbf{A=(B,N)}，其中\mathbf N是m\times(n−m)矩阵，它由\mathbf A中剩余的列向量组成．由于矩阵\mathbf B是非奇异的，因此求解方程组\mathbf {Bx_B}=\mathbf b可以得到唯一解\mathbf{x_B=B}^{−1}\mathbf b．

将上面描述性分析以公式推导表示，即

\begin{aligned}\mathbf{Ax} =\mathbf b &\overset{矩阵分块}{\Longrightarrow}\mathbf {B x_B +N  x_N} =\mathbf b\\ &\overset{左乘B^{-1}}{\Longrightarrow}\mathbf {x_B +B^{-1}N  x_N} =\mathbf{B}^{-1}\mathbf b\\ &\overset{\qquad}\Longrightarrow \mathbf{x_B} = \mathbf{B}^{-1}\mathbf b -\mathbf B^{-1}\mathbf N\mathbf {x_N} \\ &\overset{令 \mathbf {x_N}=\mathbf 0}{\Longrightarrow} \mathbf{\bar x} =  \begin{pmatrix}\mathbf B^{-1}\mathbf b \\ \mathbf 0\end{pmatrix}. \end{aligned}

称\mathbf{\bar x} =  \begin{pmatrix}\mathbf B^{-1}\mathbf b \\ \mathbf 0\end{pmatrix}是\mathbf{Ax=b}在基\mathbf B下的基本解，向量\mathbf{x_B}中的元素称为基变量，\mathbf B中的列向量称为基向量，\mathbf B称为基矩阵，\mathbf {x_N}中的元素称为非基变量。若\mathbf B^{-1}\mathbf b中的元素均非负，则称基本解\mathbf{\bar x}为基本可行解，若\mathbf B^{-1}\mathbf b中的元素至少有一个为0，即基本可行解中存在“零”的基变量，则称基本解\mathbf{\bar x}为退化的基本可行解．

例1  考虑问题\min z =_1−_2\\ \text{s.t.}\begin{cases}2_1−_2−_3 =2\\ _1−2_2 +_4 =2\\ _1+_2 +_5=5\\ _≥0, =1,2,3,4,5 \end{cases}，其中\mathbf A=(\mathbf p_1,\mathbf p_2,\mathbf p_2,\mathbf p_4,\mathbf p_5)=\begin{pmatrix}2&−1&−1&0&0\\1&−2&0&1&0\\1&1&0&0&1\end{pmatrix}．若基矩阵取为

-\mathbf B_1=(\mathbf p_3,\mathbf p_4,\mathbf p_5)=\begin{pmatrix}−1&0&0\\0&1&0\\0&0&1\end{pmatrix}时，其对应的基本解为\mathbf x^{(1)}=\mathbf B_1^{−1}\mathbf b=(0,0,−2,2,5)^\top，不是基本可行解；

-\mathbf B_2=(\mathbf p_1,\mathbf p_4,\mathbf p_5)=\begin{pmatrix}2&0&0\\1&1&0\\1&0&1\end{pmatrix}时，其对应的基本解为\mathbf x^{(2)}=\mathbf B_2^{−1} \mathbf b=(1,0,0,1,4)^\top，是基本可行解．