单纯形法的循环问题和解决方法摘要：单纯形法是解决线性规划的最普遍的方法，但是在出现退化问题的时候很容易出现循环现象本文对循环问题进行了分析，并给出了解决循环问题的几种方法关键字： 单纯形法循环问题单纯形法的循环问题在单纯形法计算过程中， 基变量有时存在两个以上相同的最小比值，在下一次的迭代中就有一个或几个基变量等于零，这称之为退化单纯形法迭代过程中选取出基变量，若多于一个可选者就会出现退化，当出现这样情况， 选择出基变量不当的话， 就可能导致迭代过程中基的反复，即迭代过程的循环， 这样目标函数值永远达不到最优解这种问题就是单纯形法的循环问题出现循环问题的原因退化是循环的必要条件， 当线形规划中出现退化的基本可行解时，如果进基，出基变量选取准则不合理就有可能出现循环现象例子：123412345123463731min( )20442115602 11102022 10(1,2,...,7)jf xxxxxxxxxxxxxxxxxxj迭代次数基变量CBX1 x2 x3 x4 x5 x6 x7 b 比值3/4 -20 1/2 -4 0 0 0 0 X5 X6 X7 0 0 0 1/2-15 -1 6 1 0 0 1/2 -10 -1/2 2 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 Zj Cj-zj 0 0 0 0 0 0 0 3/4 -20 1/2 -4 0 0 0 迭代次数基变量CBX1 x2 x3 x4 x5 x6 x7 b 比值3/4 -20 1/2 -4 0 0 0 1 X1 X6 X7 3/4 0 0 1 -30 -2 12 2 0 0 0 51/2 -4 -1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 1 Zj Cj-zj 3/4 -45/2 -3/2 9 3/2 0 0 0 5/2 2 -13 -3/2 0 0 迭代次数基变量CBX1 x2 x3 x4 x5 x6 x7 b 比值3/4 -20 1/2 -4 0 0 0 2 X1 X2 X7 3/4 -20 0 1 0 1-12 -4 6 0 0 1 1/10 -4/5 -1/5 1/5 0 0 0 1 0 0 0 1 0 0 1 0 0 1 Zj Cj-zj 3/4 -20 -5/4 7 1 1/2 0 0 0 7/4 -11 -1 -1/2 0 迭代次数基变量CBX1 x2 x3 x4 x5 x6 x7 b 比值3/4 -20 1/2 -4 0 0 0 3 X3 X2 X7 1/2 -20 0 1 0 1 -12 -4 6 0 -1/10 1 0 2/51/5 -2/5 0 -1 0 0 12 4 6 1 0 0 1 0 0 1/12 Zj Cj-zj 5/2 -20 1/2 -14 -6 11 0 -7/4 0 0 10 6 -11 0 迭X1 x2 x3 x4 x5 x6 x7 代次数基变量CB3/4 -20 1/2 -4 0 0 0 b 比值4 X3 X4 X7 1/2 -4 0 -2 30 1 0 2-6 0 -1/4 5/2 0 1 1/2 -1 0 2 -30 0 0 -2 6 1 0 0 1 0 0 Zj Cj-zj 0 5 1/2 -4 -1 1 0 3/4 -25 0 0 1 -1 0 迭代次数基变量CBX1 x2 x3 x4 x5 x6 x7 b 比值3/4 -20 1/2 -4 0 0 0 5 X5 X4 X7 0 -4 0 -1 15 1/2 0 1 -3 0 1/4 -5 -1/4 1 0 1/20 0 0 1 0 0 0 1 0 0 1 0 Zj Cj-zj -1 20 1 -4 0 -2 0 7/4 -40 -1/2 0 0 2 0 迭代次数基变量CBX1 x2 x3 x4 x5 x6 x7 b 比值3/4 -20 1/2 -4 0 0 0 6 X5 X6 X7 0 0 0 1/2-15 -1 6 1 0 0 1/2 -10 -1/2 2 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 Zj Cj-zj 0 0 0 0 0 0 0 3/4 -20 1/2 -4 0 0 0 在上面的例子中， 每次迭代出现多个候选的出基变量时，我们都是选取最上面行的基变量作为出基变量， 最后还是出现了循环。
有学者证明： 迭代出现循环的最小迭代次数是6 次，因此上面的例子已经是出现循环的最简单的例子不难发现在出现循环现象时， 每次迭代至少有两个基变量取零值，且其中至少有一个变量是候选的出基变量解决循环的方法退化是循环的必要条件， 要避免循环要么是考虑如何在退化的情况下采取措施使循环不会发生，要么是从根本上消除退化现象1、摄动法就是从根本上消除退化现象，将原规划进行摄动处理，使之成为一个非退化的规划问题 线形规划存不存在退化的基本可行解，重要是和右端常数 b 有关摄动法用向量1( )n j j jbba来代替原规划 P 中的 b 得到一个新的规划P() ; 其中ja 是系数矩阵的列向量，是一个非常小的正数可以证明：当是个很小的正数时， P()是不会退化的；当→0 时，P()的最优解就是原问题P 的最优解实际计算时并不需要引入，还是进行 P的基变换， 不过要注意现在选取出基变量的指标是0 10,1...min ikm j iij jyim ikyyy，其中0iy 是某次迭代中右端常数向量的第 i 行值，ijy ，iky 分别是某次迭代中系数矩阵第i 行第 j 列和第 i 行第 k 列的值摄动法考虑了收敛速度的问题， 但遇到多个候选出基变量时， 计算机计算比较费时，在实用上该方法不是一个理想的方法。
2、Bland 方法是最简单，应用最广的避免循环的方法，该方法只是对进基和出基的准则作了一些修改：首先把松弛变量（剩余变量） 、人工变量都用 xj 表示，一般松弛变量（剩余变量）的下标号列在决策变量之后， 人工变量的下标号列在松弛变量 （剩余变量）之后，在计算中：选取进基变量时， 在所有检验数大于零的非基变量中，选取相应下标最小者进基；选取出基变量时，如果出现多个候选者， 即存在两个和两个以上最小比值时，选取下标最小者出基；该方法计算简单但迭代次数比较多， 现在有很多学者在对Bland 方法进行改进，提出改进的选基准则，主要是加快目标函数下降的速度比如有的人提出：开始把变量重新排序， 使得 c1<=c2<=⋯..<=cn,再使用 Bland 方法 还有学者提出：在进行迭代时，在当前迭代点的所有邻近极点中，选取目标函数值最好的极点另外还有辞典序法等近几年来，不断有学者提出新的避免循环的方法这里主要介绍 2 种新的选基准则ⅰ 设1(,)(,0)0BNXXXB b是线形规划的初始基本可行解，且经检验不是最优解，那么，在候选进基变量中选择一个是初始基变量的变量进基：（1）若这样的初始基变量有两个以上，则任选一个进基：（2）若候选进基变量都不是初始基变量， 也任选其中一个进基， 同时在候选出基变量中选择一个是初始基变量的变量出基：（1）若这样的初始基变量有两个以上，则任选其中一个出基，若候选出基变量都不是初始基变量，也任选其中一个出基。
ⅱ 当有多个检验数是正数时， 若相应的基本可行解最多只有一个基变量取0值，则取最大检验数对应的非基变量出基；若相应的基本可行解有多于一个基变量取 0 值，则用 Bland 方法，选对应变量中下标最小者为进基变量参考文献[1] 周 勤学 , 丘 兆福 .Bland避 免 循 环 的 单 纯形 法的 改进 [J].中 南 大 学 学报.1989.3 [2] 李思惠 . 单纯形法求解LP 问题克服循环的一种方法及其证明[J]. 南京农业大学学报 .1991,14 [3] 张有德 , 王全清. 关于用单纯形方法解线性规划问题出现循环的一点探讨[J].工科数学 .1990 [4] 裘宗沪 . 解决线性规划的单纯形算法中避免循环的几种方法[J]. [5] 金涛, 刘三阳 , 孙小军 . 一种线性规划问题单纯形法的改进算法[J]. 宝鸡文理学院学报 2007.12 。