【运筹学】线性规划问题的解 ( 可行解 | 可行域 | 最优解 | 秩的概念 | 极大线性无关组 | 向量秩 | 矩阵秩 | 基 | 基变量 | 非基变量 | 基解 | 基可行解 | 可行基 )

韩曙亮

发布于 2023-03-27 17:28:19

1.7K0

发布于 2023-03-27 17:28:19

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录
I . 线性规划问题解
II . 可行解与可行域
III . 最优解
IV . 秩的概念
V . 基的概念
VI . 基变量与非基变量
VII . 基解
VIII . 基可行解与可行基
IX . 示例求基矩阵

I . 线性规划问题解

下面是一个线性规划数学模型的标准形式 :

1. 决策变量个数 : 线性规划数学模型中有

个决策变量 ;

2. 约束方程个数 : 该模型中有

个约束方程 ;

\begin{array}{lcl} max Z = \sum_{j = 1}^n c_j x_j && ① 目标函数 \\ \\ s.t \begin{cases} \sum_{j = 1}^n a_{ij} x_j = b_i ( i = 1, 2, \cdots , m ) && ② 约束方程 \\ \\ x_j \geq 0 , j = 1 , 2 , \cdots , n && ③ 变量约束 \end{cases} \\ \end{array}

线性规划的解 : 满足约束条件 ② 和 ③ 有很多解 , 这些解中肯定有一个或多个解 , 使 ① 目标函数有最大值 ;

II . 可行解与可行域

可行解 : 满足约束方程 , 变量约束的解是可行解 ;

可行域 : 所有的可行解集合是可行域 ;

III . 最优解

首先这个解必须是可行解 , 在可行解的基础上 , 使目标函数达到最大值的解是最优解 ;

IV . 秩的概念

1. 向量概念 :

① 数学概念 : 空间中的箭头 , 二维或三维 , 由方向和长度两种属性 ;
② 计算机概念 : 有序的数字列表 , 这里使用的就是这种概念 ,

维向量有

个数字组成 ;

2. 向量组 : 由多个向量组成的结构 , 下面的

\alpha_1

就是一个

维向量 , 该向量由

个数字组成 (

n > 0

) ; 多个这种向量组成向量组 ;

3. 极大线性无关组 : 向量组

中 , 如果有一部分组

\alpha_1 , \alpha_2 , \cdots , \alpha_3

满足下面两个条件 :

① 部分组线性无关 :

\alpha_1 , \alpha_2 , \cdots , \alpha_3

是线性无关的 ;

② 部分组线性表示 :

中的每个向量都可以由

\alpha_1 , \alpha_2 , \cdots , \alpha_3

此部分组中的一个或多个线性表示 ; ( 如向量组

\beta = 2\alpha_1 + \alpha_2

)

\alpha_1 , \alpha_2 , \cdots , \alpha_3

称为向量

的极大无关组 ;

4. 向量的秩 : 一个向量组的极大线性无关组所包含的向量个数 , 是向量组的秩 ;

① 如果向量组中的向量都是

向量 , 那么其秩为

;

② 向量组

\alpha_1 , \alpha_2 , \cdots , \alpha_n

的秩记为

rank \{ \alpha_1 , \alpha_2 , \cdots , \alpha_3 \}

5. 矩阵的秩 :

① 方阵的秩 : 方阵是行数和列数相等的矩阵 , 其列秩和行秩是相等的 , 其行数 = 列数 = 秩 ;
② 矩阵的秩 :

m \times n

矩阵的秩最大取值是

和

中较小的那个值 , 即

min(m , n)

;

③ 满秩 : 如果矩阵的秩等于

min(m , n)

, 那么该矩阵被称为有满秩 , 是满秩矩阵 ;

④ 欠秩 : 反之如果矩阵的秩小于

min(m , n)

, 那么该矩阵称为秩不足 ( 欠秩 ) ;

V . 基的概念

系数矩阵 : 约束方程的系数可以组成一个

m \times n

阶矩阵 , 即

行 ,

列 , 代表有

个约束方程 , 每个约束方程有

个变量 ;

基 :

① 矩阵秩 : 设

为上述

m \times n

阶系数矩阵

( m < n )

, 其秩为

; ( 该矩阵的秩的最大取值是

min(m , n)

)

② 满秩矩阵 : 矩阵

是矩阵

的

阶满秩子矩阵 , 其中

|B| \not=0

B= \begin{bmatrix} & a_{11} & \cdots & a_{1m} \\ \\ &\vdots &\vdots &\vdots \\ \\ & a_{m1} & \cdots & a_{mm} \end{bmatrix} = ( p_1 \cdots p_m )

③ 基引入 : 则称

是线性规划问题的一个基 ;

矩阵的阶数 :

行

列矩阵称为

m \times n

阶矩阵 ;

行

列方阵 , 称为

阶矩阵 ;

阶满秩子矩阵 :

阶 : 是指矩阵是

m \times m

阶矩阵 , 其实一个

行

列的方阵 ;

② 满秩 : 该矩阵的最大秩是

min(m , m)

, 其秩为

时 , 是满秩矩阵 ;

③ 子矩阵 : 该矩阵

(

m \times

m 阶矩阵 ) 是矩阵

(

m \times

n 阶矩阵 ) 的子矩阵 ;

VI . 基变量与非基变量

基向量 : 设有以下系数矩阵 :

B= \begin{bmatrix} & a_{11} & \cdots & a_{1m} \\ \\ &\vdots &\vdots &\vdots \\ \\ & a_{m1} & \cdots & a_{mm} \end{bmatrix} = ( p_1 \cdots p_m )

称矩阵

中的每个列向量

P_j ( j = 1, 2 , \cdots , m )

为基向量 ;

基变量 : 与基向量

P_j

对应的变量

x_j

称为基变量 ;

非基变量 : 基变量之外的其它变量 , 称为非基变量 ;

VII . 基解

基解 :

① 确定基 : 确定一个基

, 该矩阵是系数矩阵

的满秩子矩阵 , 即一个

m \times m

阶矩阵 ;

② 处理非基变量 : 将非基变量设置成

;

③ 解出基解 : 将基代入约束方程 , 解出对应的变量值 , 即基解 ;
④ 基解个数 : 基解中变量取值非

个数 , 小于等于约束方程个数

, 基解的总数不超过

C_n^m

排列组合说明 :

n > m

, 从

个变量中取

个 , 这是集合的组合问题 , 从

元集中取

个元素的个数 , 即

C(n, m) = C_n^m =\frac{P( n, m )}{m!}=\frac{n!}{(n-m)!m!}

, 如果要求顺序 , 就是排列问题

P( n, m ) = \frac{n!}{(n-m)!}

;

阶满秩子矩阵 : 基是满秩子矩阵

阶 : 是指矩阵是

m \times m

阶矩阵 , 其实一个

行

列的方阵 ;

② 满秩 : 该矩阵的最大秩是

min(m , m)

, 其秩为

时 , 是满秩矩阵 ;

③ 子矩阵 : 该矩阵

(

m \times

m 阶矩阵 ) 是矩阵

(

m \times

n 阶矩阵 ) 的子矩阵 ;

VIII . 基可行解与可行基

基可行解 : 解出的基解 , 有一部分满足变量的非负约束 , 即解大于等于

, 这些解称为基可行解 ;

有些解小于

的 , 显然不满足大于等于

的条件 , 这些基解不是可行解 , 没有用处 ;

可行基 : 基可行解对应的基 , 称为可行基 ;

下面的文氏图描述的是非可行解 , 基解 , 可行解的集合关系 ; 总体分为可行解与非可行解 , 基解中一部分是可行解 , 一部分是非可行解

IX . 示例求基矩阵

求下列线性规划问题的基矩阵 :

\begin{array}{lcl} max Z = 4x_1 - 2x_2 - x_3 \\\\ \begin{cases} 5x_1 + x_2 - x_3 + x_4 = 3 \\\\ -10 x_1 + 6x_2 + 2x_3 +x_5 = 2 \\\\ x_j \geq 0 , j = 1 , \cdots , 5 \end{cases} \end{array}

解 :

该约束方程 , 共有

x_1 , x_2 , x_3 , x_4 , x_5

, 五个变量 ;

将约束方程补全变量为 :

\begin{cases} 5x_1 + x_2 - x_3 + x_4 + 0x_5= 3 \\\\ -10 x_1 + 6x_2 + 2x_3 + 0x_4 +x_5 = 2 \end{cases}

其系数矩阵为 :

A=\begin{bmatrix} 5 & 1 & -1 & 1 & 0 \\\\ -10 & 6 & 2 & 0 & 1 \end{bmatrix}

该系数矩阵的秩为

min(2, 5) = 2

, 矩阵的基为 2阶满秩子矩阵 ; 每一列都是一个向量 , 共有 5 个向量 , 选择其中 2 个 , 该问题是从 5 元集中选取 2 个的组合问题 ; 其基的组合方式有

C(5 , 2)

种 :

C(5 , 2) = \frac{5!}{2! ( 5 - 2 )!} = \frac{5 \times 4 \times 3 \times 2}{2\times 3\times 2} = 10

2阶子矩阵有

种选取方式 ; 基的要求还需要满秩 , 2阶的满秩子矩阵才是基 , 满秩即其列向量线性无关 , 两列向量不能使用线性表示 ;

① 子矩阵 1 : ( 不是基矩阵 )

B_1 = \begin{bmatrix} 5 &-1 \\ -10 & 2\end{bmatrix}

注意该矩阵第一列与第二列存在线性关系 , 第一列向量乘以

-5

即可得到第二列向量 ;

B_{11} = \begin{bmatrix} 5 \\ -10\end{bmatrix} B_{12} = \begin{bmatrix} -1 \\ 2\end{bmatrix}

B_{12} = -5 \times B_{11}

该矩阵的秩为

, 不是满秩的 , 满秩秩为

min(2 , 2) = 2

, 因此该矩阵不是基矩阵 ;

② 子矩阵

2 \cdots 9

: 其它矩阵列向量之间没有线性关系 , 都是满秩的 , 且都为

阶满秩子矩阵

B_2 = \begin{bmatrix} 5 &1 \\ -10 & 6\end{bmatrix}

B_3 = \begin{bmatrix} 5 &0 \\ -10 & 1\end{bmatrix}

B_4 = \begin{bmatrix} 5 &1 \\ -10 & 0\end{bmatrix}

B_5 = \begin{bmatrix} 1 &-1 \\ 6 & 2\end{bmatrix}

B_6 = \begin{bmatrix} 1 &1 \\ 6 & 0\end{bmatrix}

B_7 = \begin{bmatrix} 1 & 0 \\ 6 & 1\end{bmatrix}

B_8 = \begin{bmatrix} -1 &1 \\ 2 & 0\end{bmatrix}

B_9 = \begin{bmatrix} -1 &0 \\ 2 & 1\end{bmatrix}

B_{10} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}

该矩阵

B_2 \cdots B_{10}

是系数矩阵的 2阶满秩子矩阵 ;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-11-05，如有侵权请联系 cloudcommunity@tencent.com 删除

变量

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度