线性规划数学模型三要素 :

参考博客 : 【运筹学】线性规划数学模型 ( 三要素 | 一般形式 | 向量形式 | 矩阵形式 )

线性规划一般形式 :

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

线性规划标准形式特点 :

约定 : 决策变量个数为 n n n 个 , 约束条件不等式个数为 m m m 个 , 约束条件不等式的系数为一个 m × n m \times n m×n 矩阵 , m m m 行 n n n 列的矩阵 ;

参考博客 : 【运筹学】线性规划数学模型标准形式 ( 标准形式 | 目标函数转化 | 决策变量转化 | 约束方程转化 | 固定转化顺序 | 标准形式转化实例 ) ★★

目标函数 转换 : 求 极小值 转为 求 极大值 ;

如果目标函数是 m i n W = ∑ c j x j \rm min W = \sum c_j x_j minW=∑cj​xj​ 可以将目标函数乘以 − 1 -1 −1 , − m i n W = − ∑ c j x j \rm - min W = -\sum c_j x_j −minW=−∑cj​xj​ W W W 是大于 0 0 0 的数 , W W W 的最小值时 , − W -W −W 是最大值 , W W W 是最大值时 , − W -W −W 是最小值 , 这里令 Z = − W Z = -W Z=−W , 可以得到 m a x Z = − m i n W = − ∑ c j x j \rm max Z = -minW = -\sum c_j x_j maxZ=−minW=−∑cj​xj​

1 . 针对没有约束的变量

无约束变量 转换 : 所有的决策变量必须 ≥ 0 \geq 0 ≥0

如果某个决策变量 x j x_j xj​ 没有任何约束 , 在标准形式中 , 所有的决策变量必须都大于等于 0 ;

这里令 x j = x j ′ − x j ′ ′ x_j = x_j' - x_j'' xj​=xj′​−xj′′​ , 其中 x j ′ ≥ 0 x_j' \geq 0 xj′​≥0 , x j ′ ′ ≥ 0 x_j'' \geq 0 xj′′​≥0

2 . 针对小于等于 0 0 0 的变量

如果出现 变量约束 x j ≤ 0 x_j \leq 0 xj​≤0 , 需要将该变量约束转为大于等于 0 ( ≥ 0 \geq 0 ≥0 ) 的情况 ;

当前 x j ≤ 0 x_j \leq 0 xj​≤0 , 令 x j ′ = − x j x_j' = -x_j xj′​=−xj​ , 此时 x j ′ ≥ 0 x_j' \geq 0 xj′​≥0 ;

约束方程 转换 : 在线性规划中 , 约束方程都是等式 , 需要将不等式 ( ≤ \leq ≤ , ≥ \geq ≥ ) 转为 等式 ( = = = ) ;

1. 针对小于等于的不等式 :

∑ a i j x j ≤ b i \sum a_{ij} x_j \leq b_i ∑aij​xj​≤bi​

等式左边比右边小 , 左侧加上一个 变量 x n + i x_{n+i} xn+i​ 与右侧相等 ;

∑ a i j x j + x n i = b i \sum a_{ij} x_j + x_{ni} = b_i ∑aij​xj​+xni​=bi​

这个 x n + i x_{n+i} xn+i​ 称为松弛变量 ;

2. 针对大于等于的不等式 :

∑ a i j x j ≥ b i \sum a_{ij} x_j \geq b_i ∑aij​xj​≥bi​

等式左边比右边小 , 左侧加上一个 变量 x n + i x_{n+i} xn+i​ 与右侧相等 ;

∑ a i j x j − x n i = b i \sum a_{ij} x_j - x_{ni} = b_i ∑aij​xj​−xni​=bi​

这个 x n + i x_{n+i} xn+i​ 称为剩余变量 ;

① 先处理变量没有约束的问题 , 需要用两个 ≥ 0 \geq 0 ≥0 的变量替换原来的变量 ;

这里特别注意 , 之后处理 约束方程 , 每个步骤都要讲该变量替换掉 ; 该步骤优先级最高 ;

② 在处理约束方程 , 如果是 ≤ \leq ≤ 不等式 , 需要在不等式左侧加入松弛变量 , 将不等式转为等式 ; 如果是 ≥ \geq ≥ 不等式 , 不等式左侧需要减去一个 剩余变量 , 将不等式转为等式 ;

该处理过程会增加新的变量 , 如松弛变量或剩余变量 , 优先级 低于 处理没有变量约束 的问题 ;

③ 约束方程等式右侧常数必须大于 0 0 0 , 如果右侧的常数小于 0 0 0 , 在等式左右两侧都乘以 − 1 -1 −1 ;

④ 先将之前 替换 或 新增的变量加入到目标函数中 , 在处理最大值最小值的问题 , 如果目标函数求最大值 , 什么都不用做 , 如果目标函数求最小值 , 需要将 求最小值的目标函数转为求最大值的目标函数 , 两边乘以 − 1 -1 −1 ;

目标函数需要将之前所有的变量都总结到一起 , 上述两个步骤都会增加新的变量 , 因此转换目标函数的工作放在最后 ;

自下而上 : 变量约束都大于等于 0 0 0 , 约束不等式转等式 , 约束方程右侧大于 0 0 0 , 目标函数必须求最大值 ;

下面是线性规划问题模型 , 将其转化为标准形式 :

m i n W = − 2 x 1 + x 2 + 3 x 3 { 5 x 1 + x 2 + x 3 ≤ 7 x 1 − x 2 − 4 x 3 ≥ 2 − 3 x 1 + x 2 + 2 x 3 = − 5 x 1 ≥ 0 , x 2 ≥ 0 , x 3 无 约 束 \begin{array}{lcl}min W = -2x_1 + x_2 + 3x_3 \\ \\ \\ \begin{cases} 5x_1 + x_2 + x_3 \leq 7 \\ \\ x_1 - x_2 - 4x_3 \geq 2 \\ \\ -3x_1 + x_2 + 2x_3 = -5 \\ \\ x_1 \geq 0 , x_2 \geq 0 , x_3 无约束 \end{cases} \end{array} minW=−2x1​+x2​+3x3​⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​5x1​+x2​+x3​≤7x1​−x2​−4x3​≥2−3x1​+x2​+2x3​=−5x1​≥0,x2​≥0,x3​无约束​​

1. 处理变量无约束的问题 ( 变量必须大于 0 )

处理决策变量 x 3 x_3 x3​ 无约束的问题 , 在标准形式中 , 所有的变量必须都 ≥ 0 \geq 0 ≥0 ; 这里使用 x 3 ′ − x 3 ′ ′ x_3' - x_3'' x3′​−x3′′​ 代替 x 3 x_3 x3​ , 新增加的两个变量 x 3 ′ , x 3 ′ ′ ≥ 0 x_3' , x_3'' \geq 0 x3′​,x3′′​≥0

注意之后的每个步骤都要考虑 将 x 3 x_3 x3​ 转为 ( x 3 ′ − x 3 ′ ′ ) ( x_3' - x_3'' ) (x3′​−x3′′​) ;

2. 约束方程 5 x 1 + x 2 + x 3 ≤ 7 5x_1 + x_2 + x_3 \leq 7 5x1​+x2​+x3​≤7 转化 ( 松弛变量 )

该约束条件是 ≤ \leq ≤ 不等式 , 需要在左侧加上 松弛变量 x 4 x_4 x4​ , 将 小于等于不等式 转为等式 ; 5 x 1 + x 2 + ( x 3 ′ − x 3 ′ ′ ) + x 4 = 7 5x_1 + x_2 + ( x_3' - x_3'' ) + x_4 = 7 5x1​+x2​+(x3′​−x3′′​)+x4​=7

3. 约束方程 x 1 − x 2 − 4 x 3 ≥ 2 x_1 - x_2 - 4x_3 \geq 2 x1​−x2​−4x3​≥2 转化 ( 剩余变量 )

该约束条件是 ≥ \geq ≥ 不等式 , 需要在左侧减去 剩余变量 x 5 x_5 x5​ , 将 大于等于不等式 转为等式 ; x 1 − x 2 − 4 ( x 3 ′ − x 3 ′ ′ ) − x 5 = 2 x_1 - x_2 - 4( x_3' - x_3'' ) - x_5 = 2 x1​−x2​−4(x3′​−x3′′​)−x5​=2

4. 约束方程 − 3 x 1 + x 2 + 2 x 3 = − 5 -3x_1 + x_2 + 2x_3 = -5 −3x1​+x2​+2x3​=−5 转化 ( 右侧常数转正数 )

该式子是等式 , 但是右侧常数小于 0 0 0 , 这里需要将右侧的常数转化为正数 , 在方程两边乘以 − 1 -1 −1 ;

原 式 : − 3 x 1 + x 2 + 2 x 3 = − 5 两 边 乘 以 − 1 : ( − 1 ) × ( − 3 x 1 + x 2 + 2 x 3 ) = ( − 1 ) × ( − 5 ) 最 终 结 果 : 3 x 1 − x 2 − 2 ( x 3 ′ − x 3 ′ ′ ) = 5 \begin{array}{lcl}\\ 原式 : & -3x_1 + x_2 + 2x_3 = -5 \\ \\ 两边乘以 -1 : & (-1) \times ( -3x_1 + x_2 + 2x_3 ) = (-1) \times ( -5 ) \\ \\ 最终结果 : & 3x_1 - x_2 - 2( x_3' - x_3'' ) = 5 \end{array} 原式:两边乘以−1:最终结果:​−3x1​+x2​+2x3​=−5(−1)×(−3x1​+x2​+2x3​)=(−1)×(−5)3x1​−x2​−2(x3′​−x3′′​)=5​

5. 目标函数转化

转化顺序说明 : 在处理上述转化时 , 需要加入新的变量 , 如 无约束的变量需要增加两个变量 , 约束方程的 松弛变量 和 剩余变量 , 因此目标函数最后转化 ;

( 1 ) 将新增的变量加入

原目标函数为 : m i n W = − 2 x 1 + x 2 + 3 ( x 3 ′ − x 3 ′ ′ ) min W = -2x_1 + x_2 + 3( x_3' - x_3'' ) minW=−2x1​+x2​+3(x3′​−x3′′​) 新增的变量 :

此时加入 新增变量 后的 目标函数 为 :

m i n W = − 2 x 1 + x 2 + 3 ( x 3 ′ − x 3 ′ ′ ) + 0 x 4 + 0 x 5 min W = -2x_1 + x_2 + 3 ( x_3' - x_3'' ) + 0x_4 + 0x_5 minW=−2x1​+x2​+3(x3′​−x3′′​)+0x4​+0x5​

( 2 ) 最小值 转 最大值

标准形式的目标函数是求最大值 , 这里在上面加入变量的结果的基础上 , 两边乘以 − 1 -1 −1 , 得到如下公式 :

m a x Z = 2 x 1 − x 2 − 3 ( x 3 ′ − x 3 ′ ′ ) + 0 x 4 + 0 x 5 max Z = 2x_1 - x_2 - 3( x_3' - x_3'' ) + 0x_4 + 0x_5 maxZ=2x1​−x2​−3(x3′​−x3′′​)+0x4​+0x5​

6. 最终结果 :

m a x Z = 2 x 1 − x 2 − 3 ( x 3 ′ − x 3 ′ ′ ) + 0 x 4 + 0 x 5 { 5 x 1 + x 2 + ( x 3 ′ − x 3 ′ ′ ) + x 4 = 7 x 1 − x 2 − 4 ( x 3 ′ − x 3 ′ ′ ) − x 5 = 2 3 x 1 − x 2 − 2 ( x 3 ′ − x 3 ′ ′ ) = 5 x 1 , x 2 , x 3 ′ , x 3 ′ ′ , x 4 , x 5 ≥ 0 \begin{array}{lcl} max Z = 2x_1 - x_2 - 3( x_3' - x_3'' ) + 0x_4 + 0x_5 \\ \\ \\ \begin{cases} 5x_1 + x_2 + ( x_3' - x_3'' ) + x_4 = 7 \\ \\ x_1 - x_2 - 4( x_3' - x_3'' ) - x_5 = 2 \\ \\ 3x_1 - x_2 - 2( x_3' - x_3'' ) = 5 \\ \\ x_1 , x_2 , x_3' , x_3'', x_4 , x_5 \geq 0 \end{cases} \end{array} maxZ=2x1​−x2​−3(x3′​−x3′′​)+0x4​+0x5​⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​5x1​+x2​+(x3′​−x3′′​)+x4​=7x1​−x2​−4(x3′​−x3′′​)−x5​=23x1​−x2​−2(x3′​−x3′′​)=5x1​,x2​,x3′​,x3′′​,x4​,x5​≥0​​

参考博客 : 【运筹学】线性规划数学模型标准形式 ( 标准形式 | 目标函数转化 | 决策变量转化 | 约束方程转化 | 固定转化顺序 | 标准形式转化实例 ) ★★

线性规划标准形式如下 :

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 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​ 变量 , 称为 基变量 ;

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