前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >【运筹学】线性规划 单纯形法 阶段总结 ( 初始基可行解 | 判定最优解 | 迭代 | 得到最优解 | 全流程详细解析 ) ★

【运筹学】线性规划 单纯形法 阶段总结 ( 初始基可行解 | 判定最优解 | 迭代 | 得到最优解 | 全流程详细解析 ) ★

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

文章目录

\sigma_j

判定最优解 并选择入基变量

单纯形法 参考博客 :

1 . 查找初始基可行解 :

2 . 最优解判定 :

3 . 迭代原则 :

4 . 单纯形法阶段总结 :

一、线性规划示例

使用单纯形法求解线性规划最优解 :

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

二、转化标准形式

首先将该线性规划转为标准形式 :

参考 【运筹学】线性规划数学模型标准形式 ( 标准形式 | 目标函数转化 | 决策变量转化 | 约束方程转化 | 固定转化顺序 | 标准形式转化实例 ) 线性规划 普通形式 -> 标准形式 转化顺序说明 博客 , 先处理变量约束 , 再将不等式转为等式 , 最后更新目标函数 ;

① 变量约束 : 首先查看变量约束 , 两个变量都是

\geq 0

的 , 符合线性规划标准形式要求 ;

② 不等式转换 : 两个等式都是 小于等于不等式 , 需要 在不等式左侧加入松弛变量 , 将其转为等式 ;

  • ​
2 x_1 + x_2 \leq 40

, 左侧加入松弛变量

x_3

, 变为

2 x_1 + x_2 + x_3 = 40
  • ​
x_1 + 3x_2 \leq 30

, 左侧加入松弛变量

x_4

, 变为

x_1 + 3x_2 + x_4 = 30

③ 更新目标函数 : 将

x_3

和

x_4

加入到目标函数中 , 得到新的目标函数

max Z = 3x_1 + 4x_2 + 0x_3 + 0x_4

;

此时线性规划标准形式为 :

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

三、查找初始基可行解

找基矩阵 :

上述线性规划标准形式的系数矩阵为

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

, 其中子矩阵中有

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

单位阵

I

;

使用该单位阵

I

作为基矩阵 , 单位阵肯定是可逆的 , 其对应的基解 , 解出后的值就是右侧的常数值 , 肯定大于等于

0

, 是基可行解 ;

列出单纯形表 :

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
c_j
3
4
0
0
C_B

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

b
x_1
x_2
x_3
x_4
\theta_i
0

( 目标函数

x_3

系数

c_3

)

x_3
40
2
1
1
0
0

( 目标函数

x_4

系数

c_4

)

x_4
30
1
3
0
1
\sigma_j
3
4
0
0

基变量是

x_3

和

x_4

, 基变量在约束条件中的系数矩阵

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

就是基矩阵 , 这是个单位阵 ;

基变量是

x_3

和

x_4

在目标函数中的系数是

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

;

此时的基解是

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

, 该解是初始解 , 下面判定该解是否是最优解 ;

四、初始基可行解的最优解判定

使用 检验数矩阵

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

判断上述解 , 是否是最优解 , 该矩阵计算结果中所有的数 , 都是检验数

\sigma

, 如果 所有的数都小于等于

0

, 说明该解就是最优解 ;

这里只求非基变量的检验数 , 即

x_1

,

x_2

的检验数 ;

列出目标函数非基变量系数

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

矩阵 :

  • 非基变量在目标函数中的系数矩阵 :
C_N^T=\begin{pmatrix} \quad 3 \quad 4 \quad \end{pmatrix}
  • 基变量在目标函数中的叙述矩阵 :
C_B^T = \begin{pmatrix} \quad 0 \quad 0 \quad \end{pmatrix}
B^{-1}N

是系数矩阵中经过矩阵变换后 , 基变量系数是单位阵

I

, 非基变量系数是

B^{-1}N

:

B^{-1}N =\begin{bmatrix} &2 & 1 & \\\\ &1 & 3 & \end{bmatrix}
( C_N^T - C_B^T B^{-1}N ) = C_N^T=\begin{pmatrix} \quad 3 \quad 4 \quad \end{pmatrix} - \begin{pmatrix} \quad 0 \quad 0 \quad \end{pmatrix} \times \begin{bmatrix} &2 & 1 & \\\\ &1 & 3 & \end{bmatrix}
= \begin{pmatrix} \quad \sigma_{1} \quad \sigma_{2} \quad \end{pmatrix}

其中

\sigma_{1}

是目标函数中

x_1

的系数 ,

\sigma_{2}

是目标函数中的

x_2

的系数 ;

如果上述两个系数都小于等于

0

, 那么当 非基变量

X_N =\begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix}

取值为

0

时 , 目标函数取值最大 ;

系数的计算公式为 :

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

, 其中

c_j

对应的是非基变量在目标函数系数 ,

c_i

是基变量在目标函数中的系数 ,

a_{ij}

是

B^{-1}N

中的矩阵向量 , 代表一列 ;

\sigma_{1} = c_1 - ( c_3 a_{11} + c_4 a_{12} )
\sigma_{1} =3 - (0 \times 2) - (0 \times 1) = 3

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

\sigma_{2} = c_2 - ( c_3 a_{21} + c_4 a_{22} )
\sigma_{2} =4 - (0 \times 1) - (0 \times 3) = 4

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

如果这两个系数 , 如果都小于等于

0

, 该 基可行解

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

才是最优解 , 这两个系数都大于

0

, 因此不是最优解 ;

五、第一次迭代 : 入基与出基变量选择

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

\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

;

六、第一次迭代 : 方程组同解变换

方程组做同解变换 :

线性规划原始方程组为

\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
c_j
3
4
0
0
C_B

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

b
x_1
x_2
x_3
x_4
\theta_i
0

( 目标函数

x_3

系数

c_3

)

x_3
40
2
1
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

––––––––

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

;

十、第一次迭代 : 根据入基变量计算并选择出基变量

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

入基变量 根据检验数

\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
c_j
3
4
0
0
C_B

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

b
x_1
x_2
x_3
x_4
\theta_i
0

( 目标函数

x_3

系数

c_3

)

x_3
40
2
1
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

––––––––

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
0
-\dfrac{4}{3}

(

\sigma_4

)

十一、第二次迭代 : 方程组同解变换

当前的方程组为

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

, 选择

x_1, x_2

作为基变量 , 基矩阵为

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

, 进行同解变换 , 将基矩阵转为单位阵 ;

方程

1

同解变换 :

将

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

方程中的

x_1

的系数变为

1

,

x_2

的系数为

0

保持不变 ;

方程的左右变量乘以

\dfrac{3}{5}

:

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

当前方程组变成

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

方程

2

同解变换 : 将方程

1

乘以

-\dfrac{1}{3}

, 与方程

2

相加 ;

① 方程

1

乘以

-\dfrac{1}{3}

:

\begin{array}{lcl} ( x_1 + 0x_2 + \dfrac{3}{5} x_3 - \dfrac{1}{5}x_4 ) \times -\dfrac{1}{3} &=& 18 \times -\dfrac{1}{3} \\\\ -\dfrac{1}{3} x_1 + 0x_2 + -\dfrac{1}{5}x_3 + \dfrac{1}{15} x_4 &=& -6 \end{array}

② 与方程

2

相加 :

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

当前方程组变成

\begin{cases} x_1 + 0x_2 + \dfrac{3}{5} x_3 - \dfrac{1}{5}x_4 = 18 \\\\ 0x_1 + x_2 -\dfrac{1}{5}x_3 + \dfrac{6}{15} x_4 = 4 \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​

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

​

第二次迭代

–

–

–

–

–

–

–

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

x 1 x_1 x1​

18 18 18

1 1 1

0 0 0

3 5 \dfrac{3}{5} 53​

− 1 5 -\dfrac{1}{5} −51​

? ? ? ( θ 3 \theta_3 θ3​ )

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

x 2 x_2 x2​

4 4 4

0 0 0

1 1 1

− 1 5 -\dfrac{1}{5} −51​

2 5 \dfrac{2}{5} 52​

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

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

​

​

0 0 0

0 0 0

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

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

​

c_j
c_j
3
4
0
0
C_B

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

b
x_1
x_2
x_3
x_4
\theta_i
0

( 目标函数

x_3

系数

c_3

)

x_3
40
2
1
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

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

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
0
-\dfrac{4}{3}

(

\sigma_4

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

3

( 目标函数

x_1

系数

c_1

)

x_1
18
1
0
\dfrac{3}{5}
-\dfrac{1}{5}
?

(

\theta_3

)

4

( 目标函数

x_2

系数

c_2

)

x_2
4
0
1
-\dfrac{1}{5}
\dfrac{2}{5}
?

(

\theta_2

)

\sigma_j

( 检验数 )

0
0
?

(

\sigma_3

)

?

(

\sigma_4

)

十三、第二次迭代 : 计算检验数、最优解判定

计算检验数

\sigma

:

\sigma_3 = 0 - 3 \times \dfrac{3}{5} - 4 \times (-\dfrac{1}{5}) = -\dfrac{9}{5} + \dfrac{4}{5} = -1
\sigma_4 = 0 - 3 \times (-\dfrac{1}{5}) - 4 \times \dfrac{2}{5} = \dfrac{3}{5} - \dfrac{8}{5} = -1

两个非基变量的检验数都是小于等于

0

的 , 因此该基可行解

\begin{pmatrix} \quad 18 \quad \\ \quad 4 \quad \\ \quad 0 \quad \\ \quad 0 \quad \end{pmatrix}

是最优解 ;

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-07-21，如有侵权请联系 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. 腾讯云 版权所有

登录 后参与评论