《线性规划单纯形法的改进—避免无效回溯和循环》由会员分享，可在线阅读，更多相关《线性规划单纯形法的改进—避免无效回溯和循环（5页珍藏版）》请在金锄头文库上搜索。
1、线性规划单纯形法的改进避免无效回溯和循环第 1 页 共 5 页线线性性规规划划单单纯纯形形法法的的改改进进避避免免无无效效回回溯溯和和循循环环余四清（北京市丰台科学城富丰路6 号北京金自天正公司轧钢部 100071 e-mail: ）摘摘 要要 对于用线性规划单纯形法解决问题时所遇到的一类无效回溯和循环现象，本文提出了简单而有效的解决方法，即尽量避免以等于零的变量入基，改进了单纯形法选择入基变量的方法。这种方法对减少因入基变量为零而产生的回溯现象很有效，减少了计算量；它打破了Klee 和 Minty 给出的实例叠代次数为变量个数的指数函数的结论，具有极其重要的理论意义。关关键键词词 线性规划，
2、单纯形法，多项式时间算法，回溯现象，循环现象分分类类号号 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
3、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 matr
4、ix 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 expone
5、ntial 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 年提出的单纯形法是非常有效的，但它不是多项 式时间算法。所谓多项式时间算法，就是算法计算时间不超过将问题的数据输入计算机上
6、所需二进制代码长度的某个多项式所确定的数值的算法。原因是Klee 和 Minty1给出实例： min f= xn st. x1 - r1 =1/4x1 + r1 =1xj 1/4 xj - rj =0，j=2,3,nxj +1/4 xj + sj =0，j=2,3,nxj , rj , sj 0，j=1,2,n 文献1证明，用单纯形法解之，叠代次数为2 n-1。 另外，Beale2给出的例子： min f=-3/4 x4 + 20x5 1/2x6 + 6x7 st. x1 +1/4 x4 - 8 x5 - x6 +9 x7 = 0x2 +1/2 x4 -12 x5 1/2x6 +3 x7 =
7、0x3 +x6 = 1线性规划单纯形法的改进避免无效回溯和循环第 2 页 共 5 页xj0，j=1,2,7 用单纯形法解之，会产生无限循环现象，得不出结论，需要用所谓摄动法解才能得出 结论。 本人认为，产生以上结果的原因是叠代过程中产生了回溯现象。在每次叠代过程中， 要选择一个入基变量和一个离基变量，以形成新的基。如果某个变量入基后又离基，或离 基后又入基，这就是回溯现象。试看Beale 的例子单纯形表格法解题过程如下：表 1 表 2 x1 x2 x3 x4 x5 x6 x7bx1 x2 x3 x4 x5 x6 x7b x1 x2 x31 0 0 1/4 -8 -1 9 0 1 0 1/2 -
8、12 -1/2 3 0 0 1 0 0 1 00 0 1x4 x2 x34 0 0 1 -32 -4 36 -2 1 0 0 4 3/2 -15 0 0 1 0 0 1 00 0 1 -f0 0 0 -3/4 20 -1/2 60-f3 0 0 0 -4 -7/2 330表 3 表 4 x1 x2 x3 x4 x5 x6 x7bx1 x2 x3 x4 x5 x6 x7b x4 x5 x34 8 0 1 0 8 -84 -1/2 1/4 0 0 1 3/8 -15/4 0 0 1 0 0 1 00 0 1x6 x5 x3-3/2 1 0 1/8 0 1 -21/2 -1/16 -1/8 0 -3
9、/64 1 0 3/16 3/2 -1 1 -1/8 0 0 21/20 0 1 -f1 1 0 0 0 -2 180-f-2 3 0 1/4 0 0 -30表 5 表 6 x1 x2 x3 x4 x5 x6 x7bx1 x2 x3 x4 x5 x6 x7b x6 x7 x32 -6 0 -5/2 56 1 0 1/3 2/3 0 -1/4 16/3 0 1 -2 6 1 5/2 -56 0 00 0 1x1 x7 x31 -3 0 -5/4 28 1/2 0 0 1/3 0 1/6 -4 -1/6 1 0 0 1 0 0 1 00 0 1 -f-1 1 0 -1/2 16 0 00-f-2
10、3 0 1/4 0 0 -30表 7 x1 x2 x3 x4 x5 x6 x7b x1 x2 x31 0 0 1/4 -8 -1 9 0 1 0 1/2 -12 -1/2 3 0 0 1 0 0 1 00 0 1 -f0 0 0 -3/4 20 -1/2 60表 2 中变量 x4入基，到表4 中又离基；表2 中变量 x1出基，到表6 中又入基；其它变 量也有类似现象，这就是回溯。解Klee 和 Minty 给出的实例时，也因为产生回溯，导致叠 代次数增加。 一般情况下，n 个变量，m 个约束条件的标准线性规划在最优化时，需找出n-m 个等于 0 的非基变量，或者找出m 个可能不等于0 的基变量
11、。如不产生回溯现象，叠代次数将不超 过 minn,n-m。 如何避免回溯现象呢？2避避免免无无效效回回溯溯的的方方法法 表 2 中，x4入基，它的取值是0，这样它入基后目标函数f=CTX 没有增减。所以变量x4 的回溯是无效回溯。虽然最优解中不是所有的基变量都大于0，但只有入基的变量大于 0， 才能使目标函数有增减，才不致产生无效回溯。线性规划单纯形法的改进避免无效回溯和循环第 3 页 共 5 页表 1 目标函数f 右边的变量系数（即所谓判别数）小于0 的除了 c4= -3/4 外，还有c6= - 1/2。如果选择x6为入基变量，则x6=1，x6入基才能使目标函数下降，所以应该首先使x6而 不
12、是 x4入基，按照这种思路解题如下：表 8 表 9 x1 x2 x3 x4 x5 x6 x7bx1 x2 x3 x4 x5 x6 x7b x1 x2 x31 0 0 1/4 -8 -1 9 0 1 0 1/2 -12 -1/2 3 0 0 1 0 0 1 00 0 1x1 x2 x61 0 1 1/4 -8 0 9 0 1 1/2 1/2 -12 0 3 0 0 1 0 0 1 01 1/2 1 -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 x7b x1 x4 x61 -1/2 3/4 0 -2 0
13、15/2 0 2 1 1 -24 0 6 0 0 1 0 0 1 03/4 1 1 -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 右边的变量
