（交通信息工程及控制专业论文）极大代数线性离散事件动态系统性能估计算法研究.pdf

中文摘要 摘要：离散事件动态系统( d e d s ) 是上世纪8 0 年代以来兴起的一门学科。它渊 源于排队和网络分析问题，由于信息处理、计算机和机器人等技术的发展、完善 和应用的需要，出现了计算机集成制造、通讯网络、计算机网络、交通调度和公 共服务等一系列人造系统，这使得对于d e d s 的研究更为迫切，并且极具实际的 价值。越来越多的人进入到d e d s 这一极富挑战性的研究领域，在建模、分析、 控制、综合等问题作了很多研究。 本论文是在已有成果的基础上，对极大代数线性d e d s 的性能分析算法( 即 周时计算算法) 进行研究。h o w a r d 算法和c a l c c y c l e t i m e 算法是目f j 该类算法中 效率最高的算法，本文重点对它们通过数值试验，进行比较和研究，并对算法提 出改进。 本文首先深入研究了这两个算法。h o w a r d 算法是策略迭代算法，首先进行策 略选择并求出相应的策略矩阵的广义特征模式，然后检测策略矩阵的广义特征模 式是否为最初矩阵的广义特征模式。如果满足，则极大代数矩阵的周时被求出， 不满足，进行策略改进。c a l c c y c l e t i m e 算法也是策略迭代算法，但与h o w a r d 算法 相比采用了不同的思路。它首先利用c a l c s p e c t r a l r a d i u s 计算谱半径，其实质也是通 过策略迭代不断地对策略进行改进，当到达最优策略时，策略矩阵的最大特征值 就是函数的谱半径，然后将周时分量等于该谱半径的节点从原系统中消去，最后 递归调用c a l c c y c l e t i m e 算法计算简化函数的周时。 证是这两个算法采用策略迭代这一思想。使得他们具有很高的计算效率。平 均时间复杂度近似线性，针对这两个算法，论文做了如下主要工作： ( 1 ) 在国内首次对h o w a r d 算法进行了详细分析，写出了详细的h o w a r d 算 法的中文文档。对h o w a r d 算法编写了大量数值实验程序，得到了关于其运行效率 的数据。 。 ( 2 ) 将h o w a r d 算法与对偶c a l c c y c l e t i m e 算法进行数值试验比较。首次得 出了前者在总体上优于后者的结论，并为后者的进一步优化指明了方向和思路。 ( 3 ) 对h o w a r d 算法进行了尽可能的优化和改进。h o w a r d 算法是一个比较成 熟的算法，对其进行优化已经很困难。作者实现了先前有人提出的“优化选择初 始策略 的思路，并对此项修改进行了数值实验分析，得出了这项修改无论是针 对h o w a r d 算法还是对偶c a l c c y c l e t i m e 算法都是完全值得的。作者并对h o w a r d 算法在浮点数计算( 有误差计算) 情况下有可能出现死循环提出了解决方案。 关键词：线性d e d s ；极大代数；周时；h o w a r d 算法；c a l c c y c l e t i m e 算法 分类号：t p l 3 匕立窒遭厶亟 ：羔位迨塞垦塞! 基至 a bs t r a c t a b s t r a c t ：t h ed i s c r e t ee v e n td y n a m i cs y s t e m sa r ed i s c i p l i n e se m e r g i n gi nt h ee a r l y 19 8 0 s t h em o t i v a t i o nt os t u d yd e d so r i g i n a t e di nt h eq u e u i n gp r o b l e m sa n dn e t w o r k a n a l y s i sp r o b l e m s w i t ht h ed e v e l o p m e n t ，i m p r o v e m e n to ft e c h n o l o g yo fi n f o r m a t i o n p r o c e s s i n g ，c o m p u t e r sa n dr o b o t i c sa n da p p l i c a t i o nr e q u i r e m e n t ，al o to fm a n m a d e s y s t e m sa p p e a r e d ，s u c ha sc o m p u t e ri n t e g r a t em a n u f a c t u r i n gs y s t e m s ，c o m m u n i c a t i o n n e t w o r ks y s t e m s ，c o m p u t e rn e t w o r ks y s t e m s ，t r a f f i cd i s p a t c hs y s t e m sa n dp u b l i c s e r v i c es y s t e m s t h e r e f o r e ，i ti sm o r eu r g e n ta n dh a sm o r ep r a c t i c a lv a l u a b l et os t u d y o nd e d s m o r ea n dm o r ep e o p l ef o c u so nt h i sc h a l l e n g i n gr e s e a r c hf i e l da n ds t u d yo n m o d e l i n g ，a n a l y s i s ，c o n t r o l l i n ga n di n t e g r a t i n g b a s e do nt h ec u r r e n tl i t e r a t u r e ，t h i sd i s s e r t a t i o ns t u d i e sp e r f o r m a n c ee v a l u a t i o n a l g o r i t h m s ( a l g o r i t h m o fc o m p u t e r i n gc y c l et i m e ) f o rm a x p l u s - l i n e a rd e d s h o w a r d sa l g o r i t h ma n dc a l c c y c l e t i m ea l g o r i t h ms h o wt h eh i g h e s te f f i c i e n c yb yf a r s ot h i sd i s s e r t a t i o nf o c u s e so nc o m p a r i s o na n ds t u d yo nt h e mt h r o u g hn u m e r i c a l e x p e r i m e n t ，a n di m p r o v e st h ea l g o r i t h m s t h i sd i s s e r t a t i o nf i r s ts t u d i e so nb o t ho fa l g o r i t h m s h o w a r d sa l g o r i t h mi sa p o l i c y i t e r a t i v ea l g o r i t h m f i r s t ，ap o l i c yi sc h o s e na n dt h ee i g e n m o d eo ft h ec o r r e s p o n d i n g p o l i c ym a t r i xi sc o m p u t e d n e x t ，i ti st e s t e dw h e t h e rt h eg e n e r a l i z e de i g e n m o d eo ft h e p o l i c ym a t r i xi sa l r e a d yag e n e r a l i z e de i g e n m o d eo ft h eo r i g i n a lm a t r i x i fs o ，t h ec y c l e t i m eo fm a x p l u sm a t r i xh a sb e e nf o u n d i fn o t ，t h ep o l i c yh a st ob e a d a p t e d c a l c c y c l e t i m ea l g o r i t h mi sa l s op o l i c yi t e r a t i v ea l g o r i t h m ，b u ti th a ss e v e r a ld i s t i n c t t h o u g h t f r i s t ，c a l c c y c l e t i m ea l g o r i t h mc a l l sc a l c s p e c t r a l r a d i u st oc a l c u l a t et h e s p e c t r a lr a d i u s ，w h i c he s s e n c ei sa l s oi m p r o v ep o l i c yb yi t e r a t i v ep o l i c y w h e nt h e p o l i c yi so p t i m a l ，t h el a r g e s te i g e n v a l u eo fp o l i c ym a t r i xi st h es p e c t r a lr a d i u so f f u n c t i o n t h e nt h en o d e sw h o s ec y c l et i m ee q u a lt os p e c t r a lr a d i u sw i l lb ee l i m i n a t e d a tl a s t ，c a l c c y c l e t i m ea l g o r i t h mr e c u r s i v e l yc a l l si t s e l ft oc o m p u t et h ec y c l et i m eo f t h er e d u c e df u n c t i o n j u s ta st h ei t e r a t i v ep o l i c ya d o p t e d ，b o t ho ft h e ma r ev e r ye f f i c i e n t i ti sa l m o s t l i n e a ro na v e r a g ei nt i m ec o m p l e x i t y t h em a i nc o n t e n t si nt h i sd i s s e r t a t i o na r ea s f o l l o w s ： ( 1 ) t h i sd i s s e r t a t i o nm a k e sad e t a i l e da n a l y s i so fh o w a r d sa l g o r i t h mf o rt h ef i r s t t i m ei nc h i n a ，a n dw o r k so u tt h ed e t a i l e dc h i n e s ed o u c u m e n t so fh o w a r d sa l g o r i t h m ：i 匕立交道厶亟：! ：堂位论塞旦墨! b ! al o to fn u m e r i c a le x p e r i m e n t a lp r o g r a m so nh o w a r d sa l g o r i t h ma r ed e v e l o p e d ，a n d t h ed a t a sa b o u ti t so p e r a t i o ne f f i c i e n c ya r eo b t a i n e d ( 2 ) t h er e s u l to fn u m e r i c a le x p e r i m e n t a lc o m p a r i s o no nh o w a r d sa l g o r i t h ma n d c a l c c y c l e t i m ea l g o r i t h ms h o w st h a tt h ep e r f o r m a n c eo ff o r m e ra l g o r i t h mi sb e t t e rt h a n t h el a t t e rf o rt h ef i r s tt i m e ，a n dp o i n t so u tt h ed i r e c t i o na n dt h o u g h tf o rf u r t h e r o p i t i m i z a t i o n ( 3 ) a no p t i m i z a t i o na n di m p r o v e m e n tt oh o w a r d sa l g o r i t h mi so b t a i n e da sf a ra s p o s s i b l e h o w a r d sa l g o r i t h mi sar e l a t i v e l ym a t u r ea l g o r i t h m ，s oi t sd i f f i c u l tt oi m p r o v e i t t h i sd i s s e r t a t i o nr e a l i z e st h et h o u g h to f “o p t i m i z e ds e l e c t i o nt oi n i t i a lp o l i c y p u t f o r w a r db yp r e d e c e s s o r s ，a n da n a l y s e st h em o d i f i c a t i o nb yn u m e r i c a le x p e r i m e n t t h e r e s u l ts h o w st h a tt h i sm o d i f i c a t i o ni sv a l u a b l eb o t ht oh o w a r d sa l g o r i t h ma n d c a l c c y c l e t i m ea l g o r i t h m as o l u t i o nt oi n f i n i t el o o pw h i c hm a y b eo c c u r e su n d e r t h e c o n d i t i o no ff l o a tc a l c u l a t i o n ( e r r o rc a l c u l a t i o n ) i sp r o p o s e d k e y w o r d s ：l i n e a rd e d s ；m a x p l u sa l g e b r a ；c y c l et i m e ；h o w a r d sa l g o r i t h m ； c a l c c y c l e t i m ea l g o r i t h m c i 。a s s n o ：t p l 3 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在沦文中作 了明确的说明并表示了谢意。 学位论文作者签名：物1 1 | i ( 救 签字同期： b 0 0 7 年 6 月彩 r 5 5 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交沦文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：扬喙救 签字日期： 彻? 年6 月2 6 同 导师签名：缘移秀久乎 签字同期：力研年6 月历泊 致谢 在本论文即将完成之际，谨向我的导师程轶平副教授表示最诚挚的感谢! 本 文的研究工作j 下是在他的直接指导和帮助下完成的。在我攻读北京交通大学硕士 的两年中，程老师一直悉心指导我的学习，关心我的生活，自始至终都给予我无 私的帮助。程老师丰富的理论知识，严谨的治学态度使我深受教诲，严于律己， 仁厚谦和的生活态度更对我影响至深，这些都将为我今后的为人、处事指引方向， 让我在未来的工作和生活中受益终身。 感谢同实验室和我一起学习的付强、崔庆权、彭海强、付海涛、高冰、张悦 铃、张广伟、韦钟辉。他们给予我课题上的许多建议和帮助，并在生活上关心帮 助我，让我感受到集体和团队的温暖。 感谢我的室友刘艳芳，还有孙萍和高云等人，她们陪伴我走过两年的学习生 活，使我度过了一个愉快的研究生时代。 最后要感谢我的父母和家人，在学习和生活上给予我无私的支持，使我在科 研的道路上无所羁绊；并不断给我以激励与鼓舞，使我j 爿j 有迎接和战胜一切凼难 的勇气和决心。 1 综述 本论文是在极大代数方法下，对线性离散事件动态系统的性能估计算法进行 研究比较。 1 1离散事件动态系统 离散事件动态系统( d i s c r e t ee v e n td y n a m i cs y s t e m s ，简称d e d s ) 是8 0 年代 以来兴起的- - l - j 学科。其称谓是哈佛大学y c h o 教授提出的【l 】，他倡导了对d e d s 理论进行系统研究并创立了d e d s 扰动分析技术。d e d s 是由离散事件触发而引 起状态迁移的一类自然的或是人造的动态系统。它的应用主要集中在计算机集成 制造系统，计算机网络通信系统，排队服务系统，机器人控制系统和交通管理系 统等领域【2 j 。d e d s 与传统的c v d s ( 连续变量动念系统) 最重要的区别是前者中， 系统的发展演化是由一些离散事件驱动的。为实现对这类系统的分析、设计、及 控制，离散事件动态系统这门学科得以产生和发剧3 , 4 , 5 】。 研究任何一个系统，首先要做的一项工作就是建模。然后在已建成的模型的 基础上分析研究系统的各种性质。研究离散事件动态系统也不例外，第一个重要 问题就是对其建模。d e d s 建模的研究方法有多种。根据不同系统的特点和研究者 所关心的对象，提出不同的模型。d e d s 的研究模型可以分为三个层次，即逻辑层 次、代数层次和统计性能层次【6 】。 d e d s 的逻辑层次模型着眼于事件和状态之间的逻辑关系，而不涉及事件发生 的具体时间或者时间间隔，所以它属于定性模型。逻辑层次模型所用的数学工具 主要包括有限自动机、p e t r i 网、m a r k o v 链等。 d e d s 的代数层次模型着眼于在时间层次上描述事件与下次事件的发生时间 之间的代数关系，从而揭示系统的发展过程，因此它属于定量模型。代数层次模 型所用的数学工具主要包括极大代数( m a x p l u sa l g e b r a ) 、计时事件图( t i m e de v e n t g r a p h ) 、极小极大函数( m i n m a xf u n c t i o n ) 等。 d e d s 的统计性能层次模型着眼于在性能层次上研究随机情况下d e d s 的平 均性能，它也属于定量模型。统计性能层次模型所用的数学工具主要包括排队论、 广义半m a r k o v 过程等。 d e d s 的上述三种层次模型各有其优缺点和适用场合，它们缺一不可，相互补 充，共同构成d e d s 的理论大厦。 1 2 极大代数线性与非线性系统 在离散事件动念系统的代数层次的模型中，极大代数方法是最具代表性的方 法【7 】。它使得d e d s 这种复杂的非线性系统在极大代数方法下，建成的模型与传统 的线性系统理论( a ，b ，c ) 的模型相对应。也就是说，d e d s 在极大代数方法下建 的模型是线性的。只不过这种线性不是传统意义上的。 极大代数是一种比较新的代数系统，其历史至少可以追溯到上世纪六十年代 初，英国的r a c u n i n g h a m e g r e e n 教授用来描述与分析工业过程【引。并在1 9 7 9 年， 他系统地总结了极大代数的数学理论，并指出它的一些应用f j 景【9 】。法国学派在上 世纪7 0 年代至8 0 年代对更一般的双子( d i o i d ) 代数结构及双子上的线性代数做 了系统研究，极大代数是双子的特例。法国自动控制与应用数学专家g c o h e n 博 士等人在上述科学家工作的基础上，从8 0 年代初丌始，以极大代数为工具，系统 研究了离散事件动态系统( d e d s ) 的线性系统理论。以缓冲区容量为无限的串行 生产线为背景的一类离散事件动态系统，其代数模型的原始形式是逻辑非线性的。 c o h e n 等人首先把极大代数应用于这类离散事件动态系统的建模和分析，把逻辑非 线性关系转化为极大代数意义下的线性关系，所建立的系统模型与传统的线性系 统模型非常相似，并对系统的能控和能观测性、稳定性、周期性稳态及特征结构 做了比较系统的研列1 0 , 1 1 】。后来，在1 9 8 5 年g c o h e n 等人的论文【1 2 1 在著名的刊物 i e e et r a n s a c 上发表后，引起了控制理论界广泛的关注与兴趣。 总之，经过众多学者的努力，在传统代数眼中是复杂的非线性d e d s 在极大 代数方法下成为线性的。这种线性的d e d s 可以描述一类实际系统的动态行为， 例如制造系统中加工活动的开始和结束就可以看成事件，而矩阵中的元素则代表 事件的延迟。在极大代数线性d e s 的演化方程中只有两种基本运算：取极大和加 法，这反映了系统中前驱事件与结果事件之间的关系是“与 的关系。但是，也 有一些系统中前驱事件与结果事件之问的关系不一定全部是“与 关系，而可能 同时存在“与 关系和“或”关系。这种系统为极小极大系统，它们即使在极大 代数意义下也是非线性的。对这类极小极大系统系统，o s l d e r 首先研究了其特征值、 不动点以及相关的几个问题，得到了一些初步结果【1 3 , 1 4 】。后来，g u n a w a r d e n a 对极 小极大系统的谱、不动点等诸多问题，以及在数字电路时序分析中的应用做了深 入的系统研刭b 。8 1 。g u n a w a r d e n a 和g a u b e r t 证明了深刻的对偶定理，并将其推广 到代数表示更为一般和复杂的t o p i c a l 函数类【”却】。陈文德首先研究了极小极大系 统的控制问题1 2 l 2 2 】。赵千) l l 矛n 郑大钟研究了极小极大系统的全局时间及其随机情 况【2 3 j 。程轶平提出了求解极小极大系统周时的c a l c c y c l e t i m e 算法【6 】。 2 1 3 极大代数线性系统的性能估计 本论文将限于极大代数线性d e d s ，因为它是极大代数非线性d e d s 的相应 研究的基础。一个极大代数线性d e d s 的演化方程完全取决于一个极大代数矩阵， 而其性能( 周时) 取决于该矩阵的周时( c y c l et i m e ) 。对于一个制造系统，粗糙的说： 周时指的是完成一个或一批工件所需要花费的平均时间，它是一个决定生产率的 非常重要的性能指标【2 4 1 。( 本文采用周时这一术语，是为了避免与极大代数系统 的另一概念周期( p e r i o d ) 发生混淆【6 】) 因此，周时的计算问题是线性d e d s 性 能分析的中心问题。本论文就是围绕这一中心问题展丌的。 计算周时有很多算法，许多学者都在这方面作了大量工作。本文选了其中一 些比较常见并且运行时间较短的算法制成如下所示的表l ，以使大家有个大体上的 认识，要想进一步理解相关算法，可以参考相应的一些文献。其他一些算法还可 以参见文献1 2 引。 表1 常她的计算周时的算法 名字出处时i 日j结果 ld g d a s d a n & g u p t a 2 6 】 1 9 9 7精确 2h oh a r t m a n n & o d i n 2 7 】1 9 9 3精确 3 k a r p sk a r p 2 8 】 1 9 7 8精确 4y t o y o u n g ，t a r j a n ，& o d i n 2 9 】 1 9 9 1精确 5k o k a r p & o d i n 3 0 】 1 9 8 l精确 6o a o r l i n & a h u j a 3 1 1 1 9 9 2近似 7 c u n i n g h a m e g r e e n & y i x u n 3 2 】 1 9 9 6精确 8 b u m s b u m s 3 3 1 9 9 l精确 9 m e g i d d o 3 4 】 1 9 7 9精确 1 0l a w l e r sl a w l e d 3 5 】1 9 7 6近似 1 1i t o & p a r h i 3 6 】1 9 9 5精确 1 2g e r e ze ta 1 1 3 7 11 9 9 2精确 1 3h o w a r d s c o c h e t t e r r a s s o ne ta l 【3 8 】 1 9 9 7精确 1 4 c a l c c y c l e t i m ec h e n ga n dz h e n g 6 】 2 0 0 4精确 在表1 中算法生成的结果有两种，一是“精确”的，二是“近似 的。l a w l e r 算法使用折半查找法来查找可能的刀，当选择的兄太大，则减少它的值，太小则 增大。当可能的刀的值所在区间非常小时，l a w l e r 算法结束。这个区间的大小为e ， 由用户定义，决定算法的精度。这就是为什么说它的结果是“近似 的原因。第6 3 行的o a 算法使用和l a w l e r 相同的收敛策略，所以产生的结果也是“近似”的。 第8 行的b u m s 算法和1 3 行的h o w a r d 算法虽然产生的结果是精确的，但是它们 也有精度l 、口j 题。例如，在b u r n s 算法中需要检测两个浮点数是否相等，这样的检测 由e 控制。e 是由用户定义的非常小的一个变量。所以，b u m s 算法存在精度问题。 对于h o w a r d 算法的精度问题，在后面的章节将有具体的介绍，在这不进行展开。 在以往的算法研究中，那些算法的作者大多集中于理论研究，为他们提出的 算法提供的试验验证或实施指导较少。所以，对于大多数的算法，虽然其运行时 间范围在理论上得到了证明，但是在实际中的性能还不是很清楚。并且，现有理 论一般仅注重最坏情况下的时问复杂度分析。而实际上，在理论上卓越的时间复 杂度并不意味着在实际中依然卓越，反之亦然。例如在文献【3 9 】中指出，h o w a r d 算 法的时间复杂度是指数的，l 匕k a r p 算法的时间复杂度差，但是k a r p 算法运行时问 却l l h o w a r d 算法要慢。因此，要找到在实际使用中比较好的算法，提供实验分析 显得很重要。并且实验研究可以揭示算法的改变能否使运行时间在理论上更有效。 d a s d a n 等人的研究【3 9 1 在这个方向上迈出重要的一步。他们评估和比较了当时几乎 所有的算法。他们发现h o w a r d 算法是最快的算法。 在d a s d a n 沦文发表后，程轶平针对极小极大函数的周时计算问题提出了 c a l c c y c l e t i m e 算法。该算法需要调用求解极大代数矩阵周时的算法。而有趣的是， 该算法本身的对偶算法就可以用于计算极大代数矩阵的周时。由于c a l c c y c l e t i m e 算法和h o w a r d 算法都采用了策略迭代( p o l i c yi t e r a t i o n ) 这一思想。使得他们具有 很高的计算效率。 从目前的文献看，h o w a r d 算法和( 对偶) c a l c c y c l e t i m e 算法是目i j 仅有的平 均复杂度接近于线性的算法。因此，很有必要对这两个算法进行比较，以便为有 需要的科研人员和工程师提供选用算法的重要参考，并且，如有可能，在这两个 算法的基础上实施改进甚至提出新的更好的算法。 本文将用数值实验的方式来分析比较h o w a r d 算法和对偶c a l c c y c l e t i m e 算法， 以得出这两个算法在实际中的性能结果。本文在相同的实验环境下采用尽量统一 有效的编程方式，然后从运行时间，迭代次数，精度等方面比较这个算法的性能。 为后续研究提供参考。 1 4 本文的主要工作和结构 本章为本文的综述部分，首先介绍了论文的研究背景，有关文献的观点。以 往的研究历史和研究方法，主要的研究成果，并指出本论文是在以往的研究成果 的基础上，对计算线性d e d s 周时的两个算法进行数值实验研究。并列出本文的主 4 要工作和结构安排。 论文的主要工作包括以下几个方面： ( 1 ) 在国内首次对h o w a r d 算法进行了详细分析，写出了详细的h o w a r d 算 法的中文文档。实现了先前有人提出的“优化选择初始策略”的思路，并进行了 数值实验。 ( 2 ) 将h o w a r d 算法与对偶c a l c c y c l e t i m e 算法进行比较。编写了大量数值 实验程序，得到了关于其运行效率的数据。分析结果，首次得出了前者在总体上 优于后者的结沦，并为后者的进一步优化指明了方向和思路。 ( 3 ) 对算法进行了尽可能的优化和改进。将“优化选择初始策略”的思路用 于对偶c a l c c y c l e t i m e 算法，进行数值实验分析，得出了这项修改无论是针对 h o w a r d 算法还是对偶c a l c c y c l e t i m e 算法都是完全值得的。作者并对h o w a r d 算 法在浮点数计算( 有误差计算) 情况下有可能出现死循环提出了解决方案。 论文的结构安排如下： 第二章，介绍线性d e d s 研究的基础知识。包括极大代数的概念及相关定理， 系统特征结构分析的基础有向图的概念和特性，然后自然地引出极大代数矩 阵的特征值和特征向量的概念，并用图论语言给出周时这一关键概念。 第三章，介绍h o w a r d 算法，详细写出了关于h o w a r d 算法的中文文档。指出 该算法初始策略选择优化的方法及效果。然后用计算机编程语言进行算法实现。 第四章，详细介绍c a l c c y c l e t i m e 算法和可用于求极大代数矩阵周时的对偶 c a l c c y c l e t i m e 算法。并把对偶c a l c c y c l e t i m e 算法的计算机编程的思路和关键步 骤用伪代码形式展示。 第五章，对h o w a r d 算法和对偶c a l c c y c l e t i m e 算法，本文从运行时问，迭代 次数和精度三个方面进行比较，然后分析，得出结论。 第六章，对c a l c c y c l e t i m e 算法也采用初始策略的选择优化的方法，并把 c a l c c y c l e t i m e 算法和h o w a r d 算法各自优化前后对迭代次数的影响进行比较分析。 最后对h o w a r d 算法提出改进。 第七章，将对本文所作的工作进行总结，并指出下一步研究要努力的方向。 5 2 预备知识 本章介绍本论文后续部分必需的预备知识。包括极大代数的基础知识，有向 图分析法，极大代数矩阵的特征向量和特征值，以及本论文的一个非常关键的概 念周时。 2 1极大代数 极大代数概念是c u n i n g h a m e g r e e n 首先提出来的。随后，c o h e n 等人将极大 代数用于制造系统的分析，由此形成线性d e d s 理论。本章的主要概念参考文献【柏1 。 定义2 1 记g = - - 0 0 ，r 。= rup ) ，对任意a , b r 。，定义口o6 = m a x ( a ，b ) ， a b = a + 6 ，称( r m 。，0 ， ) 为极大代数。o 和。分别视为极大代数上的加法和乘 法。 容易验证下面的 定理2 1 ( 1 )交换律： a o b = 6 0 a ，a o b = 6 0 a ； ( 2 1 ) ( 2 ) 给合律： ( 口o b ) o c = a o ( 6 0 c ) ， 0 6 ) c = a o ( 6 0 c ) ；( 2 2 ) ( 3 )o 对。的分配律： a p ( 6 0 c ) = ( 口0 6 ) o ( a o c )( 2 3 ) ( 4 )幂等律： aoa = a ； ( 2 4 ) ( 5 )零元： a o g = s o a = a ； ( 2 5 ) ( 6 )单位元： a 圆0 = 0 圆a = a ； ( 2 6 ) ( 7 ) 吸收元： ao s = 占o a = s 。 ( 2 7 ) 极大代数满足域公理中除“存在加法逆元之外所有公理，所以极大代数是 半域。极大代数加法满足幂等性，即a o a = a ，所以极大代数构成一个幂等半域。 与线性代数相似，可以定义极大代数上的矩阵的加法和乘法。设r 黧表示极 大代数上所有m xn 矩阵组成的集合。当n 且n 0 ，定义丝= 1 , 2 ，n ) 矩阵 6 a r 。i l l 。i i 的第i 行第列元素记做a 盯，其中f m ，j 丝，则有： 定义2 2 设a ，b 尺= ，a = ( a “) ，b = ( b i j ) ，则 彳ob = ( a fo ) 定义2 3 设a 尺黧，b m r l 。m 则 【a o b 】让= m a x 口| ：+ 6 肛) 相应的，方阵彳的k 次幂定义为a 龇= a a 圆a 。 1 f 一 定s l 2 4 设a r 。缸，a r , 2 7 ，则纯量与矩阵相乘定义为： a 圆彳】盯= a o a 盯 结论2 1 设e r 三： e = 0g 占o ( 2 8 ) ( 2 9 ) ( 2 1 0 ) 则e 是尺。上的n 阶单位矩阵。 定义2 5 设a 尺黧若存在b r 竺：，满足a b = b a = e 则称矩阵彳可逆，b 称 为么逆矩阵，彳的逆通常记为a 。 与极大代数形成对偶的是极小代数r 。m = ru 0 0 ) ，其加法和乘法分别记为o 和o 。对任意口，b r 。i 。， a o b = m i n ( a ，功( 2 1 1 ) a o b = a + 6 ( 2 1 2 ) 任何极大代数概念都在极小代数有对偶概念。 2 2 有向图分析法 离散事件动态系统的动态行为，特别是周期性稳态过程行为，是由系统在极 大代数上的特征结构所决定的。在极大代数框架下，对系统特征结构的分析是以 有向图的概念和特性为基础的。为此，本文首先给出有向图的一些基础知识。 定义2 5 一个有向图是一个二元组( ，d ) ，n 是图中所有节点的集合，d 是 所有弧的集合，可用自然数1 ，2 ，刀对图中所有的n 个节点进行标号，用有序数对 ( f ，) 表示节点f 到节点，有弧，这里i 和，可以是同一个点。 值得注意的是，在有向图中，弧( f ，j ) 和弧( ，f ) 是不同的，弧( f ，) 是指从节点 i 出发指向节点，的弧，相反的，弧( ，f ) 是指从节点，出发指向节点i 的弧，两者 的方向不同。例如，( f ，) d 但是( ，f ) 诺d ，这说明从节点i 到节点，有弧存在， 从节点，到节点i 没有弧存在。这就是为什么称这样的图为有向图的原因。 7 占 g 0 定义2 6 若存在k 个节点f 。，如，对任意l p ，z 的路径，总可以通过消去其中的回路而成为一条简单回路，而因 为g ( 彳) 中所有圈的平均权重都0 ，这条简单回路的权重不会小于原回路的权重。 所以，g ( 么) 中从顶点，到f 的最大权重总可以取为边数n 的路径。由此可以得到 彳+ 】是从顶点到i 的最大权重。 定义2 1 2 对任何a r m ；： d e f a + = eo a + = o a 龇 ( 2 15 ) 七2 0 彳的意义可以理解为：假定从任何顶点f 到自身有一条边数为0 的路径，其长 度为0 。a 盯是在这种意义下的从顶点，到f 的最大权重。 置换矩阵定义为任一行和任一列有且仅有一个单位元0 ，而其他元均为一0 0 的 方阵。 2 3极大代数矩阵的特征值和特征向量 极大代数上矩阵的特征问题不仅有理论意义，而且有应用价值。 r a c u n i n g h a m e g r e e n 首先解决了不可约矩阵的特征问题。g c o h e n 等人对不可约 矩阵以及含有两个强连通分支的情况作了分析，陈文德、齐向东解决了一般可约 矩阵的特征问题。 定义2 1 3 令a r 黧为一个方阵，标量心。，向量y 群。包含至少一个 有限元，如果， 彳o ，= 0 1 ，( 2 1 6 ) 则，为彳的特征值，1 ，为方阵彳中t 对应的特征向量。 引理2 2 令a r 。n x 。n 有一个有限的特征值a 。那么，在g ( a ) 中有一个回路y ， 满足： ：磐 ( 2 1 7 ) l71 7 iyi ，为回路的长度，l 川，为回路的权重。 通过上面的引理，回路的平均权重的被提出用于表示特征值，但是，上面 9 的引理没有说明哪一个网路用来定义特征值。下而本文将更加深入指出。 令e ( 彳) 表示图g ( a ) 所有的简单回路的集合，用 肚脚m a x 酱 ( 2 1 8 ) j 口e 上1 月jd1 表示最大平均权重，且e ( 彳) = 矽时，五= m o o 。 定义2 1 4 在图g ( a ) 中平均权重最大的回路，被称为临界回路。图g ( 彳) 中临 界回路中的节点和弧构成的图被称为临界图，用g f ( 爿) = ( n f ( 彳) ，d f ( 彳) ) 表示。节 点i n f ( 么) 有时被称为临界节点，类似的，临界回路中的路径被称为i 临界路径。 值得注意的是，不可约矩阵的临界回路不一定必须是强连通的。 定理2 3 对于不可约方阵a r m t x 有一个且唯一的一个特征向量名( 彳) ，这个 向量是一个有限的数，等于关联图g ( a ) 中的最大平均权重。 z ( a ) = m a x ! 等 ( 2 1 9 ) 2 4 极大代数矩阵的周时 周时( c y c l et i m e ) 是d e d s 最重要的性能指标， 它的基本含义是系统中两次相 邻事件发生时间的渐近间隔，即! i m 烈肛。具体将在下一章讲述，这里用图论语 c - - 扣o几 言简单地给出定义。 定义2 1 5 设a r 。n 。p 。l ，其周时( 么) 定义为： 对每个l i 疗， 鸬( 爿) = m a x icl 。：c 是g ( 4 ) 中的圈，且从c 至l j i 有路径) 。 上面定义对所有极大代数方阵有意义。当在g ( a ) 中没有圈到i 有路径时， 从( 彳) = s ，否则“( 彳) r 。因此，( 彳) 磷。 a 的周时常称为矩阵a 或图g ( a ) 的谱。图的谱是一个深刻的概念，因研究目 的不同而有多种定义【4 1 4 3 1 。 2 5本章小结 第一节从极大代数的概念入手，简单介绍了极大代数的有关定理，以及极大 代数矩阵上的加法和乘法，并指出在极大代数上的单位矩阵，可逆矩阵的含义。 最后指出极大代数的概念在其对偶的极小代数上都有对偶的概念。 第二节介绍有向图的概念和特性。d e d s 的周时是由系统相应的极大代数矩阵 的特征结构所决定，而有向图是分析d e d s 特征结构的基础。所以在这一节介绍 了很多有向图的知识。有向图的概念，回路，简单回路，自回路( 圈) 的含义， l o 强连通的定义。以及在有向图的基础上得到的赋权有向图的概念，并引出论文关 键的概念，关联图和关联矩阵等等。这一节的概念很多并且非常有用，在这里进 行总结，以便读者在遇到不懂的地方有针对性的查阅。 第三节提出了本论文最重要的两个定义，极大代数矩阵的特征值和特征向量。 并说明什么是临界回路，临界图，及临界节点等。 第四节就简要的给出了用图论语言定义的周时的概念，因为在后面章节中还 要详细展开。 3h o w a r d 算法 本章开始研究曾被d a s d a n 等人指出是最快算法的h o w a r d 算法。下面将给出 该算法的详细说明【4 0 】。 3 1预