文章目录

• 一、单纯形法原理
• 二、单纯形法流程
• 三、单纯形法案例一
• • 1、线性规划示例
  • 2、转化标准形式
  • 3、查找初始基可行解
  • 4、初始基可行解的最优解判定
  • 5、第一次迭代 : 入基与出基变量选择
  • 6、第一次迭代 : 方程组同解变换
  • 7、第一次迭代 : 生成新的单纯形表
  • 8、第一次迭代 : 解出基可行解
  • 9、第一次迭代 : 计算检验数 ${\sigma }_j$ 判定最优解 并选择入基变量
  • 10、第一次迭代 : 根据入基变量计算并选择出基变量
  • 11、第二次迭代 : 方程组同解变换
  • 12、第二次迭代 : 生成新的单纯形表
  • 13、第二次迭代 : 计算检验数、最优解判定
• 四、单纯形法案例二
• • 1、线性规划示例
  • 2、转化成标准形式
  • 3、初始基可行解
  • 5、计算检验数
  • 6、选择入基变量与出基变量
  • 7、第一次迭代 : 列出单纯形表
  • 8、第一次迭代 : 进行行变换
  • 9、第一次迭代 : 计算检验数
  • 10、第一次迭代 : 最优解判定
  • 11、第一次迭代 : 入基变量
  • 12、第一次迭代 : 出基变量
  • 13、第二次迭代 : 进行矩阵变换
  • 14、第二次迭代 : 计算检验数
  • 15、第二次迭代 : 最优解判定
• 五、线性规划最优解分析
• • 1、唯一最优解
  • 2、无穷多最优解
  • 3、无界解
  • 4、无可行解

一、单纯形法原理

---

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

单纯形法的理论基础 :

定理 $1$ ( 可行域是凸集 ) : 如果线性规划的问题 存在可行解 , 其 可行域 必定是 凸集 ;

定理 $2$ ( 基可行解是凸集顶点 ) : 线性规划的 基可行解 $X_B$ 对应了上述 可行域 ( 凸集 ) 的顶点位置 ;

定理 $3$ ( 某个基可行解是最优解 ) : 如果线性规划问题 存在最优解 , 那么 一定存在一个基可行解是最优解 ;

参考上一篇博客 【运筹学】线性规划 图解法 ( 唯一最优解 | 无穷最优解 | 无界解 | 无可行解 ) 进行分析 :

给定线性规划 :

$$\begin{array}{l}maxZ=2x_1+x_2\\ \\ s.t=\{\begin{array}{l}{x}_1+1.9x_2\ge 3.8\\ \\ x_1-1.9x_2\le 3.8\\ \\ x_1+1.9x_2\le 10.2\\ \\ x_1-1.9x_2\ge -3.8\\ \\ x_1,x_2\ge 0\end{array}\end{array}$$

使用图解法进行分析 , 得到如下结果 ;

使用迭代的思想进行求解 :

• 无限个解中迭代 : 上图中的 可行域 $D$ 中的点是无限的 , 可以在所有的无限个可行域 $D$ 解中进行迭代 , 逐个迭代很难 ;

• 有限个解中迭代 : 因此选取 可行域 ( 凸集 ) 的顶点 , 也就是 基可行解 进行迭代 , 该线性规划问题的基可行解是有限的 , 只有 $4$ 个 , 即该凸集有 $4$ 个顶点 ;

上图的凸集中的 $4$ 个顶点 , 必然有一个是最优解 , 因此迭代的时候 , 不用从 $D$ 可行域中的无限个点中进行迭代 , 只需要在有限个基可行解中进行迭代 , 即可找到最优解 ;

单纯形法的原理的基础就是源自上述理论 , 在线性规划的有限个基可行解中 , 必定存在一个解释最优解 , 逐个迭代 , 将这个最优解找出即可 ;

从无限个可行解中进行迭代 , 到有限个基可行解中进行迭代 , 简单了很多 ;

但是对于 $m\times n$ 阶的线性规划系数矩阵 , 其基可行解的个数可能有 $C_n^m$ 个 , 如果 $n$ 和 $m$ 很大的话 , 基可行解的数目还是很大 , 这是一个指数级的数 , 因此使用多项式算法 , 完成上述操作 , 计算量还是很大的 ;

这里使用单纯形法 , 进行迭代 , 要比使用多项式法计算量更少 ;

二、单纯形法流程

---

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

单纯形法的基本流程 :

① 初始基可行解 : 首先找到初始的基可行解 ;

② 判定是否最优解 : 需要一个准则 , 判定该初始基可行解 , 是否是最优解 ; 这里是单纯形法最核心问题 ;

③ 是最优解 : 如果该基可行解是最优解 , 那么结束迭代 ;

④ 不是最优解 : 如果该基可行解不是最优解 , 那么迭代到下一个基可行解 , 继续判定是否是最优解 ; 如何迭代也需要一个准则 ;

这里涉及到了两个准则 :

• 判断最优解 : 判断一个 基可行解 是否是最优解 ;
• 迭代原则 : 如何从一个 基可行解 迭代到下一个基可行解 ;

单纯形法涉及到的问题 :

① 初始解 : 如何找到初始基可行解 ;

② 最优解 : 如何找到一个准则 , 用于判定基可行解是否是最优解 ;

③ 迭代解 : 如果一个基可行解不满足准则 , 如何去选择下一个基可行解进行迭代 ;

解决上述 $3$ 个问题 , 基可行解的算法 , 也就可以得出 ;

三、单纯形法案例一

---

1、线性规划示例

使用单纯形法求解线性规划最优解 :

$$\begin{array}{l}maxZ=3x_1+4x_2\\ \\ \{\begin{array}{ll}2x_1+x_2\le 40& \\ & \\ x_1+3x_2\le 30& \\ & \\ x_j\ge 0& (j=1,2)\end{array}\end{array}$$

2、转化标准形式

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

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

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

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

• $2x_1+x_2\le 40$ , 左侧加入松弛变量 $x_3$ , 变为 $2x_1+x_2+x_3=40$
• $x_1+3x_2\le 30$ , 左侧加入松弛变量 $x_4$ , 变为 $x_1+3x_2+x_4=30$

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

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

$$\begin{array}{l}maxZ=3x_1+4x_2+0x_3+0x_4\\ \\ \{\begin{array}{ll}2x_1+x_2+x_3+0x_4=40& \\ & \\ x_1+3x_2+0x_3+x_4=30& \\ & \\ x_j\ge 0& (j=1,2,3,4)\end{array}\end{array}$$

3、查找初始基可行解

找基矩阵 :

上述线性规划标准形式的系数矩阵为 $\left[\begin{array}{cccccc}& 2& 1& 1& 0& \\ & & & & & \\ & 1& 3& 0& 1& \end{array}\right]$ , 其中子矩阵中有 $\left[\begin{array}{cccc}& 1& 0& \\ & & & \\ & 0& 1& \end{array}\right]$ 单位阵 $I$ ;

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

列出单纯形表 :

$c_j$$c_j$$3$$4$$0$$0$

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	${\theta }_i$
$0$ ( 目标函数 $x_3$ 系数 $c_3$ )	$x_3$	$40$	$2$	$1$	$1$	$0$
$0$ ( 目标函数 $x_4$ 系数 $c_4$)	$x_4$	$30$	$1$	$3$	$0$	$1$
		${\sigma }_j$	$3$	$4$	$0$	$0$

基变量是 $x_3$ 和 $x_4$ , 基变量在约束条件中的系数矩阵 $\left[\begin{array}{cccc}& 1& 0& \\ & & & \\ & 0& 1& \end{array}\right]$ 就是基矩阵 , 这是个单位阵 ;

基变量是 $x_3$ 和 $x_4$ 在目标函数中的系数是 $\left(\begin{array}{c}00\end{array}\right)$ ;

此时的基解是 $\left(\begin{array}{c}0\\ 0\\ 40\\ 30\end{array}\right)$ , 该解是初始解 , 下面判定该解是否是最优解 ;

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

使用 检验数矩阵 $(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=\left(\begin{array}{c}34\end{array}\right)$

• 基变量在目标函数中的叙述矩阵 : $C_B^T=\left(\begin{array}{c}00\end{array}\right)$

• $B^{-1}N$ 是系数矩阵中经过矩阵变换后 , 基变量系数是单位阵 $I$ , 非基变量系数是 $B^{-1}N$ : $B^{-1}N=\left[\begin{array}{cccc}& 2& 1& \\ & & & \\ & 1& 3& \end{array}\right]$

$$(C_N^T-C_B^T{B}^{-1}N)=C_N^T=\left(\begin{array}{c}34\end{array}\right)-\left(\begin{array}{c}00\end{array}\right)\times \left[\begin{array}{cccc}& 2& 1& \\ & & & \\ & 1& 3& \end{array}\right]$$

$$=\left(\begin{array}{c}{\sigma }_1{\sigma }_2\end{array}\right)$$

其中 ${\sigma }_1$ 是目标函数中 $x_1$ 的系数 , ${\sigma }_2$ 是目标函数中的 $x_2$ 的系数 ;

如果上述两个系数都小于等于 $0$ , 那么当 非基变量 $X_N=\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)$ 取值为 $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$ , 该 基可行解$\left(\begin{array}{c}0\\ 0\\ 40\\ 30\end{array}\right)$ 才是最优解 , 这两个系数都大于 $0$ , 因此不是最优解 ;

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

入基变量选择 : 具体哪个变量入基 , 是由检验数决定的 , 检验数 ${\sigma }_j$ 较大的入基 ; $x_2$ 的检验数 ${\sigma }_2$ 是 $4$ , 大于 ${\sigma }_1=3$ , 因此这里选择 $x_2$ 作为入基变量 ;

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

这里将出基变量与入基变量选择好了 , $x_2$ 的检验数较大 , 选择 $x_2$ 作为入基变量 , $x_4$ 的 ${\theta }_4$ 较小 , 选择 $x_4$ 作为出基变量 ;

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

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

方程组做同解变换 :

线性规划原始方程组为 $\{\begin{array}{l}2x_1+x_2+x_3+0x_4=40\\ \\ x_1+3x_2+0x_3+x_4=30\end{array}$ , 需要将 $x_2$ 的系数变为 $\left(\begin{array}{c}0\\ 1\end{array}\right)$ , $x_3$ 的系数保持 $\left(\begin{array}{c}1\\ 0\end{array}\right)$ 不变 ;

方程 $2$ 同解变换 : 在 $x_1+3x_2+0x_3+x_4=30$ 中 , 需要将 $x_2$ 的系数变成 $1$ , 在方程两端乘以 $\frac{1}{3}$ , 此时方程变成 $\frac{1}{3}{x}_1+x_2+0x_3+\frac{1}{3}{x}_4=10$ ;

方程 $1$ 同解变换 : 将上述方程 $2$ 作同解变换后 , 方程组变成 $\{\begin{array}{l}2x_1+x_2+x_3+0x_4=40\\ \\ \frac{1}{3}{x}_1+x_2+0x_3+\frac{1}{3}{x}_4=10\end{array}$ , 目前的需求是将方程 $1$ 的 $x_2$ 系数变为 $0$ , 使用方程 $1$ 减去 方程 $2$ 即可得到要求的矩阵 :

$$\begin{array}{lcl}(2-\frac{1}{3})x_1+0x_2+x_3+(0-\frac{1}{3})x_4& =& 40-10\\ & & \\ \frac{5}{3}{x}_1+0x_2+x_3-\frac{1}{3}{x}_4& =& 30\end{array}$$

最终方程 $1$ 转化为 $\frac{5}{3}{x}_1+0x_2+x_3-\frac{1}{3}{x}_4=30$ ;

同解变换完成后的方程组为 $\{\begin{array}{l}\frac{5}{3}{x}_1+0x_2+x_3-\frac{1}{3}{x}_4=30\\ \\ \frac{1}{3}{x}_1+x_2+0x_3+\frac{1}{3}{x}_4=10\end{array}$

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

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

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

$c_j$$c_j$$3$$4$$0$$0$

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	${\theta }_i$
$0$ ( 目标函数 $x_3$ 系数 $c_3$ )	$x_3$	$40$	$2$	$1$	$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$
–	–	–	–	–	–	–	–
$0$ ( 目标函数 $x_3$ 系数 $c_3$ )	$x_3$	$30$	$\frac{5}{3}$	$0$	$1$	$-\frac{1}{3}$	$?$ ( ${\theta }_3$ )
$4$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$10$	$\frac{1}{3}$	$1$	$0$	$\frac{1}{3}$	$?$ ( ${\theta }_2$ )
${\sigma }_j$ ( 检验数 )			$\frac{5}{3}$ ( ${\sigma }_1$ )	$0$	$0$	$-\frac{4}{3}$ ( ${\sigma }_4$ )

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

新的 基变量是 $x_3,x_2$ , 对应的基矩阵是 $\left(\begin{array}{c}10\\ 01\end{array}\right)$ , 非基变量是 $x_1,x_4$ , 对应的非基矩阵是 $\left(\begin{array}{c}\frac{5}{3}-\frac{1}{3}\\ \frac{1}{3}\frac{1}{3}\end{array}\right)$ , 将非基变量设置为 $0$ , 方程组为 $\{\begin{array}{l}\frac{5}{3}\times 0+0x_2+x_3-\frac{1}{3}\times 0=30\\ \\ \frac{1}{3}\times 0+x_2+0x_3+\frac{1}{3}\times 0=10\end{array}$ , 解出基变量为 $\{\begin{array}{l}{x}_3=30\\ \\ x_2=10\end{array}$ , 基可行解 为 $\left(\begin{array}{c}0\\ 10\\ 30\\ 0\end{array}\right)$

9、第一次迭代 : 计算检验数 ${\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 \frac{5}{3})-(4\times \frac{1}{3})=\frac{5}{3}$ , 是从下面的单纯形表中的如下位置提取的数值 ;

${\sigma }_4=c_4-(c_3{a}_{41}+c_2{a}_{42})$

${\sigma }_4=0-(0\times -\frac{1}{3})-(4\times \frac{1}{3})=-\frac{4}{3}$ , 是从下面的单纯形表中的如下位置提取的数值 ;

检验数 $\{\begin{array}{l}{\sigma }_1=3-(0\times \frac{5}{3})-(4\times \frac{1}{3})=\frac{5}{3}\\ \\ {\sigma }_4=0-(0\times -\frac{1}{3})-(4\times \frac{1}{3})=-\frac{4}{3}\end{array}$ , ${\sigma }_1$ 是大于 $0$ 的 , 两个检验数必须都小于等于 $0$ , 该基可行解才算作是最优解 , 因此 该基可行解不是最优解 ;

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

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

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

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

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

$\theta$ 值计算 : 常数列 $b=\left(\begin{array}{c}30\\ 10\end{array}\right)$ , 分别除以除以入基变量 $x_1$ 大于 $0$ 的系数列 $\left(\begin{array}{c}\frac{5}{3}\\ \\ \frac{1}{3}\end{array}\right)$ , 计算过程如下 $\left(\begin{array}{c}\frac{30}{\frac{5}{3}}\\ \\ \frac{10}{\frac{1}{3}}\end{array}\right)$ , 得出结果是 $\left(\begin{array}{c}18\\ \\ 30\end{array}\right)$ , 然后选择一个最小值 $18$ , 查看该最小值对应的变量是 $x_3$ , 选择该变量作为出基变量 ;

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

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

更新一下单纯形表 :

$c_j$$c_j$$3$$4$$0$$0$

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	${\theta }_i$
$0$ ( 目标函数 $x_3$ 系数 $c_3$ )	$x_3$	$40$	$2$	$1$	$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$
–	–	–	–	–	–	–	–
$0$ ( 目标函数 $x_3$ 系数 $c_3$ )	$x_3$	$30$	$\frac{5}{3}$	$0$	$1$	$-\frac{1}{3}$	$18$ ( ${\theta }_3$ )
$4$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$10$	$\frac{1}{3}$	$1$	$0$	$\frac{1}{3}$	$30$ ( ${\theta }_2$ )
${\sigma }_j$ ( 检验数 )			$\frac{5}{3}$ ( ${\sigma }_1$ )	$0$	$0$	$-\frac{4}{3}$ ( ${\sigma }_4$ )

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

---

当前的方程组为 $\{\begin{array}{l}\frac{5}{3}{x}_1+0x_2+x_3-\frac{1}{3}{x}_4=30\\ \\ \frac{1}{3}{x}_1+x_2+0x_3+\frac{1}{3}{x}_4=10\end{array}$ , 选择 $x_1,x_2$ 作为基变量 , 基矩阵为 $\left(\begin{array}{c}\frac{5}{3}0\\ \\ \frac{1}{3}1\end{array}\right)$ , 进行同解变换 , 将基矩阵转为单位阵 ;

方程 $1$ 同解变换 :

将 $\frac{5}{3}{x}_1+0x_2+x_3-\frac{1}{3}{x}_4=30$ 方程中的 $x_1$ 的系数变为 $1$ , $x_2$ 的系数为 $0$ 保持不变 ;

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

$$\begin{array}{lcl}\frac{5}{3}{x}_1+0x_2+x_3-\frac{1}{3}{x}_4& =& 30\\ & & \\ (\frac{5}{3}{x}_1+0x_2+x_3-\frac{1}{3}{x}_4)\times \frac{3}{5}& =& 30\times \frac{3}{5}\\ & & \\ x_1+0x_2+\frac{3}{5}{x}_3-\frac{1}{5}{x}_4& =& 18\end{array}$$

当前方程组变成 $\{\begin{array}{l}{x}_1+0x_2+\frac{3}{5}{x}_3-\frac{1}{5}{x}_4=18\\ \\ \frac{1}{3}{x}_1+x_2+0x_3+\frac{1}{3}{x}_4=10\end{array}$

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

① 方程 $1$ 乘以 $-\frac{1}{3}$ :

$$\begin{array}{lcl}(x_1+0x_2+\frac{3}{5}{x}_3-\frac{1}{5}{x}_4)\times -\frac{1}{3}& =& 18\times -\frac{1}{3}\\ & & \\ -\frac{1}{3}{x}_1+0x_2+-\frac{1}{5}{x}_3+\frac{1}{15}{x}_4& =& -6\end{array}$$

② 与方程 $2$ 相加 :

$$\begin{array}{lcl}(-\frac{1}{3}{x}_1+0x_2+-\frac{1}{5}{x}_3+\frac{1}{15}{x}_4)+(\frac{1}{3}{x}_1+x_2+0x_3+\frac{1}{3}{x}_4)& =& -6+10\\ & & \\ 0x_1+x_2-\frac{1}{5}{x}_3+\frac{2}{5}{x}_4& =& 4\end{array}$$

当前方程组变成 $\{\begin{array}{l}{x}_1+0x_2+\frac{3}{5}{x}_3-\frac{1}{5}{x}_4=18\\ \\ 0x_1+x_2-\frac{1}{5}{x}_3+\frac{6}{15}{x}_4=4\end{array}$

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

---

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

$c_j$$c_j$$3$$4$$0$$0$

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	${\theta }_i$
$0$ ( 目标函数 $x_3$ 系数 $c_3$ )	$x_3$	$40$	$2$	$1$	$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$
第一次迭代	–	–	–	–	–	–	–
$0$ ( 目标函数 $x_3$ 系数 $c_3$ )	$x_3$	$30$	$\frac{5}{3}$	$0$	$1$	$-\frac{1}{3}$	$18$ ( ${\theta }_3$ )
$4$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$10$	$\frac{1}{3}$	$1$	$0$	$\frac{1}{3}$	$30$ ( ${\theta }_2$ )
${\sigma }_j$ ( 检验数 )			$\frac{5}{3}$ ( ${\sigma }_1$ )	$0$	$0$	$-\frac{4}{3}$ ( ${\sigma }_4$ )
第二次迭代	–	–	–	–	–	–	–
$3$ ( 目标函数 $x_1$ 系数 $c_1$ )	$x_1$	$18$	$1$	$0$	$\frac{3}{5}$	$-\frac{1}{5}$	$?$ ( ${\theta }_3$ )
$4$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$4$	$0$	$1$	$-\frac{1}{5}$	$\frac{2}{5}$	$?$ ( ${\theta }_2$ )
${\sigma }_j$ ( 检验数 )			$0$	$0$	$?$ ( ${\sigma }_3$ )	$?$ ( ${\sigma }_4$ )

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

---

计算检验数 $\sigma$ :

${\sigma }_3=0-3\times \frac{3}{5}-4\times (-\frac{1}{5})=-\frac{9}{5}+\frac{4}{5}=-1$

${\sigma }_4=0-3\times (-\frac{1}{5})-4\times \frac{2}{5}=\frac{3}{5}-\frac{8}{5}=-1$

两个非基变量的检验数都是小于等于 $0$ 的 , 因此该基可行解 $\left(\begin{array}{c}18\\ 4\\ 0\\ 0\end{array}\right)$是最优解 ;

四、单纯形法案例二

---

1、线性规划示例

线性规划示例 : 使用单纯形法求解下面的线性规划 ;

$$\begin{array}{l}maxZ=x_1+2x_2+x_3\\ \\ s.t\{\begin{array}{ll}2x_1-3x_2+2x_3\le 15& \\ & \\ \frac{1}{3}{x}_1+x_2+5x_3\le 20& \\ & \\ x_j\ge 0& (j=1,2,3)\end{array}\end{array}$$

2、转化成标准形式

首先将现行规划转化成标准形式 :

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

1 . 处理约束变量 : 所有的约束变量都大于等于 $0$ , 这里无需处理 ;

2 . 将不等式转为等式 : 两个不等式都是小于等于不等式 , 在左侧加入松弛变量即可 ;

① 添加松弛变量 : 上述两个不等式 $\{\begin{array}{l}2x_1-3x_2+2x_3\le 15\\ \\ \frac{1}{3}{x}_1+x_2+5x_3\le 20\end{array}$ , 在左侧分别添加 $x_4,x_5$ 松弛变量 ;

② 最终结果 : 转化后的结果是 $\{\begin{array}{l}2x_1-3x_2+2x_3+x_4=15\\ \\ \frac{1}{3}{x}_1+x_2+5x_3+x_5=20\\ \\ x_j\ge 0(j=1,2,3,4,5)\end{array}$

3 . 处理目标函数取最大值 : 目标函数就是取最大值 , 无需处理 ;

4 . 最终的标准形结果是 :

$$\begin{array}{l}maxZ=x_1+2x_2+x_3+0x_4+0x_5\\ \\ s.t\{\begin{array}{l}2x_1-3x_2+2x_3+x_4+0x_5=15\\ \\ \frac{1}{3}{x}_1+x_2+5x_3+0x_4+x_5=20\\ \\ x_j\ge 0(j=1,2,3,4,5)\end{array}\end{array}$$

3、初始基可行解

找初始基可行解 :

① 查找单位阵 : 该线性规划标准形的系数矩阵中 , $x_4,x_5$ 的系数矩阵是 $\left(\begin{array}{c}10\\ 01\end{array}\right)$ , 该矩阵是单位阵 ;

② 可行基 : 选择该矩阵作为可行基 ;

③ 初始基可行解 : 其对应的解是基可行解 $\left(\begin{array}{c}0\\ 0\\ 0\\ 15\\ 20\end{array}\right)$ ;

## 4、列出单纯形表

$$\begin{array}{l}maxZ=x_1+2x_2+x_3+0x_4+0x_5\\ \\ s.t\{\begin{array}{l}2x_1-3x_2+2x_3+x_4+0x_5=15\\ \\ \frac{1}{3}{x}_1+x_2+5x_3+0x_4+x_5=20\\ \\ x_j\ge 0(j=1,2,3,4,5)\end{array}\end{array}$$

$c_j$$c_j$$1$$2$$1$$0$$0$

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	${\theta }_i$
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$15$	$2$	$-1$	$2$	$1$	$0$	$-$
$0$ ( 目标函数 $x_5$ 系数 $c_5$)	$x_5$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$20$
${\sigma }_j$ ( 检验数 )			$1$ ( ${\sigma }_1$ )	$2$ ( ${\sigma }_2$ )	$1$ ( ${\sigma }_3$ )	$0$	$0$

5、计算检验数

计算非基变量的检验数 :

单个检验数计算公式 : ${\sigma }_j=c_j-\sum c_i{a}_{ij}$ , 其中 $c_j$ 是对应目标函数非基变量系数 , $c_i$ 是目标函数中基变量系数 , $a_{ij}$ 是系数矩阵中对应的 $x_j$ 非基变量列向量 ;

① ${\sigma }_1$ 检验数计算 : ${\sigma }_1=1-(0\times 2+0\times \frac{1}{3})=1$

② ${\sigma }_2$ 检验数计算 : ${\sigma }_2=2-(0\times (-1)+0\times 1)=2$

③ ${\sigma }_{1}3$ 检验数计算 : ${\sigma }_3=1-(0\times 2+0\times 5)=1$

6、选择入基变量与出基变量

入基变量选择 : 选择检验数 ${\sigma }_j$ 较大的非基变量作为入基变量 , 即 $x_2$ ;

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

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

7、第一次迭代 : 列出单纯形表

上述已经得到 $x_2$ 作为入基变量 , 由非基变量转为基变量 , $x_5$ 作为出基变量 , 由基变量转为非基变量 ; 使用 $x_2$ , 替换基变量中的 $x_5$ 的位置 ;

基变量为 $x_4,x_2$ , 注意顺序不要写反 ;

$c_j$$c_j$$1$$2$$1$$0$$0$

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	${\theta }_i$
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$15$	$2$	$-1$	$2$	$1$	$0$	$-$ (${\theta }_4$)
$0$ ( 目标函数 $x_5$ 系数 $c_5$)	$x_5$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$20$ ( ${\theta }_5$ )
${\sigma }_j$ ( 检验数 )			$1$ ( ${\sigma }_1$ )	$2$ ( ${\sigma }_2$ )	$1$ ( ${\sigma }_3$ )	$0$	$0$
第一次迭代	–	–	–	–	–	–	–	–
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$15$	$?$	$1$	$?$	$1$	$?$	$?$ ( ${\theta }_4$ )
$2$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$20$	$?$	$0$	$?$	$0$	$?$	$?$ (${\theta }_2$)
${\sigma }_j$ ( 检验数 )			$1$ ( ${\sigma }_1$ )	$0$	$1$ ( ${\sigma }_3$ )	$0$	$?$ ( ${\sigma }_2$ )

8、第一次迭代 : 进行行变换

当前的线性规划标准形式等式方程组 : $\{\begin{array}{l}2x_1-3x_2+2x_3+x_4+0x_5=15\\ \\ \frac{1}{3}{x}_1+x_2+5x_3+0x_4+x_5=20\end{array}$

当前的单纯性表 :

$c_j$$c_j$$1$$2$$1$$0$$0$

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	${\theta }_i$
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$15$	$2$	$-3$	$2$	$1$	$0$	$-$ (${\theta }_4$)
$0$ ( 目标函数 $x_5$ 系数 $c_5$)	$x_5$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$20$ ( ${\theta }_5$ )
${\sigma }_j$ ( 检验数 )			$1$ ( ${\sigma }_1$ )	$2$ ( ${\sigma }_2$ )	$1$ ( ${\sigma }_3$ )	$0$	$0$
第一次迭代	–	–	–	–	–	–	–	–
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$?$	$?$	$?$	$?$	$?$	$?$	$?$ ( ${\theta }_4$ )
$2$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$?$	$?$	$?$	$?$	$?$	$?$	$?$ (${\theta }_2$)
${\sigma }_j$ ( 检验数 )			$?$ ( ${\sigma }_1$ )	$0$	$?$ ( ${\sigma }_3$ )	$0$	$?$ ( ${\sigma }_2$ )

下面进行矩阵变换 :

• 入基变量是 $x_2$
• 出基变量是 $x_5$

中心元 : 在下面单纯形表中 , $x_2$ 列 ( 红色选框 ) , 与 $x_5$ 行 ( 绿色选框 ) , 上述 行列相交的部分 是 中心元 ,

以上述 中心元 为轴做变换 , 变换目的是把 中心元位置变换成 $1$ , 把中心元所在列的另一个位置变换成 $0$ ;

该行中 $x_2$ 的系数 , 就是 $1$ , 不用改变 , 因此这里将第二行的系数原封不动填入第一次迭代的单纯形表中 ;

接下来要将上图 蓝色选框 部分的位置 , 变为 $0$ , 变换过程如下 :

• 将 $\frac{1}{3}{x}_1+x_2+5x_3+0x_4+x_5=20$ 方程 等式左右两边乘以 $3$ ;
• 与 $2x_1-3x_2+2x_3+x_4+0x_5=15$ 相加 ;

$$\begin{array}{lcl}(\frac{1}{3}{x}_1+x_2+5x_3+0x_4+x_5)\times 3+(2x_1-3x_2+2x_3+x_4+0x_5)& =& 20\times 3+15\\ & & \\ (x_1+3x_2+15x_3+3x_5)+(2x_1-3x_2+2x_3+x_4+0x_5)& =& 75\\ & & \\ 3x_1+0x_2+17x_3+x_4+3x_5& =& 75\end{array}$$

新的单纯形表为 :

$c_j$$c_j$$1$$2$$1$$0$$0$

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	${\theta }_i$
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$15$	$2$	$-3$	$2$	$1$	$0$	$-$ (${\theta }_4$)
$0$ ( 目标函数 $x_5$ 系数 $c_5$)	$x_5$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$20$ ( ${\theta }_5$ )
${\sigma }_j$ ( 检验数 )			$1$ ( ${\sigma }_1$ )	$2$ ( ${\sigma }_2$ )	$1$ ( ${\sigma }_3$ )	$0$	$0$
第一次迭代	–	–	–	–	–	–	–	–
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$75$	$3$	$0$	$17$	$1$	$3$	$?$ ( ${\theta }_4$ )
$2$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$?$ (${\theta }_2$)
${\sigma }_j$ ( 检验数 )			$?$ ( ${\sigma }_1$ )	$0$	$?$ ( ${\sigma }_3$ )	$0$	$?$ ( ${\sigma }_5$ )

9、第一次迭代 : 计算检验数

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

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

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

${\sigma }_3=1-\left(\begin{array}{c}02\end{array}\right)\times \left(\begin{array}{c}17\\ \\ 5\end{array}\right)=1-(0\times 17+2\times 5)=-9$

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

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

新的单纯形表为 :

$c_j$$c_j$$1$$2$$1$$0$$0$

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	${\theta }_i$
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$15$	$2$	$-3$	$2$	$1$	$0$	$-$ (${\theta }_4$)
$0$ ( 目标函数 $x_5$ 系数 $c_5$)	$x_5$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$20$ ( ${\theta }_5$ )
${\sigma }_j$ ( 检验数 )			$1$ ( ${\sigma }_1$ )	$2$ ( ${\sigma }_2$ )	$1$ ( ${\sigma }_3$ )	$0$	$0$
第一次迭代	–	–	–	–	–	–	–	–
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$75$	$3$	$0$	$17$	$1$	$3$	$?$ ( ${\theta }_4$ )
$2$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$?$ (${\theta }_2$)
${\sigma }_j$ ( 检验数 )			$\frac{1}{3}$ ( ${\sigma }_1$ )	$0$	$-9$ ( ${\sigma }_3$ )	$0$	$-2$ ( ${\sigma }_5$ )

10、第一次迭代 : 最优解判定

上述三个检验数 , $\{\begin{array}{l}{\sigma }_1=\frac{1}{3}\\ \\ {\sigma }_3=-9\\ \\ {\sigma }_5=-2\end{array}$ , 其中 ${\sigma }_1$ 大于 $0$ , 只有当检验数都小于等于 $0$ 时 , 该基可行解才是最优解 ; 该解不是最优解 ;

无穷多最优解 : 当有检验数等于 $0$ 时 , 其它都小于 $0$ , 该线性规划有无穷多个最优解 ;
无界解 : 找不到出基变量 , 则该线性规划是无界解 ;

11、第一次迭代 : 入基变量

根据上述三个检验数 $\{\begin{array}{l}{\sigma }_1=\frac{1}{3}\\ \\ {\sigma }_3=-9\\ \\ {\sigma }_5=-2\end{array}$ 的值 , 选择检验数最大的非基变量作为入基变量 , 这里选择 $x_1$ ;

12、第一次迭代 : 出基变量

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

新的单纯形表为 :

$c_j$$c_j$$1$$2$$1$$0$$0$

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	${\theta }_i$
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$15$	$2$	$-3$	$2$	$1$	$0$	$-$ (${\theta }_4$)
$0$ ( 目标函数 $x_5$ 系数 $c_5$)	$x_5$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$20$ ( ${\theta }_5$ )
${\sigma }_j$ ( 检验数 )			$1$ ( ${\sigma }_1$ )	$2$ ( ${\sigma }_2$ )	$1$ ( ${\sigma }_3$ )	$0$	$0$
第一次迭代	–	–	–	–	–	–	–	–
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$75$	$3$	$0$	$17$	$1$	$3$	$25$ ( ${\theta }_4$ )
$2$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$60$ (${\theta }_2$)
${\sigma }_j$ ( 检验数 )			$\frac{1}{3}$ ( ${\sigma }_1$ )	$0$	$-9$ ( ${\sigma }_3$ )	$0$	$-2$ ( ${\sigma }_5$ )

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

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

新的单纯形表为 :

$c_j$$c_j$$1$$2$$1$$0$$0$

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	${\theta }_i$
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$15$	$2$	$-3$	$2$	$1$	$0$	$-$ (${\theta }_4$)
$0$ ( 目标函数 $x_5$ 系数 $c_5$)	$x_5$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$20$ ( ${\theta }_5$ )
${\sigma }_j$ ( 检验数 )			$1$ ( ${\sigma }_1$ )	$2$ ( ${\sigma }_2$ )	$1$ ( ${\sigma }_3$ )	$0$	$0$
第一次迭代	–	–	–	–	–	–	–	–
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$75$	$3$	$0$	$17$	$1$	$3$	$25$ ( ${\theta }_4$ )
$2$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$60$ (${\theta }_2$)
${\sigma }_j$ ( 检验数 )			$\frac{1}{3}$ ( ${\sigma }_1$ )	$0$	$-9$ ( ${\sigma }_3$ )	$0$	$-2$ ( ${\sigma }_5$ )
第二次迭代	–	–	–	–	–	–	–	–
$1$ ( 目标函数 $x_1$ 系数 $c_1$ )	$x_1$	$?$	$?$	$?$	$?$	$?$	$?$	$?$ ( ${\theta }_1$ )
$2$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$?$	$?$	$?$	$?$	$?$	$?$	$?$ (${\theta }_2$)
${\sigma }_j$ ( 检验数 )			$0$	$0$	$?$ ( ${\sigma }_3$ )	$?$ ( ${\sigma }_4$ )	$?$ ( ${\sigma }_5$ )

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

• 中心元系数 : 转换成 $1$ ;
• 中心元所在列另一个系数 : 转换成 $0$ ;

当前的线性规划标准形式等式方程组 : $\{\begin{array}{l}3x_1+0x_2+17x_3+x_4+3x_5=75\\ \\ \frac{1}{3}{x}_1+x_2+5x_3+0x_4+x_5=20\end{array}$

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

$$\begin{array}{lcl}(3x_1+0x_2+17x_3+x_4+3x_5)\times \frac{1}{3}& =& 75\times \frac{1}{3}\\ & & \\ x_1+0x_2+\frac{17}{3}{x}_3+\frac{1}{3}{x}_4+x_5& =& 25\end{array}$$

与中心元同一列的 $x_1$ 的系数转换为 $0$ : 将 $\frac{1}{3}{x}_1+x_2+5x_3+0x_4+x_5=20$ 中的 $x_1$ 系数转为 $0$ :

• 将 $x_1+0x_2+\frac{17}{3}{x}_3+\frac{1}{3}{x}_4+x_5=25$ 方程 左右变量乘以 $-\frac{1}{3}$ ;
• 将上个步骤得到的等式与 $\frac{1}{3}{x}_1+x_2+5x_3+0x_4+x_5=20$ 相加 , 即可使 $x_1$ 系数为 $0$ ;

$$\begin{array}{l}(x_1+0x_2+\frac{17}{3}{x}_3+\frac{1}{3}{x}_4+x_5)\times -\frac{1}{3}+(\frac{1}{3}{x}_1+x_2+5x_3+0x_4+x_5)=25\times -\frac{1}{3}+20\\ \\ (-x_1+0x_2-\frac{17}{9}{x}_3-\frac{1}{9}{x}_4-\frac{1}{3}{x}_5)+(\frac{1}{3}{x}_1+x_2+5x_3+0x_4+x_5)=\frac{35}{3}\\ \\ 0x_1+x_2+\frac{28}{9}{x}_3-\frac{1}{9}{x}_4+\frac{2}{3}{x}_5=\frac{35}{3}\end{array}$$

新的单纯形表为 :

$c_j$$c_j$$1$$2$$1$$0$$0$

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	${\theta }_i$
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$15$	$2$	$-3$	$2$	$1$	$0$	$-$ (${\theta }_4$)
$0$ ( 目标函数 $x_5$ 系数 $c_5$)	$x_5$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$20$ ( ${\theta }_5$ )
${\sigma }_j$ ( 检验数 )			$1$ ( ${\sigma }_1$ )	$2$ ( ${\sigma }_2$ )	$1$ ( ${\sigma }_3$ )	$0$	$0$
第一次迭代	–	–	–	–	–	–	–	–
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$75$	$3$	$0$	$17$	$1$	$3$	$25$ ( ${\theta }_4$ )
$2$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$60$ (${\theta }_2$)
${\sigma }_j$ ( 检验数 )			$\frac{1}{3}$ ( ${\sigma }_1$ )	$0$	$-9$ ( ${\sigma }_3$ )	$0$	$-2$ ( ${\sigma }_5$ )
第二次迭代	–	–	–	–	–	–	–	–
$1$ ( 目标函数 $x_1$ 系数 $c_1$ )	$x_1$	$25$	$1$	$0$	$\frac{17}{3}$	$\frac{1}{3}$	$1$	$?$ ( ${\theta }_1$ )
$2$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$\frac{35}{3}$	$0$	$1$	$\frac{28}{9}$	$-\frac{1}{9}$	$\frac{2}{3}$	$?$ (${\theta }_2$)
${\sigma }_j$ ( 检验数 )			$0$	$0$	$?$ ( ${\sigma }_3$ )	$?$ ( ${\sigma }_4$ )	$?$ ( ${\sigma }_5$ )

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

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

${\sigma }_3=1-\left(\begin{array}{c}12\end{array}\right)\times \left(\begin{array}{c}\frac{17}{3}\\ \\ \frac{28}{9}\end{array}\right)=1-(1\times \frac{17}{3}+2\times \frac{28}{9})=\frac{9-17\times 3+28\times 2}{9}=-\frac{98}{9}$

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

${\sigma }_4=0-\left(\begin{array}{c}12\end{array}\right)\times \left(\begin{array}{c}\frac{1}{3}\\ \\ -\frac{1}{9}\end{array}\right)=0-(1\times \frac{1}{3}-2\times \frac{1}{9})=-\frac{1}{9}$

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

${\sigma }_5=0-\left(\begin{array}{c}12\end{array}\right)\times \left(\begin{array}{c}1\\ \\ \frac{2}{3}\end{array}\right)=0-(1\times 1+2\times \frac{2}{3})=-\frac{7}{3}$

新的单纯形表为 :

$c_j$$c_j$$1$$2$$1$$0$$0$

$C_B$ 基变量系数 (目标函数)	基变量	常数 $b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	${\theta }_i$
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$15$	$2$	$-3$	$2$	$1$	$0$	$-$ (${\theta }_4$)
$0$ ( 目标函数 $x_5$ 系数 $c_5$)	$x_5$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$20$ ( ${\theta }_5$ )
${\sigma }_j$ ( 检验数 )			$1$ ( ${\sigma }_1$ )	$2$ ( ${\sigma }_2$ )	$1$ ( ${\sigma }_3$ )	$0$	$0$
第一次迭代	–	–	–	–	–	–	–	–
$0$ ( 目标函数 $x_4$ 系数 $c_4$ )	$x_4$	$75$	$3$	$0$	$17$	$1$	$3$	$25$ ( ${\theta }_4$ )
$2$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$20$	$\frac{1}{3}$	$1$	$5$	$0$	$1$	$60$ (${\theta }_2$)
${\sigma }_j$ ( 检验数 )			$\frac{1}{3}$ ( ${\sigma }_1$ )	$0$	$-9$ ( ${\sigma }_3$ )	$0$	$-2$ ( ${\sigma }_5$ )
第二次迭代	–	–	–	–	–	–	–	–
$1$ ( 目标函数 $x_1$ 系数 $c_1$ )	$x_1$	$25$	$1$	$0$	$\frac{17}{3}$	$\frac{1}{3}$	$1$	$?$ ( ${\theta }_1$ )
$2$ ( 目标函数 $x_2$ 系数 $c_2$)	$x_2$	$\frac{35}{3}$	$0$	$1$	$\frac{28}{9}$	$-\frac{1}{9}$	$\frac{2}{3}$	$?$ (${\theta }_2$)
${\sigma }_j$ ( 检验数 )			$0$	$0$	$-\frac{98}{9}$ ( ${\sigma }_3$ )	$-\frac{1}{9}$ ( ${\sigma }_4$ )	$-\frac{7}{3}$ ( ${\sigma }_5$ )

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

上述三个检验数 , $\{\begin{array}{l}{\sigma }_3=-\frac{98}{9}\\ \\ {\sigma }_4=-\frac{1}{9}\\ \\ {\sigma }_5=-\frac{7}{3}\end{array}$ , 三个检验数都小于等于 $0$ , 该基可行解是最优解 ;

五、线性规划最优解分析

---

1、唯一最优解

使用单纯形法求解线性规划时 , 得到最优解时 , 所有的非基变量对应的检验数都小于 $0$ , 该线性规划有唯一最优解 ;

2、无穷多最优解

使用单纯形法求解线性规划时 , 得到最优解时 , 存在一个或多个非基变量对应的检验数等于 $0$ , 那么该线性规划有无穷多最优解 ;

3、无界解

使用单纯形法求解线性规划时 , 某个非基变量 $x_j$ , 其对应的检验数 ${\sigma }_j\le 0$ , 但是该非基变量的所有系数都是小于等于 $0$ 的 , 此时该线性规划有 无界解 ;

4、无可行解

使用人工变量法 ( 大 $M$ 单纯形法 ) 求解线性规划 , 得到最优解时 , 此时基变量中还存在人工变量 , 人工添加的变量没有迭代出去 , 这种情况下 , 该线性规划没有可行解 ;

总结

以上是生活随笔为你收集整理的【运筹学】单纯形法总结 ( 单纯形法原理 | 单纯形法流程 | 单纯形表 | 计算检验数 | 最优解判定 | 入基变量 | 出基变量 | 方程组同解变换 ) ★★★的全部内容，希望文章能够帮你解决所遇到的问题。

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