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

2023-03-28 21:58:48 浏览数 (1)

文章目录

  • 一、线性规划模型三要素
  • 二、线性规划一般形式和标准形式
  • 三、线性规划普通形式转为标准形式
  • ​
    • 1、目标函数
    • 2、决策变量约束
    • 3、等式约束方程
    • 4、总体顺序说明
    • 5、线性规划标准形式转化案例
  • 四、线性规划解、可行解、最优解
  • 五、线性规划 基、基向量、基变量、非基变量

一、线性规划模型三要素

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

  • ( 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

大于等于

0

;

  • 3. 决策变量 : 决策变量
x_j

大于等于 0 ;

约定 : 决策变量个数为

n

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

m

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

m times n

矩阵 ,

m

行

n

列的矩阵 ;

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

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

1、目标函数

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

如果目标函数是

rm min W = sum c_j x_j

可以将目标函数乘以

-1

,

rm - min W = -sum c_j x_j
W

是大于

0

的数 ,

W

的最小值时 ,

-W

是最大值 ,

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 . 针对小于等于

0

的变量

如果出现 变量约束

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

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

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

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

0

, 如果右侧的常数小于

0

, 在等式左右两侧都乘以

-1

;

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

-1

;

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

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

0

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

0

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

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

转化 ( 右侧常数转正数 )

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

0

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

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

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

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

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

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

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

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

A

矩阵是

m times n

维的矩阵 ,

m

行 ,

n

列 , 线性规划中 , 有

n

个变量 ,

m

个等式 ;

矩阵

A

的秩是

m

, 即等式个数 ;

矩阵

A

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

B

;

矩阵

B

是矩阵

A

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

B

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

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

变量 , 称为 基变量 ;

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

变量 博客 产品 函数 模型

0 人点赞