【运筹学】线性规划数学模型 ( 知识点回顾

线性规划三要素 :

m a x ( m i n ) z = ∑ j = 1 n c j x j { ∑ j = 1 n a i j x j = b i ( i = 1 , 2 ⋯ m ) x j ≥ 0 ( i = 1 , 2 ⋯ n ) \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} max(min)z=∑j=1n​cj​xj​⎩⎪⎨⎪⎧​∑j=1n​aij​xj​=bi​xj​≥0​(i=1,2⋯m)(i=1,2⋯n)​​

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

线性规划标准形式 :

m a x Z = ∑ j = 1 n c j x j s . t { ∑ j = 1 n a i j x j ≤ ( = ⋅ ≥ ) b i i = 1 , 2 , ⋯   , m x j ≥ 0 j = 1 , 2 , ⋯   , n \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} maxZ=∑j=1n​cj​xj​s.t⎩⎪⎨⎪⎧​∑j=1n​aij​xj​≤(=⋅≥)bi​xj​≥0​i=1,2,⋯,mj=1,2,⋯,n​​

线性规划标准形式如下 :

m a x Z = ∑ j = 1 n c j x j s . t { ∑ j = 1 n a i j x j = b i i = 1 , 2 , ⋯   , m x j ≥ 0 j = 1 , 2 , ⋯   , n \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} maxZ=∑j=1n​cj​xj​s.t⎩⎪⎨⎪⎧​∑j=1n​aij​xj​=bi​xj​≥0​i=1,2,⋯,mj=1,2,⋯,n​​

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

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

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

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

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

拿到一个方程组 A X = B AX = B AX=B , 其中

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

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

将系数矩阵 A A A 和 B B B 做成一个矩阵 ( A B ) \bigl( A B \bigr) (AB) , 进行行变换 , 消元成阶梯形式 , 此时可以判断该方程组是否有解 , 如果有 , 可以将所有的解解出来 , 求解时 , 阶梯元素很关键 ,

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

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

{ x 1 + x 2 + x 3 = 8 x 2 − x 3 = 2 \begin{cases} x_1 + x_2 + x_3 = 8 \\ \\ x_2 - x_3 = 2 \end{cases} ⎩⎪⎨⎪⎧​x1​+x2​+x3​=8x2​−x3​=2​

( A B ) \bigl( A B \bigr) (AB) 矩阵为 [ 1 1 1 8 0 1 − 1 2 ] \begin{bmatrix} &1 & 1 & 1 & 8 & \\\\ &0 & 1 & -1 & 2 & \end{bmatrix} ⎣⎡​​10​11​1−1​82​​⎦⎤​

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

前两列的矩阵 [ 1 1 0 1 ] \begin{bmatrix} &1 & 1 & \\\\ &0 & 1 & \end{bmatrix} ⎣⎡​​10​11​​⎦⎤​ 就是特殊矩阵 , 分别是 x 1 x_1 x1​ 和 x 2 x_2 x2​ 对应的矩阵 ;

x 3 x_3 x3​ 是特殊的变量 , 其可以任意取值的 , 当 x 3 x_3 x3​ 取任意值时 , 通过阶梯型矩阵 , 可以计算出 x 1 x_1 x1​ 和 x 2 x_2 x2​ 的值 ;

假设 x 3 x_3 x3​ 取值为 k k k , 那么 :

{ x 1 + x 2 + x 3 = 8 x 2 − x 3 = 2 \begin{cases} x_1 + x_2 + x_3 = 8 \\ \\ x_2 - x_3 = 2 \end{cases} ⎩⎪⎨⎪⎧​x1​+x2​+x3​=8x2​−x3​=2​

方程组中有如下向量 :

x 1 x_1 x1​ 对应的矩阵列向量 [ 1 0 ] \begin{bmatrix} &1 & \\\\ &0 & \end{bmatrix} ⎣⎡​​10​​⎦⎤​ 称为 P 1 P_1 P1​ ,

x 2 x_2 x2​ 对应的矩阵列向量 [ 1 1 ] \begin{bmatrix} &1 & \\\\ &1 & \end{bmatrix} ⎣⎡​​11​​⎦⎤​ 称为 P 2 P_2 P2​ ,

x 3 x_3 x3​ 对应的矩阵列向量 [ 1 − 1 ] \begin{bmatrix} &1 & \\\\ &-1 & \end{bmatrix} ⎣⎡​​1−1​​⎦⎤​ 称为 P 3 P_3 P3​ ,

写成向量形式 (   P 1   P 2   P 3   b   ) \bigl( \ P_1 \ P_2 \ P_3 \ b \ \bigr) ( P1​ P2​ P3​ b ) , 在上方程组的矩阵中 , 找到阶梯型矩阵后 , 阶梯型矩阵对应的向量 P 1 P_1 P1​ 和 P 2 P_2 P2​ 是特殊的 ;

(   P 1   P 2   ) \bigl( \ P_1 \ P_2 \ \bigr) ( P1​ P2​ ) 两个列向量构成了 2 × 2 2 \times 2 2×2 二阶方阵 , 该方阵是阶梯型矩阵 , 是可逆的 ;

可逆矩阵参考

上述方程组可以写成 P 1 x 1 + P 2 x 2 + P 3 x 3 = b P_1x_1 + P_2 x_2 + P_3x_3 = b P1​x1​+P2​x2​+P3​x3​=b 形式 ;

有如下计算推导过程 :

A X = B AX = B AX=B

P 1 x 1 + P 2 x 2 + P 3 x 3 = b P_1x_1 + P_2 x_2 + P_3x_3 = b P1​x1​+P2​x2​+P3​x3​=b

(   P 1   P 2   ) ( x 1 x 2 ) + P 3 x 3 = b \bigl( \ P_1 \ P_2 \ \bigr) \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} + P_3x_3 = b ( P1​ P2​ )(x1​x2​​)+P3​x3​=b

将 (   P 1   P 2   ) \bigl( \ P_1 \ P_2 \ \bigr) ( P1​ P2​ ) 当做一个矩阵 B B B , 将 ( x 1 x 2 ) \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} (x1​x2​​) 当做一个矩阵 X B X_B XB​ ;

将整个系数矩阵 除了 B B B 之外剩下的矩阵称为 N N N , 对应的变量矩阵称为 X N X_N XN​ ;

B X B + N X N = b BX_B + NX_N = b BXB​+NXN​=b

在上述矩阵的表达式中 , 方程组 { x 1 + x 2 + x 3 = 8 x 2 − x 3 = 2 \begin{cases} x_1 + x_2 + x_3 = 8 \\ \\ x_2 - x_3 = 2 \end{cases} ⎩⎪⎨⎪⎧​x1​+x2​+x3​=8x2​−x3​=2​ 中 一定有一个系数矩阵的子矩阵 B B B 是特殊的矩阵 ;

B B B 矩阵与 A A A 矩阵的关系 :

A A A 矩阵是 m × n m \times n m×n 维的矩阵 , m m m 行 , n n n 列 , 有 n n n 个变量 , m m m 个等式 ;

A A A 的秩为 m m m , 且 n ≥ m n \geq m n≥m ;

矩阵 B B B 就是 m × m m \times m m×m 的方阵 ;

线性规划前提 :

这里说明一下 , 如果 n ≤ m n \leq m n≤m , 那么该方程组有唯一解 , 或无解 ;

整个运筹学讨论的就是等式个数 m m m 少于变量个数 n n n , 有多个解的情况下 , 如何找出最优解 , 因此其矩阵的秩就是等式个数 m m m ;

A A A 矩阵是 m × n m \times n m×n 维的矩阵 , m m m 行 , n n n 列 , 线性规划中 , 有 n n n 个变量 , m m m 个等式 ;

矩阵 A A A 的秩是 m m m , 即等式个数 ;

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

矩阵 B B B 是矩阵 A A A 中的满秩子矩阵 , 则称该 矩阵 B B B 是线性规划问题的一个 基 ;

P 1 x 1 + P 2 x 2 + P 3 x 3 = b P_1x_1 + P_2 x_2 + P_3x_3 = b P1​x1​+P2​x2​+P3​x3​=b

上述示例中的 (   P 1   P 2   ) \bigl( \ P_1 \ P_2 \ \bigr) ( P1​ P2​ ) 就是线性规划中的基 ;

(   P 1   P 2   ) \bigl( \ P_1 \ P_2 \ \bigr) ( P1​ P2​ ) , (   P 1   P 3   ) \bigl( \ P_1 \ P_3 \ \bigr) ( P1​ P3​ ) , (   P 2   P 3   ) \bigl( \ P_2 \ P_3 \ \bigr) ( P2​ P3​ ) 都是线性规划的基 ;

基向量 : 上述 基矩阵 中的 P 1 , P 2 , P 3 P_1 , P_2 , P_3 P1​,P2​,P3​ 列向量 , 称为 基向量 ;

基变量 : 与基向量相乘的 x 1 , x 2 , x 3 x_1 , x_2, x_3 x1​,x2​,x3​ 变量 , 称为 基变量 ;

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