(运筹学与控制论专业论文)线性规划的最钝角松弛算法.pdf_第1页
(运筹学与控制论专业论文)线性规划的最钝角松弛算法.pdf_第2页
(运筹学与控制论专业论文)线性规划的最钝角松弛算法.pdf_第3页
(运筹学与控制论专业论文)线性规划的最钝角松弛算法.pdf_第4页
(运筹学与控制论专业论文)线性规划的最钝角松弛算法.pdf_第5页
已阅读5页,还剩31页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 潘平奇教授给出了线性规划问题最优基的个启发式特征刻划( 最钝角原理) ,引入反 映目标梯度与约束梯度夹角大小的“主元标”作为确定变量进基优先性的依据( p a n ,1 9 9 0 ) 本文先基于最钝角原理略去部分约束条件,用原始单纯形算法求解由此得到的一个规模 较小的松弛子问题;然后再添加原先所略去的约束条件恢复原问题;此时若全部约束条 件均满足则已获得一个基本最优解,否则用对偶单纯形算法继续求解得到基本最优解 我们的初步数值试验表明,与传统两阶段单纯形算法相比,本文提出的算法可很有 效地减少迭代次数;由于其中用于较小松弛子闯题的迭代占很大比重,从而就大大降低 了求解线性规划问题所需要的c p u 时间,新算法对于大规模问题的求解有明显的潜在优 势,是一种非常有前途的新算法 关键词t 线性规划单纯形法最钝角主元标放松问题 a b s t r a c t p r o f e s s o rp i n g - q ip a ng a v et h eh e u r i s t i cc h a r a c t e r i z a t i o no ft h eo p t i m a lb a s i s ( t h ep r i n c i p l e o ft h em o s to b t u s ea n g l e ) a n dp u tf o r w a r dt h ec o n c e p to f ”p i v o t i n gi n d e x ( p a n ,1 9 9 0 ) t h e p iv j o t i n gi n d i c e sc a nr e f l e c tt h ea n g l e sf o r m e db yt h eg r a d i e n t so ft h ec o n s t r a i n t sa n dt h o s eo f t h eo b j e c t i v ef u n c t i o n ,a n dt h e yc a r lb et a k e ne st h eb a s e st od e c i d et h ep r i o r i t yo ft h ee n t r a n c e o ft h ev a r i a b l et h i sp a p e ro m i tp a r to ft h ec o n s t r a i n t sf i r s t l y , 8 0w ec a ng e tar e l a x a t i o np r o b l e m w i t hs m a l l e rs c a l e ,w ec a nu 8 es i m p l e xm e t h o dt os o l v ei t ,t h e na d du pt h ec o n s t r a i n t so m i t t e d b e f o r et or e s n n l et h ep r i m a lp r o b l e m ;i fa l lt h ec o n s t r a i n t sa r em e t ,t h e nw eg e tab a s i co p t i m a l s o l u t i o n o t e r w i a s w ec o n t i n u et os o l v ei tw i t hd u a ls i m p l e xm e t h o dt og e tt h eb a s i co p t i m a l s o l u t i o n o u rp r e l i m i n a r yc o m p u t a t i o n a lt e s t ss h o w c o m p a r e d 谢t ht h ec o n v e n t i o n a lp h a s et w os i m - p l e xm e t h o d ,t h ea l g o r i t h mp u tf o r w a s di nt h i sp a p e rc a nr e d u c et h ei t e r a t i o n sv e r ye f f e c t i v e l y b e c a u s et h ei t e r a t i o n sw h i c ha l eu s e dt os o l v et h er e l a x a t i o np r o b l e mt a k et h em o s tp a r ta m o n g t h e s ei t e r a t i o n s ,t h ea v e r a g ec p ut i m en e e d e di no n ei t e r a t i o nc a nb er e d u c e dg r e a t l y f o rt h e p r o g r a m sw i t hl a r g es c a l e s ,t h en e wa l g o r i t h mh a st h ep o t e n t i a la d v a n t a g e ,i ti sav e r yp r o m i s i n g a l g o r i t h m k e y w o r d s :l i n e a rp r o g r a m m i n gs i m p l e xm e t h o d t h em o s to b t u s ea n g l e p i v o t i n g 东南大学学位论文 独创性声明及使用授权的说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果尽我所知,除了文中特别加以标明和致谢的地方外,论文中不包含其他人已经发表 或撰写过的研究成果,也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意 二、关于学位论文使用授权的说明 东南大学,中国科学技术信息研究所国家图书馆有权保留本人所送交学位论文的 复印件和电子文档,可以采用影印、缩印或其他复制手段保存论文本人电子文档的内 容和纸质论文的内容相一致除在保密期内的保密论文外,允许论文被查阅和借圆,可 以公布( 包括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生 院办理 函匠地 第一章引言 线性规划是产生较早,影响最深远和应用最广泛的一个运筹学分支历经半个多世 纪的发展,其理论巳日臻成熟,并已成为国民经济,科学技术,管理和工程等诸多领域 不可或缺的数学工具 线性规划主要经历了如下三个里程碑式的发展: 1 1 9 4 7 年,g b d a n t z i g 在文【1 】1 中首次提出了求解线性规划问题的单纯形算法, 标志着这一学科的创立此后,线性规划如雨后舂笋般得到了迅猛的发展与此同时, 单纯形算法也取得了巨大的发展,其理论也日趋成熟与完善虽然单纯形算法的时间复 杂性是指数阶的,然而它在实际应用中却取得了显著的效果后来,b o r g w a r d t 和s m a l e 都证明了单纯形算法的平均运算次数是多项式级的因而一直以来,不论在理论上还是 在实际计算中,单纯形算法都是极其重要的 2 1 9 7 9 年,苏联青年数学家啥奇扬提出了第一个多项式时闻复杂性算法一椭球算 法( 文【3 1 ,1 4 】) ,从而证明了线性规划问题确实存在多项式时间算法因此,椭球算法 从理论上说是个重要的突破但遗憾的是广泛的实际检验表明其计算效果比单纯形算法 差,因而它还不能在实际使用方面取代单纯形算法 3 1 9 8 4 年,k a r m a r k a r 在文 5 】中提出了求解线性规划问题的另个具有多项式时 间复杂性的算法- - k a r m a r k a r 算法理论上,k a r m a r k a r 算法计算复杂性的阶比椭球算 法有所降低,且实际效果好得多,因而引起了学术界的广泛关注,从此掀起了一股内点 法研究的热潮许多学者曾认为,对于中小型线性规划问题而言,内点算法稍逊于单纯 形算法;而对于大型稀疏线性规划问题,前者则胜于后者然而近年来单纯形类算法也 有重要进展,使这两类算法形成了不相上下难分胜负的局面特别是在求解整数规划问 题上,单纯形类算法目前尚是不可替代的 本文提出算法属于单纯形类算法,致力于进一步减少迭代次数提高效率对于大规 模线性规划问题,通过减少约束条件来降低其规模似乎是一种很吸引人的想法事实上 这并不是个新想法,如在( 4 0 】中介绍的“松弛算法。就基于此该算法的基本做法是先 取其中部分约束条件求解,得到最优解之后判断其是否为原问题的最优解;若不是, 东南大学硕士学位论文 第二章单纯形算法 2 就换一些约束再次求解,如此重复直至求出原问题的最优解为止这样一来可以求解规 模较小的子问题然而该方法略去和加入约束都带有很大的盲目性,以至于可能增加所 需要的迭代次数那么究竟应该略去哪些约束条件好呢? 显然,如果预先就知道哪些约束是最优解处的积极约束,那么只要略去那些非积极 约束,就可以立即求出问题的最优解可惜我们事先并不知道尽管如此,潘平奇教授给 出的最优基的启发式特征刻划( 最钝角原理) ( 1 9 9 0 ) ,为我们提供了一个很好的出发点 他引入的反映目标梯度与约束梯度夹角大小的“主元标”可以作为确定略去或保留约束 的依据最钝角原理正是新的松弛算法建立的基础 我们对新算法编写了f o r t r a n 程序,并进行了初步的数值试验对6 0 个问题的所做 的检测表明,与传统两阶段单纯形算法相比,本文提出的算法可非常有效地减少迭代次 数;而由于其中用于较小松弛子问题的迭代占有相当大的比重,从而大大降低了所需要的 c p u 时间鉴于对于大规模问题的求解更显其潜在优势,新算法的确是菲常有前途的 本文的主要框架如下:第二章给出本文所用的一些记号,简述单纯形法的基本概念 和定理以及单纯形算法和对偶单纯形算法的基本步骤;第三章介绍最优基的启发式特征 刻划和主元标;第四章给出了最钝角松弛算法;最后一章报告了我们的数值试验结果, 并将传统单纯形算法和新算法进行了比较和分析 第二章单纯形法 2 1 基本概念和定理 本节我们简单地介绍具体实施单纯形算法的基本理论及相关概念 准线性规划模型 m i nc r x s t , 4 x = b 我们考虑如下标 ( 2 1 口) ( 2 l b ) 0 20 ( 2 1 c ) 其中a j p 一,c 、z 丹,b c t = 称为该线性规划问题的目标函数,式 ( 2 1 b ) ,( 2 1 c ) 称为约束条件 此外,我们还作如下规定t 吩 的第j 列; c 第t 个分量为1 的单位向量; 叶 向量的第j 个分量; 狞( )矩阵的域空间; j 单位矩阵; 矩阵用大写的英文字母a ,b ,l ,u 等表示; 列向量用小写的英文字母a ,b ,c 等表示 定义2 , 1 设b 为矩阵a 中的个m 阶满秩方阵,则称b 为个基( b a s i s ) ;b 中 m 个线性无关的列向量称为基向量( b a s i sv e c t o r ) ;$ 中与之对应的m 个分量称为基变量 ( b a s i sv a r i a b l e ) ,其余的变量称为非基变量令所有的非基变量取值为零,得到的解z , 。七 - b - 。b 称为相应子b 的基本解( b a s i cs o l u t i o n ) 定义2 2 若个基本解满足z20 ,即其也是一个可行解,则称。为个基本可行 解( b a s i cf e a s i b l es o l u t i o n ) ,这时对应的基b 称为可行基( f e a s i b l eb a s i s ) 东南大学硕士学位论文 第二章单纯形算法4 定义2 3 一个基本可行解。,如果其所有的基变量都取正值,则称之为非退化的 ( n o n d e g e n e r a t e ) ;反之,如果有的基变量也取零值,则说其是退化的( d e g e n e r a t e ) 一个 线性规划问题,如果它的所有基本可行解都是非退化的,就称该问题是非退化的,否则 就说它是退化的 定义2 4 一个基本可行解。,如果满足式( 2 1 a ) ,则称之为线性规划问题的最优 解;相应的目标函数值,z 称为线性规划问题的最优值 关于解,基本解、基本可行解等概念之间的关系,我们有下面的基本结论t 定理2 5 可行解z 是基本可行解的充分必要条件是其正分量所对应的列向量线性 无关 定理2 6 若个标准的线性规划问题有可行解,则其必有基本可行解 定理2 7 若一个标准的线性规划问题的目标函数有有限最优值,则必可在某个基本 可行解处达到 根据定理2 7 ,我们在本文中有如下定义: 定义2 8 与最优解相关联的基变量称为最优基变量,与最优解相关联的非基变量称 为最优非基变量 上面的定理说明,对于标准的线性规划问题,若其存在有限最优值,则我们可以在 基本可行解的集合中去寻找最优解然而当矩阵的列数n 很大时,基本可行解的个数比 较大,枚举法显然是不可取的。单纯形算法则是依照一定的规则在基本可行织的一个子 集中去寻找最优解下面介绍单纯形算法的相关理论 2 2 原始单纯形算法 单纯形算法的主要思想是,从一个基本可行解开始,先判定其是否为最优解若是最 优解则停止否则,沿某边方向到达另一个基本可行解,再进行判定如此迭代进行,直 至找到最优解,或判定其无界下面我们就来介绍究竟如何判断是否是最优解、无界, 怎样进行迭代、判定假设我们已有一个非退化的基本可行解; z 七 。, 对应的基矩阵为b ,非基矩阵为j v ,并设基变量下标集为如,非基变量下标集为j , ,= 旧,舀1 。则式( 2 1 b ) 可化为; 。b + b 一1 n x = b l b 不妨设b = ( a l ,口,i ) 记向量 五j = b 一1 q = ( a 玎,嘞) ,j = 1 ,一,竹 以及 则式( 2 3 ) 化为: 或 5 = b 一1 b = ( 5 1 一,k 尸 霄:b 一1 n z b + n z n = b 目标函数化为。 如= 晶5 + 妈一晶毛) 令白= 勺一西弓,j = 1 ,n ,则有 e t = ,一西b 一1 a = ( n ,岛) = ( 疆,商) = ( o ,西一r b 坷衄) 则问题( 2 1 ) 可化为 r a i n 最君- 1 b + c r s t z b + b l n z = b 一1 b z 0 定理2 9 如果2 使得式( 2 5 a ) 中( 0 ,则雪为原问题的最优解 5 ( 2 3 ) ( 2 4 ) ( 2 ,蚴 ( 2 5 6 ) ( 2 s o ) 东南大学硕士学位论文第二章单纯形算法 6 定理2 1 0 如果式( 25 a ) 中向量 有分量靠 o ( 显然m + l ksn ) ,而向量 钆0 ,则原问题无界 定理2 1 1 如果式( 2 5 a ) 中向量( 有分量“ 一 i | 一 卅划 0 0 k z 生 z 东南大学硕士学位论文第三章 最优基随塞塞塞赞征刻划及主元堡 9 考虑线性规划问题 2 3 对偶单纯形算法 ( 2 8 n ) ( 2 8 6 ) z 0( 2 8 c ) 定义2 1 2 设。o 是( 2 8 ) 的个基本解,它对应的基矩阵为b ,记 = c b b ,若 ”是( 2 8 ) 的对偶问题的可行解,即对所有的j 有”0 一勺0 ,则称x 0 为原问题的对偶 可行解 最优性的判别;已知线性规划问题的一个基矩阵b 及与它对应的基解为( x b ,0 ) 丁, 并且此基解的所有判别数非正若x b = b _ 1 b 0 ,则所得到的基解为最优解 设单纯形表在对偶可行时,右端向量为5 = b - 1 6 ,若5 中有正分量,则我们有如下 选主元规则一 若 瓦= m l n 面i 匠 o ) , 则选择其对应变量z ,为出基变量 确定进基变量t 若 以= 咧警i 叼 0 ( 3 1 1 ) 注意到,对充分小的q 0 , x ;矿+ a y 满足后n 十m p 个约束此外,利用a 0 ,( 3 8 ) 和( 3 9 ) 我们有 a x = a x + 口a y 2b( 3 1 2 ) 西; h ;b 塞童查兰堑圭兰堡垒奎 篁三塞里垡董墼塞垄塞丝堡型型垦圭重堡 1 5 利用o t 0 和( 3 1 1 ) 式,我们有 = c r + a c y ( 3 1 3 ) 也就是说。这一可行解,其对应的函数值比口。大,这与r 是最优解矛盾所以, 对任何满足( 3 9 ) 的y ,( 3 1 0 ) 都成立于是,由f a r k a 8 引理,我们知存在个p 维列 向量 p = ( p 1 ,脚) r 0( 3 1 4 a ) 使得 c = 一且7 p( 3 1 4 b ) 将( 3 1 4 b ) 两端同乘以c ,利用( 3 1 4 a ) 和主元标的定义,可得 0 0 ,对任意i = 1 ,r n l ,有,啦 0 ,则结 论显然成立于是,我们可以较容易地证明向量z = a c 是可行解,这里 a 丘= 【 l ,瑟 去) ) o 在z 点处,目标函数值a c r e 是无界的 上面的推论有时会比较有用例如。以例子2 来说,我们根本无需运用单纯形法, 因为从上面我们在约束条件后列处的主元标全为非负的这一特点中,我们就能得出目标 函数在可行域上是无界的这一结论 茎童奎兰塑圭兰篁篁塞 篁三塞 塞矍鱼丝塑堡篁 1 6 现在我们简单地讨论一下把结论i 应用于单纯形法的可能性我们从任意一个单纯 形表格开始( 以典式形式,不必可行) 在一步迭代中,我们在所有基变量中挑选具有最 小可能主元标的变量出基,在所有非基变量中,我们选择具有最大主元标的变量进基( 假 设对应的主元菲零) ,形成一个新的表格,这种循环一直进行下去,直到m 个基变量所 对应的主元标是前m 个最大的那个表格出现为止如果这个表格是不可行的,我们通过 一阶段使其达到可行,然后象往常一样用第二阶段得到最优解 第四章最钝角松弛算法 4 1 松弛算法 本章中我们考虑的是如下形式的线性规划问题: ( 4 1 n ) 5 t a :r b【4 1 b ) z 0( 4 1 c ) 其中a j p 一,c ,善舻,b j p ,并且b 20 ,b ,z ,c 的分量不全为零 关于松弛算法,已有学者提出过( 例文1 4 0 】) ,下面为了和我们即将在下一节介绍的 算法作个比较,在本节中我们把 4 0 1 中介绍的算法列出 如果问题( 4 1 ) 的约束条件个数m 很多,为了计算方便,可以先取其中一部分约束 条件求解,求得最优解之后判断此最优解是否为( 4 1 ) 的最优解若不是,就换一些约束 再求解,直至求出( 4 1 ) 的最优解 令m = 1 ,m ) ,r m ,构造一放松问题 咖:,z 8 t 毋z 如a r )( p r ) 文献【4 0 】中所描述的松弛算法的计算步骤如下t 0 0 置2 = 一。,挑选一个初始曲r ,使放松问题( p r ) 的目标函数值有下界 1 0 求解放松问题( p r ) 若( p r ) 无解,则原问题( 4 1 ) 无解,停止;否则设( p r ) 的 最优解为矿,最优值为勾 2 0 若铲满足a z b ,则。r 也是( 4 1 ) 的最优解,停止;否则令 妒v s a i 扩 6 ,t m r 1 7 束南大学硕士学位论文 第五章 最钝角松弛算法 1 8 d = i id 铲 乏,则主一印,再以刷= ( r d ) u v 代替原哭的曰,返回l o 4 2 最钝角松弛算法 本节中,我们同样考虑线性规划问题( 4 1 ) 对于上一节中给出的算法,我们不免要考虑这样的问题: 1 在o o 中,如何挑选一个初始的r ,使得( p 的目标函数值有下界; 2 在2 0 ,3 0 ,4 0 中,算法能否不比较函数值,不需删去约束就能进行 鉴于此,我们将第三章中介绍的主元标引入,不过与第三章中的主元标稍微有些不 同的是,在本文中,我们对于z 0 的约束不给予主元标的定义,我们定义 q = 黑,江1 ,m ( 舭) q 2 厕”1 ” 阱) 为第i 个约束的主元标 由第三章我们受到启发,我们把所有主元标为负值的那些约束挑出,即左端函数的 梯度方向与目标函数的下降方向成最钝角的那些约束条件构造放松问题( p 8 ) m 伽z ;,o 8 t a t x s 玩a 固 z o 之后我们用原始单纯形算法求解此放松问题,得到一个最优解,然后判断此最优解是否 满足原问题的约束条件若满足,则此解就是原问题的最优解否则,我们再把那些原 先所略去的约束条件添加到此放松问题中,恢复原问题,因在放松问题中我们的迭代表 格是对偶可行的,故我们用对偶单纯形算法继续求解便可得到原问题的基本最优解。 我们构造的放松问题( p 8 ) 在绝大多数情况下是有界的,但有时也会出现无界的情 况对于这种情况,我们的解决办法是加入一个人工约束 f $ f m( 5 2 ) 奎室奎耋堡圭堂堡篁塞 量垂塞墨堡垒堡矍篓鎏 1 9 这里m 为一个充分大的数,j 为( p r ) 问题中的非基变量的下标,然后求解新的放松问 题 r a i n。= ,z 8 ,毋z 6 tu r ) ( p 科) x j s m z 0 虽然我们理论上是把所有主元标小于0 的约束条件挑选出,但在实际计算中,我们 可以引进一参数6 ,其中6 为一较小的正数参数引进后我们可以把主元标小于- 6 的 那些约束条件保留,这样通过调整参数5 ,我们就能有所选择以上我们介绍的整个过 程可归纳为最钝角松弛算法( m o s t - o b t u s e - a n g l er e l a x a t i o na l g o r i t h m ) t m r a l 算法 1 0 用( 5 1 ) 武计算各约束条件的主元标啦,i = l ,m ,将主元标为负值的那些约 束条件挑出,记r ;a l 啦 o 2 0 求解放松问题( p 8 ) 若( p r ) 无解,则原问题( 4 1 ) 无解,停止;否则设( p 且) 的 最优解为z r ;若( p r ) 无界,则我们求解问题( p 碍) ,得最优解护 3 0 着z 五满足a x sb ,则。足也为“1 ) 的最优解。停止;否则进行下一步; 4 0 将所有剩余的约束条件r 即主元标非负的那些约束) 全部加到放松问题( 2 ) 上, 进行新的求解,也就是对改变约束条件顺序后的原问题进行求解 下面我们介绍的m r a 2 算法与m r a l 算法基本相同,唯一不同的就是选择哪些约 束需要保留的规则不同 在m r a 2 算法中我们以如下公式来代替m r a l 算法中的步骤1 0 中的r , r = 川啦 0 ,而且所有的n i 0 k “ 我们假设r 中有m 1 个元彖我们把人工约束( 5 2 ) 先引入一松弛变量x 。+ r n l + l ,将 其化为等式 巧十z 。慨+ 1 = m ( 5 3 ) 后加到问题( p 8 ) 上形成一个耨的表格此时,我们选变量z 。,+ ,出基,x k 进基进行 迭代,因+ 。,扎= 1 ,故将单纯形表中的n + “1 + 1 行元素同乘以一味,i j b ,加到 前m - 行,将第列对应元素化为0 ,然后同乘以- 靠加到检验数一行因人工约束一行 中非基变量对应的系数均为1 ,其余元素均为0 ,故同乘以一靠加上之后,变量z k 对应 的检验数为0 ,而其余检验数均为非正数,所以此时便可达到最优 此外,还有几点需要说明: 说明i ;对于放松同题,可以用任何一种方法求解在我们后面的程序中,我们应 用的是( 2 2 ) 节介绍的传统的两阶段单纯形法 说明2 ;在对放松问题求解结束之后,因检验向量保持不变,故在求解改变约束条 件顺序后的原问题时,用我们在( 2 3 ) 节介绍的对偶单纯形法求解即可 说明3t ( m r a ) 算法从总体上可分为两个阶段t 第一阶段求解一个放松问题,第二 阶段求出最优解,所以此算法可以认为是求解线性规划问题的一种新的两阶段方法 说明4 ,以上我们考虑的问题是( 4 1 ) 形式的问题下面我们将说明,对一个标准形 的l p 问题 r a i nc 正 s t a x = b o 0 我们总可以找到一个基矩阵,将其中的等式化为( 41 ) 问题中的形式 设b 为a 的一个基矩阵,n 为非基矩阵,c 与x 中相应的两部分分别为印,c n 和 z b ,x n ,则a x = b 可化为 $ b + b 一1 n x = b 一1 b 奎堕奎竺堡圭兰堡垒塞 墼奎耋墼堡堡塞一 代入目标函数得 z ;c b z b + c n z n = c b ( b 一1 b b 一1 n x n ) + c ,$ ;c b b i b f c b b 一1 n c n ) x l v 于是原问题可化为 r a i nz = c b b b f c b b n c n ) m n 8 t b 一1 z b 一1 b 20 这样就把标准形的l p 问题转化为具有( 4 i ) 形式的问题了 第五章数值试验 5 1 数值试验结果及结论 前一章我们阐述了最钝角松弛算法的迭代步骤为了进一步了解算法的实际表现, 我们进行了初步的数值试验和比较本章中将报告数值试验所得到的有关结果并进行相 应的分析 我们试验了如下f o r t r a n 程序: c l s 。两阶段单纯形算法 m r a i ;最钝角松弛算法1 ;其中保留主元标小于一j 的约束而略去其余这里取 j = 1 0 一 m r a 2t 最钝角松弛算法2 ;其中保留主元标满足条件 剧,型? 。q 的约束而略去其余这里取口= 0 0 0 1 以上的程序在w i n d o w s 9 8 操作系统上利用v i s u a lf o r t r a n9 0 环境进行编译和运行 数值试验所使用的计算机为i b mp e n t i u mi i i6 6 6 m h z 的兼容机,内存2 9 6 m b y t e s ,机器 精度为3 2 位所有的程序都以e = 1 0 - 6 为原始和对偶可行容限,都采用了h a r r i s 主元规 则,并在其中取对主元的绝对值不低于6 = 1 0 一 我们测试了6 0 个l p 问题表l 给出了用以上三种算法得到的数值结果( 表2 是表1 的继续) 表格的第二,三、四列分别列出问题的行数m 、列数n 及行列数之和r e + n ( 问 题的规模) 第五,六两列分别列出用最钝角松弛算法m r a l 所需的总迭代次数和求解 放松子问题所用的迭代次数第七、八两列分别列出用最钝角松弛算法m r a 2 所需的总 迭代次数和求勰放松子问题所用的迭代次数第九、十两列分别为用两阶段单纯形算法 c l s 所需的总迭代次数和第一阶段所用的迭代次数 表3 ( 袁4 是表3 的继续) 给出了求解全部问题传统的单纯形算法与m r a l ,m r a 2 所用迭代次数之比 壅堕奎耋堡圭堂堡垒苎塞奎童墼堡塑 2 3 t a b l e1 数值结果 m r a lm r a 2c l s p r o b l e m m + ni t e r si t e r s ri t e r si t e r s ri t e r si t e r s l 132 5202133 244 8 76 3264 3 44820425 4 45 4940526 5 51 031 310 321 01 0 6 34766226 3 7821 03031 77 81 241 699 6 3 1 31 2 944853 6265 1 01 031 31 11 1 321 01 0 1 152 7 33 2165 1 21 241 6 g 9 631 31 2 1 354 9515187 1 4 4 482o4254 1 54 2620324 3 1 6661 25o 7777 1 7459533 155 1 8358 4o3143 1 9841 2 1o221 01 0 2 0 448 324l64 2 1 4481 11 l211 1 6 2 236920 1122 2 3448432l6 4 2 425720 2132 2 52 5 7 3 33232 2 625 7223222 2 774 1 120311 08 船74 1 12o3286 2 964 1 0884397 3 064 1 0304285 至童奎耋塑圭堂堡冀圣篁奎翼墼堡垒矍 2 4 t a b l e2 数值结果( 续) m r a lm r a 2 c l s p r o b l e m竹i + nh e r s t e r s ri t e r sh e r s ri t e r s t e r s l 3 1358445343 3 2461 0774277 3 3 538425155 3 45492o3285 3 5 471 1882l84 3 6 871 5771 011 31 1 3 7 336443243 3 8 69 1 5 50721 07 3 9 628662l86 4 03 8 1 l2 o3233 4 15493042 64 4 2831 l 55 7 388 4 3 661 25452 1 18 4 4 681 41 01 051 1 09 4 5551 07751 7 5 4 6 81 6 2 4 1 71 7511 79 4 7 1 52 2 3 7 4 54 51 424 52 9 4 881 62 41 8 1 8 1 1 11 81 2 4 9861 49 o 1 02 1 01 0 5 0681 41 01 05 1l o9 5 11 11 72 82 72 71 12 2 71 3 5 2781 59 9 51 98 5 31 11 42 59662 1 8 1 2 5 41 52 23 74 54 51 42 4 5 2 9 5 581 62 41 81 81 111 81 2 5 6 1 11 72 82 72 71 122 71 3 5 7 1 11 42 51 58822 11 2 5 8 86 1 4 70 82 1 0 1 0 5 9 8 1 62 4 1 41 4 1 l2 1 4 9 6 01 3 1 6 2 92121 2 6 2 6 t o t a l3 8 54 4 98 3 4 4 7 93 8 9 3 0 51 0 6 6 2 94 6 8 t a b l e3 传统单纯形算法与新算法的迭代次数之比 p r o b l e _ r n m + nc l s m r a l c l s m r a 2 1426 1 5 01 5 0 24 480 8 6 2 0 0 34 482 5 01 2 5 45 491 5 01 2 0 5 1 031 31 0 0 03 3 3 63471 ,0 03 ,0 0 7821 023 32 3 3 81 241 6 1 4 42 1 7 9448 1 2 01 0 0 l o1 03 1 3o 9 13 3 3 1 16 2 82 0 03 0 0 1 2 1 2 4 1 61 4 42 1 7 1 354 91 6 01 1 4 4 482 5 01 2 5 1 5 3252 0 01 3 3 1 666 1 2 1 4 0 1 0 0 1 74 5 91 0 01 6 7 1 84 59 1 0 01 3 , 3 1 9 7 4 1 11 0 0 05 ,0 0 2 0 5492 ,0 01 5 0 2 15491 0 05 5 0 2 22681 0 0 2 0 0 2 34 4 81 5 03 ,0 0 2 425 71 5 01 5 0 2 52571 0 01 0 0 2 62571 0 00 6 7 2 7741 15 ,0 03 ,3 3 2 864 1 0 4 ,0 02 6 7 2 964 1 01 1 3 2 2 5 3 0 5492 6 72 0 0 奎童奎兰堡圭兰堡丝塞篁奎童墼堡篁墼 2 6 t a b l e4 传统单纯形算法与新算法的迭代次数之比( 续) p r o b l c m m + nc l s m r a ic l s m r a 2 3 135 81 o oo8 0 3 2461 0 10 017 5 3 363 91 2 510 0 3 4641 04 0 02 6 7 3 5471 11 _ 0 04 0 0 3 6971 618 61 3 0 3 73361 0 01 3 3 3 8 7 91 62 0 01 4 3 3 96 281 3 34 0 0 4 03 81 l15 01 0

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论