（运筹学与控制论专业论文）传统选主元规则的变形及其在亏基方法中的应用.pdf

摘要 攀js s 8 3 3 0 传统的单纯形两阶段方法只是根据辅助函数所对应的检验数信息进行第一阶段的迭 代，而没有利用原问题目标函数所对应的检验数信息为了利用该信息，使得在求解辅助 司题时可以兼顾原问题的求解，本文从几何直观入手，对两阶段方法加以分析，得到变形 传统选主元规则的思想，然后在变形思想下，给出了几种新的选主元规则 1 9 9 7 年，潘平奇教授在文章 1 中提出了亏基的概念，将传统基的概念进行了扩展由 此得到的亏基单纯形算法，能够有效地减少运算量和运算时间，并且极大地降低退化现象 的影响2 0 0 0 年，潘平奇教授又在文章 2 中，给出了亏基算法的初始可行基的寻求方法 这种方法只增加一个人工变量便可以构造辅助函数，因此大大降低了辅助问题的规模本 文利用该辅助函数的这个优点，将新主元规则在亏基架构下加以实现，得到了三种新的亏 基算法在实现过程中，还采用了动态选主元的策略，以进一步提高求解效率数值试验结 果表明，后两种算法能减少计算时间和迭代次数 关键词：线性规划，单纯形法，亏基，退化，两阶段法，检验数，辅助函数 a b s t r a c t t h ec o n v e n t i o n a lp h a s e - 2s i m p l e xm e t h o dc a r r i e so u ti t si t e r a t i o n si nt h ef i r s tp h a s eo n l yb a s e d i l lt h ei n f o r m a t i o no fr e d u c e dc o s t sa s s o c i a t e dw i t ht h ea u x i l i a r yf m m t i o n t oo b t a i nab e t t e ri n i t i a l b a s i s b yp h a s e 一1a n d t od e c r e a s et h et o t mi t e r a t i o n s ，t h i sw o r km o t i v a t e db yi n t m t i o n i s t i cg e o m e t r y t oa n a l y z ea n dt r a n s f i g u r et h ec o n v e n t i o n a lp i v o tr u l e la n dp r o v i d e ss o m en e wp i v o tr u l e st h e s e n e wp i v o tr u l e sa l s ou s ef o rr e f e r e n c et h ei n f o r m a t i o no ft h er e d u c e dc o s t sr e l a t e dt ot h ei n i t i a l f u n c t i o n i n1 9 9 7 ，p r o f e s s o rp i n g - q ip a ni n t r o d u c e dan e wc o n c e p t - - - d e f i c i e n tb a s i s ，a n dg e n e r a l i z e d t h eb a s i st oa l l o wt h ed e f i c i e n tc a s e 1 s ot h a to n ec a l ls o l v el i n e a rp r o g r a m m i n gp r o b l e m si n s u c han e wf r a m eo fb a s i s d e f i c i e n c y - a l l o w i n gc o n t e x tr a t h e rt h a nw i t ht h es q u a r es u b m a t r i x t h e s i m p l e xa l g o r i t h mb a s e d o nt h en e w c o n c e p tc a ne f f i c i e n t l ys o l v ed e g e n e r a t ep r o b l e m sa n dr e d u c e i t e r a t i o n sa n dr u n n i n gt i m e i n2 0 0 0 ，h ep r o p o s e dan e w m e t h o d 【2 】t of i n da ni n i t i a lf e a s i b l eb a s i s f o rd e f i c i e n tb a s i sa l g o r i t h m s a c c o r d i n g t ot h i sm e t h o d ，o n em a y o n l yi n t r o d u c eas i n g l ea r t i f i c i a l v a r i a b l et oc o n s t r u c tan e wa u x i l i a r yp r o b l e ms i m p l e rt h a nt h ec o n v e n t i o n a lo n e i nv i e wo ft h e m e r i to ft h ea u x i l i a r yf u n c t i o n ，w ei n c o r p o r a t eo u rn e wp i v o tr u l e si nt h ef r a m eo fd e f i c i e n tb a s i s ， r e s u l t i n gi nt h r e en e wd e f i c i e n tb a s i sa l g o r i t h m s m o r e o v e r ，w ed e t e r m i n ep i v o t sd y n a m i c a l l yi n s o l u t i o np r o c e s st oa c h i e v eh i g h e re f f i c i e n c yo u rp r e l i m i n a r yc o m p u t a t i o n a le x p e r i m e n t ss h o w t h a tt h el a t t e rt w oa l g o r i t h m so u t p e r f o r m e dt h ec o n v e n t i o n a ls i m p l e xa l g o r i t h m ，b o t hi nt e r m so f r u n n i n gt i m ea n d i ni t e r a t i o nc o u n t s k e y w o r d s ：l i n e a rp r o g ia m m i n g ，s i m p l e xm e t h o d l d e f i c i e n tb a s i s ，d e g e n e r a c y , p h a s e 2 m e t h o d ，r e d u c e dc o s t ，a u x i l i a r yf u n c t i o n 东南大学学位论文独创性声明及使用授权的说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 栗。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任河贡献均已在论文中作了明确的说明并表示了 谢意。 签名：磋缝日期：趔：! 二、关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和 纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 签名：i ! 避导师签名：磕李童日期：理：! 第一章绪论 线性规划是运筹学中产生较早、应用广泛的一个分支，历经了半个多世纪的发展，其 理论已习臻成熟，并且已经成为科学技术、国民经济、国防建设等众多领域中不可或缺的 数学工具 早在2 0 世纪3 0 年代，俄国数学家康脱洛维奇在生产组织与计划的数学方法一书 中就论述到了线性规划问题1 9 4 7 年，g bd a n t i g 在文【3 卜【5 】中提出了求解线性规划问 题的单纯形算法，由此开创了线性规划领域的一个新纪元由于该算法的有效性，单纯形 方法逐渐成为求解线性规划问题的一类主要方法大量的专家学者在选主元规则、数值稳 定性、计算时间、计算量、初始可行基、减少或避免循环等方面作了更进一步的探讨，并对 该方法进行了推广和应用( 如文【6 卜【2 2 等) 1 9 7 9 年，俄国数学家哈奇扬在非线性规划的椭球方法的基础上提出了椭球算法( 文 2 3 1 ) ， 这个算法是求解线性规划问题的第一个多项式时间复杂性的算法，并且是一种内点算法 尽管实际的计算效果并不理想，但它引起了许多人开始关注内点算法1 9 8 4 年，k & r m a r k ，t r 在文 2 4 中提出了另一个多项式时间算法- - 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 提出的原始对偶预测校正内点法( 文 2 5 】) 在内点法中独占鳌头 然而，单纯形方法并没有因为内点方法的飞速发展而停滞不前1 9 7 7 年，g o l d f a r b 和 r e i d 给出了最速下降边算法的迭代公式( 文 2 6 ) ，并由f o r r e s t 和g o l d f a x b 在1 9 9 2 年给出了 大型稀疏问题的数值结果( 文( 2 7 ) 结果表明该算法在单纯形方法中一支独秀，并且丝毫不 逊色于内点算法，由此单纯形方法和内点法形成了对峙局面 近年来，潘平奇教授在单纯形方法方面进行了卓有成效的探索1 9 9 0 年，给出了最优 基的启发性特征刻划，在此基础上，引进了主元指标并对b l a n d 有限选主元规则进行了 推广；给出了原始和对偶的非单调性无比检验主元规则，并给出了原始和对偶的新的摄动 单纯形算法；1 9 9 1 年，给出了新架构下的二分单纯形算法，用二分的思想求解线性规划问 题( 以上文章可参见文 2 8 一 4 6 1 ) 尤其是亏基的提出( 文 1 1 和文和投影算法的实现( 文 4 7 卜 4 9 ) ，使得单纯形方法有了新的架构和选主元规则，其效果十分明显，在数值稳定性、 退化、迭代次数和计算时间等方面都有了很好的改善；并使得单纯彤方法能够和内点法相 结合，产生新的线性规划问题的求解方法；他近期的研究结果表明，对偶投影亏基算法已 i 东南大学理学硕士毕业论文 2 经成功应用到大型稀疏问题中，并且大大地减少了计算时间和迭代次数，从而极有可能将 线性规划的算法发展到另一个高潮 然而，现有的单纯形算法一般是利用两阶段方法，在求解初始可行基时，通常只利用 第一阶段的辅助函数所对应的检验数信息进行迭代，而没有考虑原问题目标函数所对应的 检验数信息由于原问题的所有解都是辅助问题的最优解，因此，如果能够在第一阶段结 束时，找到一个更接近于原问题最优解的初始可行解，并且第一阶段的迭代次数没有很大 增加的话，就有可能较好地减少问题的总迭代次数和总迭代时间。为此，通过几何七的分 析和启示，我们对传统的选主元规则进行了变形，使得在第一阶段迭代时，也同时考虑到 原目标函数所对应的检验数信息，从而在求解辅助问题时，也兼顾了原问题的求解鉴于 亏基较传统基有明显的优势，我们在亏基架构下应用变形后的主元规则，由此得到几种新 的亏基算法 为了进一步提高算法的效率，我们还尝试在迭代过程中部分地或有限度地使用变形后 的主元规则，也就是动态地使用主元规则，从而使得在主元的选取上有较大的灵活性和适 应性。 本文的主要框架如下：在下一章中，给出一些记号，并且回顾线性规划中的一些重要 理论和传统单纯形算法，包括初始可行基的寻求方法；然后，在第三章中，我们简单介绍 了亏基单纯形算法以及亏基初始可行基的一种较为简便直观的寻求方法；在第四章中，将 根据几何直观，对传统选主元规则给出几种变形，并在亏基架构下给出新算法；在最后一一 章，我们给出了数值试验结果，并对传统单纯形算法和新算法进行比较与分析 第二章基本理论 作为本文的开始，在这一一章中，我们将对传统的单纯形方法的理论基础和相关算法进 行回顾 2 1 若干基本结果 我们考虑如下形式的线性规划问题 ( 2 1 o ) ( 2 1b ) f 2 1 c 1 其中，a 虢“，且r a n k ( a ) = m ；b 虢“；z 蹰“，c 乳“；并且b o ，b 、x 、c 的分量不 全为零 本文中将用到如下的记号： o ja 的第j 列； e ：第i 个元素为1 的单位向量； 向量的第j 个元素； l 向量的2 范数； 孵( ) 矩阵的乘空间； ，单位矩阵 定义2 1 在问题( 2 1 ) 中，满足约束条件的向量z = ( z l ，z 2 ，一，。) t 称为( 21 ) 的可 j 解或可行点可行点的集合称为可行域，记作 s = z 、酽fa x = b ，z 0 ) 并把使目标函数取得最小值的可行解为最优解 东南大学理学硕士毕业论文 定义2 2 设b 是矩阵a 中的一个满秩子方阵，则称b 为一个基 a 中的剩余元素 分作两个部分，记为z 片和z w z e 的分量与b 的列相对应，称为基变量；x n 的分量与n 中的列相对应，称为非基变量 定义基指标集和非基指标集为： 。吃= j l ，j 2 ，j ，。) ，j u = k l ，k 2 ，k 。) ( 2 3 ) 其中： ，i = 1 ，2 ，m 为b 的第i 列的指标；畸，j = l ，2 ，n m 为第j 列的指标 定义2 3 设问题( 2 1 ) 的基为b ，在约束条件a x = 6 中令所有的非基变量取零值时， 得到的解z = ： 一 b 。06 ，称为相应于b 的基本解，当基本解的基本变量都取非负 值时，即满足z 且0 时，基本解称为基本可行解，相应的基b 称为可行基 下面，我们给出线性规划的一些基本结果，( 限于篇幅，此处只给出结果，详细证明请 参见引文 5 0 定理2 4 若线性规划问题( 2 1 ) 存在有限的最优值，则它必在可行域s 的一个极点上 达到；且目标函数有有限的最优值的充要条件是对d 的所有极方向都有，o 定理2 5 向量i 为s = 。舻la x = b ，z 之0 ) 的极方向的充要条件是：存在一个基 b ，a = 陋，n 1 ，并且存在中的一个列向量毗，使得b - 1 a t 0 ，而i 与 a = 一2 卜 旧a ， 同向 此外，对于变换后的( l p ) 问题 其中 s t ：e b + n x n = b o 0 = b n ，i = b b = c 吾口a c ，g o = c 葛5 ( 25b ) ( 25 ( ) 东南大学理学硕士毕业论文 5 即 = ( 1 ，2 ，一，矗) = ( 日，) = ( o ，西b 一1 n c ) ， 有如下结论： 定理2 6 若( 2 5 ) 式中对某个i 有0 ，则i 为原问题的最优解 定理2 7 若( 2 5 ) 式中的f 有分量靠0 ，其中m + 1sk n ，而乱0 ，则原问题无 界 定理2 8 若( 2 5 ) 式中有分量氨0 ，且瓯至少有一个正分量，则能找到基本可行解 岔，使得c r 岔 o ) ( 27 ) a r 女a i k 。 确定f 标_ 蛐为离基变量； ( 7 ) 以c 地代替a 口，得到新基，返回( 2 ) ， 东南大学理学硕士毕业论文 定理2 1 4 ：若算法终止于 ( i ) 步骤( 4 ) ，则此时基本可行解z 为f = c b i ( 虮步骤( 5 ) ，则问题无界 ： 是最优解，且目标函数的最优值 该算法要求有一个初始基本可行解及与之相对应的初始可行基而初始基本可行解并 不容易求出，因此，还需要额外的步骤来求解它两阶段法和大m 法就比较好的解决了这 个问题，下面我们简要介绍一下这两种方法 两阶段法首先对问题( 2 1 ) 引入人工变量z 。= ( 。扎z 叶2 ，一，x n + m ) 丁，从而构造辅助问 题 x 0 ，z o 0 其中，e = ( 1 ，1 ，1 ) 是分量全为1 的m 维行向量，并且b 0 则辅助问题有初始基本可行解 三 由此基本可行解开始进行单纯形迭代当 ( 28 b ) f 2 8 c 1 相应的目标函数值g ：曼6 。于是，可 l + ( i ) m i n 9 0 ，则不存在z 使得i 4 l 满足( 2 8 ) ，即原问题无可行解 1 0j ( i i ) r u i n g = 0 ，即z 。= 0 ，且。的分量都是非基变量这时基变量全是原问题的变量， i ，l 又知i “i 是( 2 t o ) 的基本可行解所以，z ：i 是原问题的一个基本可行解 1 o j ( i i i ) r a i n 9 = 0 ，且的某些分量为基变量，这时，可以通过消元法将含在基变量中的 人工变量换出，然后转( i i ) 当找到原问题的一个基本可行解时，我们可以把这个解作为原问题的初始基本可行解， 来求解原问题这样就可以求原问题的最优值了这个方法根据函数问题的不同，把求解 步骤分成了两个阶段，因此称为两阶段方法 我们也町以只通过一个阶段就求解出问题的最优值，大m 法就是这么一种方法大5 , 1 东南大学理学硕士毕业论文 方法是在约束中引入人工变量并在目标函数中增加惩罚项m e x 。，得到一个新问题 7 ( 29 a ) f 29b 1 其中m 为足够大的数由于惩罚项m e x 。的存在，在极小化目标函数值的迭代过程中，将 迫使人工变量z n = 。，故i 为原问题c z - ，的最优解和 ： 为c z ，中的最优解是等价 的由于但有初始基本可行解l ：j ，因此可以用单纯形方法进行求解当求解得到的最 优值中不含有大m 项时，就找到了原问题的最优解 以上就是对传统单纯形方法的回顾。在下一章中，我们将对亏基单纯形算法进行简要 的介绍 第三章亏基及亏基单纯形算法 在本章中，我们介绍潘平奇教授提出的基的推广概念一一亏基以及对应的亏基单纯形 算法和初始可行亏基的寻找方法。 考虑如下形式的线性规划问题 3 1 亏基 n l l nc 1z sta z = b z o ( 3 1 a ) ( 3 1b ) ( 3 1 c ) 其中，a 瓣”( m 0 z n o c k 1 】 x k ，。 ( 3 3a ) ( 33b ) ( 3 3c ) 当基为正则基( m = m ) 时，我们可以用上一章所介绍的传统单纯形算法来求解规划 ( 3 1 ) 然而，在亏基的情况下，以上的公式以及传统单纯形算法的迭代步骤是无法使用的 在下一节中，我们将介绍亏基架构下的原始单纯形算法 3 2 原始亏基单纯形算法 在这一节中，将介绍在亏基的基础上，对传统的原始单纯形算法进行修改而建立的原 始亏基单纯形算法在计算的过程中，随着迭代次数的增加，基的列数将动态的变化，直至 最优解达到( 若最优解存在) 为简单起见，我们将利用增广矩阵来代替系统( 31 ) 对于任意的非奇异矩阵q r 况m “ ，l q t b ，q 7 n ，q t 6 i 显然与陋，n ，6 】等价特别的，可以确定一个正交矩阵q 7 ，使得q 7 b 瓣“- ( 其中，m 1 为基b 的列的个数) 是一个上三角矩阵，此时，矩阵l q t b ，q t n ，q r b f 被称为正则矩阵( 或增广矩阵) 可以看出，由于b 是一个基，因此，q 2 。b 的对角元均为非 零，并且，若q t b 的最后n m 1 个分量存在，则全部为0 下面，我们准备叙述原始过程的表格形式算法。假设，已知一个正则矩阵1 q t b ，q t n ，q r b 及相应的指标集如，山为叙述方便，仍记此正则阵为f b ，n ，翻假设啊”t ，并且加入 价值向量行，然后对矩阵进行适当划分，可将规划( 3 3 ) 描述为如下形式的表： 纠 b 1n i b l 0 2 ( ) ( 34 ) b 1 东南大学理学硕士毕业论文 其中b l 虢m 1 为上三角阵n l 晴竹。( 舻竹1 1 ) ，2 蛇( m - - m 1 ) 。_ m ，b l 瓣m 从表( 34 ) 可以得到一个基本解 i = 0 2 b = b i l b l l ( ) 其对应的目标函数值，为b i l b l 另外，我们也可以从表格上直接得到j 实际上，用g u a s s i a n 消去法，将( 3 4 ) 中价值 向量行中的基指标对应的元素消去，就可以得到j 和，并同时得到表格 小 b 1 1b 1 0 20 2( 35 ) 这个表格被称为正则表 现在，我们考虑某一次迭代假若当前的正则表原始可行，即z 口0 不妨设该表格 就为( 3 5 ) 若2 0 ，则找到最优解，求解结束故现在假设j 含有小于零的分量，根据 d a n t z i g 的列主元规则，确定指标 q = a r gr a i n z k j lj = 1 ，2 ，n m 1 )( 3 6 ) 然后让非基列a k 。进基，这时，将会产生如下两种情形 情形l ：m l = m 或m l 0 则可以由最小比检验确定行指标p ，使得 o = ! 韭一r a i n 塑ii ，) 0 ( 3 9 ) v p 1 ) i 。 当非退化时，。口 0 ，则( 3 9 ) 对应的不等式成立此时，随着非基变量z 蛔的值从零 增加到n ，并且其它的非基变量值保持不变，z 如的值由句，减为零，并保证原始可行性保 持不变这样，就得到了如下的修正过的基本可行解i 的迭代公式： ( 3 1 0 ) 然后，我们将正则表中的第p 个基本列旋出基本列，并把指标q 所对应的非基列放于 基本列的末尾，随后相应的调整如和山若p = m l ，则所得的b 乳4 。m 已经是上三角 矩阵，而p m l 时，且只是一个上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 成立时，。钿隹豫( b ) 这时，非基变量z 幻的值不能从。开始增加，因为这 样有可能破坏后( m m 1 ) 个约束条件然而，我们可以对矩阵 b ；n ，6 1 左乘h o u s e h o l d e r 反射变换矩阵，将。的第( m 1 + 2 ) 列至第m 个元素化为0 ，并将正则表( 3 5 ) 中的第q 个 非基列移至基的最末，然后令m ，：= m 。+ 1 ，并相应的调整如和如此时，原来的基本可 行解不变，但基列数增加，亦算作一次迭代 显然，在这两种情形下，5 的子分量0 z 并未改变，依旧为0 当我们用g a u s s 变换将 新进基的列所对应的价值向量中的元素零化后，就产生了一张新的正则表。 由于在情形i 中，基列未改变，因此称此类迭代为满秩迭代( 或等秩达代) ；而在情形 2 中，基列数增加了1 列，因此称此类迭代为增秩迭代 这样，我们就完成了一次迭代的描述重复这样的步骤，直至得到最优解或者问题无 界在整个计算过程中，基的列数会动态的增加，但不会减少我悔以上步骤总结为如下 的算法： 东南大学理学硕士毕业论文 1 2 算法34 ( 亏基表格单纯形原始算法) 对于标准线性规划问题( 31 ) ，给定初始正则表( 3 5 ) 和相对应的集合如和山，并假定 由此导出的基为可行基 ( 1 ) 若j 0 ，停止 ( 2 ) 据式( 3 6 ) 确定进基的列指标口； ( 3 ) 若m 1 m 是q t a k 目的第( m 1h - 1 ) 至第m 个元素有非零元，转( 1 1 ) ； ( 4 ) 由式( 3 7 ) 确定向量u ； ( 5 ) 若由式( 3 8 ) 定义的集合j = 0 ，停止 ( 6 ) 由式( 3 9 ) 确定步长n 及相应的行指标p ； ( 7 ) ，据式( 31 0 ) 修正基本可行解i ； ( 8 ) 将( 3 5 ) 中的第p 个基本列移出非基列，并将指标q 所对应的非基列放至基的最 后，相应的调整如，如； ( 9 ) 若p 0 ，选取对应的变量进基，然后转( 7 ) ； ( 6 ) 若三0 ，寻找最大检验数1 选取对应的变量进基，然后转( 7 ) ； ( 7 ) 根据选取的进基列寻找出基变量，若找到出基变量，则进行相应的等秩或增秩迭 代；然后转( 2 ) ； ( 8 ) 若找不到出基变量，则原问题无解，停止 ( 9 ) 根据算法3 4 ，计算原问题( 3 1 ) 的最优值 变形2 ：在第一阶段选基时，在所有满足l ，三m a x f l j ) 2 3 的列中，选取白中最大 的项所对应的非基变量进基第二阶段依旧利用传统选主元规则进行选择 这种变形是在图4 3 所对应的思想上得出的，为了保证在第一阶段过程中，辅助函数 的目标函数值不减，让对白的信息的考虑建立在矗f 0 的基础上，尤其是这里的限制更 加强烈，是建立在f ，m a x f l j ) 2 3 的基础上的这是由于我们不能仅仅考虑寻找一个 好的初始基，就忽略掉第一阶段的迭代速度，这样就极有可能影响总的计算效率因此， 要给定优先考虑白还是优先考虑t ，的一种规则，或者是给定相关于白和f - ，的一种策 略，使得这种策略既考虑了原问题的求解，又考虑到了辅助问题的求解此处，给定在保证 辅助函数的目标函数值不减的前提下的考虑两者之间关系的一种策略，即对f ，的考虑要在 f 1 ，m a x f l a 2 3 的基础上由此，得到另外的亏基算法 算法42 ( 表格形式的亏基m 2 方法) 对于标准线性规划问题( 31 ) ， ( 1 ) 引入人工变量x 。+ j ，并构造辅助问题( 31 1 ) ； ( 2 ) 若有最优值9 ，9 0 ，则原问题无可行解，停止 ( 3 ) 若有最优值9 g = 0 ，且人工变量+ l 已经旋出基，则转( 9 ) ； 东南大学理学硕士毕业论文 1 8 ( 4 ) 若有最优值9 ，g = 0 ，但人工变量+ 1 未旋出基，则旋出人工变量x n + l ，然后转 ( 9 ) ； ( 5 ) 否则，l j m & x l j ) 2 3 的列，构成集合如； ( 6 ) 在集合而中，寻找最大检验数白。，然后选取对应的变量进基，再转( 7 ) ； ( 7 ) 根据选取的进基列寻找出基变量若找到出基变量，则进行相应的等秩或增秩迭 代；然后转( 2 ) ； ( 8 ) 若找不到出基变量，则原问题无解，停止 ( 9 ) 根据算法3 4 ，计算原问题( 31 ) 的最优值 变形3 ：在第一阶段选基时，当迭代次数小于( m 6 0 ) 时，在满足1 ， 0 的变量集合如 中，根据白+ z j 的最大项选进基变量；否则，直接根据1 ，选进基变量第二阶段依旧利 用传统选主元规则进行选择 这种变形也是在图4 3 所对应的思想上得出的，为了保证在第一阶段过程中，辅助函数 的目标函数值不减，让对白的信息的考虑建立在，0 的基础上根据数值试验结果，使 用这种选基规则时，迭代次数是在小于( + 6 0 ) 的情况下进行的对整个求解过程来讲，这 也就意味着本算法的前一部分其实是一种调整手段这种调整极有可能使得后面的使用传 统选主元规则进行迭代的步骤是建立在一个好的基的基础上的因此，这个算法可以看作 是变相的寻找辅助问题初始可行基的一种方法由此，得到新的亏基算法 算法4 3 ( 表格形式的亏基c + c 1 方法) 对于标准线性规划问题( 3 1 ) ， ( 1 ) 引入人工变量x n + l ，并构造辅助问题( 3 儿) ； ( 2 ) 若有最优值g ，g 0 ，则原问题无可行解，停止 ( 3 ) 若有最优值g ，g = 0 ，且人工变量。+ 1 已经旋出基，则转( 9 ) ； ( 4 ) 若有最优值g ，g = 0 ，但人工变量。n 1 1 未旋出基，则旋出人工变量z 。然后转 ( 9 ) ： ( 5 ) 当迭代次数小于( m 6 0 ) 时，在满足1 ， 0 的集合i o 中，根据白+ f l j 最大项选 取进基变量，然后转( 7 ) ； ( 6 ) 当达代次数大于等于( m 6 0 ) 时，寻找最大检验数“，然后选取对应的变量进基 再转( 7 ) ； 东南大学理学硕士毕业论文 ( 7 1 根据选取的进基列寻找出基变量若找到出基变量，则进行相应的等秩或增秩迭 代；然后转( 2 ) ； ( 8 ) 若找不到出基变量，则原问题无解，停止 ( 9 ) 根据算法3 - 4 ，计算原问题( 31 ) 的最优值 定理4 4 在标准线性规划问题( 31 ) 非退化和存在最优解的假设下，算法( 3 1 ) 、算法 ( 3 2 ) 、算法( 3 3 ) 均收敛 证明：由于算法( 3 2 ) 、算法( 3 3 ) 的第一阶段均是在保证如 0 的情况下进行选进 基变量的操作的，并且在菲退化假设下，每次迭代都会使得目标函数值上升，再根据极点 的有限性，可以得知，第一阶段必能达到最优解，因此，再根据原有的亏基算法进行第二阶 段的运算，必然收敛到最优解而算法( 31 ) 的第一阶段首先根据白选择进基变量的操作， 若在某次迭代时，转到根据f ，j 选择进基变量，则根据原有的亏基算法可以证明，该算法收 敛而若在第一阶段迭代中，只根据6 选择进基变量，则根据极点的有限性和算法的非退 化以及存在最优解的假设下，迭代必然在某一极点停止而该极点所对应的辅助函数值为 0 ，也就是找到辅助函数的最优解因此，这种迭代过程也会是收敛的证毕 对于弱化后的变形思想并不仅仅只能得到以上三种类型，而是还有许多其它的类型 譬如，我们可以结合潘平奇教授在文2 0 1 中提出的主元标的思想构建变形后的有限选主元 规则，也可以将变形思想应用在其它的选主元规则( 如最陡边选主元规则等) 中，当然还可 以构造一种能够有效平衡，和h ，的约束函数作者还考虑了一些其它的简单变形，鉴于 篇幅，这里只介绍以上三种变形后的选主元规则这些新选主元规则，可以看作是对传统 选主元规则的初步的拓展和延伸 第五章数值试验及分析 上一章我们阐述了变形后的选主元规则在亏基中应用的几个算法为了对算法的实际 表现有深入的认识，我们进行了大量的数值试验和反复比较在本章中，我们报告数值试 验所得到的部分结果，并对这些结果进行相应的分析 为了进行比较，给出四个下面程序： c o d ec l s ：传统的表格原始两阶段单纯形方法， c o d ec d p i ：表格形式的亏基m 1 方法，即算法4 1 在进行第一阶段迭代时，如果能 够根据原问题对应的白迭代，则根据，选进基变量；否则，根据如选进基变量 c o d ec d p 2 ：表格形式的亏基m 2 方法，即算法4 2 在进行第一阶段迭代时，在所有 满足1 j m a x u 2 1 3 的列中，选取白中最大的项所对应的非基变量进基 c o d ec d p 3 ：表格形式的亏基c + c 1 方法，即算法4 3 在进行第一阶段迭代时，当迭 代次数小于( m 6 0 ) 时，根据白十t ，选进基变量；否则，根据钆选进基变量 以上的程序是用标准c 语言编写的，并在w i n d o w sm e 操作系统上利用m i c r o s o f tv i s u a l c + + ( 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 mp e n t i u mi i i6 6 6 m h z 的兼容机，内存1 2 8 m b y t e s ，机器精度为3 2 位所有的程序都以= 1 0 “为容限，都采用了 h a r r i s 选主元规则，并在h a r r i s 主元规则中取d = 1 0 为了增加程序的数值稳定性，这四 个程序都使用了均衡尺度( s c a l i n g ) 的技术计算运行时间所用的工具为v i s u a lc + + 的标准 库函数f t i m e ，以秒为单位，不包括数据预处理的时间 这儿用于测试的2 5 个问题都是来自h t t p ：w w wn e t l i b o r g l p d a t a 的不含b o u n d s 和 r a n g e s 的标准l p 问题，并且这些问题在网上都是以压缩格式给出，在使用前必须用e l l l p s c 对数据进行解压，变为m p s 格式，才能够参与计算e m p s c 程序同样是在上述的网址上 进行下载的 表1 给出了用传统的表格原始两阶段单纯形方法( c l s ) 来测试这些问题所得到的结 果在表格的第一列列出的是问题的名称，第二、三、四列列出的分别是与之对应的问题的 行数m 、列数扎行列之和m + n ；后面的几列包括迭代次数( 总迭代次数、第一阶段迭代次 数、第二阶段迭代次数) 、运行时间( 总时间、第一阶段运行时间、第二阶段运行时间) 表 2 、表3 、表4 分别给出的是用表格形式的亏基m 1 方法( c d p i ) 、亏基m 2 方法( ( 。d p 2 ) ， 亏基c + c 1 力法( c d p 3 ) 测试这2 5 个问题所得到的结果，数据包括两个阶段的迭代次数和 2 n j i ，南大学理学硕士毕业论文 迭代时间，还有总迭代次数和总迭代时间然后我们对原始两阶段方法( c l s ) 和m 1 方法 ( c d p i ) 、m 2 方法( c d p 2 ) 、c + c 1 方法( c d p 3 ) 等3 种方法分别进行了比较，其结果在表 5 中列出，包括总迭代次数的比较和总迭代时间的比较；计算方法是，c l s c d p i ，i = l ，2 , 3 为了能够更好的分析问题，在此表中同时列出了问题的规模( 用m + 来表示) 从表1 表4 中可以看出，相对于c l s 来说，c d p i 的总迭代次数要多3 6 5 次，但是 总迭代时间却下降了2 04 7 秒，这说明该变形尽管迭代次数多，但由于是在亏基架构下，故 也能够很好的减少迭代时