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

韩曙亮

发布于 2023-03-27 17:27:12

2.9K0

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

文章目录

一、线性规划标准形式

线性规划标准形式 :

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}

线性规划标准形式特点 :

1. 目标函数 : 目标函数都是求最大值 , 如果出现最小值 , 那么将其转为求最大值的形式 ;
2. 约束条件 : 约束条件都是等式方程 , 等式右侧的常数项

b_i

大于等于

;

3. 决策变量 : 决策变量

x_j

大于等于 0 ;

约定 : 决策变量个数为

个 , 约束条件不等式个数为

个 , 约束条件不等式的系数为一个

m \times n

矩阵 ,

行

列的矩阵 ;

二、线性规划普通形式 -> 标准形式目标函数转化

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

如果目标函数是

\rm min W = \sum c_j x_j

可以将目标函数乘以

-1

\rm - min W = -\sum c_j x_j

是大于

的数 ,

的最小值时 ,

-W

是最大值 ,

是最大值时 ,

-W

是最小值 , 这里令

Z = -W

, 可以得到

\rm max Z = -minW = -\sum c_j x_j

三、线性规划普通形式 -> 标准形式无约束的决策变量转化

无约束变量转换 : 所有的决策变量必须

\geq 0

如果某个决策变量

x_j

没有任何约束 , 在标准形式中 , 所有的决策变量必须都大于等于 0 ;

这里令

x_j = x_j' - x_j''

, 其中

x_j' \geq 0

x_j'' \geq 0

四、线性规划普通形式 -> 标准形式约束方程转化

约束方程转换 : 在线性规划中 , 约束方程都是等式 , 需要将不等式 (

\leq

\geq

) 转为等式 (

) ;

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

\sum a_{ij} x_j \leq b_i

等式左边比右边小 , 左侧加上一个变量

x_{n+i}

与右侧相等 ;

\sum a_{ij} x_j + x_{ni} = b_i

这个

x_{n+i}

称为松弛变量 ;

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

\sum a_{ij} x_j \geq b_i

等式左边比右边小 , 左侧加上一个变量

x_{n+i}

与右侧相等 ;

\sum a_{ij} x_j - x_{ni} = b_i

这个

x_{n+i}

称为剩余变量 ;

五、线性规划普通形式 -> 标准形式小于等于 0 的变量转化

如果出现变量约束

x_j \leq 0

, 需要将该变量约束转为大于等于 0 (

\geq 0

) 的情况 ;

当前

x_j \leq 0

, 令

x_j' = -x_j

, 此时

x_j' \geq 0

;

六、线性规划普通形式 -> 标准形式转化顺序说明

① 先处理变量没有约束的问题 , 需要用两个

\geq 0

的变量替换原来的变量 ;

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

② 在处理约束方程 , 如果是

\leq

不等式 , 需要在不等式左侧加入松弛变量 , 将不等式转为等式 ; 如果是

\geq

不等式 , 不等式左侧需要减去一个剩余变量 , 将不等式转为等式 ;

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

③ 约束方程等式右侧常数必须大于

, 如果右侧的常数小于

, 在等式左右两侧都乘以

-1

;

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

-1

;

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

自下而上 : 变量约束都大于等于

, 约束不等式转等式 , 约束方程右侧大于

, 目标函数必须求最大值 ;

七、线性规划普通形式 -> 标准形式转化实例

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

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

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

处理决策变量

x_3

无约束的问题 , 在标准形式中 , 所有的变量必须都

\geq 0

; 这里使用

x_3' - x_3''

代替

x_3

, 新增加的两个变量

x_3' , x_3'' \geq 0

注意之后的每个步骤都要考虑将

x_3

转为

( x_3' - x_3'' )

;

2. 约束方程

5x_1 + x_2 + x_3 \leq 7

转化 ( 松弛变量 )

该约束条件是

\leq

不等式 , 需要在左侧加上松弛变量

x_4

, 将小于等于不等式转为等式 ;

5x_1 + x_2 + ( x_3' - x_3'' ) + x_4 = 7

3. 约束方程

x_1 - x_2 - 4x_3 \geq 2

转化 ( 剩余变量 )

该约束条件是

\geq

不等式 , 需要在左侧减去剩余变量

x_5

, 将大于等于不等式转为等式 ;

x_1 - x_2 - 4( x_3' - x_3'' ) - x_5 = 2

4. 约束方程

-3x_1 + x_2 + 2x_3 = -5

转化 ( 右侧常数转正数 )

该式子是等式 , 但是右侧常数小于

, 这里需要将右侧的常数转化为正数 , 在方程两边乘以

-1

;

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

5. 目标函数转化

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

( 1 ) 将新增的变量加入

原目标函数为 :

min W = -2x_1 + x_2 + 3( x_3' - x_3'' )

新增的变量 :

① 之前

x_3

没有约束变量 , 使用

x_3' , x_3''

代替 ;

② 处理

\leq

不等式时 , 加入了

x_4

松弛变量 ;

③ 处理

\geq

不等式时 , 加入了

x_5

剩余变量 ;

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

min W = -2x_1 + x_2 + 3 ( x_3' - x_3'' ) + 0x_4 + 0x_5

( 2 ) 最小值转最大值

标准形式的目标函数是求最大值 , 这里在上面加入变量的结果的基础上 , 两边乘以

-1

, 得到如下公式 :

max Z = 2x_1 - x_2 - 3( x_3' - x_3'' ) + 0x_4 + 0x_5

6. 最终结果 :

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

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

原始发表：2019-10-30，如有侵权请联系 cloudcommunity@tencent.com 删除

变量