文章目录
I . 基矩阵 BII . 基向量
P
j
P_j
PjIII . 基变量IV . 非基矩阵
N
N
NV . 系数矩阵分块形式
A
=
(
B
N
)
A = ( B N )
A=(BN)VI . 基变量向量
X
B
X_B
XB 非基变量向量
X
N
X_N
XN 及 分块形式VII . 分块形式的计算公式VIII . 逆矩阵IX . 解基变量X . 基解XI . 基可行解
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=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡a11a21⋮am1a12a22⋮am2⋯⋯⋱⋯a1na2n⋮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=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡a11a21⋮am1a12a22⋮am2⋯⋯⋱⋯a1ma2m⋮amm⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤=[P1P2⋯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+1a2m+1⋮amm+1a1m+2a2m+2⋮amm+2⋯⋯⋱⋯a1na2n⋮amn⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤=[Pm+1Pm+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=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡a11a21⋮am1a12a22⋮am2⋯⋯⋱⋯a1na2n⋮amn⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤=[BN]
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=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡x1x2⋮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+1xm+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=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡x1x2⋮xn⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎡xBxN⎦⎥⎥⎥⎥⎤
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=[BN]
X
=
[
X
B
X
N
]
X = \begin{bmatrix}\\\\ & X_B &\\\\ &X_N &\\\\ \end{bmatrix}
X=⎣⎢⎢⎢⎢⎡XBXN⎦⎥⎥⎥⎥⎤
得到
[
B
N
]
×
[
X
B
X
N
]
=
b
\begin{bmatrix} & B & N & \end{bmatrix} \times \begin{bmatrix}\\\\ & X_B &\\\\ & X_N &\\\\ \end{bmatrix} = b
[BN]×⎣⎢⎢⎢⎢⎡XBXN⎦⎥⎥⎥⎥⎤=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=⎣⎢⎢⎢⎢⎡100010001⎦⎥⎥⎥⎥⎤
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=⎣⎡XB0⎦⎤=⎣⎡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∑mpjxj=b 方程组有唯一解
X
B
=
[
x
1
x
2
⋮
x
m
]
X_B = \begin{bmatrix} & x_1 & \\\\ & x_2 &\\\\ & \vdots &\\\\ & x_m & \end{bmatrix}
XB=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡x1x2⋮xm⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤ 该解
X
B
X_B
XB 是线性规划的一个基解 ;
XI . 基可行解
基可行解 : 如果上述解出的基解
X
B
X_B
XB , 满足线性规划数学模型 标准形式 的变量非负约束 , 即所有的变量都大于等于
0
0
0 , 该解称为基可行解 ;
并不是所有的基解都是基可行解 , 只有部分基解是基可行解 ;