提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

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

案例计算变量迭代 矩阵 最优 变换 检验
2023-06-13 09:17:43 时间

文章目录

【运筹学】线性规划 单纯形法 ( 案例解析 | 标准形转化 | 查找初始基可行解 | 最优解判定 | 查找入基变量与出基变量 | 迭代一 : 列出单纯形表) 后续博客 , 在上一篇博客中进行了 初始基可行解的检验数计算 , 最优解判定 , 入基变量与出基变量计算 , 并开始第一次迭代 ; 本篇博客中进行后续步骤解析 ;

一、第一次迭代 : 进行行变换

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

\begin{cases} 2 x_1 - 3x_2 + 2x_3 + x_4 + 0x_5 = 15 \\\\ \dfrac{1}{3}x_1 + x_2 + 5x_3 + 0x_4 + x_5 = 20 \end{cases}

当前的单纯性表 :

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​

? ? ?

? ? ?

? ? ?

? ? ?

? ? ?

? ? ?

? ? ? ( θ 4 \theta_4 θ4​ )

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​ ( 检验数 )

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

0 0 0

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

0 0 0

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

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

(

\theta_4

)

2

( 目标函数

x_2

系数

c_2

)

x_2
?
?
?
?
?
?
?

(

\theta_2

)

\sigma_j

( 检验数 )

?

(

\sigma_1

)

0
?

(

\sigma_3

)

0
?

(

\sigma_2

)

下面进行矩阵变换 :

  • 入基变量是
x_2
  • 出基变量是
x_5

中心元 : 在下面单纯形表中 ,

x_2

列 ( 红色选框 ) , 与

x_5

行 ( 绿色选框 ) , 上述 行列相交的部分 是 中心元 ,

以上述 中心元 为轴做变换 , 变换目的是把 中心元位置变换成

1

, 把中心元所在列的另一个位置变换成

0

;

该行中

x_2

的系数 , 就是

1

, 不用改变 , 因此这里将第二行的系数原封不动填入第一次迭代的单纯形表中 ;

接下来要将上图 蓝色选框 部分的位置 , 变为

0

, 变换过程如下 :

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

方程 等式左右两边乘以

3

;

  • 与
2 x_1 - 3x_2 + 2x_3 + x_4 + 0x_5 = 15

相加 ;

\begin{array}{lcl} (\dfrac{1}{3}x_1 + x_2 + 5x_3 + 0x_4 + x_5 ) \times 3 + ( 2 x_1 - 3x_2 + 2x_3 + x_4 + 0x_5 ) &=& 20 \times 3 + 15 \\\\ ( x_1 + 3x_2 + 15x_3 + 3x_5 ) + ( 2 x_1 - 3x_2 + 2x_3 + x_4 + 0x_5 ) &=& 75 \\\\ 3 x_1 + 0x_2 + 17x_3 + x_4 + 3x_5 &=& 75 \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

? ? ? ( θ 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

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

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

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

0 0 0

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

0 0 0

? ? ? ( σ 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
?

(

\theta_4

)

2

( 目标函数

x_2

系数

c_2

)

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

(

\theta_2

)

\sigma_j

( 检验数 )

?

(

\sigma_1

)

0
?

(

\sigma_3

)

0
?

(

\sigma_5

)

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

1 . 计算非基变量

x_1

的检验数

\sigma_1

:

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

2 . 计算非基变量

x_3

的检验数

\sigma_3

:

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

3 . 计算非基变量

x_5

的检验数

\sigma_5

:

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

新的单纯形表为 :

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

? ? ? ( θ 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

? ? ? ( θ 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​ )

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
?

(

\theta_4

)

2

( 目标函数

x_2

系数

c_2

)

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

(

\theta_2

)

\sigma_j

( 检验数 )

\dfrac{1}{3}

(

\sigma_1

)

0
-9

(

\sigma_3

)

0
-2

(

\sigma_5

)

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

上述三个检验数 ,

\begin{cases} \sigma_1 = \dfrac{1}{3} \\\\ \sigma_3= -9 \\\\ \sigma_5 = -2 \end{cases}

, 其中

\sigma_1

大于

0

, 只有当检验数都小于等于

0

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

无穷多最优解 : 当有检验数等于

0

时 , 其它都小于

0

, 该线性规划有无穷多个最优解 ; 无界解 : 找不到出基变量 , 则该线性规划是无界解 ;

四、第一次迭代 : 入基变量

根据上述三个检验数

\begin{cases} \sigma_1 = \dfrac{1}{3} \\\\ \sigma_3= -9 \\\\ \sigma_5 = -2 \end{cases}

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

x_1

;

五、第一次迭代 : 出基变量

出基变量选择 : 常数列

b =\begin{pmatrix} \quad 75 \quad \\ \quad 20 \quad \end{pmatrix}

, 分别除以除以入基变量

x_1

大于

0

的系数列

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

, 计算过程如下

\begin{pmatrix} \quad \cfrac{75}{3} \quad \\\\ \quad \cfrac{20}{ \dfrac{1}{3}} \quad \end{pmatrix}

, 得出结果是

\begin{pmatrix} \quad 25 \quad \\\\ \quad 60 \quad \end{pmatrix}

, 如果系数小于等于

0

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

25

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

x_4

, 选择该

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​ )

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

)

下一篇博客 开始第二次迭代

相关文章