【运筹学】线性规划数学模型 ( 知识点回顾 | 可行解 | 最优解 | 阶梯型矩阵 | 阶梯型矩阵向量 | 基 | 基向量 | 基变量 | 非基变量 )

韩曙亮

发布于 2023-03-28 16:19:30

1.8K0

发布于 2023-03-28 16:19:30

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

文章目录

一、知识点回顾

1、线性规划三要素

线性规划三要素 :

决策变量 :

x_1 , x_2 , \cdots

目标条件 : 决策变量的线性函数 , 求最大值或最小值 ;
约束条件 : 一组由决策变量组成的等式或不等式 ;

2、线性规划一般形式

\begin{array}{lcl}max (min) z = \sum_{j=1}^{n}c_j x_j\\ \\ \begin{cases} \sum_{j=1}^{n} a_{ij}x_j = b_i & (i = 1 , 2 \cdots m) \\ \\x_j \geq 0 & (i = 1 , 2 \cdots n) \end{cases}\end{array}

3、线性规划标准形式

标准形式特点及转化步骤 : 按照如下顺序进行处理 ;

约束条件都是等式 , 且右侧常数

\geq 0

, 小于等于不等式加上松弛变量 , 大于等于不等式减去剩余变量 ;

决策变量

\geq 0

, 没有约束的变量

x_j = x_j' - x_j''

, 使用两个变量代替

个变量 ;

目标函数求最大值 , 如果是求最小值 , 目标函数

\times -1

;

线性规划标准形式 :

\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 \leq ( = \cdot \geq) b_i & i = 1,2,\cdots,m \\ \\ x_j \geq 0 & j= 1, 2,\cdots,n \end{cases}\end{array}

二、线性规划解、可行解、最优解

线性规划标准形式如下 :

\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}

可行解 : 满足约束条件的解 , 称为可行解 ;

可行域 : 所有的可行解组成的集合 , 称为可行域 ;

最优解 : 使目标函数达到最大值的可行解 , 称为最优解 ;

线性规划求解就是在可行解中找出一个最优解 ;

将线性规划转化为标准形式 , 就可以使用求解方程组的方法 , 求解线性规划的可行解 ;

三、阶梯型矩阵

拿到一个方程组

AX = B

, 其中

是

m \times n

的矩阵

是

n \times 1

维向量

是

m \times 1

维向量

这是线性规划的矩阵形式 , 参考【运筹学】线性规划数学模型 ( 三要素 | 一般形式 | 向量形式 | 矩阵形式 ) VI 线性规划数学模型矩阵形式

解上述方程组 , 使用高斯方程 , 高斯消元法 ;

将系数矩阵

和

做成一个矩阵

\bigl( A B \bigr)

, 进行行变换 , 消元成阶梯形式 , 此时可以判断该方程组是否有解 , 如果有 , 可以将所有的解解出来 , 求解时 , 阶梯元素很关键 ,

阶梯型矩阵参考 : 矩阵中每行的第一个不为零的元素 , 其左侧和下方全是 0 ;

高斯消元法示例 : 求解下面的方程组 ;

\begin{cases} x_1 + x_2 + x_3 = 8 \\ \\ x_2 - x_3 = 2 \end{cases}

\bigl( A B \bigr)

矩阵为

\begin{bmatrix} &1 & 1 & 1 & 8 & \\\\ &0 & 1 & -1 & 2 & \end{bmatrix}

找到阶梯型矩阵 : 前两列就是阶梯型矩阵 ;

前两列的矩阵

\begin{bmatrix} &1 & 1 & \\\\ &0 & 1 & \end{bmatrix}

就是特殊矩阵 , 分别是

x_1

和

x_2

对应的矩阵 ;

x_3

是特殊的变量 , 其可以任意取值的 , 当

x_3

取任意值时 , 通过阶梯型矩阵 , 可以计算出

x_1

和

x_2

的值 ;

假设

x_3

取值为

, 那么 :

x_2 = k + 2

x_1 = 6 - 2k

四、阶梯型矩阵向量

\begin{cases} x_1 + x_2 + x_3 = 8 \\ \\ x_2 - x_3 = 2 \end{cases}

方程组中有如下向量 :

x_1

对应的矩阵列向量

\begin{bmatrix} &1 & \\\\ &0 & \end{bmatrix}

称为

P_1

x_2

对应的矩阵列向量

\begin{bmatrix} &1 & \\\\ &1 & \end{bmatrix}

称为

P_2

x_3

对应的矩阵列向量

\begin{bmatrix} &1 & \\\\ &-1 & \end{bmatrix}

称为

P_3

写成向量形式

\bigl( \ P_1 \ P_2 \ P_3 \ b \ \bigr)

, 在上方程组的矩阵中 , 找到阶梯型矩阵后 , 阶梯型矩阵对应的向量

P_1

和

P_2

是特殊的 ;

\bigl( \ P_1 \ P_2 \ \bigr)

两个列向量构成了

2 \times 2

二阶方阵 , 该方阵是阶梯型矩阵 , 是可逆的 ;

可逆矩阵参考

上述方程组可以写成

P_1x_1 + P_2 x_2 + P_3x_3 = b

形式 ;

有如下计算推导过程 :

AX = B

P_1x_1 + P_2 x_2 + P_3x_3 = b

\bigl( \ P_1 \ P_2 \ \bigr) \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} + P_3x_3 = b

将

\bigl( \ P_1 \ P_2 \ \bigr)

当做一个矩阵

, 将

\begin{pmatrix} x_1 \\ x_2 \end{pmatrix}

当做一个矩阵

X_B

;

将整个系数矩阵除了

之外剩下的矩阵称为

, 对应的变量矩阵称为

X_N

;

BX_B + NX_N = b

在上述矩阵的表达式中 , 方程组

\begin{cases} x_1 + x_2 + x_3 = 8 \\ \\ x_2 - x_3 = 2 \end{cases}

中一定有一个系数矩阵的子矩阵

是特殊的矩阵 ;

矩阵与

矩阵的关系 :

矩阵是

m \times n

维的矩阵 ,

行 ,

列 , 有

个变量 ,

个等式 ;

的秩为

, 且

n \geq m

;

矩阵

就是

m \times m

的方阵 ;

线性规划前提 :

这里说明一下 , 如果

n \leq m

, 那么该方程组有唯一解 , 或无解 ;

整个运筹学讨论的就是等式个数

少于变量个数

, 有多个解的情况下 , 如何找出最优解 , 因此其矩阵的秩就是等式个数

;

五、基、基向量、基变量、非基变量

矩阵是

m \times n

维的矩阵 ,

行 ,

列 , 线性规划中 , 有

个变量 ,

个等式 ;

矩阵

的秩是

, 即等式个数 ;

矩阵

中肯定能找到一个可逆的方阵 , 矩阵

;

矩阵

是矩阵

中的满秩子矩阵 , 则称该矩阵

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

P_1x_1 + P_2 x_2 + P_3x_3 = b

上述示例中的

\bigl( \ P_1 \ P_2 \ \bigr)

就是线性规划中的基 ;

\bigl( \ P_1 \ P_2 \ \bigr)

\bigl( \ P_1 \ P_3 \ \bigr)

\bigl( \ P_2 \ P_3 \ \bigr)

都是线性规划的基 ;

基向量 : 上述基矩阵中的

P_1 , P_2 , P_3

列向量 , 称为基向量 ;

基变量 : 与基向量相乘的

x_1 , x_2, x_3

变量 , 称为基变量 ;

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

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

原始发表：2020-07-12，如有侵权请联系 cloudcommunity@tencent.com 删除

变量

函数

集合

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

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

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

变量

函数

集合

登录后参与评论

0 条评论

热度