（应用数学专业论文）线性规划主元算法研究.pdf

线性规划主元算法研究 博士生姓名t 李炜 ( 东南大学数学系 指导教师：潘平奇 南京，2 1 0 0 9 6 ) 摘要 g bd a n t z i g 干1 9 4 7 年开创的线性规划理论及其单纯形算法，是影响最深远和应用最广 泛的数学工具之一它在国民经济、科学技术、管理和工程等诸多领域有着广泛的应用在线 性规划诸算法中，gb d a n t z i g 的单纯形算法，k h a c h i y a n 的椭球算法以及k a r m a r k a r 的内 点算法可谓为三大里程碑本文的贡献主要在线性规划的主元算法这一领域，包括麒下内容： 一在潘平奇教授提出的亏基理论的框槊下，本文首次将亏基理论推广到带有界约束的 线性规划求解，建立r 有界变量单纯形算法的理论基础在亏基单纯形算法的基础上，进一步 提出了亏基有界变量线性规划单纯形算法，证明了算法的收敛性，并建立了一个相应的简清 的一阶段算法 _ _ - 在亏基概念及最钝角规则的基础上，本文和j 用最钝角法则，在亏基的框架下建立了 一个新的求原始可行解的一阶段单纯形算法由r 于基的引入，在很大的程度上克服了退化带 来的困难；而最钝角法则的应用，则使我们能每次简单地选取恰当的变量进基，从而使新算法 具有简单易行且计算量小的特点 三 c r i s s c r o s s 算法的主要优点是其简洁优美，它可从任一个基本解开始，仅用一个 阶段在有限步内就可求解一般线性规划问题，且求解的过程具有对称性但可惜其实际计算 效率不高本文提出一种新的有限的c r i s s c r o s s 算法，利用重排下标的技巧，一方面保持了 c r i s s - e r o s s 算法原有的优点，男一方面提高了汁算效率同时，新算法的有限性也得到了汪明 四线性规划的主元算法( 如单纯形算法) 最后可以到达一个精确的最优解，但在计算过 程中会受到退化现象的严重干扰内点法虽没有这个缺陷，但通常只能产生一个e 最优解要 获得精确最优解，必须要有一个计算域不小的所谓的纯化过程本文将内点算法与主元算法 的技巧有机的结合起来，建立了一个混台算法该算法具有两者的优点它不仅克服了退化现 象带来的困难，还可获得一对精确的原始与对偶的最优解 五潘乎奇教授提出的求解线性规蜘的射影单纯形算法，尽管在实践中非常有效，却仍 然没有完全摆脱由于退化而带来的停顿现象本文提出一个修正的射膨单纯形算法在确定搜 索疗向时，求解一个增广的最小r 二乘l 叫题，从而完全避免了退化的影响，在不做任何非退化假 设的前提下证明了算法的有限性 六本文就一些国内外学者所提出的线性规划新算法给出了若干反例 关键词：线性规划，主元算法，单纯形算法，内点算法，射彩单纯形算法， c r i s s c r o s s 算法，主元规则，亏基，遢化，最钝角法则 中图分类号：0 2 2 1 1 i i s t u d y o nt h ep i v o ta l g o r i t h m sf o rl i n e a r p r o g r a m m m g “h s u p e r v i s e db yp r o ( p a np i n g q i ( d e p a r t m e n to fm a t h e m a t i c s ，s o u t h e a s tu n i v e r s i t y ，n a n j i n g ，2 1 0 0 9 6 ) a b s t r a t l i n e a rp r o g r a m m i n ga n ds i m p l e xm e t h o d ，p r o p o s e db yg b d a n t z i g ，m i g h tb eo l l e o ft h em o s tp o w e r f u la n dw i d e l yu s e dm a t h e m a t i c a lt o o l si nn a t i o n a le c o n o m y ，n a t u r a l s c i e n c e ，t e c h n o l o g y ，m a n a g e m e n ta n de n g i n e e r i n g a m o n ga l l t h ea l g o r i t h m sf o rl i n e a r p r o g r a m m i n g ，s i m p l e xa l g o r i t h mp r o p o s e db ygb d a n t z i g ，k h a c i j a n se l l i p s o i dm e t h o d a n di n t e r i o rm e t h o d sd u et ok a r m a r k a r ，a r et h r e em i l e s t o n e si nt h el i n e a rp r o g r n i m i n g h i s t o r y t ou s et h et h e o r yo f t h ed e f i c i e n tb a s i sf o rt i l el i n e a rp r o g r a m m i n go ft h eg e n e r a lf o r m ， w ef i r s t g e n e r a l i z e dt h eb a s i st oi n c l u d et h ed e f i c i e n tc a s ef o rl i n e a rp r o g r a m m i n gw i t h b o u n dv a r i a b l e si nt h i sp a p e r t h e n ，w ep r o p o s e dav e r s i o no fb a s i sd e f i c i e n c ys i m p l e x m e t h o dw i t hb o u n dc o n s t r a i n t sa n dp r o v et h ec o n v e r g e n c eo ft h em e t h o d an e wp h a s e 一1 a p p r o a c hi se s t a b l i s h e dt os u p p l ya ni n i t i a l b a s i s b a s e do nt h et h e o r yo fd e f i c i e n tb a s i sa n dt h em o s t o b t u s e a n g l er u l e ，p r o p o s e db y p r o f e s s o rp a n ，w ee s t a b l i s han e wb a s i s d e f i c i e n c y a l l o w i n gp h a s e is i m p l e xm e d m d ， u s i n gt h es o - c a l l e dm o s t - o b t u s e a n g l ec o l u m np i v o tr u l et op r o d u c eap r i m a ld e f i c i e n to f f u l lb a s i s i to v e l 。c o r n et h ed i f f i c u l t ya r i s i n gf r o mt i l ed e g e n e r a c yt oag r e a te x t e n t ，s i n c ew e u s et h ed e f i c i e n tb a s i s o nt h eo t h e rh a n d ，w ec 8 i ic h o o s et h ee n t e r i n gv a r i a b l ec h e a p l yb y m o s t - o b t u s e a n g l er u l e ，t h u s ，t h en e wp h a s e ir e q u i r e sl e s sr u n n i n gt i m ea n di t e r a t i o n s o v e r a l lt h a nt h a tu s i n gt h et y p i c a lp h a s e 一1 t h em a i na d v a n t a g eo ft h ec r i s s 一( ：r o s sm e t h o d si st h e i rt h e i re l e g a n c ea n ds i m p l i c i t y t h e yc a ns t a r t f r o ma n yb a s i cs o l u t i o n ，a n ds o l v et h el i n e a rp r o g r a m m i n gw i t h i no n e p h a s e b u t ，t h em e t h o d sa r en o te f f i c i e n ti np r a c t i c e i nt h i sp a p e rw ed e v e l o pan e w v a r i a n to fc r i s s - c r o s sp i v o ta l g o r i t h mf o rl i n e a rp r o g r a m m i n gp r o b l e m t h en e wa l g o r i t h m i sa l s of i n i t ea n dh a st h es a m ea d v a n t a g eo fs i m p l i c i t y m o r e o v e r ，b yr e o r d e r i n gv a r i a b l e i n d e x ，t h i sn e we r i s s - c r o s sm e t h o da p p e a r st ob em o r ee f f i c i e n ti np r a c t i c e p i v o ta l g o r i t h m sf o rl i n e a rp r o g r a m m i n gs u f f e rf r o mp r o b l e m s e s p e c i a l l ys t a l l i n g a r i s i n gf r o md e g e n e r a c y ，i n t e r i o rp o i n tm e t h o d s ，a l t h o u g hn o ta f f e c t e db yd e g e n e r a c y , r e q u i r eap u r i f i c a t i o np r o c e d u r et oo b t a i na ne x a c to p t i m a ls o l u t i o n t h i sp a p e rd e r i v e s i i i an o v e lp r o j e c t i v es i m p l e xm e t h o dw i t ht h ep r o o ft h a ti t c o n v e r g e ss u c c e s s f u l l y t h en e w a l g o r i t h mc o m b i n e sp i v o ta n di n t e r i o rp o i n tt e c h n i q u e su a t u r a l l y ，a n da p p e a r st oh a v e a d v a n t a g e so fb o t ht y p e so fa l g o r i t h m s i ti si nf a c tn o to n l yr e d u c et h ep o s s i b i l i t yo f d i f f i c u l t ya r i s i n gf r o md e g e n e r a c y , b u ta l s or e a c hap a i ro fe x a c tp r i m a la n dd u a lo p t i m a l s o l u t i o n s p r o f e s s o rp a np r o p o s e dt h ep r o j e c t i v es i m p l e xm e t h o d r e c e n t l y t h ea l g o r i t h mh a n d i et h el i n e a rp r o g r a m m i n gp r o b l e m su n d e rt h ef r a m eo fd e f i c i e n tb a s i s a l t h o u g hi ti s v e r ye f f e c t i v ei np r a c t i c e ，h o w e v e r ，t h ea l g o r i t h mm a y s t a l lw h e nt h ep r i m a ld e g e n e r a t e o c c h ft h i sp a p e rp r e s e n t sam o d i f i e dp r o j e c t i v es i m p l e xm e t h o df o rl i n e a rp r o g r a m m i n g d e t e r i n i n i n g s e a r c hd i r e c t i o nb ys o l v i n gas e q u e n c eo fc o n s t r a i n e dl e a s ts q u a r e sp r o b l e m s ， t h en e wm e t h o di s i m p e r v i o u st op r i m a ld e g e n e r a c ya n dh e n c eh a v ea na d v a n t a g eo n d e g e n e r a t ep r o b l e m so v e rt h es i m p l e xa n dp r o j e c t i v es i m p l e xm e t h o d t h ef i n i t e n e s s i s p r o v e nu n d e rr i oa s s u m p t i o no fn o n d e g e n e r a c y a na s s o c i a t ep h a s e ii sa l s oe s t a b l i s h e d s o m ec o u n t e r e x a m p l e sa r eg i v e nt os h o wt h a ts o m ea l g o r i t h m sf o rl i n e a rp r o g r a m m i n ge s t a b l i s h e di nt h er e c e n ty e a r sa r en o tc o r r e c t k e y w o r d s ：l i n e a rp r o g r a m m i n g ，p i v o ta l g o r i t h m ，s i m p l e xa l g o i i t h m ，i n t e r i o i a l g o r i t h m ，p r o j e c t i v es i m p l e xa l g o r i t h m ，c r i s s c r o s sa l g o r i t h m ，p i v o tr u l e ，d e f i q c i e n 【_ b a s i s ，d e g e n e r a c y ，m o s t o b t u s e r u l e a m s ( 2 0 0 0 ) ：9 0 c 0 5 东南大学学位论文独创性声明 本人声明所呈交的学位沦文是我个人住导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文巾不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学l 电或证书而使用过的材料。与我 一f 叫工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 东南大学学位论文使用授权声明 东南夫学、巾国科学技术信息研究所、困家图节馆有权保留本人所送交学位论义的复印 件和电子文档，r 叮以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一敛。除在保密期内的侏密论文外，允许论文被查阅和借阅，可以公布( 包括 纠登) 论文的全部或部分内容。论文的公布( 包括f 登) 授权东南大学研究生院办理。 跹日期：晰 第一章绪论 1 1课题的来源及意义 线性规划是运筹学中产生较早一个分支早在1 9 3 9 年，俄国数学家康脱洛维奇在生 产组织与计划的数学方法一书中就提出并研究了一些特殊结构的线性规划问题4 5 1 1 9 4 7 年，g bd a n t i g 在文 2 0 ，2 1 】中提出了求解线性规划问题的单纯形算法，标志着线性规划这 一学科的创立随后，出现了非线性规划、参数规划、随机规划、模糊规划、不确定规划等领 域时至今日，线性规划已被广泛地用于工业、农业、商业、金融、管理、军事等各个领域并 获碍了辉煌的成就。如著名华裔运筹学家于刚教授和他带领的团队所获得的当民航班机受到 各种干扰之后如何以最快的时间和最佳的组合来恢复航班的运营的研究成果，仅在2 0 0 1 年就 为美国大陆航空公司创造了超过6 0 0 0 万美元的实际价值可以毫不夸张的说，线性规划的提 出与广泛应用，屉上世纪运筹学界最有意义的成就之一因此，如何提高线性规划问题的计算 效率，是一直受到国际运筹界广泛关注的且具有深远意义的问题 本文所研究的问题属于潘平奇教授主持的两项国家自然科学基金项目：大规模稀疏线性 规划投影主元算法的研究( 编号： l9971014 ) 及大规模稀疏线性规划主元内点算法的研 究( 编号：1 0 3 7 1 0 1 7 ) 的于课题主要对线性规划问题的若干新的主元算法以及与内点法相 结合的主元算法进行了探讨 1 2问题综述 在线性规划的发展史上，g b d a n t i g 的成果标志着的第一个里程碑g b d a a t z i g 不 仅提出了单纯形算法，他还系统的研究了线性规划的几何理论、对偶理论、典型实用问题及其 它有效的算法单纯形算法属于主元类算法正是由于主元类方法在求解实际问题时的高效 率，使得其逐渐成为求解线性规划问题的主要方法之一大量的专家学者在选主元规则、数值 稳定性、计算时间、计算量、初始可行基、减少或避免循环等方面作了深入的探讨 k l e e 和m i n t y1 5 3 l 于1 9 7 2 年首次构造出了这样的一类线性规划问题，若用d a n t z i g s 的最负检验数主元规则，则求解此类问题所需的迭代次数是指数阶的自此以后，对于其它主 元规则，需要指数次迭代才能求解的例子也被相继构造出来k l e e m i n t y 的例子激发了人们 探讨线性规划其它算法的热情一个长期困扰人们的问题是：是否存在求解线性规如的多项式 算法? 直至1 9 7 9 年，俄国数学家哈奇扬给出了这个问题的肯定答复 在非线性规划的椭球方法的基础上，啥奇扬提出了线性规划的椭球算法f 4 9 ，5 0 ，这个算 法是求解线性规划问题的第一个多项式时间复杂性的算法，也是一个内点算法椭球算法的 基本思想是：每次迭代给出一个包含所有最优解的椭球根据这个椭球的中心构造超平面，使 得所有最优解位该超平面的一侧而椭球的中心或严格地位于超平面的另一侧( 深切割) ，或 位于超平面之上( 中心切割) 然后在该超平面的适当的一侧构造一个包含所有最优懈的较小 新椭球重复以上过程直到求出最优解 椭球算法是线性规划理论上的一个重大进展然而，人们不久就发现它的实际计算效果不 】 2 奎查奎堂堡圭兰垒墼塞 理想在计算实践中，具有指数阶时间复杂性的单纯形算法的实际计算效率远运超过了具有多 项式时间复杂性的椭球算法这一理论与实践的矛盾促使人们认识到有必要从一个新的角度来 审视单纯形算法有必要估计线性规划单纯形算法的概率意义下的平均迭代次数b o r g w a r d t 1 1 2 ，1 3 1 指出：用单纯形算法求解对按一定的概率分布随机构造的线性规划问题，其时间复杂 性足多项式的1 9 9 9 年，b o r g w a r d tf 1 4 1 给出了总迭代次数的期望值为0 ( m 3 n 1 ，沏- 1 ) ) 内点法的复兴要归功于数学家k a r m a r k a r 1 9 8 4 年，k a r m a r k a r 4 6 提出了线性规划 问题的另一个多项式时间算法一k a r m a r k a r 算法该算法不仅具有多项式时间复杂性，而且 在大型稀疏问题上的数值效果超过了传统的单纯形方法国际上也因此再次引发了内点法的 研究热潮后来人们发现，早在1 9 6 7 年，康脱洛维奇的学生d i k i n 就提出并研究了此类算法 f 2 6 ，2 7 k a r l n a r k a r 算法的基本思想是：在每次迭代时，将一个内点解通过射影变换变为多 胞形的中心然后使它沿着最速下降方向移动，再作逆变换将改进的解映射回原来的解空间 中的一个新的内点重复以上过程直到得到满足精度要求的最优解g i l l ，m u r r a y ，s a u n d e r s 柳w r i g h tf 3 5 1 指出k a r m a r k a r 的搜索方向等价于每次迭代选取适当障碍参数的障碍函数法 的方向通过对内点法的深入研究，人们发现大多数内点法的搜索方向可统一为在适当的条 件下线性规划满足k k t 条件的解的n e w t o z l 方向f a 8 1 这使得内点法的研究进一步深入 自此，以k a r m a r k a r 算法为代表的内点法的出现打破了单纯形方法一统天下的格局 1 9 9 2 年，l u s t i g 等人的报告表明，m e h r o t a 提出的原始对偶预测校正内点法【6 0 j 在内点法中独 占璧头 在内点法的研究方兴未艾的同时，主元算法( 单纯形类方法) 的研究也取得了长足的进 展主元算法的关键之一是如何确定一个适当的主元规则，因为主元的选取是影响计算效率的 关键因素关于这一方面的研究，自g b d a n t z i g 提出单纯形算法以来，育受到人们的广 泛关注各种主元规则层出不穷，试图由此使主元算法得到根本性改进的努力从未间断例如 b l a n d h 1 的有限主元规则，g o l d f a r b 3 6 i 等的最陡边主元规则和t e r l a k y 8 7 j 等的c r i s s c r o s s 主元规则等等历经半个多世纪的发展，主元算法的理论日臻完善g b d a n t z i g 的传统的 最负检验数规则因其简单易于实现而被各神教科书广泛采用1 9 7 3 年，h a r t i s 4 0 i 给出了 一种新的主元规则，该规则容许变量在一定范围内不可行，由此增加了主元的选择范围，因之 在数值稳定性上取得很好的效果同时，j e r o s l o w 【4 4 】、k l e e 及m i n t y 【5 3 】对g b d a n t z i g 提出的按目标函数的最大改进选主元的想法进行了深入的探讨，表明该规则在计算试验中效 果不佳 1 9 7 7 年，g o l d f a r b 导出了边方向的迭代公式1 3 6 l ，提出了实用的最陡边单纯形算法从 而使最陡边主元规则受到了人们关注1 9 9 2 年，f o r r e s t 和g o h t f a r b 【2 9 】报告了最陡边单 纯形算法在求解大规模稀疏问题时的数值试验结果结果表明，该算法与现今实用的内点法 在计算效率方面不相上下，被认为是最好的主元算法之一目前，国际运筹界的共识是：主元 类算法与内点算法势均力敌主元类算法对中小型问题的计算效率优于内点算法，在优化后 分析方面有明显的优势，对某些大问题的计算更有效；而内点算法则对另外的一些大问题效 率更高1 9 0 ，9 l j 为了能够寻找线性规划问题更为有效的算法，十几年来，潘平奇教授在线性规划算法的理 论和计算方面以及相关领域进行了卓有成效的探索，得到了一系列有创造性的成果例如，基于 兰三萋量垒 3 对可行域几何特征的深入分析提出最优基的启发性特征刻划和相关的有限主元规则f 6 1 ，6 8 1 ， 其实际效果优于b l e n d 规则；所提出的二分单纯形算法1 6 2 ，6 7 、摄动单纯形算法f 7 2 ，7 4 1 等 等也受到学术界的关注和好评 尽管如上所述，主元算法是求解一般线性规划问题最有效的方法之一，但它的一个主要 不足是容易受到退化现象的严重影响传统单纯形算法是一种“顶点”算法其基本思路是由 可行域的一个顶点沿着某个边方向转移到另一个相邻顶点，并使目标值有所改善，从而在有 限多个顶点中找到最优顶点不幸的是，退化情形可能使所谓。另一个相邻顶点”实际上与原 来的顶点相重合，结果导致转移被停顿甚至有永无进展( 循环) 的可能该困难源于下面的事 实：在n 维空间中有可能有多于n 个的超平面交于同一个顶点，而基矩阵是个r l 阶方阵， 所以顶点同基矩阵并不一一对应 为了有效的克服这一难题，潘平奇教授经过了多年的思索和研究，从原始单纯形算法入 手，利用、借鉴单纯形算法的丰富成果，修改并推广了基矩阵的概念，】- 1 9 9 7 年提出了亏基 单纯形算法【7 0 1 该方法推广了基的概念，将传统的主元算法发展到了一个新阶段亏基单纯 形算法使我们在解线性规划问题时，可以有效地降低退化现象的影响，数值实验表明，亏基单 纯形算法在迭代次数和计算时间方面都明显优于同类传统的主元算法基于亏基的思想，潘 平奇教授进一步提出了射影单纯形算法、对偶射影单纯形算法、一类新的仿射尺度法等新的 有效的主元类算法1 6 9 ，7 1 ，7 3 ，7 8 | 1 3本文研究的主要内容 本文将对线性规划问题的主元类算法开展进一步的研究在本文中，我们就以下问题进 行了探讨 有界约束亏基单纯形算法 本文中在亏基框架下建立了有界变量单纯形算法的理论基础我们史 7 ( ) 1 的基础上进一 步提出了亏基有界变量线性规j t , j 单纯形算法，证明了算法的收敛性，并建立了一个相应的简 洁一阶段算法以给新算法提供一个初始基 基于最钝角规则的亏基单纯形一阶段算法 主元规则对单纯形类的算法起着决定性的影响1 9 9 4 年，潘平奇教授在文f 6 3 1 中提出 了一个无比值检验的行主元规则 最钝角规则基于该规则的对偶i 阶段算法，可为对偶单 纯形算法或原始对偶单纯形算法提供初始对偶可行基1 9 9 7 年，潘平奇教授又提出亏基的 概念【6 9 ，7 0 1 ，给出了亏基单纯形算法和对偶单纯形算法最近，文1 7 7 1 将最钝角行主元规则 应用到亏基情形，在亏基的框架下建立了基于最钝角规则的亏基对偶i 阶段算法本文中进 一步利用最钝角法则，在亏基的框架下建立了一个新的求原始可行解的一阶段单纯形算法， 由于亏基的引入，在很大的程度上克服了退化带来的困难；而最钝角法则的应用，则使我们能 每次简单地选取恰当的变量进基，从而新算法具有简单易行且计算量小的持点 主元标e r i s s c r o s s 方法 4 圣里奎堂堡圭堂篁垒塞 c r i s s c r o s s 算法的主要优点是其简洁优美它可从任一个基本解开始，仪用一个阶段 在有限步内就可求解线性规划问题且求解的过程具有对称性但它的实际计算效率却不高 4 3 】本文中提出一种新的有限的c r i s s c r o s s 算法利用重排下标的技巧，新算法一方面保持 丁c r i s s - c r o s s 算法原有的优点，另一方面它也具有更好的计算效率同时，新算法的有限性 也算得到了证明 单纯形方法与内点法相结合的混合算法 主元算法一般会受到退化现象的严重影响内点算法虽摆脱了退化现象的干扰，但要达 到一个精确最优解，内点法却还需要一个计算量不小的所谓的纯化过程而且，在优化后分析 方面，内点法也远远不如主元算法方便本文中将建立一个内点法与主元算法相结合的混合 算法我们试图将内点法与主元算法的技巧有机的结合起来，困之新算法看来具有两者的优 点它不仅克服了退化现象带来的困难，而且可获得精确的最优解 修正的射影单纯形算法 射影单纯形算法在实践中非常有效，它却没有完全摆脱由于退化而带来的停顿现象本 史中提出一个修正的射影单纯形算法巧妙地完全避免了退化的影响在不做任何非退化假 设的前提下证明了算法的有限性我们建立了一个非常简单有效的一阶段算法 线性规划算法的若干反例 本文中给出了最近一些国内外学者所提出的新算法的反例 1 4符号说明 本文将引入以下的符号和记法如果不特别声明，则以下面为准 用大写的英文字母a ，b ，m ，n 等表示； 用小写的英文字母a , b ，c 等表示； 矩阵a 的秩， a 的第j 列； 第i 个元素为1 的单位向量； 向量的第j 个无索f 向量的2 一范数； 矩阵的程空间： 单位矩阵 1 5基本概念和定理 最基本的主元算法是单纯形算法我们首先简单回顾单纯形算法的基本思想及有关结论 单纯形算法的主要思想是，从一个基本可行解开始，先判定其是否为最优解若是最优解则 叁三塞蕉堕 5 停止否则，沿某遗方向到达另一个基本可行解，再进行判定如此迭代进行，直至找到最优 解，或判定其无界从几何意义上来说，线性规划的可行域构成一个多胞形单纯形算法就是 从多胞形的某一个顶点出发，沿着下降( 上升) 边的方向到达相邻的另一个顶点就这样迭代 下去，直到得到最优值为止其中，边方向( 搜索方向) 的确定也即主元规则的选取是算法中 最关键的环节好的主元规则可以减少退化，以较少的迭代次数和运算时间便可达到最优；反 之，则有可能造成算法长期在某一个顶点处停滞不前，使算法的效率大大降低，最终影响算法 的效果甚至会产生循环，使算法失败下面我们简单的介绍具体实施单纯形算法的基本理论 及相关概念，为本文后面的开展打下基础 考虑如下标准形式的线性规划问题： m i n e lz s a z = b ( 1 1 “) ( 1 1 b 1 x 0( 1 1 c ) 其中一1 r ”“，c 兄“，舻，b r ”，一1 z 称为目标函数，式( 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 ： ( 玲( b 称为相应于b 的基本解( b a s i cs o l u t i o n ) 定义1 2 若一个基本解满足z20 ，即其也是一个可行解，则称z 为一个基本可行解 ( b a s i cf e a s i b l es o l u t i a n ) ，这时对应的基口称为可行基( f e a s i b l eb a s i s ) 定义1 3 一个基本可行解z ，如果其所有的基变量都取正值，则称之为非退化的 ( n o n d e 9 e n e r 以e ) ；反之，如果有的基变量也取零值，则说其是退化的( d e g e n e r a t e ) 一个 线性规划问题，如果它的所有基本可行解都是非退化的，就称该问题是非退化的，否则就说它 是退化的 定义1 ，4 一个基本可行解z ，如果满足式( 1 1 a ) ，则称之为线性规划问题的最优懈；相 应的目标函数值c 7 茁称为线性规划问题的最优值 关于解、基本解、基本可行锯等概念之间的关系，我们列举下面的基本结论； 定理1 j 可行鳃z 是基本可行解的充分必要条件是其正分量所对应的到向量线性无关 定理1 ，6 若一个标准的线性规划问题有可行解，则其必有基本可行解 定理1 7 若个标准的线性规划问题的目标函数有有限最优值，则必可在某个基本可 行解处达到 上面的定理说明对于标准的线性规划问题，若其存在有限最优值。则我们可以在基本可 行解的集合中去寻找最优解然而当矩阵的列数n 很大时，基本可行解的个数比较大，枚举 法显然是不可取的单纯形算法则是依照一定的规则在基本可行解的一个子集中去寻找最优 解下面介绍单纯形算法的相关理论 假设我们已有一个基本可行解： 。= ( ：) 对应的基矩阵为b ，非基矩阵为n ，= 【c 暑，西】，则式( 1 1 b ) 化为： 不妨没b = ( a 1 ，- ，n 。) 记向量 以及 则式( 12 ) 化为 或 。丘+ b1 n x = b 一1 6 a j = b a j = ( a 1 ，五”u ) t ，j = 1 ，n 6 = b “b = ( 5 ，k ) r n = b 一、n 目标函数化为： 令 j = 勺一f 墨吗，j = 1 ， x b + n x x = b r = c t 一西b _ 。a = ( e ，厶) = ( 矗，靠) = ( o ，嚣一n r b 。c b ) 标准线性规划问题化为： m i n c 喜b 一1 6 + i r x s t z b + b n x = b 一1 b x 0 定理1 , 8 如果牙使得式( 1 4 ) 中( 0 ，则牙为原问题的最优解 ( 12 ) ( 1 3 ) f 1 4 n 1 ( 1 4 b ) ( 1 4 c ) = 一n 。一 十 日 z 巧一叼 ，口 c 。一 + 一6 露 = 有 z 则 ， n 篁三塞丝鎏 7 定理1 9 如果式( 1 4 ) 中向量( 有分量靠 o ( 显然m + 1 冬k n ) ，而向量乱0 ， 则原问题无界 定理1 1 0 如果式( 1 4 0 ) 中向量有分量靠 0 众所周知，作为单纯形算法最基本的概念，基定义为由a 的1 2 1 个线性无关列昕构成的方阵 亏基单纯彩算法把这个概念推广如下1 7 0 l ： 定义2 1 ：系数钜阵4 的若干线性无关列所构成的矩阵称为基，若其张成的空间包含右 端项b 据以上定义，基分为两类： 定义2 2 ：如果基的列数等于系数矩阵的行数，则称其为完全基；否则称为亏基 可见传统单纯形算法所使用的基只限于完全基 设b 为基，其列数为m l ；设为非基，它由矩阵4 除去b 的各列构成，列数为7 一m 1 此后，我们不妨总设m l 0 z n 0 在下一节中，我们将介绍亏基原始单纯形表格算法在原始亏基单纯形算法的计算过程中，基 的列数将随着迭代过程动态的变化 2 2 亏基原始单纯形表格算法 为简单起见，我们利用增广矩阵来代替系统( 2 1 ) 对于任意的非奇异矩阵q 。r ”。 ，f q 甲b ，q v n ，q 丁6 l 显然与【b ，n ，b 】等价特别的，可以确定一个正交矩阵q 1 。，使得q 2 b 南x m - ( 其中，m i 焉基b 的列的个数) 是一个上三角矩阵，此时，矩阵 q r 日，q 了1 n ，q l 被称为正则矩阵( 或增广矩阵) 可以看出，由于b 是一个基，因此，q 。b 的对角元均为非 零，并且，若q 。b 的最后礼一m 1 个分量存在，则全部为0 现没已知一个正则矩阵1 q r b ，( 了1 n ，q t b l 及相应的指标集j b ，j n 为叙述方便，仍 记此正则阵为( 口，n ，6 j 假设，n 1 7 n ，并且加入价值向量行，然后对矩阵进行适当划分， 则线性规划( 2 1 ) 可描述为如下形式的表： 曼。n 爵小 f 2 4 ) 其中b 1 r - z i m - 为上三角阵m 妒“。( n - m - ) ，2 r ( m m 1 ) 。( “一m ，h 冗m 从表( 2 4 ) 立可得到一个基本解 至_ v = o 虿b = b f l 扫1 ( 2 5 ) 其对应的目标函数值，= b i l 1 检验数也可以从表格上直接得到事实上，用g u a s s i a n 消去法将( 2 4 ) 中价值向量行 中的基指标对应的元索消去，就可以得到j 和，并同时得到表格 讣 b lmb l 0 20 2 0 2 斋一， f 2 6 ) 32 n 1 j i 一一 一 一 沁 8 k 巩 儿o o m 帆靠玩0 呸 ：篁三兰 重羹兰丝矍兰壅量塾璧兰垫丝兰壅 1 1 这个表格被称为正则表 下面考虑某一次选代假若当前的正则表原始可行，即牙口o 不妨设该表恪就为( 2 6 ) 若知0 ，则已求得最优解故现在假设劾中含有小于零的分量，由d a n t z i g 的列主元规 则确定指标 q = a r gm i n 磊，1j = 1 ，2 ，礼一m 1 ) ( 2 7 ) 此时非基列o h 进基考虑如下两种情形 情形1 ：m 1 = m 或m l 0 ，则可以由最小比检验确定行指钚p 使得 a = 等一t n 罢秒ot b乞j o ( 2 1 0 1 当非退化时，z 日 0 ，则( 2 1 0 ) 对应的不等式成立此时，随着非基变量x k q 的值从零 增加到q ，并且其它的非基变量值保持不变，巧p 的值由f ，p 减为零，并保证原始可行性保持 不变这样就得到了如下的修正过的基本可行解哥的迭代公式： 易：2 锄一。地 v 待l ，2 ，1 ( 2 1 1 1 露如：= 然后我们将正则表中的第p 个基本列旋出基本列，并把指标q 所对应的非基列放于基本 列的末尾，随后相应的调整如和如若p = m l ，则所得的b r ”。”1 已经是上三角矩阵， 而p m i 时，b 只是一个上h e s s e n b e r g 矩阵此时通过g u a s s 消去或g i v e n s 旋转变换将 浚h e s s e n b e r g 矩阵化为上三角阵，并保证对角元非零 这样就完成了一次迭代 ( i i ) ：当情形2 成立时，a k q 隹r ( b ) 这时非基变量z 蛔的值不能从0 开始增加- 因为这样 有可能破坏后( m m 1 ) 个约束条件然而，我们可以对矩阵【b ；n ，6 j 左乘h o u s e h o l d e r 反射变换矩阵，将。幻的第( m 1 + 2 ) 列至第m 个元素化为0 ，并将正则表( 2 6 ) 中的第q 个 非基列移至基的最末，然后令r 2 1 ：= m l + l ，并相应的调整如和j 知此时原来的基本可行 解不变，但基列数增加，亦完成了一次迭代 在这两种情形下，显然b 的子分量0 2 并未改变，依旧为0 当我们用g r u s s 变换将新进 基的列所对应的价值向量中的元素零化后，就产生了一张新的正则表 由于在情形1 中，基的列数未改变，因此称此类迭代为满秩迭代( 或等秩迭代) ；而在情 形2 中，基列数增加了1 列，因此称此类迭代为增秩迭代 这样我们就完成了一次迭代的描述重复这榉的步骤，直至得到最优解或者问题无界在 整个计算过程中，基的列数会动态的增加，但不会减少我们将以上步骤总结为如下的算法： 算法2 4 ( 亏基原始单纯形表格算法) 对_ 尸标准线性规划问题( 2 1 ) ，给定初始正则表( 2 6 ) 和相对应的集合l ，b 和如，并假定 由此导出的鏊为可行基 1 + 若2 芝0 ，停止 2 据式( 2 7 ) 确定进基的列指标g 3 若m l z 且q 7 0 幻的第( m l + 1 ) 至第m 个元素有非零元，转步1 1 4 巾式( 2 8 ) 确定向量u 5 若南式( 2 9 ) 定义的集合i = 0 ，停止 6 由式( 2 1 0