- 一、线性规划标准形式
- 二、线性规划 普通形式 -> 标准形式 目标函数 转化
- 三、线性规划 普通形式 -> 标准形式 无约束的决策变量转化
- 四、线性规划 普通形式 -> 标准形式 约束方程 转化
- 五、线性规划 普通形式 -> 标准形式 小于等于 0 的变量转化
- 六、线性规划 普通形式 -> 标准形式 转化顺序说明
- 七、线性规划 普通形式 -> 标准形式 转化实例
线性规划标准形式 :
m a x Z = ∑ j = 1 n c j x j max Z = \sum_{j = 1}^{n} c_j x_j maxZ=j=1∑ncjxj 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=1naijxj=bixj≥0i=1,2,⋯,mj=1,2,⋯,n
线性规划标准形式特点 :
- 1. 目标函数 : 目标函数都是求最大值 , 如果出现最小值 , 那么将其转为求最大值的形式 ;
- 2. 约束条件 : 约束条件都是等式方程 , 等式右侧的常数项 b i b_i bi 大于等于 0 0 0 ;
- 3. 决策变量 : 决策变量 x j x_j xj 大于等于 0 ;
约定 : 决策变量个数为 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=∑cjxj 可以将目标函数乘以 − 1 -1 −1 , − m i n W = − ∑ c j x j \rm - min W = -\sum c_j x_j −minW=−∑cjxj 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=−∑cjxj
三、线性规划 普通形式 -> 标准形式 无约束的决策变量转化无约束变量 转换 : 所有的决策变量必须 ≥ 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
四、线性规划 普通形式 -> 标准形式 约束方程 转化约束方程 转换 : 在线性规划中 , 约束方程都是等式 , 需要将不等式 ( ≤ \leq ≤ , ≥ \geq ≥ ) 转为 等式 ( = = = ) ;
1. 针对小于等于的不等式 :
∑ a i j x j ≤ b i \sum a_{ij} x_j \leq b_i ∑aijxj≤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 ∑aijxj+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 ∑aijxj≥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 ∑aijxj−xni=bi
这个 x n + i x_{n+i} xn+i 称为剩余变量 ;
五、线性规划 普通形式 -> 标准形式 小于等于 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 ;
六、线性规划 普通形式 -> 标准形式 转化顺序说明① 先处理变量没有约束的问题 , 需要用两个 ≥ 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′′) 新增的变量 :
- ① 之前 x 3 x_3 x3 没有约束变量 , 使用 x 3 ′ , x 3 ′ ′ x_3' , x_3'' x3′,x3′′ 代替 ;
- ② 处理 ≤ \leq ≤ 不等式时 , 加入了 x 4 x_4 x4 松弛变量 ;
- ③ 处理 ≥ \geq ≥ 不等式时 , 加入了 x 5 x_5 x5 剩余变量 ;
此时加入 新增变量 后的 目标函数 为 :
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
