【运筹学】线性规划人工变量法 ( 人工变量法案例 | 初始单纯形表 | 检验数计算 | 入基变量 | 出基变量 )

韩曙亮

发布于 2023-03-28 16:27:08

6080

发布于 2023-03-28 16:27:08

文章目录

上一篇博客【运筹学】线性规划人工变量法 ( 单纯形法总结 | 人工变量法引入 | 人工变量法原理分析 | 人工变量法案例 ) 中 , 介绍了人工变量法 , 主要用于解决线性规划标准形式中 , 初始系数矩阵中没有单位阵的情况 , 并给出一个案例 , 本篇博客中继续使用人工变量法解解上述线性规划问题 ;

一、生成初始单纯形表

添加

2

个人工变量后 , 得到人工变量单纯形法线性规划模型 :

\begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 + 0x_4 + 0x_5 - M x_6 - Mx_7 \\\\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 + x_6 + 0x_7 = 4 \\\\ x_1 - x_2 + 2x_3 + 0x_4 + x_5 + 0x_6 + 0x_7 = 10 \\\\ 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + 0x_6 + x_7 = 1 \\\\ x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 , 6 , 7 ) \end{cases}\end{array}

其中的

M

是一个很大的数值 , 没有具体的值 , 可以理解为正无穷

+\infty

, 具体使用单纯形法进行计算时 , 将其理解为大于给出的任意一个确定的数值 ;

生成初始基可行表 :

c j c_j cj	c j c_j cj		3 3 3	2 2 2	− 1 -1 −1	0 0 0	0 0 0	− M -M −M	− M -M −M
C B C_B CB 基变量系数 (目标函数)	X B X_B XB 基变量	常数 b b b	x 1 x_1 x1	x 2 x_2 x2	x 3 x_3 x3	x 4 x_4 x4	x 5 x_5 x5	x 6 x_6 x6	x 7 x_7 x7	θ i \theta_i θi
− M -M −M ( 目标函数 x 6 x_6 x6 系数 c 6 c_6 c6 )	x 6 x_6 x6	4 4 4	− 4 -4 −4	3 3 3	1 1 1	− 1 -1 −1	0 0 0	1 1 1	0 0 0	? ? ? ( θ 6 \theta_6 θ6)
0 0 0 ( 目标函数 x 5 x_5 x5 系数 c 5 c_5 c5)	x 5 x_5 x5	10 10 10	1 1 1	− 1 -1 −1	2 2 2	0 0 0	1 1 1	0 0 0	0 0 0	? ? ? ( θ 5 \theta_5 θ5 )
− M -M −M ( 目标函数 x 7 x_7 x7 系数 c 7 c_7 c7)	x 7 x_7 x7	1 1 1	2 2 2	− 2 -2 −2	1 1 1	0 0 0	0 0 0	0 0 0	1 1 1	? ? ? ( θ 7 \theta_7 θ7 )
σ j \sigma_j σj ( 检验数 )			? ? ? ( σ 1 \sigma_1 σ1 )	? ? ? ( σ 2 \sigma_2 σ2 )	? ? ? ( σ 3 \sigma_3 σ3 )	? ? ? ( σ 3 \sigma_3 σ3 )	0 0 0	0 0 0	0 0 0

c_j

3

2

-1

0

-M

C_B

基变量系数 (目标函数)

X_B

基变量常数

b

x_1

x_2

x_3

x_4

x_5

x_6

x_7

\theta_i

-M

( 目标函数

x_6

系数

c_6

)

x_6

4

-4

3

1

-1

0

1

0

?

(

\theta_6

)

0

( 目标函数

x_5

系数

c_5

)

x_5

10

1

-1

2

0

1

0

?

(

\theta_5

)

-M

( 目标函数

x_7

系数

c_7

)

x_7

1

2

-2

1

0

1

?

(

\theta_7

)

\sigma_j

( 检验数 )

?

(

\sigma_1

)

?

(

\sigma_2

)

?

(

\sigma_3

)

?

(

\sigma_3

)

0

注意基变量顺序 : 初始基可行解的单位阵的顺序 , 是

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

, 对应的基变量顺序是

\begin{pmatrix} \quad x_6 \quad x_5 \quad x_7 \quad \\ \end{pmatrix}

x_6

系数是

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

x_5

系数是

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

x_7

系数是

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

二、计算非基变量检验数

1 . 计算非基变量

x_1

的检验数

\sigma_1

:

\sigma_1 = 3 - \begin{pmatrix} \quad -M \quad 0 \quad -M \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad -4 \quad \\\\ \quad 1 \quad \\\\ \quad 2 \quad \end{pmatrix} = 3- ( -M \times -4 + 0 \times 1 + -M \times 2) =3 - 2M

其中

M

是正无穷

+\infin

,

3 - 2M

是负数 ;

2 . 计算非基变量

x_2

的检验数

\sigma_2

:

\sigma_2 = 2 - \begin{pmatrix} \quad -M \quad 0 \quad -M \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad 3 \quad \\\\ \quad -1 \quad \\\\ \quad -2 \quad \end{pmatrix} = 2- ( -M \times 3 + 0 \times -1 + -M \times -2) = 2 + M

其中

M

是正无穷

+\infin

,

2 + M

是正数 ;

3 . 计算非基变量

x_3

的检验数

\sigma_3

:

\sigma_3 = -1 - \begin{pmatrix} \quad -M \quad 0 \quad -M \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad 1 \quad \\\\ \quad 2 \quad \\\\ \quad 1 \quad \end{pmatrix} = -1- ( -M \times 1 + 0 \times 2 + -M \times 1) =-1 + 2M

其中

M

是正无穷

+\infin

,

-1 + 2M

是正数 ;

4 . 计算非基变量

x_4

的检验数

\sigma_4

:

\sigma_4 = 0 - \begin{pmatrix} \quad -M \quad 0 \quad -M \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad -1 \quad \\\\ \quad 0 \quad \\\\ \quad 0 \quad \end{pmatrix} = 0- ( -M \times -1 + 0 \times 0 + -M \times 0) =-M

其中

M

是正无穷

+\infin

,

-M

是负数 ;

三、最优解判定

根据上述四个检验数

\begin{cases} \sigma_1 = 3 - 2M \quad ( 负数 )\\\\ \sigma_2= 2 + M \quad ( 正数 )\\\\ \sigma_3= -1 + 2M \quad ( 正数 ) \\\\ \sigma_4 = -M \quad ( 负数 ) \end{cases}

的值 , 其中

\sigma_2 , \sigma_3

检验数大于

0

, 该基可行解不是最优解 ;

只有当检验数都小于等于

0

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

四、选择入基变量

根据上述四个检验数

\begin{cases} \sigma_1 = 3 - 2M\\\\ \sigma_2= 2 + M\\\\ \sigma_3= -1 + 2M \\\\ \sigma_4 = -M \end{cases}

的值 , 选择检验数最大的非基变量作为入基变量 ,

\sigma_3= -1 + 2M

最大 , 这里选择

x_3

;

五、选择出基变量

出基变量选择 : 常数列

b =\begin{pmatrix} \quad 4 \quad \\ \quad 10 \quad \\ \quad 1 \quad \\ \end{pmatrix}

, 分别除以除以入基变量

x_3

大于

0

的系数列

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

, 计算过程如下

\begin{pmatrix} \quad \cfrac{4}{1} \quad \\\\ \quad \cfrac{10}{2} \quad \\\\ \quad \cfrac{1}{ 1} \quad \end{pmatrix}

, 得出结果是

\begin{pmatrix} \quad 4 \quad \\\\ \quad 5 \quad \\\\ \quad 1 \quad \end{pmatrix}

, 如果系数小于等于

0

, 该值就是无效值 , 默认为无穷大 , 不进行比较 , 选择

1

对应的基变量作为出基变量 , 查看该最小值对应的变量是

x_7

, 选择该

x_7

变量作为出基变量 ;

六、更新单纯形表

c j c_j cj	c j c_j cj		3 3 3	2 2 2	− 1 -1 −1	0 0 0	0 0 0	− M -M −M	− M -M −M
C B C_B CB 基变量系数 (目标函数)	X B X_B XB 基变量	常数 b b b	x 1 x_1 x1	x 2 x_2 x2	x 3 x_3 x3	x 4 x_4 x4	x 5 x_5 x5	x 6 x_6 x6	x 7 x_7 x7	θ i \theta_i θi
− M -M −M ( 目标函数 x 6 x_6 x6 系数 c 6 c_6 c6 )	x 6 x_6 x6	4 4 4	− 4 -4 −4	3 3 3	1 1 1	− 1 -1 −1	0 0 0	1 1 1	0 0 0	4 4 4 ( θ 6 \theta_6 θ6)
0 0 0 ( 目标函数 x 5 x_5 x5 系数 c 5 c_5 c5)	x 5 x_5 x5	10 10 10	1 1 1	− 1 -1 −1	2 2 2	0 0 0	1 1 1	0 0 0	0 0 0	5 5 5 ( θ 5 \theta_5 θ5 )
− M -M −M ( 目标函数 x 7 x_7 x7 系数 c 7 c_7 c7)	x 7 x_7 x7	1 1 1	2 2 2	− 2 -2 −2	1 1 1	0 0 0	0 0 0	0 0 0	1 1 1	1 1 1 ( θ 7 \theta_7 θ7 )
σ j \sigma_j σj ( 检验数 )			3 − 2 M 3-2M 3−2M ( σ 1 \sigma_1 σ1 )	2 + M 2+M 2+M ( σ 2 \sigma_2 σ2 )	− 1 + 2 M -1 + 2M −1+2M ( σ 3 \sigma_3 σ3 )	− M -M −M ( σ 3 \sigma_3 σ3 )	0 0 0	0 0 0	0 0 0

c_j

3

2

-1

0

-M

C_B

基变量系数 (目标函数)

X_B

基变量常数

b

x_1

x_2

x_3

x_4

x_5

x_6

x_7

\theta_i

-M

( 目标函数

x_6

系数

c_6

)

x_6

4

-4

3

1

-1

0

1

0

4

(

\theta_6

)

0

( 目标函数

x_5

系数

c_5

)

x_5

10

1

-1

2

0

1

0

5

(

\theta_5

)

-M

( 目标函数

x_7

系数

c_7

)

x_7

1

2

-2

1

0

1

(

\theta_7

)

\sigma_j

( 检验数 )

3-2M

(

\sigma_1

)

2+M

(

\sigma_2

)

-1 + 2M

(

\sigma_3

)

-M

(

\sigma_3

)

0

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

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

变量

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

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

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

登录后参与评论

0 条评论

热度