离散事件动态系统周期求解的线性规划方法.pdf

《离散事件动态系统周期求解的线性规划方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2001年12月东北大学学报（自然科学版）Dec.2001第22卷第6期JournalofNortheasternuniversity（NaturalScience）Vol.22，No.6!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!文章编号：1005-3026（2001）06-0623-04离散事件动态系统周期求解的线性规划方法肖文栋（东北大学信息科学与工程学院，辽宁沈阳110004）摘要：应用计时事件图中回路的线性代数特征，将线性离散

2、事件动态系统的周期计算转化为线性规划（LP）问题，并且得到的LP问题具有较少的变量和线性约束，避免了传统方法中对回路的穷举搜索，降低了计算的复杂性·关键词：离散事件动态系统；系统周期；图论；线性规划中图分类号：TP13文献标识码：A计时事件图（TEG）［1!4］描述了一类确定性E），这里V为一集合，E为V上的一个二元关的离散事件动态系统（DEDS），人们已基于dioid系·称V中的元素为图的节点，E中的元素为图代数理论为其建立了一系列线性DEDS理的边·称一个图为有向图，如果对所有的边都赋予论［1!3，5］·其中

3、，系统周期的计算在该理论中具有了方向，否则称其为无向图·下面的介绍均假定在非常重要的地位，因为它表示了系统的稳态运行有向图下·设e=（O，O）"E，则称O、O分别为ijij效率·由文献［3，5］可知，系统的周期等于其e的始点与终点，记为Oi=Pre（e），Oj=Post（e），TEG中关键回路的平均权重，即且称e为O的输出边、O的输入边·称边的序列ijN"（1）P=ei，e，⋯，e为一半路径，如果该序列中的有!=min｛｝1i2iP"T"向边是逐个相连的（但不要求各边的方向一致）·其中，"为TEG中的回路，N为该

4、回路中的"称一半路径为路径，如果该半路径是首尾相连的token总数，T"为该回路中的计时总和·求解系（即各边的方向一致）·如果半路径（路径）的始点统周期的一般方法是搜索系统的各回路，然后求与终点相交，则称其为半回路（回路）；不包含重复得其平均权重的最小值·但因为TEG中回路的节点的半回路（回路）为初等半回路（初等回路）·个数可能随着系统的规模成指数增长，因此该方如果从任一节点到任一另外节点均存在路径，则法在实际应用中常常会遇到困难·另一种方法是称该图是强连通的·本文仅考虑强连通图·利用文献［6］中提出的计算极小代

5、数下方阵特征称G/=（V/，E/）为G的子图，如果V/#值的Karp方法，此时需首先求出该TEG对应的极小代数模型下的标准系统矩阵，其缺点在于经V，E/#E·称G的不包含任何半回路的最大子处理后标准系统矩阵的维数通常很高，致使运算图T为G的生成树·一棵生成树覆盖了G的所量增大·有节点·称属于树T的边叫树枝，不属于树T的本文基于图论中回路的线性代数特征［7!9］，边叫弦，去掉树枝后的G的子图叫树T的余树·提出了线性DEDS周期计算的线性规划（LP）方TEG是一类特殊的Petri网，其主要特征为每法·其好处在于不用搜

6、索TEG中的所有回路，并个位置节点只有一个输入转换及一个输出转换·本且得出的LP问题具有较少的约束，这样可以应文假定所考虑的TEG的的位置个数与转换个数分用很有效的LP方法进行求解［10］·别为7与m·从一给定的TEG可直接得出其对应的G图，只要使TEG中的转换对应于G的节点，1图与TEG：基本概念介绍使TEG中的位置及与其相连的输入输出弧对应于一个图G抽象地定义为一个有序对（V，G的一个边，且使其方向与原TEG中相应的弧的收稿日期：2000-12-27基金项目：教育部留学回国人员基金资助项目（535012）·作

7、者简介：肖文栋（1968-），男，河北昌黎人，东北大学副教授，博士·624东北大学学报（自然科学版）第22卷方向一致·G对应的关联矩阵!=（!ij）7>m定义Ker（!）中的元素·由文献［7，8］可知，矩阵!的为秩为7-1，故Ker（!）的维数为m-（7-1）=1如果Oi是ej的起点a，故c1，c2，⋯，ca为Ker（!）的基底·于是，c可!ij=-1如果Oi是ej的始点（2）由c1，c2，⋯，ca线性表示，即!=（!1，!2，⋯，）使c=即有c!·证毕·L0否则!a!!·不难验证，下面的引理2与引理3成立·2有

8、向图中回路的线性代数特征引理"!构成一个凸集·由图论的知识可知，G的生成树T的边的个引理#令#为任一回路，则#!·数为T=7-1，余树的边（弦）的个数为a：=m引理$任给c!，存在一正整数S及初等回路#（1），#（2），⋯，#（S）及正实数"，"，⋯，"，使-7+1·将第i个弦添加到生成树中，可得到惟12S一的一个半回路，记为c如规定了该半回路的c="#（i）（6）i·i