文章/答案/技术大牛

发布

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

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

韩曙亮

发布于 2023-03-28 08:24:02

2.2K0

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

文章目录

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

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

( 目标函数

$x_4$

系数

$c_4$

)

$x_4$

$30$

$1$

$3$

$0$

$1$

$\sigma_j$

$3$

$4$

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

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

;

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

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

入基变量根据检验数

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

)

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

当前的方程组为

$\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 )