文章目录

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

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

一、生成初始单纯形表

---

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

$$\begin{array}{l}maxZ=3x_1+2x_2-x_3+0x_4+0x_5-M{x}_6-M{x}_7\\ \\ s.t\{\begin{array}{l}-4x_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\ge 0(j=1,2,3,4,5,6,7)\end{array}\end{array}$$

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

生成初始基可行表 :

$c_j$$c_j$$3$$2$$-1$$0$$0$$-M$$-M$

$C_B$ 基变量系数 (目标函数)	$X_B$ 基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$	${\theta }_i$
$-M$ ( 目标函数 $x_6$ 系数 $c_6$ )	$x_6$	$4$	$-4$	$3$	$1$	$-1$	$0$	$1$	$0$	$?$ (${\theta }_6$)
$0$ ( 目标函数 $x_5$ 系数 $c_5$)	$x_5$	$10$	$1$	$-1$	$2$	$0$	$1$	$0$	$0$	$?$ ( ${\theta }_5$ )
$-M$ ( 目标函数 $x_7$ 系数 $c_7$)	$x_7$	$1$	$2$	$-2$	$1$	$0$	$0$	$0$	$1$	$?$ ( ${\theta }_7$ )
${\sigma }_j$ ( 检验数 )			$?$ ( ${\sigma }_1$ )	$?$ ( ${\sigma }_2$ )	$?$ ( ${\sigma }_3$ )	$?$ ( ${\sigma }_3$ )	$0$	$0$	$0$

注意基变量顺序 : 初始基可行解的单位阵的顺序 , 是 $\left(\begin{array}{c}100\\ 010\\ 001\end{array}\right)$ , 对应的基变量顺序是 $\left(\begin{array}{c}{x}_6{x}_5{x}_7\end{array}\right)$

• $x_6$ 系数是 $\left(\begin{array}{c}1\\ 0\\ 0\end{array}\right)$

• $x_5$ 系数是 $\left(\begin{array}{c}0\\ 1\\ 0\end{array}\right)$

• $x_7$ 系数是 $\left(\begin{array}{c}0\\ 0\\ 1\end{array}\right)$

二、计算非基变量检验数

---

1 . 计算非基变量 $x_1$ 的检验数 ${\sigma }_1$ :

${\sigma }_1=3-\left(\begin{array}{c}-M0-M\end{array}\right)\times \left(\begin{array}{c}-4\\ \\ 1\\ \\ 2\end{array}\right)=3-(-M\times -4+0\times 1+-M\times 2)=3-2M$

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

2 . 计算非基变量 $x_2$ 的检验数 ${\sigma }_2$ :

${\sigma }_2=2-\left(\begin{array}{c}-M0-M\end{array}\right)\times \left(\begin{array}{c}3\\ \\ -1\\ \\ -2\end{array}\right)=2-(-M\times 3+0\times -1+-M\times -2)=2+M$

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

3 . 计算非基变量 $x_3$ 的检验数 ${\sigma }_3$ :

${\sigma }_3=-1-\left(\begin{array}{c}-M0-M\end{array}\right)\times \left(\begin{array}{c}1\\ \\ 2\\ \\ 1\end{array}\right)=-1-(-M\times 1+0\times 2+-M\times 1)=-1+2M$

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

4 . 计算非基变量 $x_4$ 的检验数 ${\sigma }_4$ :

${\sigma }_4=0-\left(\begin{array}{c}-M0-M\end{array}\right)\times \left(\begin{array}{c}-1\\ \\ 0\\ \\ 0\end{array}\right)=0-(-M\times -1+0\times 0+-M\times 0)=-M$

其中 $M$ 是正无穷 $+\infty$ , $-M$ 是负数 ;

三、最优解判定

---

根据上述四个检验数 $\{\begin{array}{l}{\sigma }_1=3-2M(负数)\\ \\ {\sigma }_2=2+M(正数)\\ \\ {\sigma }_3=-1+2M(正数)\\ \\ {\sigma }_4=-M(负数)\end{array}$ 的值 , 其中 ${\sigma }_2,{\sigma }_3$ 检验数大于 $0$ , 该基可行解不是最优解 ;

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

四、选择入基变量

---

根据上述四个检验数 $\{\begin{array}{l}{\sigma }_1=3-2M\\ \\ {\sigma }_2=2+M\\ \\ {\sigma }_3=-1+2M\\ \\ {\sigma }_4=-M\end{array}$ 的值 , 选择检验数最大的非基变量作为入基变量 , ${\sigma }_3=-1+2M$ 最大 , 这里选择 $x_3$ ;

五、选择出基变量

---

出基变量选择 : 常数列 $b=\left(\begin{array}{c}4\\ 10\\ 1\end{array}\right)$ , 分别除以除以入基变量 $x_3$ 大于 $0$ 的系数列 $\left(\begin{array}{c}1\\ \\ 2\\ \\ 1\end{array}\right)$ , 计算过程如下 $\left(\begin{array}{c}\frac{4}{1}\\ \\ \frac{10}{2}\\ \\ \frac{1}{1}\end{array}\right)$ , 得出结果是 $\left(\begin{array}{c}4\\ \\ 5\\ \\ 1\end{array}\right)$ , 如果系数小于等于 $0$ , 该值就是无效值 , 默认为无穷大 , 不进行比较 , 选择 $1$ 对应的基变量作为出基变量 , 查看该最小值对应的变量是 $x_7$ , 选择该 $x_7$ 变量作为出基变量 ;

六、更新单纯形表

---

$c_j$$c_j$$3$$2$$-1$$0$$0$$-M$$-M$

$C_B$ 基变量系数 (目标函数)	$X_B$ 基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$	${\theta }_i$
$-M$ ( 目标函数 $x_6$ 系数 $c_6$ )	$x_6$	$4$	$-4$	$3$	$1$	$-1$	$0$	$1$	$0$	$4$ (${\theta }_6$)
$0$ ( 目标函数 $x_5$ 系数 $c_5$)	$x_5$	$10$	$1$	$-1$	$2$	$0$	$1$	$0$	$0$	$5$ ( ${\theta }_5$ )
$-M$ ( 目标函数 $x_7$ 系数 $c_7$)	$x_7$	$1$	$2$	$-2$	$1$	$0$	$0$	$0$	$1$	$1$ ( ${\theta }_7$ )
${\sigma }_j$ ( 检验数 )			$3-2M$ ( ${\sigma }_1$ )	$2+M$ ( ${\sigma }_2$ )	$-1+2M$ ( ${\sigma }_3$ )	$-M$ ( ${\sigma }_3$ )	$0$	$0$	$0$

总结

以上是生活随笔为你收集整理的【运筹学】线性规划 人工变量法 ( 人工变量法案例 | 初始单纯形表 | 检验数计算 | 入基变量 | 出基变量 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。