（运筹学与控制论专业论文）亏基摄动对偶Ⅰ阶段算法.pdf

摘要 潘平奇教授提出的摄动单纯形算法无须引入人工变量，可以从任何一个基出发进行 迭代，所构成的两阶段算法在初步的数值试验中表现很好。近年来，为了克服退化带来 的计算困难，他又引入了亏基概念并建立了亏基单纯形算法。试验表明，这些算法能够 降低退化带来的不良影响，减少总迭代次数和运算时间。 本文将摄动算法和亏基单纯形算法相结合，以充分发挥这两种算法的优势，从丽为亏 基对偶单纯形算法提供一个新的i 阶段算法，以使其进一步克服了退化所带来的困扰。 我们的数值试验表明，所提出的算法能有效地减少总迭代次数，其效率不仅远远优于传 统的单纯形算法，且优于原有的亏基单纯形算法，是一个非常吸引人而充满希望的新尝 试。 关键词：线性规划单纯形法亏基退化摄动l u 分解 a b s t r a c t p e r t u r b a t i o na l g o r i t l u n sp r o p o s e db yp r o f e s s o rp i n g q ip a n ( 1 9 9 9 9 0 0 0 ) c a ns t a r tw i t h a n 、， b a s i s ，w i t h o u ti n t r o d u s i n ga l l ya r t i f i c i a lv a a i a b l e s ，r e l a t e dt w o p h a s ea l g o r i t h m sa r ef a v o r a b i ei n p 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 l n e n t si no r d mt , oo v e r c o m ec o m t m t a t i o n a ld i i t i c u l t i e sv i e l d i n g f r o n ld e g e n e r a c y ，r e c e n t l yh ei n t r o d u c e dan e w c o n c e p td e f i c i e n tb a s i s ，a n de 8 t a b l i s h e dd e f t c i e n t b a s i ss i m p l e xa l g o r i t h m s t e s t ss h o w e dt h a tt h e s ea l g o r i t h m sr e d u c ea d v e n te f i e c t so fd e g e n c r a c v 、 j 玎1 d e wt o t a ln u m b e ro fi t e r a t i o n sa n dr u n n i n gt i m e t h ep u r p o s eo ft h i st h e s i si st oc o m b i n et h ep e r t u r b a t i o na l g o r i t h m a n dd e f t c i e n t b a s i s 8 l g o r i t h mt ob r i n gt h ea d v a n t a g e so ft h et w ot y p e so fa l g o r i t h m si n t of u l lp l a y ，c o n s e q u e n l yo 髓r an e wp h a s e 一1p r o c e d u r ef o rt h ed u a ld e f i c i e n t b a s i s a l g o r i t h m ，a n do v c r c o m et h ed i f i c u l t i e s f r o md e g e n e r a c yt o 。h i g h e re x 7 t e n t o u rc o r n p u t a t i o n a le x p e r i m e n t ss h o wt h a tt h 8p r o p ( ) s c d 出g o r i t h m sr e d u c et o t a ln u m b e ro fi t e r a t i o n ss i g n i f i c a n t l y n e wa l g o r i t h m s ，se f l i c i e n c yi ss u p e r i o r ”to n l yt ot 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 mb u tt h ed e f i c i e n t b a s i s a l g o r i t h m s ot h i si sa v e r ya t t r a c t i v en e wa p p r o a c hb e i n gf u l lo fp r o m i s e k e y w o r d s ：l i n e a rp r o g r a m i n i n g s i m p l e xm e t h o d d e f i c i e n tb a s i s p e r t u r b a t i o nl uf a c t o r i z a t i o n 东南大学学位论文 独创性声明及使用授权的说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 二、关于学位论文使用授权的说明 签名：雄哪赴堕 东南大学、中国科学技术信息研究所国家图书馆有权保留，本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布l 包括刊登) 授权东南大学研究生 院办理。 签 名：崆导师签名 第一章引言 线性规划是产生最早，应用最广泛的个运筹学分支历经了半个多世纪的发展， 这个领域已日臻成熟，产生了许多理论、算法和软件，已经成为科学技术国民经济、国 防建设等诸多领域中不可或缺的数学工具 在其发展史上，几位学者作出了关键性的贡献， 早在2 0 世纪3 0 年代，俄国数学家康脱洛维奇在生产组织与计划的数学方法一书 中就论述到了线性规划问题及其解法，可惜未引起国际学术界注意1 9 4 7 年，g b d a n t i z i g 提出了线性规划模型和单纯形法，标志着线性规划领域的诞生( 【5 ，6 】) 其后这领域得到了迅速发展许多学者为提高数值稳定性、降低计算复杂性和提高 算法的计算效率进行了不懈的努力，使算法和理论发展到个相当高的水平1 9 7 9 年。 俄国数学家哈奇扬提出了第个求解线性规划问题的多项式时间算法一椭球算法( m ) ， 尽管实际计算效果并不理想，但因具有重要的理论价值而备受关注1 9 8 4 年，k a r m a r k a r 在文i s 中提出了另一个多项式时间算法理论上，该算法计算复杂性的阶比椭球算法有 所降低，且在大型稀疏问题求解上效果也很好，从而掀起了内点法的研究热潮内点法的 迅速发展打破了单纯形方法一统天下的格局然而，单纯形方法也没有停滞不前1 9 7 7 年，g o l d f a r b 和r e i d 给出了最速下降边单纯形算法的递推公式( 9 1 ) ；1 9 9 2 年，f o r r e s t 和g o l d f a r b 又给出了用于求解大型稀疏问题所获得的数值结果，表明该算法丝毫不逊色 于内点算法( 1 0 1 ) 随着单纯形算法研究的深入，在对退化现象的处理上也取得若干进展如字典序法。 b l a n d 规则、摄动法等( 1 1 1 7 1 ) 值得关注的是，潘平奇教授提出的原始和对偶摄动单 纯形算法( 【2 ，3 】) 不需要引入人工变量，可以从任何一个基出发进行迭代，能够非常有效 地处理高阶退化问题这种算法为对偶单纯形算法和原始对偶单纯形算法提供初始可行 基，所构成的两阶段算法在数值试验中有很好的表现1 9 9 7 年，他又提出了亏基的概念 ( 【l ，2 】) ，并在亏基的架构下，给出了投影主元算法亏基的引入为主元算法的进一步发展 注入了新的活力，提供了新的可能，使在求解线性规划问题时，降低退化现象的影响 他近期的研究结果表明，对偶投影亏基算法已经成功用于大型稀疏问题的求旃，该算法 东南大学硕士学位论文第一章引言 2 大大减少了迭代次数和计算时间，数值结果非常令人鼓舞。 本文在亏基的架构下引入原始摄动单纯形算法，能够充分发挥两种算法的优势，有 效地克服退化的影响，并减少了迭代所需的时间和总迭代次数，提高了算法效率。 本文框架如下：在第二章中，给出一些常用的符号，简要叙述单纯形法的基本概念 和定理；第三章，简要介绍亏基概念和亏基单纯形算法；第四章，在亏基的架构下给出 新算法；最后一章，我们给出了数值试验结果，并对传统单纯形算法、亏基算法和新算法 进行比较和分析 第二章基本概念和定理 单纯形算法的基本思路是：从一个基本可行廨开始，先判定其是否为最优解若是 最优解则停止否则，沿某边方向到达另一个基本可行解，再进行判定如此迭代进行。 直至找到最优解，或判定其无界从几何意义上来说，线性规划的可行域构成个多胞 形，单纯形算法就是从多胞形的某一个顶点出发，沿着下降( 上升) 边的方向到达相邻的 另一个顶点这样迭代下去，直到得到最优解为止其中，边方向( 搜索方向) 的确定也 即主元规则的选取是算法中最关键的环节好的主元规则可以克服退化，以比较少的迭 代次数和运算时间便可以达到最优；反之，则有可能造成算法长期在某个顶点处停滞 不前，使算法的效率大大降低，最终影响算法的效率，甚至会产生循环，使算法失败但 究竟如何判断是否是最优解、无界，怎样进行迭代、判定，则需要相应的理论和方法下 面我们简单介绍单纯形算法的基本理论及相关概念 考虑如下标准模型 r a i nc t = ( 2 1 a ) 8 t a x = b ( 2 1 6 ) z 0 ( 2 1 c ) 其中a j p 。”，r a n k ( a ) = m ( m 0 5 ( 2 3 ) ( 2 4 ) ( 2 5 a ) ( 2 5 6 ) ( 2 5 c ) 定理2 8 如果孟使得式( 2 5 a ) 中e 0 ，则牙为原问题的最优解 定理2 9 如果式( 2 5 a ) 中向量e 有分量“ o ( 显然m + l k s ，1 ) ，而向量s0 。 则原问题无界 东南大学硕士学位论文第二章基本概念和定理6 定理2 1 0 如果式( 25 a ) 中向量( 有分量( 0 ，且毗至少有一个正分量，则能我 到基本可行解2 ，使c 7 t c t y , 以上三个定理给出了单纯形算法的工作原理，即不断地从一个可行基迭代到与它相 邻的另一个可行基，直至找到最优基( 若最优基存在) ，或判定原问题无界下一章将要 介绍的亏基原始单纯形算法就是在这些原理的基础上建立不同的构架得到的 第三章亏基及亏基单纯形算法 为了克服退化带来的困难，众多学者相继提出了各种不同的主元规则t 一些有限规 则如扰动法，字典序规则及b l a n d 规则等虽从理论上避免了循环的出现，但实际计算中 迭代次数太多，表现远不及传统规则好；在非有限规则中，实用的h a r r i s 行主元规则表 现甚佳，最陡边规则被认为是目前最好的列主元规则近年来，潘平奇教授引入了亏基 概念并建立了亏基单纯形算法，该算法能够有效地克服退化带来的计算困难本章中， 我们将介绍亏基及其算法的基本结果 3 1亏基 单纯形算法中，基是个最基本、最重要的概念，传统的基定义为由系数矩阵的1 1 1 个线性无关列所构成的方阵，m 是系数矩阵的行数由于基的列数被固定为m ，故当 右端项b 在基的域空间的某一真子空间时，必有一些基变量取零值，这样的情形我们称 之为退化退化往往导致算法在可行域的某个顶点处停滞不前，大大降低了算法的效 率尤其对于大型稀疏问题，退化现象经常出现当前降低退化影响的方法很多，最直 接的方法是去掉那些不包含在真子空间中的基列，也就是将基变量变成非基变量 基于上面的想法，考虑问题( 2 1 ) ，假设矩阵b 是由8 个列向量组成的基矩阵， 为非基矩阵，它是由a 中除了b 的各列构成的，列数是，l s ，重新定义基指标集和非 基指标集为， 如= 协，j 2 ，矗) ，j n = 1 ，乜，k 一- ( 3 1 ) 其中五，i = 1 ，s 为b 的第i 列的指标；b ，j = 1 ，n 一8 为的第j 列的指标其中 基指标五的下标称为行指标，非基指标岛的下标称为列指标，相应于基和非基指标，向 量z 、c 的元素和a 的列称为基和非基的为了描述方便，根据历，重新划分和排列 各个向萤元素和矩阵的列，得到如下划分 a = i b ，j v 】= q ，o k ，一) c t = 障，西】_ 勺l i 一，c k l i ，一， 7 ( 3 2 ) ( 3 3 ) 东南大学硕士学位论文第三章亏基的概念及亏基单纯形算法8 z 7 = 睁；z 五 = q ，z x ，。k 一。)( 3 4 ) 根据以上分块，问题( 21 ) 就可写成 m i n z b 十商x n s , t b x b + n x = b ( 3 5 ) 相应的对偶问题为 m a x b t y 鲋协+ 忖 c b 。， 潘平奇教授把传统基的概念推广如下； 定义3 1 系数矩阵a 的若干线性无关列所构成的矩阵称为基，若其张成的空间包 含右端项b 据以上定义，基可以分为两类： 定义3 2 如果基的列数小于行数，则称为亏基；否则称其为完全基 可见传统单纯形算法所使用的基只限于完全基 潘平奇教授提出的亏基概念使单纯形算法发生了重大改变在传统单纯形算法中， 每一步迭代的迭代点( 基本可行解) 均对应着可行域的一个顶点，在非退化的情况下，下 一次迭代点则对应相邻的另一个顶点，若存在退化的情况下，则下一次迭代点并不一定 是与其相邻的顶点，而有可能仍是原来的顶点，若在一问题中多次出现这种情况，则会 造成算法长时间停留在某些顶点，影响算法数值效果如果在亏基构架下，基b 的列数 少于行数即为亏的，因此可以大大降低在退化时经常出现的循环情况另外，我们可以 从基与迭代点( 基本可行解) 的关系来分析亏基的几何意义根据单纯形法的几何原理， 基与可行域的顶点形成对应关系r 若在非退化情况下，它们之间的对应关系为一一对应 的，但是在退化的情况下，则有一个可行域的顶点与两个以上的基矩阵对应，在迭代时， 若在对应于同一顶点的基矩阵之间进行基转换，便是退化了然而，对于亏基的情形，我 们可以使基与可行域顶点之间尽可能形成一一对应的关系( 即使存在退化，则顶点对应 奎堕奎兰堑圭兰垒丝塞叁三耋茎董墼堡垒墨茎董塞丝矍篓堡 9 尽可能少的基) ，这样在迭代时可使算法在不同的点之间进行，从而减少了退化的情况， 提高了计算效率尤其在大型稀疏问题中，基本可行解的退化是常见现象，因此亏基算 法对其更有重大的意义因此，潘平奇教授实际上是推广了传统意义上的基的概念，将 基由方阵推广为列数不超过行数的般矩阵，使单纯形法的适用范围更广阔 3 2 亏基原始单纯形算法 本节我们将在亏基的基础上，介绍对传统原始单纯形法进行修改而建立的亏基原始 单纯形法在计算过程中。随着迭代次数的增加，基的列数将动态的变化，直至最优解 达到( 若最优解存在) 为方便起见，我们利用增广矩阵来代替系统( 2 1 ) 对于任意的非奇异矩阵q t j p 。”， q t b ，q 7 ，q 7 6 】显然与【b ，6 】等价特别地，可以确定一个正交矩阵q 矿，使得 q r b f p ”( 其中，s 为基b 的列的个数) 是个上三角矩阵，此时，矩阵 q t s ，q t n ，q t b 被称为正则矩阵( 或增广矩嘲可以看出，由于b 是个基，因此，q t b 的对角元均 为非零，并且，若q t b 的最后7 n 一8 个分量存在，则全部为零 现设已知一个正则矩阵 q t b ，q t q 丁6 】及相应的指标集如和打为叙述方便， 仍记此正则阵为旧，6 1 假设8 m ，并加入价值向量行，然后对矩阵进行适当划分， 则( 2 1 ) 可描述为下表： bn6 【西西。j 2 b 1 16 1 0 20 西西0 其中b 1 酽为上三角阵，le 彤x 加一”，n 2 硝m - a ) ，瓦彤 从表( 3 ”立可得到一个基本解 ( 3 7 ) 妇；0 孟口= 町1 孔( 3 8 ) 检验数j 也可从表格上得到事实上，用g a u s s 消去法将( 3 7 ) 中价值向量行中的基 东南大学硕士学位逢文 第三章 亏基的概念及亏基单纯形算法 1 0 指标集对应的元素消去，就可得到表格 b 】n 15 1 0 20 0 墨一f ( 3 9 ) 从表可得到籼= a n 一f c b ，目标函数值，= 弓b f l 5 1 我们称( 3 9 ) 为正则表，算法 的每个迭代步对应一个基或正则表 下面考虑某一次迭代假若当前的正则表( 39 ) 原始可行，即牙口20 若甜0 。 则已取得最优解现在假设甜中有小于零的分量 为了进行基变换，由传统的d a n t z i g 列选主元规则确定一个非基列进基，其列指标确 定如下； q = a r g m i n - s k ，i j = 1 ，2 ，n s )( 3 1 0 ) 显然一z k q 0 ，则使用如下的行主元规则： = 1，ij o 吖 累 日 0 【 东南大学硕士学位论文 第三章亏基的概念及亏基单纯形算法 1 l 规则1 ：让基列q ，出基。其中行标p 满足： a = 警= 俐n 警睢j ) 0 ( 3 1 3 ) q 当非退化时，i b 0 ，则( 3 1 3 ) 对应的不等式成立此时，随着非基变量钆的值 从零增加到a ，并且其它的非基变量值保持不变，的值由减为零，并保证原始可 行性保持不变这样就得到了如下的修正过的基本可行解孟的迭代公式。 乃- 2 黾一蚴2 1 ，式 f 3 1 4 1 季k ；口； 然后我们将正则表中的第p 个基列移至非基列的末端，而将第口个非基列移至基列 末端，并相应地调整有序集合如和j 若p = 8 ，则所得到的b j p ( s 一1 ) 已经是上 三角的；而当p s ，b 是上h e s s e n b e r g 矩阵，其p 列到8 1 列的次对角元非零，此时 通过g a u s s 消去或g i v e n s 旋转变换将该h e s s e n b e r g 矩阵化为上三角矩阵，并保证对角元 非零这时b j p ”或b 1 彤一是上三角且对角线元非零经过变换则可把变换得到 的矩阵重新较正为表( 3 9 ) 的形式 情形2 ：8 m 但o k 的第s + l 至第m 个元素不全为零显然，当且仅当o k 聋跪( b ) 时出现这种情形 在这种情况下，进基变量o k 的值不能从零增加，因为这样有可能破坏后一s ) 个约 束条件，因此必须增加基的列数我们对矩阵旧，b l 左乘h o u s e h o l d e r 反射变换矩阵。 将讯。的第s + 1 到第m 个分量化为零( 若这些分量存在的话) ，并将正则表( 3 9 ) 中的 第q 个非基列移至基的最末，并相应地调整有序集合如和j ，此时基增加一列，故 令8 = 8 + 1 。再用g u e s s 变换即可得到上三角矩阵b 1 r ( 1 ) ”此时原来的基本 可行解不变 在这两种情况下，显然b 的子分量0 2 并未改变，依旧为零当我们用g 8 u s s 变换将 新进基的列所对应的价值向量中的元素零化后，就产生了一张新的正则表这样我们就 完成了一次迭代的描述，重复这样的步骤，直至得到最优解或者问题无界 由于基的列数在情形1 中没有改变，而在情形2 中基列数增加了一列，故相应地迭 代分别称为保秩迭代和增秩迭代在整个计算过程中，基的列数会动态的增加，但不会 减少 衰南大学硕士学位论文 第三章 亏基的概念及亏基单纯形算法 1 2 我们将上述过程归纳为如下算法； 算法3 1 ( 亏基原始单纯形表格算法) 对于问题( 21 ) ，给定初始正则表( 3 9 ) 及相应的集合如和如，并假定由此导出的 基为可行基 1 如果i 0 ，则停止( 获得最优解) ； 2 据式( 3 1 0 ) 确定进基的列指标q ； 3 如果8 m 且q 7 a k q 的s + 1 至第m 个元素不全为零，转l l ； 4 由( 3 1 1 ) 式计算向量”； 5 若( 3 1 2 ) 式定义的集合i 为空集，则停止( 无界解) ； 6 按规则( 3 1 3 ) 确定步长d 及相应的行指标p ； 7 据式( 3 1 4 ) 修正基本可行解； 8 将( 3 9 ) 中的第p 个基列移出非基列，并将指标q 所对应的非基列放至基的最后， 相应的调整如和如； 9 若p s ，则将上h e s s e n b e r g 矩阵b 上三角化，并保证对角元非零； 1 0 转1 3 ； 1 1 若8 0 是摄动数 c t 刁 仇，t 是摄动数 显然，摄动后的问题是原始可行的，因此我们可以采用亏基原始单纯形算法的基本 架构求解 下面考虑某一次迭代定义列指标集 j = 0 1 7 b o ，j = 1 ，n 一8 ) ( 4 8 ) 奎童奎堂堑圭堂堡堡塞矍塑塞重董墼垫墼堡! 墼垦墨璧 1 5 若，为空集，则问题( 2 1 ) 已取得最优解现假设列标集，非空，即正则表( 4 4 ) 不 对偶可行，用d a n t z i g 列选主元规则确定进基指标如下。 q = a r g m i n - 2 k ji j 刀 ( 4 9 ) 显然有t 2 k 0( 4 1 0 ) 于是的第口个非基列o k 将进基，将其由知移至如的最后一列，相应地进基变 量为牙k 设陋，霄】是将的第q 列移至b 的最后得到矩阵，首先计算t = m 。k( 4 1 1 ) 其中”= t 坷r r ，显然有 雪= 阿叫= m ： 似- 。， 根据她的取值情况，会有如下两种情形之一发生，需要做不同的处理 情形l ：s o ( 4 1 7 ) 饥 。、 若妇 0 ，则( 4 1 7 ) 式成立此时，随着非基变量2 k 的值从零增加到。，其它非 基变量值保持不变，同时的值由x j l , 减为零，并且原始可行性保持不变这样就得到 了基本可行解i 的迭代公式， 瓢：2 勘t o l v l 2 1 ，8 ；( 4 1 s 、 z ：= 口； 正则表( 4 4 ) 作如下校正；将第p 个基列移至非基列末端，第q 个非基列移至基列末 端，并相应调整如和如若p = 8 ，则矾r 8 。( 一1 ) 已经是上三角矩阵；否则，巩是 上h e s s e n b e r g 矩阵，第p 到s 一1 列的次对角元非零利用g a u s s 变换将次对角元化为 零，与之相应的高斯矩阵为l 。l ，置换矩阵为只+ 1 ，则有 府= l a + 1 只+ 1 m ( 4 1 9 ) 府雪= 驴 ( 4 2 0 ) 其中驴m s 为一个对角元非零的上三角矩阵，经过变换则可把矩阵重新较正为正则 表 在整个计算过程中，基的列数动态的改变，但不会减少最后，用g u a s s 变换将进 基列所对应的价值系数化为零，就完成了一次迭代重复以上步骤，直至j 为空集，达 到对偶可行此时，川喻段过程完成 塞翼查堂堡圭堂堡篁圣塞里塞茎董堡垫塑堡! 墼垦塞堡 我们计算下式； 1 7 6 = m ( 4 2 1 ) 若620 ，则原问题取得最优解，否则，原问题达到对偶可行，可利用亏基对偶单纯 形算法求解( 若最优解存在) 我们将上述过程归纳为如下算法； 算法4 1 ( 亏基摄动对偶i 阶段算法) 给定常数琅 0 ，k = 0 ，初始正则表( 4 4 ) 及相应的如和山 1 若茁b 芝0 ，由( 4 7 ) 摄动，并令k = l ； 2 若研0 ； ( a ) 若k = 0 ，达到最优解，停止； ( b ) 若k = l ，达到对偶可行； 3 由( 4 9 ) 确定进基列标q ； 4 如果8 m 且i o 的元素不全为零，转1 2 ； 5 由( 4 1 5 ) 式计算向量 ； 6 若( 4 1 6 ) 式定义的集合i 为空集，则停止( 无对偶可行解) ； 7 按规则( 4 1 7 ) 确定步长o t 及相应的行指标p ； 8 据式( 4 1 8 ) 修正基本可行解孟； 9 将( 4 4 ) 中的第p 个基列移出非基列，并将指标q 所对应的非基列放至基的最后， 相应的调整如和西； 1 0 若p 8 ，则将上h e s s e n b e r g 矩阵b 上三角化，并保证对角元非零； 1 1 转1 3 ； 1 2 若s m 一1 ，通过对【b ，i6 】左乘适当的h o u s e h o l d e r 矩阵，将的第s + 2 至 第m 个元素化为0 ，并令8 = 8 + 1 ； 1 3 将( 4 4 ) 中的第q 个非基列进基，移至基列末端，并相应地调整如和如； 1 4 用g a u s s 变换消去； 1 5 转2 ； 1 6 根据( 4 ，2 1 ) 式计算6 ； 奎室奎竺塑圭耋篁篁塞篁里塞茎董堡垫塑堡! 墼垦丝鎏 1 8 1 7 若620 ，原问题取得最优解，否则达到对偶可行，可用亏基对偶单纯形法求解 由于基的个数有限，故若算法不出现循环，必将有限步终止此外，由于增秩迭代 不会产生循环，故循环只会出现在等秩迭代中若在等秩迭代中保证了非退化，则循环 情况就不会发生这样，就得到了如下结论： 定理4 2 在等秩迭代中的原始和对偶非退化假设下，算法4 1 终止于 ( )步骤( 2 ( 6 ) ) ，问题( 2 1 ) 获得对偶可行解；否则 ( i i )步骤( 6 ) ，问题无对偶可行解 证明：结论( i ) 证明见定理( 4 1 ，) 现设算法终止于步骤( 6 ) ，此时，为空集，即口0 设最终正则表为( 4 4 ) ，其对偶表格为 注意，该表格有可行解当且仅当原对偶规划( 2 2 ) 有可行解实际上，若( 矿，一) 是( 4 2 2 ) 的可行解，则它对偶可行解为( 矿，。7 ) ，其中矿由矿经一个可逆仿射变换得到，即存在 非奇异m m 矩阵q 和向量使矿= q 矿+ t 现假设( 4 2 2 ) 有可行解( 玩三) ，其中 i o ，而俨= ( 汀，西) ，此处孔彤及彘f p 一由它满足该表的前8 个约柬条件 得讥+ 孙= 0 或 醒丑= 一话( 4 2 3 ) 而由满足相应于磊。的约束条件得 审 砰，霹挎十= ( 4 2 4 ) 但”满足”= 丙1 e 。而霄2 白= 0 ( 见情形2 ) ，故上式可简化为 口7 玩+ 氟。= ( 4 2 5 ) 由该式，( 4 1 0 ) 和( 4 2 2 ) ，以及v 0 和话0 即得 z k 。= 氟口一口r 现= 氟口+ v t 珞 0 ( 4 2 6 ) 这与z 0 相矛盾故无对偶可行解( 证毕) o 豺。 坫n oo 程o 7 辫西 第五章数值结果及分析 5 1 数值试验 我们对得到的新算法进行了数值试验，其中编制了三个程序： c l s ： 传统原始两阶段单纯形算法； c d p s ：亏基原始单纯形算法； d p d s ：亏基摄动对偶i 阶段算法； 以上的程序用标准c 语言编写，在w i n d o w s9 8 操作系统上用m i c r o s o f tv i s u a l c + + ( v e r t i o n6 0e n t e r p r i s ee d i t i o n ) 进行编译、调试数值试验所使用的计算机为m m p e n t i u mh i6 6 6 m h z 的兼容机，内存2 s 6 m b y t e s ，机器精度为3 2 位所有的程序均以 = 1 0 - 6 为原始和对偶可行容限为了增加程序的数值稳定性，都采用了h a r r i s 主元规 则，并在其中取6 = 1 0 - 8 这两个程序都使用了均衡尺度( s c a l i n g ) 的技术 我们用于测试的2 4 个问题都是n e t l i b 标准问题表5 1 给出了用传统的原始两阶段 单纯形算法( c l s ) 来测试这些问题所得到的结果在表格的第一列列出了问题的名称， 第二三，四列分别列出其行数m ，列数n ，行列之和m + n ；最后一列是总的迭代次 数表5 2 ，表5 3 分别给出亏基原始单纯形算法( c d p s ) 和新算法( d p d s ) 求解这2 4 个 问题所得到的结果为了对c l s ，c d p s 、d p d s 进行了比较，在表4 中列出总迭代次 数的比值c l s d p d s ，c d p s d p d s 在表中还列出了m + n 的值以看出问题的规模 在表5 4 中，有2 1 个问题的求解c d p s 比c l s 的迭代次数减少了，只有3 个问题 的迭代次数增加了而有2 0 个问题d p d s 比c d p s 在迭代次数方面得到了改善，只有4 个问题的迭代次数增加了其中c l s 和c d p s 所需总迭代次数之比为1 7 7 ，其中最高达 到了9 2 6 ( 求解b e a c o n f d ) ；而c d p s 和d p d s 所需总迭代次数之比为1 5 0 ，最高达 到9 8 6 ( 求解s c 2 0 5 ) 这就是说，新算法明显地减少了求解问题所需的迭代次数这样的 结果并不出人意料之外个可能的解释是t 基于亏基的新算法可以形成较好的搜索方 向，而且容许在基矩阵成为方阵之前即达到原始可行或最优试验结果给了我们极大的 鼓舞，使我们有信心改进新算法。使之适用于求解大规模稀疏问题并取得出色的效果 圣童奎耋堡圭兰堡堕圣篁三塞 鍪堡堑墨垒塞坌堑 2 0 表5 1 ： c l ss t a t i s t i c e p r o b l e m m + ”i t e r a f i r o2 73 25 92 9 s c 5 0 b5 04 89 85 9 s c 5 0 a5 0 4 89 85 7 a d l i t t l e5 69 7 1 5 31 2 8 b l e n d7 48 31 5 7 1 1 5 s h a r e 2 b9 67 91 7 5 1 9 6 s c l 0 51 0 51 0 3 2 0 81 2 3 s t o c f o r l1 1 7i i i 2 2 81 7 4 s c a g r 71 2 91 4 0 2 6 91 8 1 i s r a e l1 7 41 4 2 3 1 65 1 3 s h a r e l b1 1 72 2 53 4 2 3 0 9 s c 2 0 52 0 52 0 34 0 8 2 6 2 b e a c o n f d1 7 32 6 24 3 52 1 3 l o t f i 1 5 33 0 84 6 13 4 8 b r a n d y 2 2 02 4 94 6 93 5 6 e 2 2 62 2 3 2 8 25 0 56 1 5 a g g4 8 8 1 6 36 5 16 4 0 b a n d m3 0 54 7 2 7 7 76 7 4 s c t a p l3 0 04 8 0 7 8 04 8 0 s c f x m l3 3 0 4 5 77 8 75 9 5 a g g 25 1 63 0 2 8 1 88 2 3 a g g 35 1 63 0 28 1 8 8 3 9 s c s d l7 77 6 08 3 7 1 9 5 s c a g r ，2 54 7 15 0 09 7 19 1 1 t o t a l5 3 2 96 2 0 61 1 5 3 5 8 8 3 5 奎童查兰堑圭堂堡垒圣塞至兰墼堡垫墨垒苎坌堑 2 1 表5 2 ：c d p ss t a t i s t i c e p r o b l e mm + ni t e r a f d2 73 2 5 9 2 5 s c 5 0 b5 04 8 9 8 6 0 s c 5 0 a5 04 89 85 9 a d l t l e5 69 71 5 31 3 0 b l e n d7 48 3 1 5 7 1 2 0 s h a r e 2 b9 6 7 9 1 7 51 7 6 s c l 0 51 0 51 0 32 0 81 3 1 s t o c f o r l1 1 71 1 12 2 81 4 5 s c a g r 71 2 91 4 02 6 91 9 7 i s r a e l1 7 41 4 23 1 63 9 3 s h a r e l b1 1 72 2 53 4 22 8 7 s c 2 0 5 2 0 5 2 0 34 0 82 8 6 b e a c o n f d1 7 32 6 24 3 51 4 0 l o t f l 1 5 3 3 0 84 6 1 2 7 1 b r a n d y 2 2 02 4 9 4 6 9 3 7 0 e 2 2 6 2 2 32 8 25 0 5 6 7 2 a g g4 8 81 6 3 6 5 1 5 6 1 b a n d m3 0 64 7 27 玎6 3 2 s c t a p l3 0 04 8 07 8 0 3 7 4 s c f x m l3 3 04 5 77 8 75 1 9 a g g 25 1 63 0 28 1 86 6 5 a g g 35 1 6 3 0 1 2 8 1 86 8 9 s c s d l 7 7 7 6 08 3 7 9 0 s c a g r 2 5 4 7 1 5 0 09 7 18 5 3 t o t a l5 3 2 96 2 0 61 1 5 3 5榔 垄童奎兰堡圭堂垒篁塞 篓圣耋 墼堡垒墨垦塞坌堑 2 2 袭5 3 ：d p d ss t a t i s t i c e p r o b l e mi t e r a f m o2 7 3 2 5 91 6 s c 5 0 b5 04 89 84 6 s c 5 0 a5 04 89 89 a d l i t t l e5 69 71 5 3 9 6 b l e n d7 4 8 31 5 7 7 1 s h a r e 2 b9 67 91 7 5 1 1 9 s c l 0 51 0 51 0 32 0 81 0 6 s t o c f o r l1 1 71 1 12 2 85 6 s c a g r 71 2 91 4 0 2 6 9 9 1 i s r a e l1 7 41 4 2 3 1 6 4 9 8 s h a r e l b1 1 72 2 53 4 22 5 6 s c 2 0 52 0 52 0 34 0 82 9 b e a c o n f d1 7 32 6 24 3 52 3 l o t f i1 5 33 0 84 6 1 2 5 3 b r a n d y2 2 02 4 94 6 9 4 3 i e 2 2 62 2 3 2 8 2 5 0 5 4 3 0 a g g4 8 81 6 36 5 1 1 7 6 b a n d m3 0 5 4 7 27 7 74 6 6 s c t a p l3 0 0 4 8 07 8 01 7 3 s c f x m l3 3 0 4 5 77 8 76 0 5 a g g 25 1 6 3 0 28 1 81 0 9 a g g 35 1 6 3 0 28 1 81 3 1 s c s d l7 7 7 6 08 3 73 6 6 s c a g r 2 54 7 15 0 09 7 14 1 9 t o t a l5 3 2 96 2 0 6 1 1 5 3 5 4 9 8 5 奎室查竺堡圭堂堡垒圣量圣翼墼堡篁量垦基坌堑 2 3 表5 4 ：c l s d p d s ，c d p s d p d s 的数值结果 p r o b l e mm + nc l s d p d s c d p s d p d s a f 的5 91 8 11 5 6 s c 5 0 b9 8 1 2 81 3 0 s c 5 0 a9 86 3 36 5 6 a d l 】：t t l e1 5 3 1 3 3 1 3 5 b l e n d1 5 7 1 6 2 1 6 9 s h a r e 2 b1 7 51 6 5 1 4 8 8 c 1 0 5 2 0 8 1 1 6 1 2 4 s t o c f o r l 2 2 8 2 ，6 4 2 2 0 s c a g r 72 6 91 9 92 1 6 i s r a 】弛3 1 61 0 30 7 9 s h a r e i b 3 4 2 1 2 l1 1 0 s c 2 0 5 4 0 8 9 0 3 9 船 b e a c o n f d4 3 59 2 66 0 9 l o t f l4 6 11 3 81 0 7 b r a n d y4 6 90 8 30 8 6 e 2 2 65 0 51 4 31 5 6 a g g 6 5 l 3 6 43 1 9 b a n d m7 7 71 4 51 3 6 s e 工：a p l7 8 02 7 7 2 1 6 s c f x m l 7 8 7 0 9 8 0 踯 a g g 28 1 87 5 56 1 0 a g g 38 1 86 4 05 2 6 s c s d i8 3 70 5 30 2 5 s c a g r 2 59 7 12 1 72 0 4 t o t a l1 1 5 3 51 7 71 5 0 东南大学硕士学位论文第五章 数值结果及其分析 2 4 5 2进一步研究方向 综上所述，新算法是一个充满希望值得进一步深入研究的算法该算法将摄动方法 和亏基算法相结合，具有非常吸引人的特色，并有可改进之处： 1 研究改进主元规则进一步提高效率； ( i ) 研究在新算法中采用最钝角行主元规则以降低每次迭代的计算复杂性，并借以发 挥最钝角规则实际效果好的优点取得更高的效率 ( i i ) 研究将最陡边主元规则应用于新算法以进一步减少迭代次数 2 研究用稀疏数据结构实现算法 5 3本文创新之处 本文首次将亏基和摄动方法相结合，在亏基这一新的架构下引入原始摄动单纯形算 法，以充分发挥两种算法的优势，有效地克服退化的影响，减少迭代次数，提高算法效 率数值试验表明，亏基摄动对偶i 阶段算法的效率不仅远远优于传统单纯形法，也优 于原有的亏基单纯形法，是非常令人鼓舞的 致谢 首先感谢我的导师潘平奇教授，他以启发式教育模式教导我们，使我的思维有了新 的飞跃和提高；潘老师渊博的知识，严谨的治学态度，敏锐的洞察力，坦荡的胸襟以及 谦逊的学者风范，让我耳濡目染，终身受益研究生学习期间，潘老师为我的学习，研究 提供了一切优越的条件环境、发展空间与机会；生活上无微不至的关怀更是让我倍感 温暖本文从选题、文献的收集到论文的写作以及最终定稿，同样也凝聚着潘老师的智 慧、心血和汗水在此，谨向我的导师致以最崇高的敬意和最衷心的感谢! 感谢数学系各位老师在我的学习期间给予我的教导和帮助从他们那里，我学到了 很多知识，为本篇论文的完成打下了坚实的基础 我还要感谢我的师兄李炜教授、闰安和胡剑锋、师姐吴建专、我的搭档岳红伟、颜 红彦，