【运筹学】线性规划数学模型 ( 线性规划三要素 | 一般形式 | 标准形式 | 标准形式转化 | 可行解 | 最优解 | 基 | 基向量 | 基变量 | 非基变量 ) ★★

韩曙亮

发布于 2023-03-28 21:58:48

2.4K0

发布于 2023-03-28 21:58:48

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

文章目录

一、线性规划模型三要素

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

( 1 ) 决策变量 : 上述产品甲乙的个数

x_1 , x_2

就是决策变量 , 直接关系到利润的多少 ; ( 示例参考【运筹学】线性规划数学模型 ( 三要素 | 一般形式 | 向量形式 | 矩阵形式 ) II . 线性规划示例 )

( 2 ) 目标条件 : 多个决策变量的线性函数 , 通常是求最大值或最小值问题 ; 上述示例中的

max Z = 2x_1 + 3x_2

就是目标条件 ;

( 3 ) 约束条件 : 一组多个决策变量的线性等式或不等式组成 , 如上述 3 ~ 7 的四种设备的使用时间限制和决策变量的取值范围 ;

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

二、线性规划一般形式和标准形式

线性规划一般形式 :

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

矩阵 ,

行

列的矩阵 ;

三、线性规划普通形式转为标准形式

1、目标函数

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

如果目标函数是

\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

2、决策变量约束

1 . 针对没有约束的变量

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

\geq 0

如果某个决策变量

x_j

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

这里令

x_j = x_j' - x_j''

, 其中

x_j' \geq 0

x_j'' \geq 0

2 . 针对小于等于

的变量

如果出现变量约束

x_j \leq 0

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

\geq 0

) 的情况 ;

当前

x_j \leq 0

, 令

x_j' = -x_j

, 此时

x_j' \geq 0

;

3、等式约束方程

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

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

称为剩余变量 ;

4、总体顺序说明

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

\geq 0

的变量替换原来的变量 ;

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

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

\leq

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

\geq

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

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

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

, 如果右侧的常数小于

, 在等式左右两侧都乘以

-1

;

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

-1

;

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

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

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

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

5、线性规划标准形式转化案例

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

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

四、线性规划解、可行解、最优解

线性规划标准形式如下 :

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

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

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

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

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

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

五、线性规划基、基向量、基变量、非基变量

矩阵是

m \times n

维的矩阵 ,

行 ,

列 , 线性规划中 , 有

个变量 ,

个等式 ;

矩阵

的秩是

, 即等式个数 ;

矩阵

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

;

矩阵

是矩阵

中的满秩子矩阵 , 则称该矩阵

是线性规划问题的一个基 ;

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

变量 , 称为基变量 ;

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

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

原始发表：2021-03-07，如有侵权请联系 cloudcommunity@tencent.com 删除

变量

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度