王树尧老师运筹学课程笔记 10 线性规划与单纯形法（关于检测数与退化的讨论）

第10讲 线性规划与单纯形法（关于检测数与退化的讨论）

对单纯形表中一些列的理解

主要注意的是，在如上图所示的单纯形表中，$b$列和填$a_{i,j}$的列中本质上填的应该是$B^{-1}b$和$B^{-1}A$，只是在之前的情况下中$B$是单位矩阵。

对检测数的讨论

检验数的计算方法为${\sigma }_i=c_i-c_B{B}^{-1}{p}_i=c_i-z_i$。而对于其他教材可能将${\sigma }_i$定义为${\sigma }_i$$=z_i-c_i$，但其本质上是一样的，只是判断${\sigma }_i$符号和大小时恰好相反。同时如果要求解的最优化问题是对目标函数求$min$，也只需要在判断${\sigma }_i$时，用符号和大小相反的规则即可。简要来说取得最优解时对检验数的正负性要求如下表所示：

	$maxZ$	$minZ$
$c_i-z_i$	$\le 0$	$\ge 0$
$z_i-c_i$	$\ge 0$	$\le 0$

如果在某轮迭代，有两个及以上相同的最大的检验数，则其给目标函数带来的收益相同，可以选择其对应的任意一个向量作为入基向量。

对$\theta$的讨论

如果在某轮迭代，有两个及以上相同的最小的$\theta$，出现“退化”情况，大部分情况下可以选择其对应的任意一个向量作为出基向量，但是有些时候会出现循环运算。

当标准型中$b_i=0$时，可能出现“退化”情况。

解决方法： 在相同的最小的$\theta$中，选择下标最小的决策变量作为出基变量，就不会出现循环运算。

总结

在单纯形表中，$b$列和填$a_{i,j}$的列中本质上填的应该是$B^{-1}b$和$B^{-1}A$。

对于不同检验数的定义和求$min$或$max$的不同，对检验数的判断法则也不同。

如果在某轮迭代，有两个及以上相同的最大的检验数，则其给目标函数带来的收益相同，可以选择其对应的任意一个向量作为入基向量。

如果在某轮迭代，有两个及以上相同的最小的$\theta$，则选择下标最小的决策变量作为出基变量，就不会出现循环运算。