【运筹学】线性规划 人工变量法 ( 人工变量法案例 | 初始单纯形表 | 检验数计算 | 入基变量 | 出基变量 )

文章目录

• 一、生成初始单纯形表
• 二、计算非基变量检验数
• 三、最优解判定
• 四、选择入基变量
• 五、选择出基变量
• 六、更新单纯形表

上一篇博客 【运筹学】线性规划 人工变量法 ( 单纯形法总结 | 人工变量法引入 | 人工变量法原理分析 | 人工变量法案例 ) 中 , 介绍了人工变量法 , 主要用于解决线性规划标准形式中 , 初始系数矩阵中没有单位阵的情况 , 并给出一个案例 , 本篇博客中继续使用人工变量法解解上述线性规划问题 ;

一、生成初始单纯形表

---

添加 $2$2 个人工变量后 , 得到 人工变量单纯形法 线性规划模型 :

$\begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 + 0x_4 + 0x_5 - M x_6 - Mx_7 \\\\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 + x_6 + 0x_7 = 4 \\\\ x_1 - x_2 + 2x_3 + 0x_4 + x_5 + 0x_6 + 0x_7 = 10 \\\\ 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + 0x_6 + x_7 = 1 \\\\ x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 , 6 , 7 ) \end{cases}\end{array}$maxZ=3x1​+2x2​−x3​+0x4​+0x5​−Mx6​−Mx7​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​−4x1​+3x2​+x3​−x4​+0x5​+x6​+0x7​=4x1​−x2​+2x3​+0x4​+x5​+0x6​+0x7​=102x1​−2x2​+x3​+0x4​+0x5​+0x6​+x7​=1xj​≥0(j=1,2,3,4,5,6,7)​​

其中的 $M$M 是一个很大的数值 , 没有具体的值 , 可以理解为正无穷 $+\infty$+∞ , 具体使用单纯形法进行计算时 , 将其理解为大于给出的任意一个确定的数值 ;

生成初始基可行表 :

$c_j$cj​	$c_j$cj​		$3$3	$2$2	$-1$−1	$0$0	$0$0	$-M$−M	$-M$−M
$C_B$CB​ 基变量系数 (目标函数)	$X_B$XB​ 基变量	常数 $b$b	$x_1$x1​	$x_2$x2​	$x_3$x3​	$x_4$x4​	$x_5$x5​	$x_6$x6​	$x_7$x7​	$\theta_i$θi​
$-M$−M ( 目标函数 $x_6$x6​ 系数 $c_6$c6​ )	$x_6$x6​	$4$4	$-4$−4	$3$3	$1$1	$-1$−1	$0$0	$1$1	$0$0	$?$? ($\theta_6$θ6​)
$0$0 ( 目标函数 $x_5$x5​ 系数 $c_5$c5​)	$x_5$x5​	$10$10	$1$1	$-1$−1	$2$2	$0$0	$1$1	$0$0	$0$0	$?$? ( $\theta_5$θ5​ )
$-M$−M ( 目标函数 $x_7$x7​ 系数 $c_7$c7​)	$x_7$x7​	$1$1	$2$2	$-2$−2	$1$1	$0$0	$0$0	$0$0	$1$1	$?$? ( $\theta_7$θ7​ )
$\sigma_j$σj​ ( 检验数 )			$?$? ( $\sigma_1$σ1​ )	$?$? ( $\sigma_2$σ2​ )	$?$? ( $\sigma_3$σ3​ )	$?$? ( $\sigma_3$σ3​ )	$0$0	$0$0	$0$0

注意基变量顺序 : 初始基可行解的单位阵的顺序 , 是 $\begin{pmatrix} \quad 1 \quad 0 \quad 0 \quad \\ \quad 0 \quad 1 \quad 0 \quad \\ \quad 0 \quad 0 \quad 1 \quad \\ \end{pmatrix}$⎝⎛​100010001​⎠⎞​ , 对应的基变量顺序是 $\begin{pmatrix} \quad x_6 \quad x_5 \quad x_7 \quad \\ \end{pmatrix}$(x6​x5​x7​​)

• $x_6$x6​ 系数是 $\begin{pmatrix} \quad 1 \quad \\ \quad 0 \quad \\ \quad 0 \quad \\ \end{pmatrix}$⎝⎛​100​⎠⎞​

• $x_5$x5​ 系数是 $\begin{pmatrix} \quad 0 \quad \\ \quad 1 \quad \\ \quad 0 \quad \\ \end{pmatrix}$⎝⎛​010​⎠⎞​

• $x_7$x7​ 系数是 $\begin{pmatrix} \quad 0 \quad \\ \quad 0 \quad \\ \quad 1 \quad \\ \end{pmatrix}$⎝⎛​001​⎠⎞​

二、计算非基变量检验数

---

1 . 计算非基变量 $x_1$x1​ 的检验数 $\sigma_1$σ1​ :

$\sigma_1 = 3 - \begin{pmatrix} \quad -M \quad 0 \quad -M \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad -4 \quad \\\\ \quad 1 \quad \\\\ \quad 2 \quad \end{pmatrix} = 3- ( -M \times -4 + 0 \times 1 + -M \times 2) =3 - 2M$σ1​=3−(−M0−M​)×⎝⎜⎜⎜⎜⎛​−412​⎠⎟⎟⎟⎟⎞​=3−(−M×−4+0×1+−M×2)=3−2M

其中 $M$M 是正无穷 $+\infin$+∞ , $3 - 2M$3−2M 是负数 ;

2 . 计算非基变量 $x_2$x2​ 的检验数 $\sigma_2$σ2​ :

$\sigma_2 = 2 - \begin{pmatrix} \quad -M \quad 0 \quad -M \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad 3 \quad \\\\ \quad -1 \quad \\\\ \quad -2 \quad \end{pmatrix} = 2- ( -M \times 3 + 0 \times -1 + -M \times -2) = 2 + M$σ2​=2−(−M0−M​)×⎝⎜⎜⎜⎜⎛​3−1−2​⎠⎟⎟⎟⎟⎞​=2−(−M×3+0×−1+−M×−2)=2+M

其中 $M$M 是正无穷 $+\infin$+∞ , $2 + M$2+M 是正数 ;

3 . 计算非基变量 $x_3$x3​ 的检验数 $\sigma_3$σ3​ :

$\sigma_3 = -1 - \begin{pmatrix} \quad -M \quad 0 \quad -M \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad 1 \quad \\\\ \quad 2 \quad \\\\ \quad 1 \quad \end{pmatrix} = -1- ( -M \times 1 + 0 \times 2 + -M \times 1) =-1 + 2M$σ3​=−1−(−M0−M​)×⎝⎜⎜⎜⎜⎛​121​⎠⎟⎟⎟⎟⎞​=−1−(−M×1+0×2+−M×1)=−1+2M

其中 $M$M 是正无穷 $+\infin$+∞ , $-1 + 2M$−1+2M 是正数 ;

4 . 计算非基变量 $x_4$x4​ 的检验数 $\sigma_4$σ4​ :

$\sigma_4 = 0 - \begin{pmatrix} \quad -M \quad 0 \quad -M \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad -1 \quad \\\\ \quad 0 \quad \\\\ \quad 0 \quad \end{pmatrix} = 0- ( -M \times -1 + 0 \times 0 + -M \times 0) =-M$σ4​=0−(−M0−M​)×⎝⎜⎜⎜⎜⎛​−100​⎠⎟⎟⎟⎟⎞​=0−(−M×−1+0×0+−M×0)=−M

其中 $M$M 是正无穷 $+\infin$+∞ , $-M$−M 是负数 ;

三、最优解判定

---

根据上述三个检验数 $\begin{cases} \sigma_1 = 3 - 2M \quad ( 负数 )\\\\ \sigma_2= 2 + M \quad ( 正数 )\\\\ \sigma_3= -1 + 2M \quad ( 正数 ) \\\\ \sigma_4 = -M \quad ( 负数 ) \end{cases}$⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​σ1​=3−2M(负数)σ2​=2+M(正数)σ3​=−1+2M(正数)σ4​=−M(负数)​ 的值 , 其中 $\sigma_2 , \sigma_3$σ2​,σ3​ 检验数大于 $0$0 , 该基可行解不是最优解 ;

只有当检验数都小于等于 $0$0 时 , 该基可行解才是最优解 ;

四、选择入基变量

---

根据上述三个检验数 $\begin{cases} \sigma_1 = 3 - 2M\\\\ \sigma_2= 2 + M\\\\ \sigma_3= -1 + 2M \\\\ \sigma_4 = -M \end{cases}$⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​σ1​=3−2Mσ2​=2+Mσ3​=−1+2Mσ4​=−M​ 的值 , 选择检验数最大的非基变量作为入基变量 , $\sigma_3= -1 + 2M$σ3​=−1+2M 最大 , 这里选择 $x_3$x3​ ;

五、选择出基变量

---

出基变量选择 : 常数列 $b =\begin{pmatrix} \quad 4 \quad \\ \quad 10 \quad \\ \quad 1 \quad \\ \end{pmatrix}$b=⎝⎛​4101​⎠⎞​ , 分别除以除以入基变量 $x_3$x3​ 大于 $0$0 的系数列 $\begin{pmatrix} \quad 1 \quad \\\\ \quad 2 \quad \\\\ \quad 1 \quad \end{pmatrix}$⎝⎜⎜⎜⎜⎛​121​⎠⎟⎟⎟⎟⎞​ , 计算过程如下 $\begin{pmatrix} \quad \cfrac{4}{1} \quad \\\\ \quad \cfrac{10}{2} \quad \\\\ \quad \cfrac{1}{ 1} \quad \end{pmatrix}$⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛​14​210​11​​⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞​ , 得出结果是 $\begin{pmatrix} \quad 4 \quad \\\\ \quad 5 \quad \\\\ \quad 1 \quad \end{pmatrix}$⎝⎜⎜⎜⎜⎛​451​⎠⎟⎟⎟⎟⎞​ , 如果系数小于等于 $0$0 , 该值就是无效值 , 默认为无穷大 , 不进行比较 , 选择 $1$1 对应的基变量作为出基变量 , 查看该最小值对应的变量是 $x_7$x7​ , 选择该 $x_7$x7​ 变量作为出基变量 ;

六、更新单纯形表

---

$c_j$cj​	$c_j$cj​		$3$3	$2$2	$-1$−1	$0$0	$0$0	$-M$−M	$-M$−M
$C_B$CB​ 基变量系数 (目标函数)	$X_B$XB​ 基变量	常数 $b$b	$x_1$x1​	$x_2$x2​	$x_3$x3​	$x_4$x4​	$x_5$x5​	$x_6$x6​	$x_7$x7​	$\theta_i$θi​
$-M$−M ( 目标函数 $x_6$x6​ 系数 $c_6$c6​ )	$x_6$x6​	$4$4	$-4$−4	$3$3	$1$1	$-1$−1	$0$0	$1$1	$0$0	$4$4 ($\theta_6$θ6​)
$0$0 ( 目标函数 $x_5$x5​ 系数 $c_5$c5​)	$x_5$x5​	$10$10	$1$1	$-1$−1	$2$2	$0$0	$1$1	$0$0	$0$0	$5$5 ( $\theta_5$θ5​ )
$-M$−M ( 目标函数 $x_7$x7​ 系数 $c_7$c7​)	$x_7$x7​	$1$1	$2$2	$-2$−2	$1$1	$0$0	$0$0	$0$0	$1$1	$1$1 ( $\theta_7$θ7​ )
$\sigma_j$σj​ ( 检验数 )			$3-2M$3−2M ( $\sigma_1$σ1​ )	$2+M$2+M ( $\sigma_2$σ2​ )	$-1 + 2M$−1+2M ( $\sigma_3$σ3​ )	$-M$−M ( $\sigma_3$σ3​ )	$0$0	$0$0	$0$0