单纯形算法中检验数计算的改进.pdf

东南大学 硕士学位论文 单纯形算法中检验数计算的改进 姓名：胡剑峰 申请学位级别：硕士 专业：运筹学与控制论 指导教师：潘平奇 20040312 众所周知，在单纯形算法的每一步迭代中都需要计算单纯形乘子 ”= 口T c e ( 即对偶变量，其中B 为当前基矩阵，c 为价格系数) ，进而求得非 基变量的检验数在实际计算时，我们通常对B 采用L u 分解进行计算， 也就是说，在计算检验数时需要求解两个三角系统 面孪茎坌绍T ．．覃壁眸进的计算检验数的算法在其中一种算法中，我们 绎喇I 另■母枣解检验数的公式；而在另一种算法中，我莉则培出亍二 2 求蟹? 昀遵穆谷式这两种算法都只需求解一个三角系统，从而减少 每一步迭代的计算时间 ‘一 关键词：单纯形算法，单纯形乘子，检验数，L u 分解，三角系统 A b s t r a c t A sw ek n o w ，a te a c hi t e r a t i o ni ns i m p l e xa l g o r i t h m s ，w en e e dc o m p u t et h es i m p l e x m u l t i p l i e r7 r = B ～c s ( t h ed u a lv a r i a b l e ，w h e r eBi st h ec u r r e n tb a s i sm a t r i x ．ci st h e p r i c ec o e f f i c i e n t ) t od e r i v et h er e d u c e dc o s t ．A ta c t u a lc o m p u t a t i o n ，w eu s u a l l yu s et h e L U d e c o m p o s i t i o no fB —t h a ti st os a y ．w en e e ds o l v et w ot r i a n g l es y s t e m si nc o m p u t i n g t h er e d u c e dc o s t U l u = c B L J 7 r = v H o w e v e r ，i nt h i sa r t i c l e ，w ei n t r o d u c et w oi m p r o v e dc o m p u t a t i o no ft h er e d u c e dc o s t ． I no n e ，w ep r e s e n ta n o t h e rf o r m u l at oc o m p u t et h er e d u c e dc o s t ；a n di n t h eo t h e r ，a r e c u r r e n c ef o r m u l ai s g i v e nt od e r i v enI nb o t ht h et w oa l g o r i t h m s ，o n l yo n et r i a n g l e s y s t e mn e e dt ob es o l v e di nc o m p u t i n gt h er e d u c e dc o s t ，s ot h a tt h et w o a l g o r i t h m st a k e f e w e tt i m ea te a c l li t e r a t i o n ． K e y w o r d s ：s i m p l e xa l g o r i t h m ，s i m p l e xm u l t i p l i e r ，r e d u c e dc o s t ，L Ud e c o m p o s i t i o n ，t r i a n g l e s y s t e m 东南大学学位论文 Y6 4 4 4 8 8 独创性声明及使用授权的说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果． 尽我所知，除了文中特别加以标明和致谢的地方外，沦文中不包台其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料．与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意． 二、关于学位论文使用授权的说明 签名日期：—— 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印，缩印或其他复制手段保存论文．本人电子文档的内容和纸质论 文的内容相一致．除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容．论文的公布( 包括刊登) 授权东南大学研究生院办理． 签名导师签名日期：—— 第一章引言 自线性规划诞生至今，已产生出了许许多多的的理论与算法，线性规划 作为- - I ' q 新兴学科也已日益丰富与完善。

如今，线性规划已成为几乎所有 的商业活动、科学研究、工业生产和军事行动的一个重要组成部分，应用 前景十分广泛线性规划的成功应用，已为人类社会节省了无数的财富 纵观线性规划的发展历程，其主要经历了如下三个里程碑式的阶段： 1 ．1 9 4 7 年， G B ．D a n t z i g 首次提出了求解线性规划问题的单纯形算法，从 此后，线性规划如雨后春笋般得到了迅猛地发展与此同时，单纯形算法也 取得了巨大的发展，其理论也日趋成熟与完善虽然单纯形算法的时间复杂 性是指数阶的，然而它在实际应用中却取得了显著的效果后来，B o r g w a r d t 和S m a l e 都证明了单纯形算法的平均运算次数是多项式级的因而一直以 来，不论在理论上还是在实际计算中，单纯形算法都是极其重要重的 2 ．1 9 7 9 年，苏联青年数学家哈奇扬提出了第一个多项式时间复杂性算法一 椭球算法，从而证明了线性规划问题确实存在多项式时间算法因此，椭 球算法从理论上说是个重要的突破但遗憾的是广泛的实际检验表明其计 算效果比单纯形算法差，因而它还不能在实际使用方面取代单纯形算法 3 ．1 9 8 4 年，K a v m a r k a r 提出了求解线性规划问题的另一个具有多项式时间复 杂性的算法- - K a r m a r k a r 算法。

从理论上说，K a r m a r k a r 算法的阶比椭球算法 有所降低，从实际效果来说也好得多，因而引起了学术界的广泛关注，从 此掀起了一股内点法研究的热潮然而，K a r m a r k a r 算法的实际效果能否胜 过单纯形算法? 学术界目前尚无定论不过越来越多的专家认为，对于中 小型线性规划问题而言，K a r m a r ' k a r 算法稍逊于单纯形算法；而对于大型稀 疏的线性规划问题，前者则略胜于后者如今，K a r m a r k a r 算法与单纯形算 法并驾齐驱，已成为求解线性规划问题最主要的算法之一 此外，1 9 7 7 年，G o l d f a r b 和R e i d 提出了最陡边算法，并由F o r r e s t 和G o l d f a r b 在1 9 9 2 年给出了大型稀疏问题的数值结果，结果表明该算法丝毫不逊色于 内点算法近年来，我的导师潘平奇教授首次提出了亏基的概念，并在亏 基的架构下，结合单纯形算法与内点算法的优点而提出了投影主元算法， 其数值结果非常令人满意，也是线性规划领域的一个重大突破 以上，我们简要地介绍了线性规划的发展历史接下来，本文主要讨论 单纯形算法及其数值实现． 单纯形算法在求解大型实际问题方面之所以能卓有成效，不仅是其原理 与规则的功力，而且还有赖于各种精巧的数值实现方法。

一般而言，这些方 法可以分成两类一类称为分解方法，即把原来的问题分解成一些规模较 小的极值问题来求解，其主要包括D a n t z i g - W o l f 分解法、B e n d e r s 分解法以及 阶梯状结构线性规划问题的套分解法等；另一类称为直接方法，即直接求 解原问题，但对基矩阵的逆的存放与使用设计一些紧凑而方便的办法，其主 要包括逆阵的乘积形式表示法、重新求逆与P 3 ，P t 法、L U 分解法，C h o l e s k y 因子分解法等如果一个大型线性规划问题既可使用分解方法，又可使用 直接方法，则通常后者的效果更好 本文所介绍的两种算法均为直接方法，它们都是对L U 分解法的改进与 提高 我们知道，无论是单纯形算法还是内点算法都属于迭代算法而一个迭 代算法的时间复杂性主要包含两部分 ( 1 ) 总的迭代次数 ( 2 ) 单步迭代的计算时间 因而若要提高一个迭代算法的效率，关键在于减少每一步迭代的计算量此 外，我们知道，在采用L u 分解法实现单纯形算法的每一步迭代的计算中， 其核心为求解四个三角系统而本文在L u 分解法的基础上所提出的两种算 法都只需要求解三个三角系统，从而减少了一个三角系统的求解以提高整 个算法的效率。

在本文的第二章中，我们简单介绍了L U 分解法；而本文的第三、四两章 是重点它们分别详细阐述了两种改进的L U 分解法的推导过程它们从不 同的思路出发，分别采用不同的计算技巧，然而却达到同样的理论效果； 在本文的第五章中，我们从理论上，分别对这三种算法的单步迭代的计算 量作了一个粗略地分析；本文的最后一章第六章则分别给出了L u 分解法与 采用递推公式的改进的L u 分解法的数值测试结果，并加以比较 第二章L U 分解法 在本文中，我们考虑如下标准线性规划模型 m i nc T z s ．t ．A z = b x 0 ( 2 ．1 a ) ( 2 1 b ) ( 2 l c ) 其中A ∈R m ×n ，r a n k ( A ) = m ( m o ) 5 对基矩阵B 进行校正 由此可知，在单纯形算法的每一步迭代中需要用B q 来得到的量是 ( n 可以是向量b 或n ”一，a 求”等价于解方程 B T 7 r = c B 而( 2 ．2 ) 式意味着 B 7 = U 7 L 7 ( 23 ) 因此，我们可先通过求解三角系统( 2 ．4 ) 式 U T “ = C B 得到u ，然后由( 2 ．5 ) 式解出”。

工T 丌= ” 同理，求i 相当于解三角系统( 2 ．6 ) ，( 2 ．7 ) 式 L 叫= a I7 a i = w 假设我们现在已找到进基变量z k 和出基变量％，我们来考虑当原来 的基矩阵B 中的列％被向量a k 代替，即换基时，L U 分解的校正目前已 知的校正法主要有两种：B a r t e l s ．G o l u b 校正法和F o r r e s t ．T o m l i n 校正法 我们这里所介绍的就属于F o r r e s t ．T o m l i n 校正法 设Y L - 1 k ( 这个向量在确定离基变量时已经用公式( 2 ．6 ) 算得) ，则用 L 左乘新的基矩阵将会得到形如图2 ．1 的方阵，它将上三角矩阵u 中的第 r 列换成蜘 为了书写与计算方便起见，我们将新的基矩阵中各列的位置作一更换， 把向量a ‰移至最后一列( 这不失一般性，只要将各列的位置作一记录即 可) ，则有 B = 【q l ' + 0 J 一1 ，n + l ，a j a k c ：= [ c j ，，，％．C ：I ，h ] ‰ 砒 一 忙 与 4 5 6 7 2 2 2 2 1 已 H = L 一1 雪 ( 28 ) 由于向量％。

a j ，都朝前移动了一列，因此H 的形状如图2 ．2 所示，它是 一个上H e s s e n b e r g 矩阵将矩阵口中的第r + 1 ，．．，m 行都朝上移动一行。