（运筹学与控制论专业论文）亏基最陡边单纯形算法.pdf

摘要 邵 曩s 6 0 3 s s 二十世纪六十年代出现的最陡边单纯形算浚与原始单纯形算法及其变种相比，迭代次 数较少，但是由于每次迭代申都港要耗费大爨的计算，因此农计算实践中没有被广泛应用 1 9 7 7 年，d 幻影a r b 秘r e i d 拦文 1 1 给出了边方向的迭代公式，从而简化了原来的算法，并 褥到了鬟弱的最陡边算法，随后f “r r e s t 和g o l 影a r b 在大规模稀疏阉题上对该算法进行了 数篡试验，其结果发表在1 9 9 2 年的文 2 1 中数值结果袭盟，该算法饯于其它嗣类的单纯 形算法，并且靼当懿最好的内点法不担上下 1 9 9 7 年，溪平鸯教授提出了亏熬的概念( ( 2 剐) ，憋基载概念攮广荟q 一般j 漪形，扶妪蠖荨导 单纯形葵法有了瑟的架槐。在热架梅下褥到的亏基算法胃以降低退化理象鲍影魄，并在计 算时阕零瑟迭代次数方嚣蠢嚷显静改替。该算法罴单缝影算法豹攘广秘擐疑 为了能够更好蟪求解线性款赵耀题，并对单纯形理论专进一步越发展；本文将这鼹秽 算法撩结合，探讨最陡逮选主元毵捌在亏基算法中黪可行憾，德到了亏莲意义下豹边方囱 递攥公式，及露成功建将最蕤逮理论应耀刭亏基中来。| 囊赢对褥到瓣亏墓最陡逸算法遴行 数德试验数餐结采表箍，新葵法农迭代次数上傀予传统懿单纯彩算法 关键词：线性规划，攀纯彤，亏基，爨陡边，遐化，主元规则 a b s t r a c t i th a sb e e nk n o w ns i n c et h ee a ! - l ye x p e r i m e n t so fk u h na n dq u a n d ta n dw o l f ea n dc u t l e r ( 1 9 6 3 ) t h a t ，i ng e n e r a l ，t i ms t e e p e s t e d g es i m p l e xa l g o r i t h mt a k e sf e w e ri t e r a t i o n st h a no t h e r v a r i a n t so ft h ep r i m ms i m p l e xm e t h o d h o w e v e r ，b e c a u s eas t r a i g h t f o r w a r di m p l e m e n t a t i o no ft h e s t e e p e s t - e d g ea l g o r i t h mr e q u i r e sa ne x c e s s i v ea l n o u n to ft i m ef o re a c hi t e r a t i o n ，t h ea l g o r i t h mw a s i n i t i a l l yr e j e c t e da si m p r a c t i c a l 。t h ef i r s tp r a c t i c a ls t e e p e s t - e d g et y p es i m p l e x l g o r r h mw a s ( 1 e v i s e db yh a r r i si n1 9 7 3 h o w e v e r ，h a r r i s a l g o r i t h mi s a p p r o x i m a t e l ys t e e p e s t ，a n di tw a sn o tu n t i l t h ep u b l i c a t i o no ft h ep a p e r 1 ( g o l d f a r ba n dr e i d ，1 9 7 7 ) t h a tt h ef i r s t p r a c t i c a l e x a c t ) s t e e p e s t e d g ea l g o r i t h mw a sd e s c r i b e d i n1 9 9 2 ，f o r r e s ta n dg o l d f a r bp u b l i s h e dt h e i rc o m p u t a t i o n a l r e s u l t s ( 离) w h i c hd e m o n s t r a t et h er e m a r k a b l ee f f i c i e n c yo fu s i n gs t e e p e s t - e d g es i m p l e xa l g o r i t h m w i t has e to fr e c u r r e n c ef o r m u l a s t h e r ei sa ni n t e n s ec o m p e t i t i o ng o i n go nb e t w e e ns i m p l e xa n d i n t e r i o r - p o i n ta l g o r i t h m s 。i ti sh o w e v e rm f i i k e l yt od e c l a r eaw i n n e r + o nt h eo t h e rh a n d ，i n1 9 9 7 ，p r o f e s s o rp i n g q ip a ng e n e r a l i z e dt h eb a s i st oa l l o wad e f i c i e n t c a s e ( 2 5 d 。c h a r a c t e r i z e da so n et h a th a sc o l u m n s f e w e rt h a nr o w 8o ft h ec o e f f i c i e n tm a t r i xa n di t s r a n g es p a c ei n c l u d e st h er i g h t h a n ds i d e t h e r e b y , h ee s t a b l i s h e dav a r i a n to ft h es i m p l e xm e t h o d b a s e do i ls u c hag e n e r a l i z e db a s i sf 1 4 l o t so fw o r kh a v eb e e nd o n es i n c et h e na n dc o m p u t a t i o n a l r e s u l t sw e r ev e r ye n c o u r a g i n g i ti s c l e a r l ya t t r a c t i v e t oc o m b i n et h es t e e p e s t e d g er u l e 、w h i c hp e r f o r m se f f e c t i v e l yi n 涵e c o n v e n t i o n a lc o n t e x t ，w i t ht h eb a s i s d e f i c i e n c y a l l o w i n gv a r i a t i o no f s i m p l e xm e t h o d t ot os o ，w e e s t a b l i s hn e wr e c u r r e n c ef o r m u l a sf o rt h ed e f i c i e n t 。b a s i sc a s e 。a n dd e s c r i b ean e w b a s i s d e f i c i e n c y - n l o w i n ga l g o r i t h m o u rc o m p u t a t i o n a lr e s u l t sw i t h o u te x p l o i t i n gs p a r s es t r u c t u r es h o wt h a tt h e p r o p o s e da l g o r i t h mo u t p e r f o r m st h ec o n v e n t i o n a lo n ei nt e r m so fi t e r a t i o nc o u n t s ，b u tn o ti n r u n n i n gt i m e p u r t h c ri n v e s t i g a t i o n sa r ee x p e c t e d k e y w o r d s ：l i n e a rp r o g r a m m i n g ，s i m p l e xm e t h o d ，b a s i sd e f i c i e n c y , s t e e p e s te d g e ，d e g e n e t a c y p i v o tl a l e 东南大学学位论文独创性声明及使用授权的说明 、学像论文独蜘性声黼 本人声躜所呈交的学位论文是我拿人在导薅指导下进行的研究工作及取 荨的掰究成 果。尽我所知，除了文中特别加以标注和致澍的地方外，论文中不包含其他人已经发表或 撰写过豹研炎成暴，也不包禽为获薅东南大学或其它教育枧橡载学位或_ i 芷书嚣使尾过豹材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并寝示了 谢意+ 、 签名日期：鲤墨：! l 二、关于学位论文使用授权的说明 东南大攀、中酗释学技术信息研究所、搿家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和 纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被凌阅和借阍，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东随大学硪宠生院办理。 签名：严魄导师签名：囊整壹日期：馥啦一 第一章绪论 1 1 综述 线性规划作为运筹学的一个重要分支，在社会生产、科学研究等许多领域有着广泛的 应用，如著名华裔运筹学家于刚教授和他带领的团队所获得的当民航班机受到各种干扰之 后如何以最快的时间和最佳的组合来恢复航班的运营的研究成果，仅在2 0 0 1 年就为美国大 陆航空公司创造了超过6 0 0 0 万美元的实际价值而获取这一成果的研究过程中，就涉及到 变量达千万的大规模稀疏线性规划问题因此，我们研究的此类模型的求解方法有重大的 理论意义和现实意义该方向的研究成果和进展一直受到社会各界的关注 线性规划发展至今已有半个多世纪的历史1 9 4 7 年，g b d a n t z i g 开创性地提出的单 纯形算法，标志着线性规划这一学科的的创立( 【3 卜 6 ) 随后，世界各地出现了研究单纯形 算法一一主元算法的热潮1 9 7 9 年，数学家哈奇扬提出了第一个多项式时间的求解线性规 划问题的的算法( 7 ) ，虽然它具有很重要的理论价值，但该算法在实践中的数值效果并不理 想1 9 8 4 年，k a r m a r k 提出了一种新的多项式时间算法( 【8 】) ，该算法在大型稀疏问题上数 值效果比传统的单纯形方法好，从而在国际上掀起了内点法的研究热潮然而，主元算法 的研究仍未停止，而且还取得了长足的进展( 1 3 卜 4 1 】) 主元算法的关键之一是如何确定一个适当的主元规则关于这一方面的研究，自g b d a n t z i g 提出单纯形算法以来，便引起了大量的专家、学者的关注经过半个多世纪的发展，其理 论日臻完善其中，g b d a n t z i 9 提出的最负检验数规则( 3 卜 6 】) 因其简单、易于理解， 而广泛出现于当前有关线性规划内容的各种教科书中，我们称之为传统规则；1 9 7 5 年， h a r r i s ( 9 ) 给出了一种新的主元规则，该规则容许变量在一定范围内不可行，由此增加了主 元的选择范围，并在数值稳定性上取得很好的效果另外，文 1 0 1 1 】对gbd a n t z i g 提出 的按最大改进选主元的想法进行了深入的探讨，表明该规则在计算试验中效果不佳；1 9 7 7 年，g o l d y a r b 和r e i d 导出了边方向的递推公式得到了实用的最陡边单纯形莽法，从 而使最陡边主元规则被人们关注1 9 9 2 年，f o r 7 、e s t 和g o l 彤n 而( 2 ) 报告了在大型稀疏问 题上对此算法进行数值试验的结果结果表明该算法与现今较为热门的内点法相比不相上 下，被认为是最好的主元算法另外，在对退化现象的处理上，随着主元算法研究的深入， 也取得可喜的进展，在理沦上椰实践上有效的处理方法有字典序法、b l a n d 规则、摄动法 ( 2 7 3 11 - 1 3 7 ) 等 1 东南大学硕士毕业论文 2 特别值得关注的是，在1 9 9 7 午，潘平奇教授创造性地提出了亏基的思想【2 5 ，推广了基 的概念，为主元算法的进一步发展注入了新的动力，提供了新的可能由于亏基的应用， 使我们在解线性规划问题时，可以降低退化现象的影响，从而在迭代次数和计算时间方面 有明显的改善数值试验表明，在亏基构架下给出的亏基单纯形算法优于同类传统主元算 法 本文所做的工作是，在亏基这一新的构架下，采用当前数值效果最好的主元规则一 最陡边规则，得到新的单纯形算法：亏基最陡边单纯形算法本文中，我们在亏基的架构下 推导出了边方向的递推公式，从而使最陡边主元规则在亏基下实用可行随后，我们对得 出的新算法进行了数值试验数值结果表明，新算法在迭代次数上优于传统单纯形算法 本文的内容安排如下：在本节综述之后，我们引入一些常用记号，随后，简要叙述了 单纯形理论的基本概念与定理；第二章，我们将介绍亏基的概念及其算法；然后，在第三 章中，我们推导出了亏基架构下的最陡边规则的边方向的迭代公式并给出相应的亏基最陡 边算法；在最后一章里，我们将给出该算法的数值结果以及与传统单纯形算法的比较和分 析 1 2 符号表示与说明 在下面的叙述中，为方便起见，我们将引入以下的符号和记法如果不特别声明，则以 下面为准 f l 虢f 1 矩阵 列向量 4 的第j 列； 第i 个元素为1 的单位向量 向量的第j 个元素； 向量的2 范数； 矩阵的乘空间； 单位矩阵； 用大写的英文字母a ，b ，m 等表示 用小写的英文字母a , b c 表示 东南大学硕士毕 业论文3 1 3 基本概念和定理 单纯形算法的主要思想是，先找一个基本可行解，判定其是否为最优解如果不是，就 找另一个基本可行解，再进行判定如此迭代进行，直至找到最优解，或判定其是无界从 几何意义上来说，线性规划的所有可行点构成一个多胞形单纯形算法就是从多胞形的某 一个顶点出发，沿着下降( 上升) 边的方向到达相邻的另一个顶点就这样迭代下去，直到 得到最优值为止其中，边方向( 搜索方向) 的确定也即主元规则的选取是算法中最关键的 环节好的主元规则可以减少退化，以较少的迭代次数和运算时间便可达到最优；反之， 则有可能造成算法长期在某一个顶点处停滞不前，使算法的效率大大降低，最终影响算法 的效果但究竟如何判断是否是最优解、无界，怎样进行迭代、判定，则需要相应的理论和 方法，下面我们介绍这些基本理论及相关概念 我们要考虑是标准的线性规划( 三p ) 问题： r a i n ，= c t ( 1 1 a ) s t a x = bf ll z 0( 11 c ) 其中a r “，c r “，。r ”，b r ”，= ，。称为目标函数，式( 1 1 6 ) ，( 1 1 c ) 称为该线性规 划问题的约束条件 定义1 1 设b 为矩阵a 中的一个m 阶满秩方阵，则称b 为一个基( b a s i s ) ；b 中m 个线性无 关的列向量称为基向量( b a s i sv e c t o r ) ；z 中与之对应的m 个分量称为基变量( b a s i cv a r i a b l e ) 其余的变量称为非基变量令所有的非基变量取值为零，得到的解z ： z = = 0 ) 称为相应于b 的基本解( b a s i cs o l u t i o n ) 定义l2 若基本解满足z 0 ，即其也是可行解，则称。为基本可行解( b a s i cf e a s i b l rs o l u t i z ) 这时对应的基b 称勾可行基( f e a s i b l eb a s i 。s ) 定义1 3 一个基本叮行解z ，如果其所有的基变量都取正值，则称之勾l 退化的( n o ? 。d e 9 一”叭e ， 反之，如果有的罄变! 也取零值，则说其是退化的( 如g e n e r a t e ) 零鸯太举臻擎监论文 4 定义1 4 ，一个基本可行解，如果满足式( 1 1 n ) ，则称之为上p 问题的最优解；相应的目标 函数德，z 称为三p 阔瑟的鬣落值， 对于蘩、基奉簿、基本可行簿等瓣念之越懿关系，我豹煮下垂魏嫠搴理论 定理1 1 可行饵z 魁基本可行解的充分必要条件是骐正分墩所对应的列向量线性无关 定璃1 2 若个标椎的l p 的阿题肖可行解，则其必宥基本可行解 定璎1 3 ，著幸撂滤静l p 溺题的器添番数有有瀑最谯僮，瓣峦哥谯蔡令基本可蠢鬃处这 丘面的定理说嘲对于标准的l p 问题，著其存在有限最优值，则貔们可蛾在基本可行 薅熬鬃会孛寻控。然薅当短静静刭数n 艰大是，基本_ 霹行瓣敬个数矬：较丈，戏们采娜单纯 形法依照一定的规则在基本可行解的一个子集中寻找下面介绍单纯形法的桶关理论 俊设我 f l 找到了一个基本_ 嚣暂躲： z = ( 冀) 对墩的基短黪为b ，非基短阵为n ，c t = 娣，嗡t 则式( 1 1 5 ) 化为： x b 十b 一1 n ：r , n = b ”1 b ( 1 2 ) 不妨设b = 国i ，a m ) 记向餐 毛群8 1 弼端尊i j ，秀哑3 ，j = 1 ，z ，健 5 一磬1 b = ( 5 1 ，- ，5 。) 以及 则式( 1 2 ) 化为： 。口手弓一5 蓑 _ 口+ n x n = bf 【3 1 东南大学硕士毕业论文 5 目标函数化为： 令白= c 丢弓一q ，j = 1 ( t = c 暑口a 一商= ( e h ，厶) = ( 函靠) = ( o ，n t b 刁c 日一礤) 标准工p 问题化为： m i n f = c ；b1 b 一r z _ s t 。口+ b n x = b 一1 b z 0 定理1 4 如果式( 1 4 a ) 中e 0 ，则。为原问题的最优解 f l4 a 1 ( 1 4 b ) f 1 4 c 、 定理1 5 如果式( 1 4 a ) 中向量e 有分量靠 o ( 显然m + i k ) 】而向量6 女s0 ，则原问 题无界 定理1 6 如果式( 14 a ) 中向量( 有分量矗 0 ，且砜至少有一个正分量，则能找到基本可 行解童，使c 【)f n f 22 a f 22 b f 22r 东南大学硕士毕业论文8 n 。b ) 。， 二心引 江a ， 东南丈学碾毕业论文 9 因此o 0 的条件下成立 增长戮a 时，英它菲基交量的篷不变，秘然为零 零，从而得到下面的基本可行解的选代公式： f 27 1 ( 2 8 ) 因此，在非邋化假设下，当2 虬的德从零 根据灏始可行蛙，出基变量豹值降为 “：= 雪 一。甜z ，v i = 1 ，。，s ； 峦：= ( 2 9 ) 关于基短阵的改变，那是将典范表的第p 列 出基列) 放到非基列的最后刿，相应她调 整指标集合、，聍，如对于进基列的放溉，我们分两种情况讨论：若p = s ，这时的u r m x ( s 一1 ) 已是上三角的；嚣当p s 时，u 为上h e s s e n b e r g 短肄，其p 列到s 一1 列的次对角元非 零对后一种情况不需要的元零化然后，( 2 4 ) 的第q 列被放到基列的最后一列，相应 建调整西，如，易涯新进基列向量的第# 个分量菲零因此，这对豹，r m 一，或矾嚣s 一 又是上三角的且对角线元非零 情影2 ：若s ”z 且i t 。盼第s + 1 到第，n 个分量是；# 零的这时当豆仅当i g 尉，) 即2 不在基矩阵u 的乘空间中，在这样的情况f ，进基变墩2 k 的值不能从零增加，否 瓣这将违蜚后m s 个约束中馥菜些约寒。因此，必须增加基矩箨的剜数，设s s + l ：涛 向量6 的第s + l 到第r n 个分量化为零，若这些分铤存在的话；然后，将篇q 列( 谶基列 淘量) 放在基矩薄酌最后一列f 第s 列) 潺整指标集合，珐，妇显然，这时u 鬣n s 为上三 角的盛对角元非零 查直太一堂 亟一主 望 ! 鲨塞一 1 0 由上面时论的两种情形，我们可以看到，基矩阵的列数在情形l 中不变，而在情形2 中增加1 列，因此相应的迭代我们分别称之为满迭代和秩增迭代我们将以上的讨论归起 来，得到算法如下： 算法1 亏基单纯形算法 假设( 24 ) 是初始正则表，如，如分别是相应的指标集合，由( 2 5 ) 给定基本可行解i 1 如果z _ 0 算法终止 2 由式( 2 6 ) 确定出基列q 3 如果s m 且i k 。的第8 + 1 到第m 个分量有非零，执行下面的步骤： ( i ) 令8 = s + l ； ( i i ) 确定行指标r 使之满足| | a r , k 。1 1 = m a x l l 西，k 。川i = 1 ，一，m ，； ( 猁) 当r 8 时，交换第r 行和第s 行； ( i v ) 利用变换将i k 。的第s + 1 到第m 个分量中的非零分量化为零； ( ”) 转步骤1 0 4 计算由式( 2 1 7 ) 定义的向量v 5 如果v 0 则算法终止 6 利用式( 2 8 ) 确定行指标p 和步长“ 7 ，利用( 2 9 ) 迭代解互 8 将表中的第p 个基本列放到非基部分的最后，同时相应地调整指标集合如，j v 9 如果p s ) ( q 的第i 列) 由著名的s e r m 。n m 0 r v i s o a 公式【4 3 l ，我们得： ( m 4 - e q e p - - e q ) t ) 1 = 掰一l i m 、- 丽i e g ( - i e 呱q ) t m - 1 = 掰一l 一! ! 二星! ；学 即 p 府“a = m 。一丝二芝拌二 东南大学硕 士 鬟塑造塞 嘶。1 = 畿 p 冉才一1 e a 黧；：；：i ( ，河一1 e 。= 亓a ) p 铂2 巍 ( 3 9 ) p ( j l - l q p q e i = m 一m - 骊l e q e t 忑m - - t e i p 维2 啦一罢( 嘞) ( 3 埘 定义啦一一g 壤，橇= 爨 则( 3 9 ) 年h ( 3 1 0 ) 化为； p 璐= 一警 ( 3 竭 p 哦= 啦一塞，( g ) ( 3 1 2 ) ( 3 1 1 ) 和( 3 1 2 ) 便是我们所得的柱满迭代时边方向递推公式，根据这两个公式，我们可 泓镘囊接邈知道嚣步耱邻迭代懿相对应数下漆边之翘购关系，瑟不必要剩薅必它豹方式花 费更多的计算量得到它们 揍影2 ：簧s m 璺譬嚣雪) 这蒌雩，鑫戆筹$ + 1 至m 令分熬孛含有# 零分鬃，郅 i 女。不在基矩阵的乘空间中因此，谯这种情形下，只有6 避基，无出基列，即进行秩增 透饯这露鏊裂壶s 确变为$ + 1 列st - s + 1 ) ，我嬲将遴基麓a 。敦爨基矩黪孛懿最后一 列利用矩阵变换将6 k 的第s + 1 到r n 个分量化为攀( 若存在非零分量的话) ，相应的变换 记为q ( 显然，q 哭对堍懿露m s 嚣超傺爝) 。q 静形式应彤磐： q = 0 ) 且盆应瓣是： 眠。2 圹曲) 东齑太学疆士毕韭论文 记 下面我们考虑这样一个过程中边方向的变化规律 卜嚣t 炳 驴i ，广5 2 贸l 增秩后的基为 其逆为 增秩后边方向的变化 i = s + 1 ，缸g ) “趣1 4 鲰2i i ，i s + 1 。川0 g ) k 豆l ：卜扎 l0 如 犁：f 贯 0 一一雪f 一觑 穰= 、， 0 旦l 二监 0 曲 一宇h 旷) 几= ( 8 l ，8 2 ，e s ) 1 则疋m 表示向量吼的前s 个分量组成的子向量 8 i l i k ? = 渤t bi a = ， 、；， n f s 舐 ； _ o 第 b：“ ，。，。 弧 耳， 町o ，f；，、 j 也 一。 一l 一日 及以 争 = 等 s r l q 一厶吼 一且 f 口 o 1 7 ( 3 1 3 ) i = s + 1 ，n 且 q 因此我们得到在增秩情况下的边方向递推公式( 31 3 ) 总结上面的推导过程及结果，我们归纳得到下面的算法： 算法2 ：亏基最陡边单纯形算法 给定基本可行解2 ，如，j n 分别是相应的指标集合 1 ，如果z 0 算法终止 2 由式( 3 1 ) 确定进基变量的列指标q 3 如果s m 且i 的第s + 1 到第m 个分量有非零，执行下面的步骤： ( i ) 令s = s + l ； ( i ) 确定行指标r 使之满足 | a r , k 。i i = m a x f t l 砒， 。i = s ，m ) ； ) 当r 8 时，交换第r 行和第s 行； ( 如) 利用变换将i 。的第s + 1 到第m 个分量中的非零分量化为零； ( u ) 利用式( 3 2 ) 和( 3 1 3 ) 计算7 i ，i = s + 1 ，n 转步骤1 0 4 计算由式( 3 6 ) 定义的向量” 5 如果ws0 则算法终止 6 利用式( 3 7 ) 确定出基变量对应的行指标p 和步长n 7 利用( 3 8 ) 修正基本可行解i ，利用式( 3 2 ) 、( 31 1 ) 、( 31 2 ) 计算n ，z = s + 1 8 将表中的第p 个基本列放到非基部分的最后，同时相应地调整指标集合拈，“ 9 如果p s ，那么对 = p ，sl 执行下面的步骤： ( i ) 确定行指标r 使得l li 。“| | = - m 圳i 。，。i = k k + 1 ) ； 东南大学硕 士 学墅整塞 ( i i ) 当r 时，交换第r 行蟊繁k 行； ( i ) 利用变换将勘。的次对角元化为零 1 0 将表申豹第拿菲蕊列教裂蘩矩莓部分豹最后一列，耀e 亨相应逮谖整撂拣囊合 b 、3 w l l 。擎歪检验数蕊，j = s 十1 ，；+ 1 2 转步骤1 苒法2 璁- 分为增秩迭代和满秩遗代两个过程，只避在遥代时要考虑边方向这一圆索 因此落对其作与算法1 同样的假设，我们有与算法1 类似的定理： 定理31 如槊在所有的迭代中不存猩退化的情形，算法l 终止于下列情况之一： 1 ) 在步骤l 姿囊，嚣我秘已墨德羹最臻解； ( 2 ) 在步骤5 终止，即我们发现原问题是无界的 东露大学疆毕攮论文 3 3l u 分解的亏基最陡边单纯形算法 潘平奇教授在文 2 8 中，利用矩阵的l u 分解，将基矩阵分解为一个上三角阵u 与 令满袄短阵掰q 酶蒙积彩式，在遮代黪每一步，t 廷要瓣u ，m 遴费穗纛酶穆委，实臻了在亏 基构架下利用l u 分解的单纯形算法在这一节中，我们采用类似的处理方法，改进算法2 设f 岛，氟】为当游给定的基、j 蒺撂标集，z 为裙应懿麓本霹行解，稳应建l p 鬻题 ( 1 1 ) 的系数矩阵a 被分块为： 建= b ，n 】 其中b 为基矩阵，n 为菲基矩阵 若l t ，五2 、，l 。为高斯变换，舅，p 2 ，b 为置换矩阵使得： m b = u 其中m = l 。只三lp i ，u 为一个上三角矩阵 上面b 的分解形式被称为矩阵曰的l u 分解，m 和u 称为l u 因子，特别地，”m 黎为发因子 若我们已经确定进基列为a k 。，将其由j u 移到j b 的最后一列，设哆，嗣为将的第 g 刭渗蜀b 懿最后霹褥到豹影式，鄹么，显然雪= ，j 我嬲诗葵： v = m a k 。( 3 1 4 ) 若”的后m s 个分量有非零存在，则为亏基算法中的情形2 ，只有进基列( 增秩迭代) ， 这时。如遂基，将”瓣后m s 一1 令分量讫为零，穗瘦熬毫袋燮换为玩+ t 置换短薅为嚣强 则有 m = l s + 1 只+ i m 融强= 习 其中驴为一个上三南矩阵我们得到相应的递推公式： 东南大学硕 士 望些迨塞 l 。= e m a k 。 磊= z i 一芒钿 2 。= 0( 3 1 5 ) 唬= 氟一2 苦碍m 扎 i = s + 1 ，、n 若”的后m s 个分量全为零，则为亏基算法中的情形1 ，这时既要进基又要出基，假 定出基列为靠，将其由如移到如的最后一列，新的基矩阵雪为豆去掉第p 列后而得到 的原来l u 中相应的矩阵u 变为一个上h e s s e n b e r g 矩阵，我们将该矩阵的次对角线上的 非零元化为零，与之相应的高斯变换为l 州置换矩阵为只+ 1 ) 则有 m = l s + 1 只+ 1 m 嘲豆= 雹 其中驴为一个上三角矩阵 对于边范数，检验数的递推公式相应地作出调整 y 7 = ( 露7 e p ) 7 西= y 1a k 施= 施一o t z q r 。= a i r 目一2 面一+ r i i = 8 + 1 n 将上面的叙述归纳为下面的算法 ( 3 1 6 ) 算法3 ：利用l u 分解的亏基最陡边单纯形算法 给定初始基本可行解z ，初始基矩阵b ( 秩为s 0 其中a r m ”，c r ”，zer ”，b r ”为了得到上面问题的一个初始可行解， 人工变量z 。，然后构造下面的辅助线性规划问题： 对于该辅助问题我们有定理 s t a x + z ， + 1 b = b z 0 ，n + l 0 ( 1l b ) ( 1 1 c ) 我们引入一个 f 4 1 、 f 4 1 们 f 4 1 c ) 定理辅助问题有最优解，且最优值为非负的更进一步地，我们有问题( 1 1 ) 的可行域非 空当且仅当辅助问题的最优值为零 由上面的定理知，我们只要将辅助问题的最优解得出，则原问题的初始可行解也就得 到 r 我们将上一章中的算法简单修改得到最陡边一阶段算法，利用该算法可得辅助问题 的最优解其算法也可描述如下： 一蛊盟一 盔 一羔一熏 ：量璧娑迨 2 3 最陡边翘始可符鳏冀泌： 0 初始化：铷始鍪列为右端常数项列，弱始变量势人工变篷，分别求蹬翡基变量所对 应懿检验数魏逑方向蕊数鲍平方 1 检验最挽，若辨鹰检验数毪瓴疆褥型基本可行绥，算法终史。否裂羧行下涮步骧： 2 ，凋爆算法3 的攀2 步到辇5 步 定疆最陡边初始可行解算法终止于下面的两种情形之一： ( 1 ) 得到最优解，即取褥廉线一陡规触问题的基本可行解 ( 2 ) 该问题无界，即原线霞规划问题无解 4 2 数值缔果及分析 我# j 对得到豹耨算法遴行了数蓬试验其中，筏我编糍了瑗个翟露： c o d ec l s ( ac o n v e n t i o n a li m p l e m e n t a t i o no f t h es i m p l e xm e t h o d ) ) ：蒋统鲢嚣醅段萃缝黟 算渡； c o d ed s e l s ( a b a s i s - d e f i c i e n c y - a l l o w i n gv a r i a t i m lo f s i m p l e x m e t h o dw i t ht h es t e e p e s t 一砖g e r u l e ) ：亏基瀑淡违零纯影雾法f 蒺烈阵剃霆l u 努籍) 。 黻上穗序惩用标穗c 潜言编写的，并在w i n d o w sm e 操作系统上帮q 用m i c r o s o f tv i s u a l c 十+ f v e r s i o n6 0e n t e r p r i s ee d i t i o n ) 环境避行编译、调试数德试验所用的计算机为i b m p e n t i u mh i6 6 6 m h z 的兼容机，内存1 2 8 m b y t 船，机器精度为3 2 位所有的程序都以8 = 1 0 _ 6 为容限，都采用了h a r r i s 选主元规则( 9 1 ) ，并在h a r r i s 主元规则中取6 = 1 0 6 为了增加程 序的数值稳定性，这两个程序酃使用了均衡尺度( s c a l i n g ) 的技术计算运褥时问所用的工 具为v i s u a lc + 十的标礁痒晒数f t i m e ，以秒为单位，不包括数搌颓处理的时闻 这儿用于测试的试验数据有两组：一缀是我们平时检验算法款常用的6 0 个微小型问 题，这螳问题的规模( 行数与列数之和) 从5 到3 7 ，零元豢在数据中黪所船比例较少，是捌密 问题；第二组数据是来皂h t t p ：w w w ，n e t l i b o r g l p d a t a 的拯准l p 阅题，阀题她嫂模扶s 9 到7 7 7 ，零元素在数握中的数据中零元较多，为耩骧问题 袅1 为绘也了第一缠数据在两种算法下的数缝结果比较，包摇了联有阍题的规模( 舒 数、到数、行数与刊数之秘) 、在掰摊算法下妁二盼段的迭代次数、总越迭代次数，总的 运算时闽以及程两盼算法下的数傣结果浆比较( 一二阶段静迭代次数之比、惑昀迭代次数之 东南大学硕士毕业论文 2 4 汔、总溺运算时阕之毙) 表2 帮表3 分爨给出了两粹葵法鹤对第二缒数据迸嚣数毽试验的 数德结架，包捂每一个瓣题翡一二阶段黪迭代次数、总翡迭饯次数，一二除段戆运算糖陬 总黪运算时滔，表的最后一行还还给出了第二缝数据所有| 、瓣题戆一二除段懿选代次数、总 的遗代次数，一二阶段酌运算时阉、总的运算时离表4 给出了两稀算法程第二缝羧撂下 的结果的遗代次数的鲍较，包括闻遂静规禳、每个闻繇的遮代次数眈帮运算爵蔺跑、第二 组数据所有闻簌静迭代次数眈和运算时褥篦 由表1 的院较结果我们可醵看穗，新算法( d s e l s ) 在迭代次数上要优于算法( c l s ) ， 僵函为都疑较小问题，在运算时间上还看不出谁的优劣e 目表4 的比较结巢我们也得到与 表1 类似的结论，即新算法( d s e l s ) 与算法( c l s ) 相比，迭代次数较少；而在运算时间 上的比较上，我们也可以由表中可以看到，新算法( d s e l s ) 所掰的运算时间比算法( c l s ) 所孀的时间要多，在对第二组数值试验的结果中，新算法( d s e l s ) 的运算时间是5 6 0 3 0 s ， 而算法( c l s ) 仅用了2 1 2 0 0 s 时间 总的说来，由表l 和表4 的数值比较结果，我们可以看到亏基最陡边单纯形算法比传 统的表格原始两阶段单纯形算法需要较少的迭代次数，这是因为我们在算法中采用了最陡 边的选主元规则，每一次边方向的选择都最”最陡的”另外，我们还看到在袭1 中算法 ( c l s ) 与算法( d s e l s ) 总迭代次数之比值是1 1 8 8 ；而在表4 中，这一比值为1 2 6 6 ，比第 组数据要好也就是说，从迭代次数上讽算法( d s e l s ) 在6 0 个微小烈稠密问题上的效果 比不上中小型稀疏问题上的效果这是因为新算法( d s e l s ) 是在亏基这一构架下得出的， 根据亏基构架下的单纯形原理，对于稀疏问题，我们可以在基矩阵成为一个方阵之前便取 得原始可行或考原始最优这榉，算法可以花费较少的迭代次数求得了稀疏问题的解，但 在稠密问题中，大多数问题都在基成为方阵后才求褥问题的鼹 从迭代时间上来看，耨算法所花费的总运算时l 向要多于传统算法所用的时l 旬，我们可 以从表4 中看到这点，算法( c l s ) 与算法( d s e l s ) 总运算时间之比值为0 3 7 8 出现这 耪情况，我们可以从每一次迭代所嚣要的计算壁这角度进行分析： 新算法每一步都嚣娶计算所有非基边方向的范数虽然，我们推导出了在亏基构架下 边方向的迭代公式，但要真正在算法中实理每一一步为”最黪约”，还爨要相当大妁计算，这 些计算是”颧步卜”的，虽然，我们的瓤赞法所燃的迭 弋次数较少，健在这一郝分节约下寰 的时阕比不上每一次迭 弋对用于计赞珀0 羁寸阍主要妁愿溷是我钠在算法实璎的过程中，辑 栗熙熬数撂结构是蜓密形式约，也就是浇，数掇豹存德形式是我鲥通誊教辩书上静彤式， 东南大学硕 士毕业沦文 2 5 我们的数据虽然是稀疏的，但并没有利用数据形式是稀疏的这样一个结构优势，我们仍然 按照稠密形式处理：零元素参与运算，从而导致在每次迭代时，需要大量的时间进行读取、 存储数据，在向量之间、矩阵之间、向量与矩阵之间进行计算时，也同样需要大量的时问来 完成相应的操作 根据我们对数值试验结果的分析，算法( d s e l