文章目录
一、知识点回顾
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'' , 使用两个变量代替
1 个变量 ;
- 目标函数求最大值 , 如果是求最小值 , 目标函数
\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 , 其中
A 是
m \times n 的矩阵
X 是
n \times 1 维向量
B 是
m \times 1 维向量
这是线性规划的矩阵形式 , 参考 【运筹学】线性规划数学模型 ( 三要素 | 一般形式 | 向量形式 | 矩阵形式 ) VI 线性规划数学模型矩阵形式
解上述方程组 , 使用高斯方程 , 高斯消元法 ;
将系数矩阵
A 和
B 做成一个矩阵
\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 取值为
k , 那么 :
x_2 = k + 2x_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 = BP_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) 当做一个矩阵
B , 将
\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} 当做一个矩阵
X_B ;
将整个系数矩阵 除了
B 之外剩下的矩阵称为
N , 对应的变量矩阵称为
X_N ;
BX_B + NX_N = b在上述矩阵的表达式中 , 方程组
\begin{cases} x_1 + x_2 + x_3 = 8 \\ \\ x_2 - x_3 = 2 \end{cases} 中 一定有一个系数矩阵的子矩阵
B 是特殊的矩阵 ;
B 矩阵与
A 矩阵的关系 :
A 矩阵是
m \times n 维的矩阵 ,
m 行 ,
n 列 , 有
n 个变量 ,
m 个等式 ;
A 的秩为
m , 且
n \geq m ;
B 就是
m \times m 的方阵 ;
线性规划前提 :
n \leq m , 那么该方程组有唯一解 , 或无解 ;
m 少于变量个数
n , 有多个解的情况下 , 如何找出最优解 , 因此其矩阵的秩就是等式个数
m ;
五、基、基向量、基变量、非基变量
A 矩阵是
m \times n 维的矩阵 ,
m 行 ,
n 列 , 线性规划中 , 有
n 个变量 ,
m 个等式 ;
矩阵
A 的秩是
m , 即等式个数 ;
矩阵
A 中肯定能找到一个可逆的方阵 , 矩阵
B ;
矩阵
B 是矩阵
A 中的满秩子矩阵 , 则称该 矩阵
B 是线性规划问题的一个 基 ;
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 变量 , 称为 基变量 ;
非基变量 : 基变量之外的其它变量 , 称为非基变量 ;