前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >【运筹学】线性规划 单纯形法 案例二 ( 第二次迭代 | 矩阵变换 | 检验数计算 | 最优解判定 )

【运筹学】线性规划 单纯形法 案例二 ( 第二次迭代 | 矩阵变换 | 检验数计算 | 最优解判定 )

作者头像
韩曙亮
发布于 2023-03-28 16:26:03
5010
发布于 2023-03-28 16:26:03
举报
文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

【运筹学】线性规划数学模型 ( 单纯形法 | 第二次迭代 | 方程组同解变换 | 生成新单纯形表 | 计算检验数 | 最优解判定 | 线性规划解个数分析 ) 后续博客 , 在上一篇博客中进行了 第二次迭代 , 使用中心元变换得到新的系数矩阵 , 计算检验数 , 验证最优解 , 计算入基变量 , 出基变量 , 本篇博客开始进行第三次迭代 ;

一、第二次迭代 : 进行矩阵变换

在上一篇博客中 , 第一次迭代后 , 找到 入基变量

x_1

, 出基变量

x_4

, 使用

x_1

替换基变量中的

x_4

位置 ;

新的单纯形表为 :

c j c_j cj​

c j c_j cj​

​

1 1 1

2 2 2

1 1 1

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​

x 5 x_5 x5​

θ i \theta_i θi​

0 0 0 ( 目标函数 x 4 x_4 x4​ 系数 c 4 c_4 c4​ )

x 4 x_4 x4​

15 15 15

2 2 2

− 3 -3 −3

2 2 2

1 1 1

0 0 0

− - − ( θ 4 \theta_4 θ4​)

0 0 0 ( 目标函数 x 5 x_5 x5​ 系数 c 5 c_5 c5​)

x 5 x_5 x5​

20 20 20

1 3 \dfrac{1}{3} 31​

1 1 1

5 5 5

0 0 0

1 1 1

20 20 20 ( θ 5 \theta_5 θ5​ )

σ j \sigma_j σj​ ( 检验数 )

​

​

1 1 1 ( σ 1 \sigma_1 σ1​ )

2 2 2 ( σ 2 \sigma_2 σ2​ )

1 1 1 ( σ 3 \sigma_3 σ3​ )

0 0 0

0 0 0

​

第一次迭代

–

–

–

–

–

–

–

–

0 0 0 ( 目标函数 x 4 x_4 x4​ 系数 c 4 c_4 c4​ )

x 4 x_4 x4​

75 75 75

3 3 3

0 0 0

17 17 17

1 1 1

3 3 3

25 25 25 ( θ 4 \theta_4 θ4​ )

2 2 2 ( 目标函数 x 2 x_2 x2​ 系数 c 2 c_2 c2​)

x 2 x_2 x2​

20 20 20

1 3 \dfrac{1}{3} 31​

1 1 1

5 5 5

0 0 0

1 1 1

60 60 60 ( θ 2 \theta_2 θ2​)

σ j \sigma_j σj​ ( 检验数 )

​

​

1 3 \dfrac{1}{3} 31​ ( σ 1 \sigma_1 σ1​ )

0 0 0

− 9 -9 −9 ( σ 3 \sigma_3 σ3​ )

0 0 0

− 2 -2 −2 ( σ 5 \sigma_5 σ5​ )

​

第二次迭代

–

–

–

–

–

–

–

–

1 1 1 ( 目标函数 x 1 x_1 x1​ 系数 c 1 c_1 c1​ )

x 1 x_1 x1​

? ? ?

? ? ?

? ? ?

? ? ?

? ? ?

? ? ?

? ? ? ( θ 1 \theta_1 θ1​ )

2 2 2 ( 目标函数 x 2 x_2 x2​ 系数 c 2 c_2 c2​)

x 2 x_2 x2​

? ? ?

? ? ?

? ? ?

? ? ?

? ? ?

? ? ?

? ? ? ( θ 2 \theta_2 θ2​)

σ j \sigma_j σj​ ( 检验数 )

​

​

0 0 0

0 0 0

? ? ? ( σ 3 \sigma_3 σ3​ )

? ? ? ( σ 4 \sigma_4 σ4​ )

? ? ? ( σ 5 \sigma_5 σ5​ )

​

c_j
c_j
1
2
1
0
0
C_B

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

b
x_1
x_2
x_3
x_4
x_5
\theta_i
0

( 目标函数

x_4

系数

c_4

)

x_4
15
2
-3
2
1
0
-

(

\theta_4

)

0

( 目标函数

x_5

系数

c_5

)

x_5
20
\dfrac{1}{3}
1
5
0
1
20

(

\theta_5

)

\sigma_j

( 检验数 )

1

(

\sigma_1

)

2

(

\sigma_2

)

1

(

\sigma_3

)

0
0

第一次迭代––––––––

0

( 目标函数

x_4

系数

c_4

)

x_4
75
3
0
17
1
3
25

(

\theta_4

)

2

( 目标函数

x_2

系数

c_2

)

x_2
20
\dfrac{1}{3}
1
5
0
1
60

(

\theta_2

)

\sigma_j

( 检验数 )

\dfrac{1}{3}

(

\sigma_1

)

0
-9

(

\sigma_3

)

0
-2

(

\sigma_5

)第二次迭代––––––––

1

( 目标函数

x_1

系数

c_1

)

x_1
?
?
?
?
?
?
?

(

\theta_1

)

2

( 目标函数

x_2

系数

c_2

)

x_2
?
?
?
?
?
?
?

(

\theta_2

)

\sigma_j

( 检验数 )

0
0
?

(

\sigma_3

)

?

(

\sigma_4

)

?

(

\sigma_5

)

中心元 : 入基变量

x_1

所在列 , 与出基变量

x_4

所在行 , 相交的位置叫做中心元 ;

  • 中心元系数 : 转换成
1

;

  • 中心元所在列另一个系数 : 转换成
0

;

当前的线性规划标准形式等式方程组 :

\begin{cases} 3 x_1 + 0x_2 + 17x_3 + x_4 + 3x_5 = 75 \\\\ \dfrac{1}{3}x_1 + x_2 + 5x_3 + 0x_4 + x_5 = 20 \end{cases}

中心元转换为

1

: 将

3 x_1 + 0x_2 + 17x_3 + x_4 + 3x_5 = 75

中的

x_1

系数变成

1

, 只需要将方程等式两边都乘以

\cfrac{1}{3}

即可 ;

\begin{array}{lcl} ( 3 x_1 + 0x_2 + 17x_3 + x_4 + 3x_5 ) \times \cfrac{1}{3} &=& 75 \times \cfrac{1}{3}\\\\ x_1 + 0 x_2 + \cfrac{17}{3} x_3 + \dfrac{1}{3}x_4 + x_5 &=& 25 \end{array}

与中心元同一列的

x_1

的系数转换为

0

: 将

\dfrac{1}{3}x_1 + x_2 + 5x_3 + 0x_4 + x_5 = 20

中的

x_1

系数转为

0

:

  • 将
x_1 + 0 x_2 + \cfrac{17}{3} x_3 + \dfrac{1}{3}x_4 + x_5 = 25

方程 左右变量乘以

-\dfrac{1}{3}

;

  • 将上个步骤得到的等式与
\dfrac{1}{3}x_1 + x_2 + 5x_3 + 0x_4 + x_5 = 20

相加 , 即可使

x_1

系数为

0

;

\begin{array}{lcl} ( x_1 + 0 x_2 + \cfrac{17}{3} x_3 + \dfrac{1}{3}x_4 + x_5 ) \times -\dfrac{1}{3} + ( \dfrac{1}{3}x_1 + x_2 + 5x_3 + 0x_4 + x_5 )= 25 \times -\dfrac{1}{3} + 20 \\\\ (-x_1 + 0x_2 -\cfrac{17}{9} x_3 - \dfrac{1}{9}x_4 -\dfrac{1}{3} x_5 ) + ( \dfrac{1}{3}x_1 + x_2 + 5x_3 + 0x_4 + x_5 ) = \dfrac{35}{3} \\\\ 0x_1 + x_2 + \cfrac{28}{9} x_3 - \dfrac{1}{9}x_4 + \cfrac{2}{3} x_5 = \dfrac{35}{3} \end{array}

新的单纯形表为 :

c j c_j cj​

c j c_j cj​

​

1 1 1

2 2 2

1 1 1

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​

x 5 x_5 x5​

θ i \theta_i θi​

0 0 0 ( 目标函数 x 4 x_4 x4​ 系数 c 4 c_4 c4​ )

x 4 x_4 x4​

15 15 15

2 2 2

− 3 -3 −3

2 2 2

1 1 1

0 0 0

− - − ( θ 4 \theta_4 θ4​)

0 0 0 ( 目标函数 x 5 x_5 x5​ 系数 c 5 c_5 c5​)

x 5 x_5 x5​

20 20 20

1 3 \dfrac{1}{3} 31​

1 1 1

5 5 5

0 0 0

1 1 1

20 20 20 ( θ 5 \theta_5 θ5​ )

σ j \sigma_j σj​ ( 检验数 )

​

​

1 1 1 ( σ 1 \sigma_1 σ1​ )

2 2 2 ( σ 2 \sigma_2 σ2​ )

1 1 1 ( σ 3 \sigma_3 σ3​ )

0 0 0

0 0 0

​

第一次迭代

–

–

–

–

–

–

–

–

0 0 0 ( 目标函数 x 4 x_4 x4​ 系数 c 4 c_4 c4​ )

x 4 x_4 x4​

75 75 75

3 3 3

0 0 0

17 17 17

1 1 1

3 3 3

25 25 25 ( θ 4 \theta_4 θ4​ )

2 2 2 ( 目标函数 x 2 x_2 x2​ 系数 c 2 c_2 c2​)

x 2 x_2 x2​

20 20 20

1 3 \dfrac{1}{3} 31​

1 1 1

5 5 5

0 0 0

1 1 1

60 60 60 ( θ 2 \theta_2 θ2​)

σ j \sigma_j σj​ ( 检验数 )

​

​

1 3 \dfrac{1}{3} 31​ ( σ 1 \sigma_1 σ1​ )

0 0 0

− 9 -9 −9 ( σ 3 \sigma_3 σ3​ )

0 0 0

− 2 -2 −2 ( σ 5 \sigma_5 σ5​ )

​

第二次迭代

–

–

–

–

–

–

–

–

1 1 1 ( 目标函数 x 1 x_1 x1​ 系数 c 1 c_1 c1​ )

x 1 x_1 x1​

25 25 25

1 1 1

0 0 0

17 3 \dfrac{17}{3} 317​

1 3 \dfrac{1}{3} 31​

1 1 1

? ? ? ( θ 1 \theta_1 θ1​ )

2 2 2 ( 目标函数 x 2 x_2 x2​ 系数 c 2 c_2 c2​)

x 2 x_2 x2​

35 3 \dfrac{35}{3} 335​

0 0 0

1 1 1

28 9 \dfrac{28}{9} 928​

− 1 9 -\dfrac{1}{9} −91​

2 3 \dfrac{2}{3} 32​

? ? ? ( θ 2 \theta_2 θ2​)

σ j \sigma_j σj​ ( 检验数 )

​

​

0 0 0

0 0 0

? ? ? ( σ 3 \sigma_3 σ3​ )

? ? ? ( σ 4 \sigma_4 σ4​ )

? ? ? ( σ 5 \sigma_5 σ5​ )

​

c_j
c_j
1
2
1
0
0
C_B

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

b
x_1
x_2
x_3
x_4
x_5
\theta_i
0

( 目标函数

x_4

系数

c_4

)

x_4
15
2
-3
2
1
0
-

(

\theta_4

)

0

( 目标函数

x_5

系数

c_5

)

x_5
20
\dfrac{1}{3}
1
5
0
1
20

(

\theta_5

)

\sigma_j

( 检验数 )

1

(

\sigma_1

)

2

(

\sigma_2

)

1

(

\sigma_3

)

0
0

第一次迭代––––––––

0

( 目标函数

x_4

系数

c_4

)

x_4
75
3
0
17
1
3
25

(

\theta_4

)

2

( 目标函数

x_2

系数

c_2

)

x_2
20
\dfrac{1}{3}
1
5
0
1
60

(

\theta_2

)

\sigma_j

( 检验数 )

\dfrac{1}{3}

(

\sigma_1

)

0
-9

(

\sigma_3

)

0
-2

(

\sigma_5

)第二次迭代––––––––

1

( 目标函数

x_1

系数

c_1

)

x_1
25
1
0
\dfrac{17}{3}
\dfrac{1}{3}
1
?

(

\theta_1

)

2

( 目标函数

x_2

系数

c_2

)

x_2
\dfrac{35}{3}
0
1
\dfrac{28}{9}
-\dfrac{1}{9}
\dfrac{2}{3}
?

(

\theta_2

)

\sigma_j

( 检验数 )

0
0
?

(

\sigma_3

)

?

(

\sigma_4

)

?

(

\sigma_5

)

二、第二次迭代 : 计算检验数

1 . 计算非基变量

x_3

的检验数

\sigma_3

:

\sigma_3 = 1 - \begin{pmatrix} \quad 1 \quad 2 \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad \dfrac{17}{3} \quad \\\\ \quad \dfrac{28}{9} \quad \\ \end{pmatrix} = 1- ( 1 \times \dfrac{17}{3} + 2 \times \dfrac{28}{9} ) = \dfrac{9 - 17 \times 3 + 28 \times 2}{9} = - \dfrac{98}{9}

2 . 计算非基变量

x_4

的检验数

\sigma_4

:

\sigma_4 = 0 - \begin{pmatrix} \quad 1 \quad 2 \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad \dfrac{1}{3} \quad \\\\ \quad -\dfrac{1}{9} \quad \\ \end{pmatrix} = 0- ( 1 \times \dfrac{1}{3} - 2 \times \dfrac{1}{9} ) = - \dfrac{1}{9}

3 . 计算非基变量

x_5

的检验数

\sigma_5

:

\sigma_5 = 0 - \begin{pmatrix} \quad 1 \quad 2 \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad 1 \quad \\\\ \quad \dfrac{2}{3} \quad \\ \end{pmatrix} = 0- ( 1 \times 1 + 2 \times \dfrac{2}{3} ) = - \dfrac{7}{3}

新的单纯形表为 :

c j c_j cj​

c j c_j cj​

​

1 1 1

2 2 2

1 1 1

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​

x 5 x_5 x5​

θ i \theta_i θi​

0 0 0 ( 目标函数 x 4 x_4 x4​ 系数 c 4 c_4 c4​ )

x 4 x_4 x4​

15 15 15

2 2 2

− 3 -3 −3

2 2 2

1 1 1

0 0 0

− - − ( θ 4 \theta_4 θ4​)

0 0 0 ( 目标函数 x 5 x_5 x5​ 系数 c 5 c_5 c5​)

x 5 x_5 x5​

20 20 20

1 3 \dfrac{1}{3} 31​

1 1 1

5 5 5

0 0 0

1 1 1

20 20 20 ( θ 5 \theta_5 θ5​ )

σ j \sigma_j σj​ ( 检验数 )

​

​

1 1 1 ( σ 1 \sigma_1 σ1​ )

2 2 2 ( σ 2 \sigma_2 σ2​ )

1 1 1 ( σ 3 \sigma_3 σ3​ )

0 0 0

0 0 0

​

第一次迭代

–

–

–

–

–

–

–

–

0 0 0 ( 目标函数 x 4 x_4 x4​ 系数 c 4 c_4 c4​ )

x 4 x_4 x4​

75 75 75

3 3 3

0 0 0

17 17 17

1 1 1

3 3 3

25 25 25 ( θ 4 \theta_4 θ4​ )

2 2 2 ( 目标函数 x 2 x_2 x2​ 系数 c 2 c_2 c2​)

x 2 x_2 x2​

20 20 20

1 3 \dfrac{1}{3} 31​

1 1 1

5 5 5

0 0 0

1 1 1

60 60 60 ( θ 2 \theta_2 θ2​)

σ j \sigma_j σj​ ( 检验数 )

​

​

1 3 \dfrac{1}{3} 31​ ( σ 1 \sigma_1 σ1​ )

0 0 0

− 9 -9 −9 ( σ 3 \sigma_3 σ3​ )

0 0 0

− 2 -2 −2 ( σ 5 \sigma_5 σ5​ )

​

第二次迭代

–

–

–

–

–

–

–

–

1 1 1 ( 目标函数 x 1 x_1 x1​ 系数 c 1 c_1 c1​ )

x 1 x_1 x1​

25 25 25

1 1 1

0 0 0

17 3 \dfrac{17}{3} 317​

1 3 \dfrac{1}{3} 31​

1 1 1

? ? ? ( θ 1 \theta_1 θ1​ )

2 2 2 ( 目标函数 x 2 x_2 x2​ 系数 c 2 c_2 c2​)

x 2 x_2 x2​

35 3 \dfrac{35}{3} 335​

0 0 0

1 1 1

28 9 \dfrac{28}{9} 928​

− 1 9 -\dfrac{1}{9} −91​

2 3 \dfrac{2}{3} 32​

? ? ? ( θ 2 \theta_2 θ2​)

σ j \sigma_j σj​ ( 检验数 )

​

​

0 0 0

0 0 0

− 98 9 - \dfrac{98}{9} −998​ ( σ 3 \sigma_3 σ3​ )

− 1 9 - \dfrac{1}{9} −91​ ( σ 4 \sigma_4 σ4​ )

− 7 3 - \dfrac{7}{3} −37​ ( σ 5 \sigma_5 σ5​ )

​

c_j
c_j
1
2
1
0
0
C_B

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

b
x_1
x_2
x_3
x_4
x_5
\theta_i
0

( 目标函数

x_4

系数

c_4

)

x_4
15
2
-3
2
1
0
-

(

\theta_4

)

0

( 目标函数

x_5

系数

c_5

)

x_5
20
\dfrac{1}{3}
1
5
0
1
20

(

\theta_5

)

\sigma_j

( 检验数 )

1

(

\sigma_1

)

2

(

\sigma_2

)

1

(

\sigma_3

)

0
0

第一次迭代––––––––

0

( 目标函数

x_4

系数

c_4

)

x_4
75
3
0
17
1
3
25

(

\theta_4

)

2

( 目标函数

x_2

系数

c_2

)

x_2
20
\dfrac{1}{3}
1
5
0
1
60

(

\theta_2

)

\sigma_j

( 检验数 )

\dfrac{1}{3}

(

\sigma_1

)

0
-9

(

\sigma_3

)

0
-2

(

\sigma_5

)第二次迭代––––––––

1

( 目标函数

x_1

系数

c_1

)

x_1
25
1
0
\dfrac{17}{3}
\dfrac{1}{3}
1
?

(

\theta_1

)

2

( 目标函数

x_2

系数

c_2

)

x_2
\dfrac{35}{3}
0
1
\dfrac{28}{9}
-\dfrac{1}{9}
\dfrac{2}{3}
?

(

\theta_2

)

\sigma_j

( 检验数 )

0
0
- \dfrac{98}{9}

(

\sigma_3

)

- \dfrac{1}{9}

(

\sigma_4

)

- \dfrac{7}{3}

(

\sigma_5

)

三、第二次迭代 : 最优解判定

上述三个检验数 ,

\begin{cases} \sigma_3 =- \dfrac{98}{9} \\\\ \sigma_4= - \dfrac{1}{9} \\\\ \sigma_5 = - \dfrac{7}{3} \end{cases}

, 三个检验数都小于等于

0

, 该基可行解是最优解 ;

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-07-26，如有侵权请联系 cloudcommunity@tencent.com 删除
变量
博客
函数

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

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

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

变量
博客
函数
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 文章目录
  • 一、第二次迭代 : 进行矩阵变换
  • 二、第二次迭代 : 计算检验数
  • 三、第二次迭代 : 最优解判定
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2024 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论