（运筹学与控制论专业论文）投影主元标单纯形算法.pdf

摘要 在单纯形算法的有限主元规则中，b l a n d 规则f 1 0 1 因其简单而受到学术界特 别关注但与其它有限主元规则一样，该规则的实际计算效果很不理想潘平奇 教授在文1 2 8 ) 中指出，这个规则的缺点是它纯粹依赖于变量下标，面最优基本变 量与其下标却并无必然联系他提出了最优基的一个启发式特征刻划( 最钝角原 理) ，并据此给出了不依赖于变量下标而依赖于其“主元标”的有限规则不过其 中所定义的主元标仅适用于只含不等式约束的线性规划问题从求解标准线性 规划问题考虑，文用同样方式基于对偶问题来生成( 对偶) 主元标，然而其 实际表现仍不十分理想本文将基于目标函数梯度在约束矩阵零空间的正交投影 定义新的主元标，以进一步提高求解标准线性规划问题的效率我们的数值试验 表明，该规则的实际表现不仅明显优子b l a n d 规则且也优于基于对偶主元标的规则 关键词线性规划主元标投影主元标单纯形方法有限规则b l a n d 规则最 钝角退化 a b s t r a c t a m o n gf i n i t eo ra n t i c y c l i n gp i v o t i n gr u l e s b l a n d sr u l ei sn o t i c e a b l ef o ri t sr e m a r k a b l e s i m p l i c i t yi z 0 h o w e v e r ，i td e p e n d so nt h ei n d i c e so ft h ev a r i a b l e se n t i r e l y , a n di t sp e r f o r m m l c e i su n s a t i s f a c t o r y t oo v e o i n et h i ss h o r t c o m i n g , i n 【2 8 4p r o f e s s o rp - 一q p a np r e s e n t e dt h ep l a u - s i b l ec h a r a c t e r i z a t i o no fa no p t i m a ls o l u t i o n ，a n dg a v ea n e w p i v o t i n gr u l eb a s e do ns o - c a l l e d p i v o t i n gi n d i c e s f o rs o l v i n gl pp r o b l e m sw i t hi n e q l l a l i t yc o n s t r a i n s i n 嘲，t h ea u t h o rd e f i n e d t h ed u a l - p i v o t i n gi n d i c e sf o rs t a n d a r dl pp r o b l e m s w ef i n dt h a ti td o e sn o tc h a r a c t e r i z ea n o p t i m a ls o l u t i o nv e r ys a t i s f a c t o r i l y i nt h i st h e s i s ，啪i n t r o d u c ean e wp i v o t i n gi n d e xs y s t e m 。 c a l l e dp r o j e c t i v ep i v o t i n gi n d i c e s ，u s i n gt h eo r t h o g o n a lp r o j e c t i o no ft h eg r a d i e n to ft h eo b j e c - t i v ef u n c t i o no n t ot h en u l ls p a c eo ft h ec o n s t r a i n tm a t r i x ，a n ds h o wi t sp r o m i s eo fs u c c e s si n c o m p a r i s o nt oe x i t i n gf i n i t er u l e s ，p r a c t i c a l l y k e y w o r d s ：l pp i v o t i n gi n d i c e s p r o j e c t i v ep i v o t i n gi n d i c e s b l a n d r u l em o s t - o b t u * a u g l e d e g e n e r a t e 东南大学学位论文 独创性声明及使用授权的说明 一，学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他 入已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意 = ，关于学位论文使用授权的说明 签名t 东南大学、中国科学技术信息研究所国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文本人电 子文档的内容和纸质论文的内容相一致除在保密期内的保密论文外，允许论文 被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容论文的公布( 包括刊 登) 授权东南大学研究生院办理 斜名一瞰魄一 肼 第一章绪论 在线性规划的发展史上，1 9 4 7 年g b d a n t z i g 的成果标志着第一个里程碑他 不仅提出了单纯形算法，还较为系统地研究了线性规划的几何理论、对偶理论， 典型实用问题及其它有效的算法，单纯形算法是主元算法正是由于此类算法在 求解实际问题的高效率，使得主元算法逐渐成为求解线性规划问题的主要方法之 一大量的专家学者在选取主元规则，数值稳定性计算时间，计算量、初始可行 基、克服退化避免循环等方面作了深入研究 众所周知，退化现象是长期困扰单纯形算法的一个难题，因为大量的退化步 会严重降低单纯形算法的效率不仅如此，退化还使得单纯形算法的有限终止性 成为问题；事实上，已有人给出了单纯形算法发生循环的例子为了克服这个难 点，许多学者随之提出了有限主元规则t 扰动法f 3 1 字典序规则1 6 】，b l a n d 规则 1 0 t 等等。不过它们的实际表现并不能令人满意，更不能和d a n t z g 规则相比在这 些有限主元规则中，b l a n d 规则因其简单而特别受到学术界关注 可惜与其他有限主元规则一样，b l a n d 规则的实际计算效果也很不理想潘平 奇教授在文( 2 8 1 中指出，这个规则的缺点是它纯粹依赖于变量下标，而最优基本变 羞与其下标却并无必然联系为此他给出最优基的一个启发式特征刻划( 最钝角原 理) ，并据此提出了不依赖于变量下标蔼依赖于其。主元标。的有限规则不过其 中所定义的主元标仅适用于只含不等式约束的线性规划问题为便于求解标准线 性规划问题，文f 3 5 j 用潘的方式从对偶问题生成( 对偶) 主元标，然而其实际表现仍 不十分理想本文将基于目标函数梯度在约束矩阵零空间的正交投影定义新的主 元标，以进一步提高求解标准线性规划问题的效率我们的数值试验表明，该规则 的实际表现不仅明显优于b l a n d 规则且也优于基于对偶生元标的规则 关于后面章节内容的安排，大致框架如下t 第二章，列出单纯形算法的基本概念和定理，鉴于b l a n d 规则对本文的重要作 用，在这一章我们也列出了b l a n d 单纯形算法的有限性证明 第三章。介绍最钝角原理和已有的主元标知识 第四章，详细地介绍有关投影主元标的定义、定理和算法 1 东南大学硕士学位论文第一章绪论 2 第五章，我们首先对对偶主元标和投影主元标对最优基的刻划准确率进行数 值试验，然后对本文提出的三个新算法和已有的b l a n d 单纯形算法、对偶主元标单 纯形算法，通过两组数值实验对它们作了系统测试，并对测试结果作了详细的探 讨分析，最后为投影主元标的应用作了两点展望 第二章单纯形算法的基本概念和定理 关于单纯形算法的理论是极其丰富的，这里我们只介绍它的一些基本概念和 定理为了整篇文章讨论上的方便，对本文所涉及的符号和记法在此我们也作了规 范性说明 2 1 单纯形算法的基本概念和定理 考虑如下标准形式的线性规翔问题， r a i n ，z ( 2 1 曲 a 。ta z = b ( 2 1 6 ) $ 0( 2 1 c ) 其中c = 池，c 2 ，岛) r ，a j p n ，c t = 称为目标函数，( 2 1 b ) 式和( 2 a e ) 式称为该 线性规翔闯题的约束条件 本文将引用以下的符号和记法，如不特别说明。则以下面为准 ( 1 ) 矩阵，集合用大写的英文字母a ，b ，m ，等表示， 在具体使用时将对它们详细区分i ( 2 ) 列向量用小写的英文字母表示i ( 3 ) r a n k ( a )矩阵a 的秩； ( 4 ) 吩 矩阵a 的第j 列； ( 5 ) 向量的第j 个元素； ( 6 ) j l 向量的玉范效； 定义2 1 1 设口为矩阵4 中的一个m 阶满秩方阵，则称b 为一个基；b 中m 个线性无关的列向量称为基向量；。中与之对应的m 个分量称为基变量，其余的 变量称为非基变量，夸所有的非基变量取值为零。得到的解； z = ( ：) = ( 口：1 6 ) 称为对应于b 的基本解 定义2 1 2 一个基本解2 满足z o ，即也是一个可行解，则称。为一个基本 可行解，这时它所对应的基b 称为基本可行基 东南大学硕士学位论文第二章单纯形算法的基本概念和定理4 定义2 1 3 一个基本可行解。，如果所有的基变量都取正值，则称为非退化 的；反之一个或多个变量取值为零，则说其是退化的一个线性规划问题，如果它 的所有基本可行解都是非退化的，就称之为非退化的；否则有一个基本可行解是 退化的，就说它是退化的 定义2 1 4 一个基本可行解x 如果满足式偿1 a ) ，则称之为线性规划问题的最 优解，相应的目标函数值c t x 就称为线性规划问题的最优值 定理2 1 1 可行解是基本可行解x 的充分必要条件是正分量所对应的列向量 线性无关。 定理2 。1 2 若一标准的线性规划问题有可行解，则其必有基本可行解。 定理2 1 3 若一个标准的线性规划问题的目标函数有有限最优值，则必在某 个基本可行解达到。 根据定义( 2 2 1 ) 我们在本文中有下面定义； 定义2 1 5 与最优解相关联的基变量称为最优基变量，与最优解相关联的非 基变量称为最优非基变量 将线性规划问题( 2 1 ) 以表格形式表示如下： 我们仍用b 表示基变量下标集合以及基本可行基，用表示非基变量下标集合以 及非基矩阵，不失一般性，设b = 1 ，2 ，m ) ，n = m + l ，m + 2 ，n ) ，则问题 ( 2 1 ) 对应的表格分块为t 将其进行g a u s s j o r d a n 消去得 令e 7 = ( o ，西一n 7 b 坷印) ，5 = b b ，这样线性规划问题( 2 1 ) 就转化为 r a i n 晶b - 1 b + 7 。 8t z 日+ 日n x n = 5 ( 2 ，2 a ) ( 2 2 6 ) 钟 黜 查童查堂堑圭耋堡墼塞董三薹 篁墼翼塞鎏墼董童堡垒堡室堡 5 $ o( 2 2 c ) 定理2 1 4 如果有一童使得上式偿别中e 20 ，则孟为原问题的最优解 定理2 1 5 如果向量( 有分量厶s0 强然m + 1sks 州，而其对应的向量 ( b 一1 ) i 一。董0 则原问题无界 定理2 1 6 如栗俾j 矽式中向量有分量奴0 ，且至少有一个负分量。则能 找到另一基本可行解岔，使，孟曼，牙 以上三个定理给出了单纯形算法的工作原理，即不断地从一个可行基迭代到 与它相临的另一个可行基，直至找到最优基( 若最优基存在的话) ，或者判断原问 题无界 2 2b l a n d 单纯形算法 严格意义上讲，本文所提出的投影主元标有限单纯形算法是b l a n d 单纯形算 法的变种，它对本文的创作有很大的启发和借鉴作用，因此在本节我们将系统她 介绍一下b l a n d 规则 如果令a i = ub - 1 n ) 。则问题( 2 2 ) 的表格形式为， 首先定义集合， d = 俐白 o ) ( 2 4 ) 准则2 2 。1 徊缸n d 准贝缈 确定一个进基变量下标互 茸= a r g m i n q l q d 俐再确定离基变量下标参 声= a r gr a i n 仞蜘f ( 蓟) ( 2 5 ) ( 2 6 ) 东南大学硕士学位论文第- - i 单纯形算遥笪薹主塑垒塑童望 6 下面我们引入b l a n d 规则的有限性定理及详细证明过程，因为它对主元标算 法的有限性证明具有重要的借鉴作用 引理2 2 1 遵循上述b l a n d 规则进行迭代，单纯形方法必在有限步终止 证假设单纯形方法按照b l a n d 规则确定进基变量、离基变量经过k 步： d 0 ，d 1 ，d k 一1 迭代后，又回到了d o 步。 d o ，d 1 ，一，口一1 ，d o ，d 1 f 2 7 1 我们把那些在这些迭代过程中不总是基变量也不总是非基变量的变量称之为易 变变量，并假设易变变量中下标最大的变量为。t ，且在某个典式d d o ，d 1 ，玖一1 ) 中，观是离基变量不失一般性，我们假设d = d o ，与其对应的z 。为进基变量， 我们将d o 记为s = 口+ 勺 ( 2 - 8 ) j 吼= b l 一a l j x i i b ( 2 9 ) j 根据x t 是离基变量，如是进基变量，我们得到，8 n ，t b 我们再假设在d + d o ，d a ，仇一1 ) 中觑是进基变量，可记为： = 矿+ 哼 ( 2 1 0 ) 赋= 瑶一吗i b ( 2 1 1 ) j 由于所有的典式都是退化的，有”= v + ，因此式子( 2 1 0 ) 也可以写为： f = u + c ；x j ( 2 1 2 ) _ + 为了记法上的方便，我们把哼扩貅弓= ；i ； 暂不考虑各个变量非负的约束，我们提高。的值，使得： fz 。：y ：o j s ) i 她= k d 。 t b 相应地目标函数在此点的函数值为； 这样( 2 1 2 ) 也可表示为 f = 口+ 岛私 f = 口+ c + ( 巩一奶 i e b 由上面的表达式( 2 a s ) 。( 2 1 4 ) 我们得到， ( c 一c ：+ = 露巩 既然它对任一都适合，必有， 一+ = 0 讵b 在d 中，是进基变量，我们得到t c 0 这样必有c ；0 ，由晖的定义可知道r n ，所以z ，是易变的，从而r t 根据 觑在驴中是进基变量，可得四 0 。又由于在d 中魂是离基变量，是进基变 量，容易知道a t a 是正的，这样 0 。也就是说r t ，从而r t r 0( 2 2 1 ) 东南大学硕士学位论文第二章单纯形算法的基本概念和定理 8 在循环体中每个典式都刻划了同一个解，这样在所有典式中每个易变量取值为o ( 因 为它所在的是非基变量的典式中取值是0 ) 特别的有x ，= 0 ，可是在d 中。，是基 变量，这样 b ，= 0( 22 2 ) 这样从式子( 2 2 1 ) 和( 2 2 2 ) 可以看出，在d 中x ，是可供作为离基变量的变量 既然r m 的情况下，而依据b l a n d 规则的最小下标法来挑选这m 个变量也可认为是一种随机 的 我们同样用这2 5 个小问题来测试投影主元标对最优基的命中率，统计结果见 表( 5 2 ) 不过这里的m l 与表5 1 中的m 1 有所不同，它指的是按照投影主元标从小 到大的顺序排列在后m 位的变量。在最优基变量中所拥有的个数。其它符号意义 同表( 5 1 ) 1 9 东南大学硕士学位论文第五章数值结果及分析2 0 从表( 5 2 ) 我们可以看出，投影主元标对最优基的特征刻划比对偶主元标有较 为大的改观，只有两个问题的最优基命中率低于5 0 ，1 5 个问题的最优基命中率 超过了7 0 ，对于这2 5 个问题统计结果显示它的平均命中率为7 0 ，这个数字相 比于对偶主元标来说是有很大的提高从而说明我们提出的投影主元标对最优基 的刻划是更为有效的，这样为投影主元标的应用带来了很大的希望。 问题 1 1 1 上i 2 m l m ( ) 1 2 795 0 0 0 2 371 06 6 6 7 3371 03 3 3 3 4371 03 3 3 3 5371 03 3 3 3 638i l3 3 3 3 7391 26 6 6 7 8 4 8 1 2 7 5 0 0 931 l1 4 3 3 3 3 1 051 01 56 0 0 0 1 141 l1 52 5 0 0 1 2 4 1 l1 52 5 0 0 1 3 6 1 42 01 6 6 7 1 461 52 15 0 0 0 1 512 12 20 0 0 0 1 671 52 24 2 8 6 1 782 43 21 2 5 0 1 882 4 3 23 7 5 0 1 982 43 23 7 5 0 2 01 12 53 65 4 5 4 2 11 12 83 92 7 2 7 2 21 53 75 26 6 6 7 2 3 2 2 4 56 74 0 9 1 2 42 3 4 66 95 6 5 2 2 52 54 57 06 0 0 0 问题 nn 1 + n “l m ( ) 1 2791 0 0 0 2371 01 0 0 o 337i 06 6 6 7 4 371 01 0 0 0 5371 01 0 0 0 638i i1 0 0 0 7 391 21 0 0 0 8481 21 0 0 0 931 11 46 6 6 7 1 051 01 5 8 0 0 0 i i4 1 l1 51 0 0 o 1 24l l1 51 0 0 ，o 1 361 42 06 6 6 7 1 46 1 5 2 15 0 0 0 1 5 l 2 12 21 0 0 0 1 671 52 24 2 8 6 1 782 43 21 0 0 ，0 1 882 43 21 0 0 o 1 9 8 2 4 3 28 7 5 0 2 01 12 53 67 2 7 2 2 1i i2 83 93 6 3 6 2 21 53 75 25 3 3 3 2 3 2 2 4 56 75 4 。5 4 2 4 2 34 66 95 6 5 2 2 52 54 57 06 8 0 0 宋南大学硕士学位论文 第五章数值结果及分析 2 2 5 2 投影主元标单纯形算法的数值试验 本节试验所涉及的五个算法均在两阶段框架下实现，我们编制了如下五个标 准f o r t r a n 7 7 程序： b l s ： b l a n d 单纯形算法4 2 1 ； p p s ： 投影主元标单纯形算法4 2 2 ； r p p s l ：修正投影主元标单纯形算法4 2 3 ； d u a l p ：对偶主元标单纯形算法4 2 4 ； r p p s 2 ：修正投影主元标单纯形算法4 2 5 试验问题将分为两组：第一组包含随意搜集的3 0 个小问题；第二组包含前十 二个标准n e t l i b 问题( 按照m + n 从小到大的顺序) 1 ，我们将在本节报告数值结果 并进行讨论和分析 5 2 13 0 个小问题的数值结果 该组有3 0 个小问题( 其中问题3 是经典单纯形算法的一个循环例子f 7 】) 由于 试验的问题较多而规模较小，故我们未单列一二阶段的迭代次数，只列出了两阶 段所需总迭代次数，详细结果见表5 3 各算法的迭代次数按照从大到小顺序排列为z b l s ( 7 6 4 ) d u a l p ( 6 7 9 ) p p s ( 6 5 5 ) r p p s l ( 5 6 5 ) r p p s 2 ( 5 6 4 ) 若以b l s 的迭代次数作为分子，其它算法的迭代次数作为分母，则比值分别为； 筹乩圮耻篇乩s s ，r 3 = 百笛乩地r 4 = 篇：乩s s 由此可以看出，b l a n d 规则单纯形算法的总迭代次数最多，对偶主元标单纯形算法 的迭代次数次之，而投影主元标单纯形算法最少 5 2 21 2 个标准n e t l i b 问题的数值结果 由于此组问题规模相对较大，我们还分别列出了其一、二阶段的迭代次数， 详细结果见表5 4 、5 5 、5 6 、5 7 、5 8 、5 9 1 h t t p ：w w w n e t l i b o r g l p d a t a 奎曼奎耋塑圭兰堡篁塞叁圣塞墼堡竺墨垦坌堑 2 3 问题 n m + nb l sp p sr p p s ld u a l pr p p s 2 l 281 0 44444 2371 06761 06 3371 077796 4 3 7 1 0 66687 5381 167676 6571 256666 7 3 91 2 5 7565 8481 287968 931 11 41 41 4969 1 0591 481 071 07 1 l41 11 51 1871 77 1 251 01 571 181 18 1 3791 645344 1 461 42 01 31 691 61 0 1 561 52 11 61 31 01 51 0 1 612 12 274363 1 781 42 21 21 l1 01 28 1 881 42 21 1879 7 1 971 52 21 41 52 01 41 8 2 01 01 32 389989 2 1 8 2 4 3 2 3 02 21 13 11 2 2 2 8 2 4 3 22 21 81 0 2 41 0 2 382 43 22 9 2 2 1 13 21 2 2 41 1 2 5 3 62 81 91 42 31 4 2 5 1 12 83 93 5 5 65 9 3 7 5 9 2 6 1 53 75 28 6 6 44 0 2 9 4 0 2 7 2 54 57 0 8 17 96 78 16 7 2 8 2 54 5 7 01 0 2 9 55 7 1 0 45 7 2 92 4 4 87 2 1 0 66 07 88 2 7 8 3 0 2 54 87 3 7 3 4 56 7 5 26 7 t o t a l2 5 6 5 6 58 2 l7 6 46 5 55 6 56 7 95 6 4 东南大学硕士学位论文 第五章数值结果及分析 在n e t l i b 问题中，我们先看一阶段各个算法的迭代次数，按照从大到小排列 它们的顺序为： b l s ( 3 5 8 4 ) p p s ( 3 3 6 1 ) r p p s l ( 2 6 0 3 ) r p p s 2 ( 2 5 2 8 ) d u a l p ( 2 1 3 8 ) 第二阶段各个算法的迭代次数也按照从大到小排列顺序为t d u a l p ( 2 2 7 8 ) b l s ( 1 4 1 1 ) p p s ( 1 2 3 4 ) r p p s 2 ( 1 2 2 4 ) r p p s l ( 1 1 5 9 ) 它们所需总迭代次数的排列顺序是： b l s ( 4 9 9 5 ) p p s ( 4 5 9 5 ) d u a l p ( 4 4 1 6 ) r p p s l ( 3 7 6 2 ) r p p s 2 ( 3 7 5 2 ) 可以看出，无论一阶段还是二阶段，投影主元标算法的求解效率均超过b l a n d 算 法在总的迭代次数上，对偶主元标虽比b l a n d 规则少，但仍比修正投影主元标算 法多 对于这组问题，以b l s 的迭代次数为分子以其它算法的迭代次数为分母，则 有以下比值： m = 篙乩吣威= 篇“s z ，国= 盎= l 域r 4 = 篇= 1 3 3 这几个比值和小问题测试结果相容，从而表明了投影主元标单纯形算法的有 效性 5 ，2 3 结论 从上面两组问题来看，在本文所测试的三个有限规则中，b l a n d 规则求解效率 最低，对偶主元标次之，投影主元标效果最好 在五个单纯形算法变种中，算法4 2 3 和算法4 2 5 的表现效果最好，它们都实 现了我们对投影主元标算法4 2 2 的修正效果需要指出的是算法4 25 是基于主元 标几何意义对算法4 2 3 实行的进一步修正，但它们两者的计算效果相当，并没有 实现我们的预期目标，其中原因也许有以下两个： ( 1 ) 最小比集合中元素较少甚或一个，选择出基变量的范围很窄，使得规则 4 1 2 和规则4 1 1 相当； ( 2 ) 我们的主元标并不能百分之百地刻划出最优基，这样有时候会适得其反 塞! 查堂堡圭兰堡垒塞塞三塞墼堡竺墨墨坌堑 2 5 问题m m + ni t e r s li t e r s 2i t e r s l + i t e r s 2 12 73 25 94 95 5 4 25 04 89 85 2l5 3 35 0 4 89 8 5 115 8 4 5 69 71 5 35 8 11 6 6 7 4 7 57 48 31 5 7 69 6 7 9 1 7 54 1 01 2 95 3 9 7 1 0 51 0 32 0 8 1 7 811 7 9 81 1 7l l l2 2 83 4 81 3 94 8 7 9 1 2 9 1 4 01 6 92 8 41 4 44 2 8 1 0 1 7 41 4 23 1 64 0 3 4 7 98 8 2 1 11 1 72 2 53 4 28 5 33 4 5 1 1 9 8 1 22 0 52 0 34 0 83 6 913 7 0 问题 nm + ni t e r s l i t e r s 2 i t e r s l + i t e r s 2 12 73 25 96 036 3 25 0 4 8 9 85 51 26 7 3 5 04 89 8 5 61 57 1 45 69 71 5 34 7 88 7 5 6 5 57 48 31 5 7 69 6 7 9 1 7 53 9 93 94 3 8 7 1 0 51 0 32 0 81 1 2 4 91 6 1 81 1 71 1 12 2 81 5 22 51 7 7 91 2 91 4 01 3 1 21 0 34 1 5 1 01 7 41 4 23 1 67 7 23 5 21 1 2 4 1 1 1 1 72 2 5 3 4 27 4 1 3 1 51 0 5 6 1 22 0 52 0 34 0 8 2 2 42 3 4 4 5 8 东南大学硕士学位论文第五章数值结果及分析 2 6 问题m + n i t e r s li t e r s 2i t e r s l + i t e r s 2 1 2 73 25 95 2 4 5 6 2 5 04 89 86 5 5 7 0 3 5 04 89 87 61 8 9 4 45 69 71 5 34 2 61 0 7 5 3 3 57 48 31 5 7 69 67 91 7 52 1 482 2 2 71 0 51 0 32 0 81 3 93 41 7 3 8 1 1 71 1 1 2 2 82 5 11 62 6 7 91 2 91 4 01 6 92 1 67 42 9 0 1 01 7 41 4 23 1 65 0 44 9 59 9 9 1 11 1 72 2 53 4 24 0 42 2 26 2 6 1 22 0 52 0 34 0 82 5 61 7 64 3 2 问题m + n i t e r s li t e r s 2 i t e r s l + i t e r s 2 12 73 25 93 384 1 25 04 89 85 11 36 4 35 04 89 84 51 86 3 4 5 69 71 5 38 44 9 55 7 9 57 48 31 5 7 69 67 91 7 52 5 31 1 8 3 7 1 71 0 51 0 32 0 81 1 55 61 7 1 81 1 71 1 12 2 82 5 01 2 63 7 6 91 2 91 4 01 6 92 3 79 53 3 2 1 01 7 41 4 23 1 63 6 45 4 2 9 0 6 l l1 1 72 2 53 4 24 8 25 7 31 0 5 5 1 22 0 52 0 34 0 82 2 42 3 44 5 8 问题 m + ni t mi t 堙i t r - , l + i t 业 12 73 25 95 2 4 5 6 25 04 89 86 557 0 3 5 04 8 9 8 7 61 89 4 45 69 71 5 3 4 2 6 1 0 7 5 3 3 57 48 31 5 7 69 67 9 1 7 52 1 482 2 2 71 0 51 0 32 0 8 1 2 5 5 9 1 8 4 81 1 71 1 12 2 82 0 91 72 2 6 91 2 91 4 0