【运筹学】线性规划 单纯形法 ( 基矩阵 | 基变量 | 非基矩阵 | 非基变量 | 矩阵分块形式 | 逆矩阵 | 基解 | 基可行解 )

I . 基矩阵 B

线性规划标准形式 , 约束方程的系数矩阵是 A A A , 如下 :

A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n ] A = \begin{bmatrix}\\\\ & a_{11} & a_{12} & \cdots & a_{1n} &\\\\ & a_{21} & a_{22} & \cdots & a_{2n} &\\\\ & \vdots & \vdots & \ddots & \vdots &\\\\ & a_{m1} & a_{m2} & \cdots & a_{mn} &\\\\ \end{bmatrix} A=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​​a11​a21​⋮am1​​a12​a22​⋮am2​​⋯⋯⋱⋯​a1n​a2n​⋮amn​​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​

该矩阵 A A A 是 m × n m \times n m×n 阶矩阵 , 有 m m m 行 , n n n 列 , 代表 m m m 个约束方程 , n n n 个变量 , 并且 n > m n > m n>m ;

基矩阵 B B B :

• ① 满秩子矩阵 : 矩阵 A A A 的 满秩子矩阵 B B B , 矩阵 B B B 的秩是 m m m ;
• ② 列向量线性无关 : 该矩阵中的 列向量 线性无关 , 即 每一列不能通过 乘以系数 加减的方式得到另外一列列向量 ,
• ③ 基矩阵 B B B : 这样的 系数矩阵 A A A 的 m × m m \times m m×m 阶满秩矩阵 B B B 就是基矩阵 ;

B = [ a 11 a 12 ⋯ a 1 m a 21 a 22 ⋯ a 2 m ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m m ] = [ P 1 P 2 ⋯ P m ] B= \begin{bmatrix}\\\\ & a_{11} & a_{12} & \cdots & a_{1m} &\\\\ & a_{21} & a_{22} & \cdots & a_{2m} &\\\\ & \vdots & \vdots & \ddots & \vdots &\\\\ & a_{m1} & a_{m2} & \cdots & a_{mm} &\\\\ \end{bmatrix} = \begin{bmatrix} & P_1 & P_2 & \cdots & P_m & \end{bmatrix} B=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​​a11​a21​⋮am1​​a12​a22​⋮am2​​⋯⋯⋱⋯​a1m​a2m​⋮amm​​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​=[​P1​​P2​​⋯​Pm​​​]

II . 基向量 P j P_j Pj​

基向量 :

• ① 概念 : 基矩阵 B B B 中的每个列向量 , 都是一个 基向量 , 记作 P j P_j Pj​ , 其中 j = 1 , 2 , ⋯   , m j = 1 , 2 , \cdots , m j=1,2,⋯,m ;
• ② 基向量个数 : 每个基矩阵中有 m m m 个列向量 ;

III . 基变量

基变量 : 每个基向量都对应一个变量 , 基向量是列向量 , 该列向量是 x j x_j xj​ 变量的系数组成 , 这个对应的 x j x_j xj​ 变量就是基变量 ;

IV . 非基矩阵 N N N

非基矩阵 N N N : 确定一个基矩阵 , 剩下的列向量就是 非基向量 , 这些非基向量 组成 非基矩阵 N N N ;

N = [ a 1 m + 1 a 1 m + 2 ⋯ a 1 n a 2 m + 1 a 2 m + 2 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m m + 1 a m m + 2 ⋯ a m n ] = [ P m + 1 P m + 2 ⋯ P n ] N= \begin{bmatrix}\\\\ & a_{1m+1} & a_{1m+2} & \cdots & a_{1n} &\\\\ & a_{2m+1} & a_{2m+2} & \cdots & a_{2n} &\\\\ & \vdots & \vdots & \ddots & \vdots &\\\\ & a_{mm+1} & a_{mm+2} & \cdots & a_{mn} &\\\\ \end{bmatrix} = \begin{bmatrix} & P_{m+1} & P_{m+2} & \cdots & P_{n} & \end{bmatrix} N=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​​a1m+1​a2m+1​⋮amm+1​​a1m+2​a2m+2​⋮amm+2​​⋯⋯⋱⋯​a1n​a2n​⋮amn​​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​=[​Pm+1​​Pm+2​​⋯​Pn​​​]

V . 系数矩阵分块形式 A = ( B N ) A = ( B N ) A=(BN)

系数矩阵 A A A , 可以写成分块形式 :

A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n ] = [ B N ] A = \begin{bmatrix}\\\\ & a_{11} & a_{12} & \cdots & a_{1n} &\\\\ & a_{21} & a_{22} & \cdots & a_{2n} &\\\\ & \vdots & \vdots & \ddots & \vdots &\\\\ & a_{m1} & a_{m2} & \cdots & a_{mn} &\\\\ \end{bmatrix} = \begin{bmatrix} & B & N & \end{bmatrix} A=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​​a11​a21​⋮am1​​a12​a22​⋮am2​​⋯⋯⋱⋯​a1n​a2n​⋮amn​​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​=[​B​N​​]

VI . 基变量向量 X B X_B XB​ 非基变量向量 X N X_N XN​ 及 分块形式

基变量向量 X B X_B XB​ :

X B = [ x 1 x 2 ⋮ x m ] X_B = \begin{bmatrix}\\\\ & x_1 &\\\\ &x_2&\\\\ &\vdots& \\\\ &x_m&\\\\ \end{bmatrix} XB​=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​​x1​x2​⋮xm​​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​

非基变量向量 X N X_N XN​ :

X B = [ x m + 1 x m + 2 ⋮ x n ] X_B = \begin{bmatrix}\\\\ & x_{m + 1} &\\\\ &x_{m + 2}&\\\\ &\vdots& \\\\ &x_n&\\\\ \end{bmatrix} XB​=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​​xm+1​xm+2​⋮xn​​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​

向量 X X X 可以写成 X B X_B XB​ 和 X N X_N XN​ 分块形式 :

X = [ x 1 x 2 ⋮ x n ] = [ x B x N ] X = \begin{bmatrix}\\\\ & x_1 &\\\\ &x_2&\\\\ &\vdots& \\\\ &x_n&\\\\ \end{bmatrix} = \begin{bmatrix}\\\\ & x_B &\\\\ &x_N &\\\\ \end{bmatrix} X=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​​x1​x2​⋮xn​​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​=⎣⎢⎢⎢⎢⎡​​xB​xN​​​⎦⎥⎥⎥⎥⎤​

VII . 分块形式的计算公式

矩阵分块形式方程代入 : 约束方程组 A X = b AX = b AX=b ;

b b b 是大于 0 0 0 的常数组成的向量 ;

将上述分块形式的 矩阵 A A A 和 矩阵 X X X 代入 上述 A X = b AX = b AX=b 公式 ;

A = [ B N ] A = \begin{bmatrix} & B & N & \end{bmatrix} A=[​B​N​​] X = [ X B X N ] X = \begin{bmatrix}\\\\ & X_B &\\\\ &X_N &\\\\ \end{bmatrix} X=⎣⎢⎢⎢⎢⎡​​XB​XN​​​⎦⎥⎥⎥⎥⎤​

得到

[ B N ] × [ X B X N ] = b \begin{bmatrix} & B & N & \end{bmatrix} \times \begin{bmatrix}\\\\ & X_B &\\\\ & X_N &\\\\ \end{bmatrix} = b [​B​N​​]×⎣⎢⎢⎢⎢⎡​​XB​XN​​​⎦⎥⎥⎥⎥⎤​=b

B X B + N X N = b BX_B + NX_N = b BXB​+NXN​=b

VIII . 逆矩阵

逆矩阵 : 其中矩阵 B B B 是满秩的 m × m m \times m m×m 阶矩阵 , 该矩阵是可逆的 ( 非奇异矩阵 ) , 必定存在一个 B − 1 B^{-1} B−1 , 使得 B × B − 1 = E B \times B^{-1} = E B×B−1=E

单位矩阵 : 这里的 矩阵 E E E 是单位矩阵 , 即 左上角到右下角 对角线 上 的元素 为 1 1 1 , 其它元素为 0 0 0 ; 主对角线 : 左上角 到 右下角 的对角线称为 主对角线 ; 单位矩阵 示例 如下 : E = [ 1 0 0 0 1 0 0 0 1 ] E=\begin{bmatrix} & 1 & 0 & 0 & \\\\ & 0 & 1 & 0 &\\\\ & 0 & 0 & 1 & \end{bmatrix} E=⎣⎢⎢⎢⎢⎡​​100​010​001​​⎦⎥⎥⎥⎥⎤​

IX . 解基变量

解基变量 :

B X B + N X N = b BX_B + NX_N = b BXB​+NXN​=b

将 N X N NX_N NXN​ 提到公式右边 :

B X B = b − N X N BX_B = b - NX_N BXB​=b−NXN​

公式两边乘以 B − 1 B^{-1} B−1 :

B X B × B − 1 = ( b − N X N ) × B − 1 BX_B \times B^{-1} = ( b - NX_N ) \times B^{-1} BXB​×B−1=(b−NXN​)×B−1

X B = B − 1 b − B − 1 N X N X_B = B^{-1}b - B^{-1}NX_N XB​=B−1b−B−1NXN​

X . 基解

引入基解 : 令非基变量 X N X_N XN​ 中所有变量为 0 0 0 , 此时上述公式为 :

X B = B − 1 b X_B = B^{-1}b XB​=B−1b 约束方程的解为 X = [ X B 0 ] = [ B − 1 b 0 ] X = \begin{bmatrix} & X_B & \\\\ & 0 & \end{bmatrix}=\begin{bmatrix} & B^{-1}b & \\\\ & 0 & \end{bmatrix} X=⎣⎡​​XB​0​​⎦⎤​=⎣⎡​​B−1b0​​⎦⎤​ 上述解为基解 , 矩阵 B B B 是满秩的 , 其秩为 m m m , 将非基变量赋值 0 0 0 , 剩余的 m m m 个变量 , m m m 个等式 , 必能解出一组唯一解 ; 即 ∑ j = 1 m p j x j = b \sum_{j = 1}^{m}p_j x_j = b j=1∑m​pj​xj​=b 方程组有唯一解

X B = [ x 1 x 2 ⋮ x m ] X_B = \begin{bmatrix} & x_1 & \\\\ & x_2 &\\\\ & \vdots &\\\\ & x_m & \end{bmatrix} XB​=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​​x1​x2​⋮xm​​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​ 该解 X B X_B XB​ 是线性规划的一个基解 ;

XI . 基可行解

基可行解 : 如果上述解出的基解 X B X_B XB​ , 满足线性规划数学模型 标准形式 的变量非负约束 , 即所有的变量都大于等于 0 0 0 , 该解称为基可行解 ;

并不是所有的基解都是基可行解 , 只有部分基解是基可行解 ;