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

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

---

在上一篇博客中 , 第一次迭代后 , 找到 入基变量 $x_1$x1​ , 出基变量 $x_4$x4​ , 使用 $x_1$x1​ 替换基变量中的 $x_4$x4​ 位置 ;

新的单纯形表为 :

$c_j$cj​	$c_j$cj​		$1$1	$2$2	$1$1	$0$0	$0$0
$C_B$CB​ 基变量系数 (目标函数)	基变量	常数 $b$b	$x_1$x1​	$x_2$x2​	$x_3$x3​	$x_4$x4​	$x_5$x5​	$\theta_i$θi​
$0$0 ( 目标函数 $x_4$x4​ 系数 $c_4$c4​ )	$x_4$x4​	$15$15	$2$2	$-3$−3	$2$2	$1$1	$0$0	$-$− ($\theta_4$θ4​)
$0$0 ( 目标函数 $x_5$x5​ 系数 $c_5$c5​)	$x_5$x5​	$20$20	$\dfrac{1}{3}$31​	$1$1	$5$5	$0$0	$1$1	$20$20 ( $\theta_5$θ5​ )
$\sigma_j$σj​ ( 检验数 )			$1$1 ( $\sigma_1$σ1​ )	$2$2 ( $\sigma_2$σ2​ )	$1$1 ( $\sigma_3$σ3​ )	$0$0	$0$0
第一次迭代	–	–	–	–	–	–	–	–
$0$0 ( 目标函数 $x_4$x4​ 系数 $c_4$c4​ )	$x_4$x4​	$75$75	$3$3	$0$0	$17$17	$1$1	$3$3	$25$25 ( $\theta_4$θ4​ )
$2$2 ( 目标函数 $x_2$x2​ 系数 $c_2$c2​)	$x_2$x2​	$20$20	$\dfrac{1}{3}$31​	$1$1	$5$5	$0$0	$1$1	$60$60 ($\theta_2$θ2​)
$\sigma_j$σj​ ( 检验数 )			$\dfrac{1}{3}$31​ ( $\sigma_1$σ1​ )	$0$0	$-9$−9 ( $\sigma_3$σ3​ )	$0$0	$-2$−2 ( $\sigma_5$σ5​ )
第二次迭代	–	–	–	–	–	–	–	–
$1$1 ( 目标函数 $x_1$x1​ 系数 $c_1$c1​ )	$x_1$x1​	$?$?	$?$?	$?$?	$?$?	$?$?	$?$?	$?$? ( $\theta_1$θ1​ )
$2$2 ( 目标函数 $x_2$x2​ 系数 $c_2$c2​)	$x_2$x2​	$?$?	$?$?	$?$?	$?$?	$?$?	$?$?	$?$? ($\theta_2$θ2​)
$\sigma_j$σj​ ( 检验数 )			$0$0	$0$0	$?$? ( $\sigma_3$σ3​ )	$?$? ( $\sigma_4$σ4​ )	$?$? ( $\sigma_5$σ5​ )

中心元 : 入基变量 $x_1$x1​ 所在列 , 与出基变量 $x_4$x4​ 所在行 , 相交的位置叫做中心元 ;

• 中心元系数 : 转换成 $1$1 ;
• 中心元所在列另一个系数 : 转换成 $0$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}$⎩⎪⎪⎨⎪⎪⎧​3x1​+0x2​+17x3​+x4​+3x5​=7531​x1​+x2​+5x3​+0x4​+x5​=20​

中心元转换为 $1$1 : 将 $3 x_1 + 0x_2 + 17x_3 + x_4 + 3x_5 = 75$3x1​+0x2​+17x3​+x4​+3x5​=75 中的 $x_1$x1​ 系数变成 $1$1 , 只需要将方程等式两边都乘以 $\cfrac{1}{3}$31​ 即可 ;

$\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}$(3x1​+0x2​+17x3​+x4​+3x5​)×31​x1​+0x2​+317​x3​+31​x4​+x5​​==​75×31​25​

与中心元同一列的 $x_1$x1​ 的系数转换为 $0$0 : 将 $\dfrac{1}{3}x_1 + x_2 + 5x_3 + 0x_4 + x_5 = 20$31​x1​+x2​+5x3​+0x4​+x5​=20 中的 $x_1$x1​ 系数转为 $0$0 :

• 将 $x_1 + 0 x_2 + \cfrac{17}{3} x_3 + \dfrac{1}{3}x_4 + x_5 = 25$x1​+0x2​+317​x3​+31​x4​+x5​=25 方程 左右变量乘以 $-\dfrac{1}{3}$−31​ ;
• 将上个步骤得到的等式与 $\dfrac{1}{3}x_1 + x_2 + 5x_3 + 0x_4 + x_5 = 20$31​x1​+x2​+5x3​+0x4​+x5​=20 相加 , 即可使 $x_1$x1​ 系数为 $0$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}$(x1​+0x2​+317​x3​+31​x4​+x5​)×−31​+(31​x1​+x2​+5x3​+0x4​+x5​)=25×−31​+20(−x1​+0x2​−917​x3​−91​x4​−31​x5​)+(31​x1​+x2​+5x3​+0x4​+x5​)=335​0x1​+x2​+928​x3​−91​x4​+32​x5​=335​​

新的单纯形表为 :

$c_j$cj​	$c_j$cj​		$1$1	$2$2	$1$1	$0$0	$0$0
$C_B$CB​ 基变量系数 (目标函数)	基变量	常数 $b$b	$x_1$x1​	$x_2$x2​	$x_3$x3​	$x_4$x4​	$x_5$x5​	$\theta_i$θi​
$0$0 ( 目标函数 $x_4$x4​ 系数 $c_4$c4​ )	$x_4$x4​	$15$15	$2$2	$-3$−3	$2$2	$1$1	$0$0	$-$− ($\theta_4$θ4​)
$0$0 ( 目标函数 $x_5$x5​ 系数 $c_5$c5​)	$x_5$x5​	$20$20	$\dfrac{1}{3}$31​	$1$1	$5$5	$0$0	$1$1	$20$20 ( $\theta_5$θ5​ )
$\sigma_j$σj​ ( 检验数 )			$1$1 ( $\sigma_1$σ1​ )	$2$2 ( $\sigma_2$σ2​ )	$1$1 ( $\sigma_3$σ3​ )	$0$0	$0$0
第一次迭代	–	–	–	–	–	–	–	–
$0$0 ( 目标函数 $x_4$x4​ 系数 $c_4$c4​ )	$x_4$x4​	$75$75	$3$3	$0$0	$17$17	$1$1	$3$3	$25$25 ( $\theta_4$θ4​ )
$2$2 ( 目标函数 $x_2$x2​ 系数 $c_2$c2​)	$x_2$x2​	$20$20	$\dfrac{1}{3}$31​	$1$1	$5$5	$0$0	$1$1	$60$60 ($\theta_2$θ2​)
$\sigma_j$σj​ ( 检验数 )			$\dfrac{1}{3}$31​ ( $\sigma_1$σ1​ )	$0$0	$-9$−9 ( $\sigma_3$σ3​ )	$0$0	$-2$−2 ( $\sigma_5$σ5​ )
第二次迭代	–	–	–	–	–	–	–	–
$1$1 ( 目标函数 $x_1$x1​ 系数 $c_1$c1​ )	$x_1$x1​	$25$25	$1$1	$0$0	$\dfrac{17}{3}$317​	$\dfrac{1}{3}$31​	$1$1	$?$? ( $\theta_1$θ1​ )
$2$2 ( 目标函数 $x_2$x2​ 系数 $c_2$c2​)	$x_2$x2​	$\dfrac{35}{3}$335​	$0$0	$1$1	$\dfrac{28}{9}$928​	$-\dfrac{1}{9}$−91​	$\dfrac{2}{3}$32​	$?$? ($\theta_2$θ2​)
$\sigma_j$σj​ ( 检验数 )			$0$0	$0$0	$?$? ( $\sigma_3$σ3​ )	$?$? ( $\sigma_4$σ4​ )	$?$? ( $\sigma_5$σ5​ )

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

---

1 . 计算非基变量 $x_3$x3​ 的检验数 $\sigma_3$σ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}$σ3​=1−(12​)×⎝⎜⎜⎛​317​928​​⎠⎟⎟⎞​=1−(1×317​+2×928​)=99−17×3+28×2​=−998​

2 . 计算非基变量 $x_4$x4​ 的检验数 $\sigma_4$σ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}$σ4​=0−(12​)×⎝⎜⎜⎛​31​−91​​⎠⎟⎟⎞​=0−(1×31​−2×91​)=−91​

3 . 计算非基变量 $x_5$x5​ 的检验数 $\sigma_5$σ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}$σ5​=0−(12​)×⎝⎜⎛​132​​⎠⎟⎞​=0−(1×1+2×32​)=−37​

新的单纯形表为 :

$c_j$cj​	$c_j$cj​		$1$1	$2$2	$1$1	$0$0	$0$0
$C_B$CB​ 基变量系数 (目标函数)	基变量	常数 $b$b	$x_1$x1​	$x_2$x2​	$x_3$x3​	$x_4$x4​	$x_5$x5​	$\theta_i$θi​
$0$0 ( 目标函数 $x_4$x4​ 系数 $c_4$c4​ )	$x_4$x4​	$15$15	$2$2	$-3$−3	$2$2	$1$1	$0$0	$-$− ($\theta_4$θ4​)
$0$0 ( 目标函数 $x_5$x5​ 系数 $c_5$c5​)	$x_5$x5​	$20$20	$\dfrac{1}{3}$31​	$1$1	$5$5	$0$0	$1$1	$20$20 ( $\theta_5$θ5​ )
$\sigma_j$σj​ ( 检验数 )			$1$1 ( $\sigma_1$σ1​ )	$2$2 ( $\sigma_2$σ2​ )	$1$1 ( $\sigma_3$σ3​ )	$0$0	$0$0
第一次迭代	–	–	–	–	–	–	–	–
$0$0 ( 目标函数 $x_4$x4​ 系数 $c_4$c4​ )	$x_4$x4​	$75$75	$3$3	$0$0	$17$17	$1$1	$3$3	$25$25 ( $\theta_4$θ4​ )
$2$2 ( 目标函数 $x_2$x2​ 系数 $c_2$c2​)	$x_2$x2​	$20$20	$\dfrac{1}{3}$31​	$1$1	$5$5	$0$0	$1$1	$60$60 ($\theta_2$θ2​)
$\sigma_j$σj​ ( 检验数 )			$\dfrac{1}{3}$31​ ( $\sigma_1$σ1​ )	$0$0	$-9$−9 ( $\sigma_3$σ3​ )	$0$0	$-2$−2 ( $\sigma_5$σ5​ )
第二次迭代	–	–	–	–	–	–	–	–
$1$1 ( 目标函数 $x_1$x1​ 系数 $c_1$c1​ )	$x_1$x1​	$25$25	$1$1	$0$0	$\dfrac{17}{3}$317​	$\dfrac{1}{3}$31​	$1$1	$?$? ( $\theta_1$θ1​ )
$2$2 ( 目标函数 $x_2$x2​ 系数 $c_2$c2​)	$x_2$x2​	$\dfrac{35}{3}$335​	$0$0	$1$1	$\dfrac{28}{9}$928​	$-\dfrac{1}{9}$−91​	$\dfrac{2}{3}$32​	$?$? ($\theta_2$θ2​)
$\sigma_j$σj​ ( 检验数 )			$0$0	$0$0	$- \dfrac{98}{9}$−998​ ( $\sigma_3$σ3​ )	$- \dfrac{1}{9}$−91​ ( $\sigma_4$σ4​ )	$- \dfrac{7}{3}$−37​ ( $\sigma_5$σ5​ )

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

---

上述三个检验数 , $\begin{cases} \sigma_3 =- \dfrac{98}{9} \\\\ \sigma_4= - \dfrac{1}{9} \\\\ \sigma_5 = - \dfrac{7}{3} \end{cases}$⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​σ3​=−998​σ4​=−91​σ5​=−37​​ , 三个检验数都小于等于 $0$0 , 该基可行解是最优解 ;