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

2023-03-27 17:32:02 浏览数 (2)

文章目录
  • I . 基矩阵 B
  • II . 基向量
P_j
  • III . 基变量
  • IV . 非基矩阵
N
  • V . 系数矩阵分块形式
A = ( B N )
  • VI . 基变量向量
X_B

非基变量向量

X_N

及 分块形式

  • VII . 分块形式的计算公式
  • VIII . 逆矩阵
  • IX . 解基变量
  • X . 基解
  • XI . 基可行解

I . 基矩阵 B

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

A

, 如下 :

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

是

m times n

阶矩阵 , 有

m

行 ,

n

列 , 代表

m

个约束方程 ,

n

个变量 , 并且

n > m

;

基矩阵

B

:

  • ① 满秩子矩阵 : 矩阵
A

的 满秩子矩阵

B

, 矩阵

B

的秩是

m

;

  • ② 列向量线性无关 : 该矩阵中的 列向量 线性无关 , 即 每一列不能通过 乘以系数 加减的方式得到另外一列列向量 ,
  • ③ 基矩阵
B

: 这样的 系数矩阵

A

的

m times m

阶满秩矩阵

B

就是基矩阵 ;

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}
II . 基向量
P_j

基向量 :

  • ① 概念 : 基矩阵
B

中的每个列向量 , 都是一个 基向量 , 记作

P_j

, 其中

j = 1 , 2 , cdots , m

;

  • ② 基向量个数 : 每个基矩阵中有
m

个列向量 ;

III . 基变量

基变量 : 每个基向量都对应一个变量 , 基向量是列向量 , 该列向量是

x_j

变量的系数组成 , 这个对应的

x_j

变量就是基变量 ;

IV . 非基矩阵
N

非基矩阵

N

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

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}
V . 系数矩阵分块形式
A = ( B N )

系数矩阵

A

, 可以写成分块形式 :

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}
VI . 基变量向量
X_B

非基变量向量

X_N

及 分块形式

基变量向量

X_B

:

X_B = begin{bmatrix}\\ & x_1 &\\ &x_2&\\ &vdots& \\ &x_m&\\ end{bmatrix}

非基变量向量

X_N

:

X_B = begin{bmatrix}\\ & x_{m 1} &\\ &x_{m 2}&\\ &vdots& \\ &x_n&\\ end{bmatrix}

向量

X

可以写成

X_B

和

X_N

分块形式 :

X = begin{bmatrix}\\ & x_1 &\\ &x_2&\\ &vdots& \\ &x_n&\\ end{bmatrix} = begin{bmatrix}\\ & x_B &\\ &x_N &\\ end{bmatrix}
VII . 分块形式的计算公式

矩阵分块形式方程代入 : 约束方程组

AX = b

;

b

是大于

0

的常数组成的向量 ;

将上述分块形式的 矩阵

A

和 矩阵

X

代入 上述

AX = b

公式 ;

A = begin{bmatrix} & B & N & end{bmatrix}
X = begin{bmatrix}\\ & X_B &\\ &X_N &\\ end{bmatrix}

得到

begin{bmatrix} & B & N & end{bmatrix} times begin{bmatrix}\\ & X_B &\\ & X_N &\\ end{bmatrix} = b
BX_B NX_N = b
VIII . 逆矩阵

逆矩阵 : 其中矩阵

B

是满秩的

m times m

阶矩阵 , 该矩阵是可逆的 ( 非奇异矩阵 ) , 必定存在一个

B^{-1}

, 使得

B times B^{-1} = E

单位矩阵 : 这里的 矩阵

E

是单位矩阵 , 即 左上角到右下角 对角线 上 的元素 为

1

, 其它元素为

0

; 主对角线 : 左上角 到 右下角 的对角线称为 主对角线 ; 单位矩阵 示例 如下 :

E=begin{bmatrix} & 1 & 0 & 0 & \\ & 0 & 1 & 0 &\\ & 0 & 0 & 1 & end{bmatrix}
IX . 解基变量

解基变量 :

BX_B NX_N = b

将

NX_N

提到公式右边 :

BX_B = b - NX_N

公式两边乘以

B^{-1}

:

BX_B times B^{-1} = ( b - NX_N ) times B^{-1}
X_B = B^{-1}b - B^{-1}NX_N
X . 基解

引入基解 : 令非基变量

X_N

中所有变量为

0

, 此时上述公式为 :

X_B = B^{-1}b

约束方程的解为

X = begin{bmatrix} & X_B & \\ & 0 & end{bmatrix}=begin{bmatrix} & B^{-1}b & \\ & 0 & end{bmatrix}

上述解为基解 , 矩阵

B

是满秩的 , 其秩为

m

, 将非基变量赋值

0

, 剩余的

m

个变量 ,

m

个等式 , 必能解出一组唯一解 ; 即

sum_{j = 1}^{m}p_j x_j = b

方程组有唯一解

X_B = begin{bmatrix} & x_1 & \\ & x_2 &\\ & vdots &\\ & x_m & end{bmatrix}

该解

X_B

是线性规划的一个基解 ;

XI . 基可行解

基可行解 : 如果上述解出的基解

X_B

, 满足线性规划数学模型 标准形式 的变量非负约束 , 即所有的变量都大于等于

0

, 该解称为基可行解 ;

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

vi 变量

0 人点赞