【运筹学】线性规划数学模型 ( 单纯形法 | 迭代原则 | 入基 | 出基 | 线性规划求解示例 )

韩曙亮

发布于 2023-03-28 16:23:00

1.2K0

发布于 2023-03-28 16:23:00

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

文章目录

一、单纯形法计算示例 ( 上篇博客回顾总结 )

在上一篇博客【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 线性规划求解示例 ) 博客给出了一个线性规划的示例 , 并进行了查找初始基可行解 , 和判定该基可行解是否是最优解 ;

在目标函数中 , 将基可行解代入目标函数中

不是最优解情况 : 非基变量的系数都是大于

0

的数值 , 该基可行解不是最优解 ;

是最优解情况 : 只有当非基变量的系数都是小于等于

0

的数时 , 该基可行解才是最优解 ;

线性规划标准形式为 :

\begin{array}{lcl} max Z = 3x_1 + 4x_2 + 0x_3 + 0x_4 \\ \\ \begin{cases} 2 x_1 + x_2 + x_3 + 0x_4 = 40 \\\\ x_1 + 3x_2 + 0x_3 + x_4 = 30 \\\\ x_j \geq 0 & (j = 1 , 2 , 3 , 4 ) \end{cases}\end{array}

单纯形表 :

c j c_j cj	c j c_j cj		3 3 3	4 4 4	0 0 0	0 0 0
C B C_B CB 基变量系数 (目标函数)	基变量	常数 b b b	x 1 x_1 x1	x 2 x_2 x2	x 3 x_3 x3	x 4 x_4 x4	θ i \theta_i θi
0 0 0 ( 目标函数 x 3 x_3 x3 系数 c 3 c_3 c3 )	x 3 x_3 x3	40 40 40	2 2 2	1 1 1	1 1 1	0 0 0
0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4)	x 4 x_4 x4	30 30 30	1 1 1	3 3 3	0 0 0	1 1 1
		σ j \sigma_j σj	3 3 3	4 4 4	0 0 0	0 0 0

c_j

3

4

0

C_B

基变量系数 (目标函数)基变量常数

b

x_1

x_2

x_3

x_4

\theta_i

0

( 目标函数

x_3

系数

c_3

)

x_3

40

2

1

0

( 目标函数

x_4

系数

c_4

)

x_4

30

1

3

0

1

\sigma_j

3

4

0

选择

\begin{bmatrix} &1 & 0 & \\\\ &0 & 1 & \end{bmatrix}

作为基矩阵 , 基变量是

x_3

,

x_4

, 初始基可行解是

\begin{pmatrix} \quad 0 \quad \\ \quad 0 \quad \\ \quad 40 \quad \\ \quad 30 \quad \\ \end{pmatrix}

, 经过计算 , 其目标函数中

x_1

的系数是

3

,

x_2

的系数是

4

, 都是大于

0

的数 , 该基可行解不是基解 , 继续向下迭代 ;

二、迭代原则

上述解出的基可行解

\begin{pmatrix} \quad 0 \quad \\ \quad 0 \quad \\ \quad 40 \quad \\ \quad 30 \quad \\ \end{pmatrix}

不是最优解 , 那么需要迭代下一个基可行解 , 下面开始讲解 , 如何进行迭代 ;

上述的解中 , 非基变量

x_1

和

x_2

取

0

不是最好的选择 , 那么这两个变量最好取非

0

的值 , 求解线性规划的思路是 :

在无穷多个可行解中迭代 , 得到最优解 ;
上述思路可以转化成在有限个基可行解中迭代 , 得到最优解 ;
无限 -> 有限 : 可行解是无限个的 , 基可行解是有限个 ;

三、最优解推导

x_1 , x_2

取值为

0

不是最优解 , 约束条件要求这两个变量必须大于等于

0

x_j \geq 0 (j = 1 , 2 , 3 , 4 )

, 那么只能取值大于

0

, 下面讨论这两个变量取值大于

0

的情况 ;

x_1

的系数是

3

,

x_2

的系数是

4

, 如果

x_3 , x_4

取

0

, 目标函数

maxZ = 0 + 3x_1 + 4x_2

, 将

x_1 , x_2

任意一个增大 , 其目标函数的值都会增大 ;

增大

x_2

: 此时可以选择将

x_2

增大 ,

x_2

增加

1

, 目标函数就会增加

4

;

增大

x_1

: 也可以选择将

x_1

增大 ,

x_1

增加

1

, 目标函数就会增加

3

, 只要是目标函数随变量增加而增加即可 ;

增大

x_2

,

x_2

不能无限增大 , 其需要受到

\begin{cases} 2 x_1 + x_2 + x_3 + 0x_4 = 40 \\\\ x_1 + 3x_2 + 0x_3 + x_4 = 30 \end{cases}

约束方程约束 ,

受第一个方程约束 , 增大

x_2

, 最多是

x_1, x_3, x_4

都取值

0

,

x_2

理论上最大值时

40

;

受第一个方程约束 , 增大

x_2

, 最多是

x_1, x_3, x_4

都取值

0

,

x_2

理论上最大值时

10

;

x_2

最大就能取值到

10

, 否则无法满足第二个约束方程 , 如果

x_2

取

40

, 那么在第二个方程中 , 就会出现有变量为负数 , 就不符合约束条件了 , 因此

x_2

最大只能取到

10

;

那么开始增加

x_2

的值 , 目标函数

maxZ = 0 + 3x_1 + 4x_2

, 增大

x_2

, 如果

x_2

从

0

增加到

10

, 目标函数可以增加

40

,

c j c_j cj	c j c_j cj		3 3 3	4 4 4	0 0 0	0 0 0
C B C_B CB 基变量系数 (目标函数)	基变量	常数 b b b	x 1 x_1 x1	x 2 x_2 x2	x 3 x_3 x3	x 4 x_4 x4	θ i \theta_i θi
0 0 0 ( 目标函数 x 3 x_3 x3 系数 c 3 c_3 c3 )	x 3 x_3 x3	40 40 40	2 2 2	1 1 1	1 1 1	0 0 0	40 40 40 ( θ 3 \theta_3 θ3 )
0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4)	x 4 x_4 x4	30 30 30	1 1 1	3 3 3	0 0 0	1 1 1	10 10 10 ( θ 4 \theta_4 θ4 )
σ j \sigma_j σj			3 3 3	4 4 4	0 0 0	0 0 0

c_j

3

4

0

C_B

基变量系数 (目标函数)基变量常数

b

x_1

x_2

x_3

x_4

\theta_i

0

( 目标函数

x_3

系数

c_3

)

x_3

40

2

1

0

40

(

\theta_3

)

0

( 目标函数

x_4

系数

c_4

)

x_4

30

1

3

0

1

10

(

\theta_4

)

\sigma_j

3

4

0

四、出基与入基

基可行解 : 选择可行基 , 自然会产生基变量 ( 可行基对应变量 ) , 与非基变量 , 非基变量取值为

0

, 解出基变量 , 此时基变量的解与

0

组合成基可行解 ;

上一次的初始基可行解选择时 ,

x_3

和

x_4

是基变量 ,

x_1

和

x_2

是非基变量 , 非基变量取值必须为

0

;

如果

x_2

变成了非

0

取值 , 此时就需要将

x_2

设置成基变量 ;

基变量的个数是固定的 , 本示例中是

2

个 , 如果将

x_2

设置成基变量 , 那么就需要将之前的

x_3

和

x_4

中其中一个基变量替换成

x_2

, 被替换的基变量变成非基变量 ;

因此该迭代的过程又称为出基 , 入基过程 ;

出基 :

x_3 , x_4

有一个变量设置成非基变量 , 称为出基 ;

入基 :

x_2

设置成基变量 , 称为入基 ;

五、出基与入基变量选择

入基变量选择 : 具体哪个变量入基 , 是由检验数决定的 , 检验数

\sigma_j

较大的入基 ;

x_2

的检验数

\sigma_2

是

4

, 大于

\sigma_1 = 3

, 因此这里选择

x_2

作为入基变量 ;

出基变量选择 : 系数矩阵中 , 常数列

b =\begin{pmatrix} \quad 40 \quad \\ \quad 30 \quad \end{pmatrix}

, 分别除以除以入基变量大于

0

的系数列

\begin{pmatrix} \quad 1 \quad \\ \quad 3 \quad \end{pmatrix}

, 得出结果是

\begin{pmatrix} \quad 40 \quad \\ \quad 10 \quad \end{pmatrix}

, 然后选择一个最小值

10

, 查看该最小值对应的变量是

x_4

, 选择该变量作为出基变量 ;

这里将出基变量与入基变量选择好了 ,

x_2

的检验数较大 , 选择

x_2

作为入基变量 ,

x_4

的

\theta_4

较小 , 选择

x_4

作为出基变量 ;

入基出基操作完成后 , 基变量变成了

x_3, x_2

;

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

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

变量

博客

函数

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

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

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

变量

博客

函数

登录后参与评论

0 条评论

热度