【运筹学】线性规划数学模型 ( 单纯形法 | 第一次迭代 | 方程组同解变换 | 计算新单纯形表 | 计算检验数 | 入基变量选择 | 出基变量选择 )

韩曙亮

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

9580

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

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

文章目录

\sigma_j

并选择入基变量

七、计算

\theta

值并选择出基变量

上篇博客【运筹学】线性规划数学模型 ( 单纯形法 | 迭代原则 | 入基 | 出基 | 线性规划求解示例 ) 讲解了单纯形法中选择了入基变量 , 与出基变量 , 找到了下一组迭代的可行基 , 下面开始继续进行后续操作 ;

一、初始基可行解后第一次迭代

线性规划标准形式为 :

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

选择初始基可行解并验证最优解 : 选择初始基可行解经过验证 , 不是最优解 , 该初始基可行解对应基变量是

x_3,x_4

;

进行迭代 : 开始进行迭代 , 选择

x_2

作为入基 , 选择

x_4

作为出基 , 新的基变量变成了

x_3 , x_2

, 新的基矩阵变为

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

;

二、迭代后新的单纯形表

单纯形表中的矩阵要求 : 单纯形表中的矩阵是特殊形式的矩阵 , 基矩阵对应的矩阵必须是单位阵 , 非基矩阵对应的矩阵是

B^{-1}N

;

只要基矩阵变换为单位阵 , 非基矩阵自然就是

B^{-1}N

参考 : 【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 ) 四、

B^{-1}N

分析

同解方程组 : 同一个线性规划 , 方程组的解不能变 ;

方程组同解变换 : 保证同解方程组前提下 , 使

x_2

对应的列向量由

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

变成

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

, 这样

x_3

与

x_2

对应的列向量组成的基矩阵就变成了

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

, 此时基变量是单位阵 , 非基矩阵自然就是

B^{-1}N

;

三、方程组同解变换

方程组做同解变换 :

线性规划原始方程组为

\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

的系数变为

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

,

x_3

的系数保持

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

不变 ;

方程

2

同解变换 : 在

x_1 + 3x_2 + 0x_3 + x_4 = 30

中 , 需要将

x_2

的系数变成

1

, 在方程两端乘以

\dfrac{1}{3}

, 此时方程变成

\dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4 = 10

;

方程

1

同解变换 : 将上述方程

2

作同解变换后 , 方程组变成

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

, 目前的需求是将方程

1

的

x_2

系数变为

0

, 使用方程

1

减去方程

2

即可得到要求的矩阵 :

\begin{array}{lcl} (2 - \dfrac{1}{3}) x_1 + 0 x_2 + x_3 + (0 - \dfrac{1}{3}) x_4 &=& 40 - 10 \\\\ \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 &=& 30 \end{array}

最终方程

1

转化为

\dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 = 30

;

同解变换完成后的方程组为

\begin{cases} \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 = 30 \\\\ \dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4 = 10 \end{cases}

四、生成新的单纯形表

单纯形表变成如下形式 : 下面的单纯形表中 , 上面部分是初始基可行解对应的单纯形表 , 下面的部分是本次迭代后生成的新的单纯形表 ;

将同解变换后的方程组中的系数矩阵 , 和常数 , 填入新的单纯形表中 ;

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 ( σ 1 \sigma_1 σ1 )	4 4 4 ( σ 2 \sigma_2 σ2 )	0 0 0	0 0 0
–	–	–	–	–	–	–	–
0 0 0 ( 目标函数 x 3 x_3 x3 系数 c 3 c_3 c3 )	x 3 x_3 x3	30 30 30	5 3 \dfrac{5}{3} 35	0 0 0	1 1 1	− 1 3 -\dfrac{1}{3} −31	? ? ? ( θ 3 \theta_3 θ3 )
4 4 4 ( 目标函数 x 2 x_2 x2 系数 c 2 c_2 c2)	x 2 x_2 x2	10 10 10	1 3 \dfrac{1}{3} 31	1 1 1	0 0 0	1 3 \dfrac{1}{3} 31	? ? ? ( θ 2 \theta_2 θ2 )
σ j \sigma_j σj ( 检验数 )			5 3 \dfrac{5}{3} 35 ( σ 1 \sigma_1 σ1 )	0 0 0	0 0 0	− 4 3 -\dfrac{4}{3} −34 ( σ 4 \sigma_4 σ4 )

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

(

\sigma_1

)

4

(

\sigma_2

)

0

––––––––

0

( 目标函数

x_3

系数

c_3

)

x_3

30

\dfrac{5}{3}

0

1

-\dfrac{1}{3}

?

(

\theta_3

)

4

( 目标函数

x_2

系数

c_2

)

x_2

10

\dfrac{1}{3}

1

0

\dfrac{1}{3}

?

(

\theta_2

)

\sigma_j

( 检验数 )

\dfrac{5}{3}

(

\sigma_1

)

0

-\dfrac{4}{3}

(

\sigma_4

)

五、解出基可行解

新的基变量是

x_3 , x_2

, 对应的基矩阵是

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

, 非基变量是

x_1, x_4

, 对应的非基矩阵是

\begin{pmatrix} \quad \dfrac{5}{3} \quad -\dfrac{1}{3} \quad \\ \quad \dfrac{1}{3} \quad \dfrac{1}{3} \quad \end{pmatrix}

, 将非基变量设置为

0

, 方程组为

\begin{cases} \dfrac{5}{3} \times 0 + 0x_2 + x_3 - \dfrac{1}{3} \times 0 = 30 \\\\ \dfrac{1}{3} \times 0 + x_2 + 0x_3 + \dfrac{1}{3} \times 0 = 10 \end{cases}

, 解出基变量为

\begin{cases} x_3 = 30 \\\\ x_2 = 10 \end{cases}

, 基可行解 为

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

六、计算检验数

\sigma_j

并选择入基变量

根据【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 ) 博客中分析 , 检验数计算公式为 :

矩阵形式 :

C_N^T - C_B^T B^{-1}N

单个检验数计算公式 :

\sigma_j = c_j - \sum c_i a_{ij}

基变量的检验数是

0

, 主要是求非基变量的检验数

\sigma_1 , \sigma_4

;

\sigma_{1} = c_1 - ( c_3 a_{11} + c_2 a_{12} )

\sigma_{1} =3 - (0 \times \dfrac{5}{3}) - (4 \times \dfrac{1}{3}) = \dfrac{5}{3}

, 是从下面的单纯形表中的如下位置提取的数值 ;

\sigma_{4} = c_4 - ( c_3 a_{41} + c_2 a_{42} )

\sigma_{4} =0 - (0 \times -\dfrac{1}{3}) - (4 \times \dfrac{1}{3}) = -\dfrac{4}{3}

, 是从下面的单纯形表中的如下位置提取的数值 ;

检验数

\begin{cases} \sigma_{1} =3 - (0 \times \dfrac{5}{3}) - (4 \times \dfrac{1}{3}) = \dfrac{5}{3} \\\\ \sigma_{4} =0 - (0 \times -\dfrac{1}{3}) - (4 \times \dfrac{1}{3}) = -\dfrac{4}{3} \end{cases}

,

\sigma_1

是大于

0

的 , 两个检验数必须都小于等于

0

, 该基可行解才算作是最优解 , 因此该基可行解不是最优解 ;

根据检验数选择入基变量 : 继续迭代 , 选择检验数较大的非基变量 , 作为入基变量 , 这里入基变量是

x_1

;

七、计算

\theta

值并选择出基变量

参考博客【运筹学】线性规划数学模型 ( 单纯形法 | 迭代原则 | 入基 | 出基 | 线性规划求解示例 ) 五、出基与入基变量选择

入基变量根据检验数

\sigma

选择的是

x_1

;

出基变量是根据

\theta

值来选择的 , 选择

\theta

值较小的值对应的基变量作为出基变量 ;

\theta

值计算 : 常数列

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

, 分别除以除以入基变量

x_1

大于

0

的系数列

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

, 计算过程如下

\begin{pmatrix} \quad \cfrac{30}{\dfrac{5}{3}} \quad \\\\ \quad \cfrac{10}{\dfrac{1}{3}} \quad \end{pmatrix}

, 得出结果是

\begin{pmatrix} \quad 18 \quad \\\\ \quad 30 \quad \end{pmatrix}

, 然后选择一个最小值

18

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

x_3

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

x_1

作入基变量 ,

x_3

作出基变量 ; 使用

x_1

替代基变量中

x_3

的位置 ;

迭代后的基变量为

x_1 ,x_2

;

更新一下单纯形表 :

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 ( σ 1 \sigma_1 σ1 )	4 4 4 ( σ 2 \sigma_2 σ2 )	0 0 0	0 0 0
–	–	–	–	–	–	–	–
0 0 0 ( 目标函数 x 3 x_3 x3 系数 c 3 c_3 c3 )	x 3 x_3 x3	30 30 30	5 3 \dfrac{5}{3} 35	0 0 0	1 1 1	− 1 3 -\dfrac{1}{3} −31	18 18 18 ( θ 3 \theta_3 θ3 )
4 4 4 ( 目标函数 x 2 x_2 x2 系数 c 2 c_2 c2)	x 2 x_2 x2	10 10 10	1 3 \dfrac{1}{3} 31	1 1 1	0 0 0	1 3 \dfrac{1}{3} 31	30 30 30 ( θ 2 \theta_2 θ2 )
σ j \sigma_j σj ( 检验数 )			5 3 \dfrac{5}{3} 35 ( σ 1 \sigma_1 σ1 )	0 0 0	0 0 0	− 4 3 -\dfrac{4}{3} −34 ( σ 4 \sigma_4 σ4 )

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

(

\sigma_1

)

4

(

\sigma_2

)

0

––––––––

0

( 目标函数

x_3

系数

c_3

)

x_3

30

\dfrac{5}{3}

0

1

-\dfrac{1}{3}

18

(

\theta_3

)

4

( 目标函数

x_2

系数

c_2

)

x_2

10

\dfrac{1}{3}

1

0

\dfrac{1}{3}

30

(

\theta_2

)

\sigma_j

( 检验数 )

\dfrac{5}{3}

(

\sigma_1

)

0

-\dfrac{4}{3}

(

\sigma_4

)

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

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

变量

博客

函数

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

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

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

变量

博客

函数

登录后参与评论

0 条评论

热度