线性规划单纯形法的改进—避免无效回溯和循环.docx

线性规划单纯形法的改进避免无效回溯和循环线性规划单纯形法的改进避免无效回溯和循环余四清（北京市丰台科学城富丰路6号北京金自天正公司轧钢部 100071 e-mail: ）摘 要 对于用线性规划单纯形法解决问题时所遇到的一类无效回溯和循环现象，本文提出了简单而有效的解决方法，即尽量避免以等于零的变量入基，改进了单纯形法选择入基变量的方法。这种方法对减少因入基变量为零而产生的回溯现象很有效，减少了计算量；它打破了Klee和Minty给出的实例叠代次数为变量个数的指数函数的结论，具有极其重要的理论意义。关键词 线性规划，单纯形法，多项式时间算法，回溯现象，循环现象分类号 O211.1Improvement of Simplex Algorithm in Linear Programming -Avoid Ineffective Recalling and CirclingYU Siqing(Steel-Rolling Department, Beijing AriTime Intelligent Control Co., Ltd., 6 Fufeng Road, Fengtai Science City,Beijing 100071)Abstract For ineffective recalling and circling phenomena in linear programming using simplex algorithm, a simple and effective solving method is put forward, that is avoiding to use variable whose value is zero as variable which will enter the basic matrix. It improves the method of selecting variable which will enter the basic matrix in simplex algorithm. The method is effective in reducing the recalling phenomena because of the zero-value variable which will enter the basic matrix. It reduces the calculating amount. It breaks the result of an example which were given by Klee and Minty that the substitution times is an exponential function of the number of variables and has very important theoretical significance.Key Words linear programming, simplex algorithm, polynomial-time algorithm, recalling phenomena, circling phenomena1 引言对于线性规划问题，G. B. Dantzig1947年提出的单纯形法是非常有效的，但它不是多项式时间算法。所谓多项式时间算法，就是算法计算时间不超过将问题的数据输入计算机上所需二进制代码长度的某个多项式所确定的数值的算法。原因是Klee和Minty1给出实例：min f= xnst. x1 - r1 =1/4 x1 + r1 =1 xj 1/4 xj - rj =0，j=2,3,n xj +1/4 xj + sj =0，j=2,3,n xj , rj , sj 0，j=1,2,n文献1证明，用单纯形法解之，叠代次数为2 n-1。另外，Beale2给出的例子：min f=-3/4 x4 + 20x5 1/2x6 + 6x7st. x1 +1/4 x4 - 8 x5 - x6 +9 x7 = 0 x2 +1/2 x4 -12 x5 1/2x6 +3 x7 = 0 x3 +x6 = 1 xj0，j=1,2,7用单纯形法解之，会产生无限循环现象，得不出结论，需要用所谓摄动法解才能得出结论。本人认为，产生以上结果的原因是叠代过程中产生了回溯现象。在每次叠代过程中，要选择一个入基变量和一个离基变量，以形成新的基。如果某个变量入基后又离基，或离基后又入基，这就是回溯现象。试看Beale的例子单纯形表格法解题过程如下：表1 表2x1 x2 x3 x4 x5 x6 x7bx1 x2 x3 x4 x5 x6 x7bx1x2 x31 0 0 1/4 -8 -1 90 1 0 1/2 -12 -1/2 30 0 1 0 0 1 0001x4x2 x34 0 0 1 -32 -4 36-2 1 0 0 4 3/2 -150 0 1 0 0 1 0001-f0 0 0 -3/4 20 -1/2 60-f3 0 0 0 -4 -7/2 330表3 表4x1 x2 x3 x4 x5 x6 x7bx1 x2 x3 x4 x5 x6 x7bx4x5 x34 8 0 1 0 8 -84-1/2 1/4 0 0 1 3/8 -15/40 0 1 0 0 1 0001x6x5 x3-3/2 1 0 1/8 0 1 -21/2-1/16 -1/8 0 -3/64 1 0 3/163/2 -1 1 -1/8 0 0 21/2001-f1 1 0 0 0 -2 180-f-2 3 0 1/4 0 0 -30表5 表6x1 x2 x3 x4 x5 x6 x7bx1 x2 x3 x4 x5 x6 x7bx6x7 x32 -6 0 -5/2 56 1 01/3 2/3 0 -1/4 16/3 0 1-2 6 1 5/2 -56 0 0001x1 x7x31 -3 0 -5/4 28 1/2 00 1/3 0 1/6 -4 -1/6 10 0 1 0 0 1 0001-f-1 1 0 -1/2 16 0 00-f-2 3 0 1/4 0 0 -30表7 x1 x2 x3 x4 x5 x6 x7bx1x2 x31 0 0 1/4 -8 -1 90 1 0 1/2 -12 -1/2 30 0 1 0 0 1 0001-f0 0 0 -3/4 20 -1/2 60表2中变量x4入基，到表4中又离基；表2中变量x1出基，到表6中又入基；其它变量也有类似现象，这就是回溯。解Klee和Minty给出的实例时，也因为产生回溯，导致叠代次数增加。一般情况下，n个变量，m个约束条件的标准线性规划在最优化时，需找出n-m个等于0的非基变量，或者找出m个可能不等于0的基变量。如不产生回溯现象，叠代次数将不超过minn,n-m。如何避免回溯现象呢？2 避免无效回溯的方法表2中，x4入基，它的取值是0，这样它入基后目标函数f=CTX没有增减。所以变量x4的回溯是无效回溯。虽然最优解中不是所有的基变量都大于0，但只有入基的变量大于0，才能使目标函数有增减，才不致产生无效回溯。表1目标函数f右边的变量系数（即所谓判别数）小于0的除了c4= -3/4外，还有c6= -1/2。如果选择x6为入基变量，则x6=1，x6入基才能使目标函数下降，所以应该首先使x6而不是x4入基，按照这种思路解题如下：表8 表9x1 x2 x3 x4 x5 x6 x7bx1 x2 x3 x4 x5 x6 x7bx1x2 x31 0 0 1/4 -8 -1 90 1 0 1/2 -12 -1/2 30 0 1 0 0 1 0001x1x2 x61 0 1 1/4 -8 0 90 1 1/2 1/2 -12 0 30 0 1 0 0 1 011/21-f0 0 0 -3/4 20 -1/2 60-f0 0 1/2 -3/4 20 0 61/2表10 x1 x2 x3 x4 x5 x6 x7bx1x4 x61 -1/2 3/4 0 -2 0 15/20 2 1 1 -24 0 60 0 1 0 0 1 03/411-f0 3/2 5/4 0 2 0 21/25/4经过两次叠代得出最优解X=(3/4,0,0,1,0,1,0)，f min = -5/4。这与摄动法解的结果是相同的，但它的解题过程要简单得多。由此，为了避免无效回溯，对传统单纯形法中选择入基变量的方法做一些改进：在求目标函数最小值，选择入基变量时，如果目标函数f右边的变量系数（即所谓判别数，这个系数每次叠代都有变化，如计算表中所示）小于0的最小者对应的变量入基后取值大于0，则以它为入基变量；如果它入基后取值为0，则需再看其余小于0的变量系数（判别数）对应变量入基时取值是否为0，取入基后不等于0且其变量系数（判别数）最小者对应变量入基。如果目标函数所有小于0的变量系数（判别数）对应的变量入基后取值均为0，那就选择小于0的变量系数最小者对应的变量作为入基变量。总之，不是总以目标函数f右边的变量系数小于0的最小者对应的变量入基，应该尽量避免以取值为0变量入基。求最大值时，也不是总以目标函数f右边的变量系数大于0的最大者对应的变量入基，也应该尽量避免以取值为0变量入基。以这种方法，同样可以避免Klee和Minty给出的实例中用传统单纯形法解题时产生的无效回溯。在n=3时，Klee和Minty证明用传统单纯形法解题，需要叠代2 3-1=7次。下面以本文中的方法解之。初表为表11，y1 , y2 , y3为人工变量，借助大M法（M是很大的正数），使目标函数等式右边初始基变量的系数化为0，得表12，从表12开始叠代：表11x1 r1 x2 r2 x3 r3 y1 s1 y2 y3 s2 s3 by1s1 y2y3s2 s3 1 -1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 -1/4 0 1 -1 0 0 0 0 1 0 0 0 0 0 -1/4 0 1 -1 0 0 0 1 0 0 1/4 0 1 0 0 0 0 0 0 0 1 0 0 0 1/4 0 1 0 0 0 0 0 0 11/410011-f 0 0 0 0 -1 0 M 0 M M 0 00表12x1 r1 x2 r2 x3 r3 y1 s1 y2 y3 s2 s3 by1s1 y2y3s2 s3 1 -1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 -1/4 0 1 -1 0 0 0 0 1 0 0 0 0 0 -1/4 0 1 -1 0 0 0 1 0 0 1/4 0 1 0 0 0 0 0 0 0 1 0 0 0 1/4 0 1 0 0 0 0 0 0 11/410011-f-3/4M M -3/4M M -M-1 M 0 0 0 0 0 0-1/4M表13x1 r1 x2 r2 x3 r3 y1 s1 y2 y3 s2 s3 bx1s1 y2y3s2 s3 1 -1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 -1 1 0 0 0 0 0 -1/4 1 -1 0 0 1/4 0 1 0 0 0 0 0 -1/4 0 1 -1 0 0 0 1 0 0 0 1/4 1 0 0 0 -1/4 0 0 0 1 0 0 0 1/4 0 1 0 0 0 0 0 0 11/43/41/16015/161-f0 1/4M -3/4M M -M-1 M 3/4M 0 0 0 0 0-1/16M表14x1 r1 x2 r2 x3 r3 y1 s1 y2 y3 s2 s3 bx1s1 x2y3s2 s3 1 -1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 -1 1 0 0 0 0 0 -1/4 1 -1 0 0 1/4 0 1 0 0 0 0 -1/16 0 -1/4 1 -1 1/16 0 1/4 1 0 0 0 1/2 0 1 0 0 -1/2 0 -1 0 1 0 0 1/16 0 1/4 1 0 -1/16 0 -1/4 0 0 11/43/41/161/647/863/64-f0 1/16M 0 1/4M -M-1 M 15/16M 0 3/4M 0 0 0-1/64M表15x1 r1 x2 r2 x3 r3 y1 s1 y2 y3 s2 s3 bx1s1 x2x3s2 s3 1 -1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 -1 1 0 0 0 0 0 -1/4 1 -1 0 0 1/4 0 1 0 0 0 0 -1/16 0 -1/4 1 -1 1/16 0 1/4 1 0 0 0 1/2 0 1 0 0 -1/2 0 -1 0 1 00 1/8 0 1/2 0 1 -1/8 0 -1/2 -1 0 11/43/41/161/647/831/32-f0 -1/16 0 -1/4 0 -1 1/16+M 0 M+1/4 M+1 0 01/64表16x1 r1 x2 r2 x3 r3 y1 s1 y2 y3 s2 s3 bx1s1 x2x3s2 r3 1 -1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 -1 1 0 0 0 0 0 -1/4 1 -1 0 0 1/4 0 1 0 0 0 0 1/16 0 1/4 1 0 -1/16 0 -1/4 0 0 1 0 1/2 0 1 0 0 -1/2 0 -1 0 1 0 0 1/8 0 1/2 0 1 -1/8 0 -1/2 -1 0 11/43/41/1663/647/831/32-f0 1/16 0 1/4 0 0 -1/16+M 0 M-1/4 M 0 163/64在表12和13中，按传统单纯形算法，应该以x3为入基变量，但这会产生无效回溯。由于有效地避免了无效回溯，以上计算经过4次而不是7次叠代，即得到最优解：x1=1/4，x2=1/16，x3=63/64，s1=3/4，s2 =7/8