单纯形法 参考博客 :

1 . 查找初始基可行解 :

• 【运筹学】线性规划数学模型 ( 单纯形法原理 | 单纯形法流程 | 查找初始基可行解 )

2 . 最优解判定 :

• 【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 可行解表示 | 目标函数推导 | 目标函数最大值分析 )
• 【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 )
• 【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 线性规划求解示例 )

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}$maxZ=3x1​+4x2​⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​2x1​+x2​≤40x1​+3x2​≤30xj​≥0​(j=1,2)​​

二、转化标准形式

---

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

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

① 变量约束 : 首先查看变量约束 , 两个变量都是 $\geq 0$≥0 的 , 符合线性规划标准形式要求 ;

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

• $2 x_1 + x_2 \leq 40$2x1​+x2​≤40 , 左侧加入松弛变量 $x_3$x3​ , 变为 $2 x_1 + x_2 + x_3 = 40$2x1​+x2​+x3​=40
• $x_1 + 3x_2 \leq 30$x1​+3x2​≤30 , 左侧加入松弛变量 $x_4$x4​ , 变为 $x_1 + 3x_2 + x_4 = 30$x1​+3x2​+x4​=30

③ 更新目标函数 : 将 $x_3$x3​ 和 $x_4$x4​ 加入到目标函数中 , 得到新的目标函数 $max Z = 3x_1 + 4x_2 + 0x_3 + 0x_4$maxZ=3x1​+4x2​+0x3​+0x4​ ;

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

$\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}$maxZ=3x1​+4x2​+0x3​+0x4​⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​2x1​+x2​+x3​+0x4​=40x1​+3x2​+0x3​+x4​=30xj​≥0​(j=1,2,3,4)​​

三、查找初始基可行解

---

找基矩阵 :

上述线性规划标准形式的系数矩阵为 $\begin{bmatrix} &2 & 1 & 1 & 0 & \\\\ & 1 & 3 & 0 & 1 & \end{bmatrix}$⎣⎡​​21​13​10​01​​⎦⎤​ , 其中子矩阵中有 $\begin{bmatrix} & 1 & 0 & \\\\ & 0 & 1 & \end{bmatrix}$⎣⎡​​10​01​​⎦⎤​ 单位阵 $I$I ;

使用该单位阵 $I$I 作为基矩阵 , 单位阵肯定是可逆的 , 其对应的基解 , 解出后的值就是右侧的常数值 , 肯定大于等于 $0$0 , 是基可行解 ;

列出单纯形表 :

$c_j$cj​	$c_j$cj​		$3$3	$4$4	$0$0	$0$0
$C_B$CB​ 基变量系数 (目标函数)	基变量	常数 $b$b	$x_1$x1​	$x_2$x2​	$x_3$x3​	$x_4$x4​	$\theta_i$θi​
$0$0 ( 目标函数 $x_3$x3​ 系数 $c_3$c3​ )	$x_3$x3​	$40$40	$2$2	$1$1	$1$1	$0$0
$0$0 ( 目标函数 $x_4$x4​ 系数 $c_4$c4​)	$x_4$x4​	$30$30	$1$1	$3$3	$0$0	$1$1
		$\sigma_j$σj​	$3$3	$4$4	$0$0	$0$0

基变量是 $x_3$x3​ 和 $x_4$x4​ , 基变量在约束条件中的系数矩阵 $\begin{bmatrix} &1 & 0 & \\\\ &0 & 1 & \end{bmatrix}$⎣⎡​​10​01​​⎦⎤​ 就是基矩阵 , 这是个单位阵 ;

基变量是 $x_3$x3​ 和 $x_4$x4​ 在目标函数中的系数是 $\begin{pmatrix} \quad 0 \quad 0 \quad \end{pmatrix}$(00​) ;

此时的基解是 $\begin{pmatrix} \quad 0 \quad \\ \quad 0 \quad \\ \quad 40 \quad \\ \quad 30 \quad \\ \end{pmatrix}$⎝⎜⎜⎛​004030​⎠⎟⎟⎞​ , 该解是初始解 , 下面判定该解是否是最优解 ;

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

---

使用 检验数矩阵 $( C_N^T - C_B^T B^{-1}N )$(CNT​−CBT​B−1N) 判断上述解 , 是否是最优解 , 该矩阵计算结果中所有的数 , 都是检验数 $\sigma$σ , 如果 所有的数都小于等于 $0$0 , 说明该解就是最优解 ;

这里只求非基变量的检验数 , 即 $x_1$x1​ , $x_2$x2​ 的检验数 ;

列出目标函数非基变量系数 $( C_N^T - C_B^T B^{-1}N )$(CNT​−CBT​B−1N) 矩阵 :

• 非基变量在目标函数中的系数矩阵 : $C_N^T=\begin{pmatrix} \quad 3 \quad 4 \quad \end{pmatrix}$CNT​=(34​)

• 基变量在目标函数中的叙述矩阵 : $C_B^T = \begin{pmatrix} \quad 0 \quad 0 \quad \end{pmatrix}$CBT​=(00​)

• $B^{-1}N$B−1N 是系数矩阵中经过矩阵变换后 , 基变量系数是单位阵 $I$I , 非基变量系数是 $B^{-1}N$B−1N : $B^{-1}N =\begin{bmatrix} &2 & 1 & \\\\ &1 & 3 & \end{bmatrix}$B−1N=⎣⎡​​21​13​​⎦⎤​

$( 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}$(CNT​−CBT​B−1N)=CNT​=(34​)−(00​)×⎣⎡​​21​13​​⎦⎤​

$= \begin{pmatrix} \quad \sigma_{1} \quad \sigma_{2} \quad \end{pmatrix}$=(σ1​σ2​​)

其中 $\sigma_{1}$σ1​ 是目标函数中 $x_1$x1​ 的系数 , $\sigma_{2}$σ2​ 是目标函数中的 $x_2$x2​ 的系数 ;

如果上述两个系数都小于等于 $0$0 , 那么当 非基变量 $X_N =\begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix}$XN​=(x1​x2​​) 取值为 $0$0 时 , 目标函数取值最大 ;

系数的计算公式为 : $\sigma_j = c_j - \sum c_i a_{ij}$σj​=cj​−∑ci​aij​ , 其中 $c_j$cj​ 对应的是非基变量在目标函数系数 , $c_i$ci​ 是基变量在目标函数中的系数 , $a_{ij}$aij​ 是 $B^{-1}N$B−1N 中的矩阵向量 , 代表一列 ;

$\sigma_{1} = c_1 - ( c_3 a_{11} + c_4 a_{12} )$σ1​=c1​−(c3​a11​+c4​a12​)

$\sigma_{1} =3 - (0 \times 2) - (0 \times 1) = 3$σ1​=3−(0×2)−(0×1)=3 , 是从下面的单纯形表中的如下位置提取的数值 ;

$\sigma_{2} = c_2 - ( c_3 a_{21} + c_4 a_{22} )$σ2​=c2​−(c3​a21​+c4​a22​)

$\sigma_{2} =4 - (0 \times 1) - (0 \times 3) = 4$σ2​=4−(0×1)−(0×3)=4 , 是从下面的单纯形表中的如下位置提取的数值 ;

如果这两个系数 , 如果都小于等于 $0$0 , 该 基可行解$\begin{pmatrix} \quad 0 \quad \\ \quad 0 \quad \\ \quad 40 \quad \\ \quad 30 \quad \\ \end{pmatrix}$⎝⎜⎜⎛​004030​⎠⎟⎟⎞​ 才是最优解 , 这两个系数都大于 $0$0 , 因此不是最优解 ;

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

---

入基变量选择 : 具体哪个变量入基 , 是由检验数决定的 , 检验数 $\sigma_j$σj​ 较大的入基 ; $x_2$x2​ 的检验数 $\sigma_2$σ2​ 是 $4$4 , 大于 $\sigma_1 = 3$σ1​=3 , 因此这里选择 $x_2$x2​ 作为入基变量 ;

出基变量选择 : 系数矩阵中 , 常数列 $b =\begin{pmatrix} \quad 40 \quad \\ \quad 30 \quad \end{pmatrix}$b=(4030​) , 分别除以除以入基变量大于 $0$0 的系数列 $\begin{pmatrix} \quad 1 \quad \\ \quad 3 \quad \end{pmatrix}$(13​) , 得出结果是 $\begin{pmatrix} \quad 40 \quad \\ \quad 10 \quad \end{pmatrix}$(4010​) , 然后选择一个最小值 $10$10 , 查看该最小值对应的变量是 $x_4$x4​ , 选择该变量作为出基变量 ;

这里将出基变量与入基变量选择好了 , $x_2$x2​ 的检验数较大 , 选择 $x_2$x2​ 作为入基变量 , $x_4$x4​ 的 $\theta_4$θ4​ 较小 , 选择 $x_4$x4​ 作为出基变量 ;

入基出基操作完成后 , 基变量变成了 $x_3, x_2$x3​,x2​ ;

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

---

方程组做同解变换 :

线性规划原始方程组为 $\begin{cases} 2 x_1 + x_2 + x_3 + 0x_4 = 40 \\\\ x_1 + 3x_2 + 0x_3 + x_4 = 30 \end{cases}$⎩⎪⎨⎪⎧​2x1​+x2​+x3​+0x4​=40x1​+3x2​+0x3​+x4​=30​ , 需要将 $x_2$x2​ 的系数变为 $\begin{pmatrix} \quad 0 \quad \\ \quad 1 \quad \end{pmatrix}$(01​) , $x_3$x3​ 的系数保持 $\begin{pmatrix} \quad 1 \quad \\ \quad 0 \quad \end{pmatrix}$(10​) 不变 ;

方程 $2$2 同解变换 : 在 $x_1 + 3x_2 + 0x_3 + x_4 = 30$x1​+3x2​+0x3​+x4​=30 中 , 需要将 $x_2$x2​ 的系数变成 $1$1 , 在方程两端乘以 $\dfrac{1}{3}$31​ , 此时方程变成 $\dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4 = 10$31​x1​+x2​+0x3​+31​x4​=10 ;

方程 $1$1 同解变换 : 将上述方程 $2$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}$⎩⎪⎪⎨⎪⎪⎧​2x1​+x2​+x3​+0x4​=4031​x1​+x2​+0x3​+31​x4​=10​ , 目前的需求是将方程 $1$1 的 $x_2$x2​ 系数变为 $0$0 , 使用方程 $1$1 减去 方程 $2$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}$(2−31​)x1​+0x2​+x3​+(0−31​)x4​35​x1​+0x2​+x3​−31​x4​​==​40−1030​

最终方程 $1$1 转化为 $\dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 = 30$35​x1​+0x2​+x3​−31​x4​=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}$⎩⎪⎪⎪⎨⎪⎪⎪⎧​35​x1​+0x2​+x3​−31​x4​=3031​x1​+x2​+0x3​+31​x4​=10​

七、第一次迭代 : 生成新的单纯形表

---

单纯形表变成如下形式 : 下面的单纯形表中 , 上面部分是初始基可行解对应的单纯形表 , 下面的部分是本次迭代后生成的新的单纯形表 ;

将同解变换后的方程组中的 系数矩阵 , 和 常数 , 填入新的单纯形表中 ;

$c_j$cj​	$c_j$cj​		$3$3	$4$4	$0$0	$0$0
$C_B$CB​ 基变量系数 (目标函数)	基变量	常数 $b$b	$x_1$x1​	$x_2$x2​	$x_3$x3​	$x_4$x4​	$\theta_i$θi​
$0$0 ( 目标函数 $x_3$x3​ 系数 $c_3$c3​ )	$x_3$x3​	$40$40	$2$2	$1$1	$1$1	$0$0	$40$40 ( $\theta_3$θ3​ )
$0$0 ( 目标函数 $x_4$x4​ 系数 $c_4$c4​)	$x_4$x4​	$30$30	$1$1	$3$3	$0$0	$1$1	$10$10 ( $\theta_4$θ4​ )
$\sigma_j$σj​			$3$3 ( $\sigma_1$σ1​ )	$4$4 ( $\sigma_2$σ2​ )	$0$0	$0$0
–	–	–	–	–	–	–	–
$0$0 ( 目标函数 $x_3$x3​ 系数 $c_3$c3​ )	$x_3$x3​	$30$30	$\dfrac{5}{3}$35​	$0$0	$1$1	$-\dfrac{1}{3}$−31​	$?$? ( $\theta_3$θ3​ )
$4$4 ( 目标函数 $x_2$x2​ 系数 $c_2$c2​)	$x_2$x2​	$10$10	$\dfrac{1}{3}$31​	$1$1	$0$0	$\dfrac{1}{3}$31​	$?$? ( $\theta_2$θ2​ )
$\sigma_j$σj​ ( 检验数 )			$\dfrac{5}{3}$35​ ( $\sigma_1$σ1​ )	$0$0	$0$0	$-\dfrac{4}{3}$−34​ ( $\sigma_4$σ4​ )

八、第一次迭代 : 解出基可行解

---

新的 基变量是 $x_3 , x_2$x3​,x2​ , 对应的基矩阵是 $\begin{pmatrix} \quad 1 \quad 0 \quad \\ \quad 0 \quad 1 \quad \end{pmatrix}$(1001​) , 非基变量是 $x_1, x_4$x1​,x4​ , 对应的非基矩阵是 $\begin{pmatrix} \quad \dfrac{5}{3} \quad -\dfrac{1}{3} \quad \\ \quad \dfrac{1}{3} \quad \dfrac{1}{3} \quad \end{pmatrix}$⎝⎜⎛​35​−31​31​31​​⎠⎟⎞​ , 将非基变量设置为 $0$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}$⎩⎪⎪⎪⎨⎪⎪⎪⎧​35​×0+0x2​+x3​−31​×0=3031​×0+x2​+0x3​+31​×0=10​ , 解出基变量为 $\begin{cases} x_3 = 30 \\\\ x_2 = 10 \end{cases}$⎩⎪⎨⎪⎧​x3​=30x2​=10​ , 基可行解 为 $\begin{pmatrix} \quad 0 \quad \\ \quad 10 \quad \\ \quad 30 \quad \\ \quad 0 \quad \end{pmatrix}$⎝⎜⎜⎛​010300​⎠⎟⎟⎞​

九、第一次迭代 : 计算检验数 $\sigma_j$σj​ 判定最优解 并选择入基变量

---

根据 【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 ) 博客中分析 , 检验数计算公式为 :

• 矩阵形式 : $C_N^T - C_B^T B^{-1}N$CNT​−CBT​B−1N
• 单个检验数计算公式 : $\sigma_j = c_j - \sum c_i a_{ij}$σj​=cj​−∑ci​aij​

基变量的检验数是 $0$0 , 主要是求非基变量的检验数 $\sigma_1 , \sigma_4$σ1​,σ4​ ;

$\sigma_{1} = c_1 - ( c_3 a_{11} + c_2 a_{12} )$σ1​=c1​−(c3​a11​+c2​a12​)

$\sigma_{1} =3 - (0 \times \dfrac{5}{3}) - (4 \times \dfrac{1}{3}) = \dfrac{5}{3}$σ1​=3−(0×35​)−(4×31​)=35​ , 是从下面的单纯形表中的如下位置提取的数值 ;

$\sigma_{4} = c_4 - ( c_3 a_{41} + c_2 a_{42} )$σ4​=c4​−(c3​a41​+c2​a42​)

$\sigma_{4} =0 - (0 \times -\dfrac{1}{3}) - (4 \times \dfrac{1}{3}) = -\dfrac{4}{3}$σ4​=0−(0×−31​)−(4×31​)=−34​ , 是从下面的单纯形表中的如下位置提取的数值 ;

检验数 $\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}$⎩⎪⎪⎪⎨⎪⎪⎪⎧​σ1​=3−(0×35​)−(4×31​)=35​σ4​=0−(0×−31​)−(4×31​)=−34​​ , $\sigma_1$σ1​ 是大于 $0$0 的 , 两个检验数必须都小于等于 $0$0 , 该基可行解才算作是最优解 , 因此 该基可行解不是最优解 ;

根据检验数选择入基变量 : 继续迭代 , 选择检验数较大的非基变量 , 作为入基变量 , 这里入基变量是 $x_1$x1​ ;

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

---

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

入基变量 根据检验数 $\sigma$σ 选择的是 $x_1$x1​ ;

出基变量是根据 $\theta$θ 值来选择的 , 选择 $\theta$θ 值较小的值对应的基变量作为出基变量 ;

$\theta$θ 值计算 : 常数列 $b =\begin{pmatrix} \quad 30 \quad \\ \quad 10 \quad \end{pmatrix}$b=(3010​) , 分别除以除以入基变量 $x_1$x1​ 大于 $0$0 的系数列 $\begin{pmatrix} \quad \dfrac{5}{3} \quad \\\\ \quad \dfrac{1}{3} \quad \end{pmatrix}$⎝⎜⎜⎛​35​31​​⎠⎟⎟⎞​ , 计算过程如下 $\begin{pmatrix} \quad \cfrac{30}{\dfrac{5}{3}} \quad \\\\ \quad \cfrac{10}{\dfrac{1}{3}} \quad \end{pmatrix}$⎝⎜⎜⎜⎜⎜⎜⎜⎛​35​30​31​10​​⎠⎟⎟⎟⎟⎟⎟⎟⎞​ , 得出结果是 $\begin{pmatrix} \quad 18 \quad \\\\ \quad 30 \quad \end{pmatrix}$⎝⎛​1830​⎠⎞​ , 然后选择一个最小值 $18$18 , 查看该最小值对应的变量是 $x_3$x3​ , 选择该变量作为出基变量 ;

$x_1$x1​ 作入基变量 , $x_3$x3​ 作出基变量 ; 使用 $x_1$x1​ 替代基变量中 $x_3$x3​ 的位置 ;

迭代后的基变量为 $x_1 ,x_2$x1​,x2​ ;

更新一下单纯形表 :

$c_j$cj​	$c_j$cj​		$3$3	$4$4	$0$0	$0$0
$C_B$CB​ 基变量系数 (目标函数)	基变量	常数 $b$b	$x_1$x1​	$x_2$x2​	$x_3$x3​	$x_4$x4​	$\theta_i$θi​
$0$0 ( 目标函数 $x_3$x3​ 系数 $c_3$c3​ )	$x_3$x3​	$40$40	$2$2	$1$1	$1$1	$0$0	$40$40 ( $\theta_3$θ3​ )
$0$0 ( 目标函数 $x_4$x4​ 系数 $c_4$c4​)	$x_4$x4​	$30$30	$1$1	$3$3	$0$0	$1$1	$10$10 ( $\theta_4$θ4​ )
$\sigma_j$σj​			$3$3 ( $\sigma_1$σ1​ )	$4$4 ( $\sigma_2$σ2​ )	$0$0	$0$0
–	–	–	–	–	–	–	–
$0$0 ( 目标函数 $x_3$x3​ 系数 $c_3$c3​ )	$x_3$x3​	$30$30	$\dfrac{5}{3}$35​	$0$0	$1$1	$-\dfrac{1}{3}$−31​	$18$18 ( $\theta_3$θ3​ )
$4$4 ( 目标函数 $x_2$x2​ 系数 $c_2$c2​)	$x_2$x2​	$10$10	$\dfrac{1}{3}$31​	$1$1	$0$0	$\dfrac{1}{3}$31​	$30$30 ( $\theta_2$θ2​ )
$\sigma_j$σj​ ( 检验数 )			$\dfrac{5}{3}$35​ ( $\sigma_1$σ1​ )	$0$0	$0$0	$-\dfrac{4}{3}$−34​ ( $\sigma_4$σ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}$⎩⎪⎪⎪⎨⎪⎪⎪⎧​35​x1​+0x2​+x3​−31​x4​=3031​x1​+x2​+0x3​+31​x4​=10​ , 选择 $x_1, x_2$x1​,x2​ 作为基变量 , 基矩阵为 $\begin{pmatrix} \quad \dfrac{5}{3} \quad 0 \quad \\\\ \quad \dfrac{1}{3} \quad 1 \quad \end{pmatrix}$⎝⎜⎜⎛​35​031​1​⎠⎟⎟⎞​ , 进行同解变换 , 将基矩阵转为单位阵 ;

方程 $1$1 同解变换 :

将 $\dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 = 30$35​x1​+0x2​+x3​−31​x4​=30 方程中的 $x_1$x1​ 的系数变为 $1$1 , $x_2$x2​ 的系数为 $0$0 保持不变 ;

方程的左右变量乘以 $\dfrac{3}{5}$53​ :

$\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}$35​x1​+0x2​+x3​−31​x4​(35​x1​+0x2​+x3​−31​x4​)×53​x1​+0x2​+53​x3​−51​x4​​===​3030×53​18​

当前方程组变成 $\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}$⎩⎪⎪⎪⎨⎪⎪⎪⎧​x1​+0x2​+53​x3​−51​x4​=1831​x1​+x2​+0x3​+31​x4​=10​

方程 $2$2 同解变换 : 将方程 $1$1 乘以 $-\dfrac{1}{3}$−31​ , 与方程 $2$2 相加 ;

① 方程 $1$1 乘以 $-\dfrac{1}{3}$−31​ :

$\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}$(x1​+0x2​+53​x3​−51​x4​)×−31​−31​x1​+0x2​+−51​x3​+151​x4​​==​18×−31​−6​

② 与方程 $2$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}$(−31​x1​+0x2​+−51​x3​+151​x4​)+(31​x1​+x2​+0x3​+31​x4​)0x1​+x2​−51​x3​+52​x4​​==​−6+104​

当前方程组变成 $\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}$⎩⎪⎪⎪⎨⎪⎪⎪⎧​x1​+0x2​+53​x3​−51​x4​=180x1​+x2​−51​x3​+156​x4​=4​

十二、第二次迭代 : 生成新的单纯形表

---

更新一下单纯形表 : 将第三次迭代的矩阵填入下面的单纯形表中 ;

$c_j$cj​	$c_j$cj​		$3$3	$4$4	$0$0	$0$0
$C_B$CB​ 基变量系数 (目标函数)	基变量	常数 $b$b	$x_1$x1​	$x_2$x2​	$x_3$x3​	$x_4$x4​	$\theta_i$θi​
$0$0 ( 目标函数 $x_3$x3​ 系数 $c_3$c3​ )	$x_3$x3​	$40$40	$2$2	$1$1	$1$1	$0$0	$40$40 ( $\theta_3$θ3​ )
$0$0 ( 目标函数 $x_4$x4​ 系数 $c_4$c4​)	$x_4$x4​	$30$30	$1$1	$3$3	$0$0	$1$1	$10$10 ( $\theta_4$θ4​ )
$\sigma_j$σj​			$3$3 ( $\sigma_1$σ1​ )	$4$4 ( $\sigma_2$σ2​ )	$0$0	$0$0
第一次迭代	–	–	–	–	–	–	–
$0$0 ( 目标函数 $x_3$x3​ 系数 $c_3$c3​ )	$x_3$x3​	$30$30	$\dfrac{5}{3}$35​	$0$0	$1$1	$-\dfrac{1}{3}$−31​	$18$18 ( $\theta_3$θ3​ )
$4$4 ( 目标函数 $x_2$x2​ 系数 $c_2$c2​)	$x_2$x2​	$10$10	$\dfrac{1}{3}$31​	$1$1	$0$0	$\dfrac{1}{3}$31​	$30$30 ( $\theta_2$θ2​ )
$\sigma_j$σj​ ( 检验数 )			$\dfrac{5}{3}$35​ ( $\sigma_1$σ1​ )	$0$0	$0$0	$-\dfrac{4}{3}$−34​ ( $\sigma_4$σ4​ )
第二次迭代	–	–	–	–	–	–	–
$3$3 ( 目标函数 $x_1$x1​ 系数 $c_1$c1​ )	$x_1$x1​	$18$18	$1$1	$0$0	$\dfrac{3}{5}$53​	$-\dfrac{1}{5}$−51​	$?$? ( $\theta_3$θ3​ )
$4$4 ( 目标函数 $x_2$x2​ 系数 $c_2$c2​)	$x_2$x2​	$4$4	$0$0	$1$1	$-\dfrac{1}{5}$−51​	$\dfrac{2}{5}$52​	$?$? ( $\theta_2$θ2​ )
$\sigma_j$σj​ ( 检验数 )			$0$0	$0$0	$?$? ( $\sigma_3$σ3​ )	$?$? ( $\sigma_4$σ4​ )

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

---

计算检验数 $\sigma$σ :

$\sigma_3 = 0 - 3 \times \dfrac{3}{5} - 4 \times (-\dfrac{1}{5}) = -\dfrac{9}{5} + \dfrac{4}{5} = -1$σ3​=0−3×53​−4×(−51​)=−59​+54​=−1

$\sigma_4 = 0 - 3 \times (-\dfrac{1}{5}) - 4 \times \dfrac{2}{5} = \dfrac{3}{5} - \dfrac{8}{5} = -1$σ4​=0−3×(−51​)−4×52​=53​−58​=−1

两个非基变量的检验数都是小于等于 $0$0 的 , 因此该基可行解 $\begin{pmatrix} \quad 18 \quad \\ \quad 4 \quad \\ \quad 0 \quad \\ \quad 0 \quad \end{pmatrix}$⎝⎜⎜⎛​18400​⎠⎟⎟⎞​是最优解 ;