离散事件动态系统-极大代数方法

R’是实数集合，e定义为-infinity,令R=R’并e，在R上定义加法和乘法：

加法：a⊕b:=max(a,b)

乘法：a.b:=a+b (普通意义下的加法)

称D={R, ⊕，.}为一个极大代数

其他的类似代数系统有半环( semiring) 、双子代数(dioid)和极小代数等.双子代数是一个比极大代数更一般的代数系统概念;极小代数是极大代数的对偶形式。

设E_n×n=[a_ij] a_ii=0, 其余a_ij=e；则E是D上的n阶单位矩阵。

满足BA=AB=E的矩阵A、B互逆。

图G(A)称为矩阵A的关联图.

定理1.2.1：设A_n×n, 则A^r_ij＝Σ_pW_p,其中p是G(A)中从点i到点j的任意一条长为r的路，W_p表示其权重。

证明：归纳法

定理1.2.2(化下三角阵): 设A_n×n, G(A)含w个强连通支,则存在置换阵P_n×n,使得

PAP^-1=[A₁              A₁₂          …             A_1w

Phi               A₂            …             A_2w

… …             …             …

Phi               Phi          …             A_w]

其中:A_i都是不可约的,它们对应G(A)的w个强连通支,Phi是每个元素均为e的阵.

离散事件动态系统的建模

法国人G.Cohen等人创立了极大代数上的线性系统理论.

定义: 一个确定性离散事件系统,可以用一个四元组(A,V,R,P)来描述,其中(A,V)是一个赋权有向图,A是所有活动的集合,设共有phi个活动,对它们编号为1,2,…,phi；V是所有弧的集合,(ij) in V表示活动i到活动j的弧.系统是确定的,是指图(A,V)中没有回路.否则,可能此回路上任意两个活动a和b,a既比b早发生,又比b晚发生,矛盾. R是所有资源的集合,设共有N个资源,对它们编号1,2,…,N；任一资源r in R,图中对应一条路Pr,称Pr为资源r的路.P表示所有资源在图(A,V)中所对应的路的集合. 每一个Pr in P,都有一个起始活动和终止活动,分别用l(r)和k(r)来表示.在图(A,V)中,弧(ij)的权重用tij来表示. 设zi表示活动i的开始时刻,ur表示资源r可以投入使用的时刻,如果(ji) in V,则有: zi>=zj+tji 这里加法是通常意义下的. 如果i=l(r),即资源r的起始活动是i,则有: zi>=ur zi表达式略… 设F in D phi×phi是图(A,V)的关联矩阵,则有: (F)ij:=      t, 如果(ij) in V;     e, 否则 设G in D N×phi,它的元素定义为: (G)ri:=     0, 如果l(r)=i                        e,否则 令Z=(z1z2…zphi),U=(u1u2…uN) 于是得到zi表达式矩阵形式: Z=ZF⊕UG 用xr表示资源r释放出来的时刻,设F in D phi×N,它的元素定义为: (F)ir:=      ti, 如果k(r)=i                       e,否则 其中t表示活动i从开始到结束的时间间隔,令X=(x1x2…xN),那么有X=ZH. 定理1.3.1 如果U是已知的,则方程Z=ZF⊕UG有如下解: Z=UGF* 且解是唯一的,其中F*=E⊕F⊕F2⊕…⊕Fphi-1. 证明: 由Z=ZF⊕UG有 Z=ZF⊕UG=(ZF⊕UG)F⊕UG  =ZF2⊕UG(E⊕F)     (?????????????????????????????????????)  =…  =ZFphi⊕UG(E⊕F⊕F2⊕…⊕Fphi-1) 因为F是(A,V)的关联矩阵,所以由定理1.2.1知(Fphi)ij等于图(A,V)中从点i到点j的长为phi的最重路的权重,但图(A,V)中没有回路,图中任何路的长度都不大于phi-1,因此必定有(Fphi)ij =e, 即有Fphi=Phi, 得证.

设加工第k批时资源r可以投入使用的时刻为u_r(k),释放出来的时刻为x_r(k) (1<=r<=N),

在文献[6]中指出,假设系统中的每个资源从加工第k-1批中释放出来后,即可投入到第k批的加工中去,这样对于系统则有:

u_i(k)=k_ix(k-1)

因为资源一释放出来即可投入到下一批加工,所以某一时刻在系统中加工的工件可能不是同一批的,而是同时加工两批或两批以上的工作.

一般地,确定性离散事件系统的模型为:

X(k)=U(k)GF*H

如果仍按文献[6]中的假定,令u_i(k)=k_ix(k-1),则系统的动态方程是:

X(k)=X(k-1)A

其中A=KGF*H, A in D ^N×N, 而K=

[k₁           e              …           e

e              k₂            …           e

…           …           …           …

 e             e             …           k_N]

制造系统的动态模型

设一个制造系统有m台机器,一批加工p个工作,则系统有m+p个资源.设系统有phi个加工活动, phi<=mp,则系统的模型为X(k)=U(k)GF*H.

现在把机器资源和工件资源分开来考虑,令: X(k)=(X_m(k)    X_p(k)),     U(k)=(U_m(k)           U_p(k)),把矩阵也相应地分块为:

GF*H=[D_m             D_mp；D_pm                             D_p]

那么X(k)=U(k)GF*H可以写为:

[X_m(k)     X_p(k)] = [U_m(k)      U_p(k)] [D_m              D_mp；D_pm                             D_p]

假设每台机器加工完第k-1批工件后即可投入加工第k批,则有:

U_m(k)=X_m(k-1)K_m

其中K_m称为机器反馈阵,且: K_m=

[k₁           e              …           e

e              k₂            …           e

…           …           …           …

 e             e             …           k_m]

这里k_i表示机器资源i两批之间的转换时间,令A_m=K_mD_m,B=D_pm,C_p=K_mD_mp,记Y_p(k)=X_p(k),则:

X_m(k)=X_m(k-1)_m⊕U_p(k)B_m

Y_p(k)=X_m(k-1)C_p⊕U_p(k)D_p

这与传统的线性系统类似,U_p(k)表示第k批工件可以进入系统的时间向量,它是系统的控制量,第二章将讨论DEDS的控制理论.

计时Petri网的极大代数描述

计时Petri网也称为事件图

一般地,一个计时Petri网,如果它的运行满足前面所提的四个条件,那么它可以用形如下面的极大代数方程描述:

Z(k)=Z(k-1) A⊕V(k)B

Y(k)=Z(k)C

其中变换Z(k)=[X(k)           X(k-1)], V(k)=[U(k)               U(k-1)].

串行生产线的建模略…

极大代数上矩阵的特征问题

在DEDS的稳态分析中有重要作用

定义1.5.1: A_n*n  XA=λX,   λ!=e, X!=空Phi, 则称λ为A的特征值,X为A的属于λ的特征向量,如果X的每个分量均不为e,则称X为A的有限特征向量.

定理1.5.1和1.5.2分别给出了特征值的必要条件和充分条件.一个实数λ是矩阵A的特征值,当且仅当λ是G(A)中某一回路的平均权重且该回路到任何平均权重比它的平均权重大的回路都没有路.(λ₁~λ_p如果有相等的,则称为重根)

特征向量

定义1.5.2: A_w1,A_w2,…,A_wn中的临界回路称为特征回路.

定义1.5.3: 设X以及X₁,X₂,…,X_k都是极大代数上的N维行向量,如果存在a₁,a₂,…,a_k in R (实数集并上-infinity),满足:

X=Σ_i=1^Na_iN_i=a₁X₁⊕…⊕a_kX_k,

则称X可由X₁,…,X_k线性表出.

定理1.5.3:

定理1.5.4:

矩阵的有限特征向量：

定理1.5.5: 矩阵A有有限的特征向量的充分必要条件是:

周期分析与动态方程的解

D上的动态系统: X(k)=X(k-1)A

A对应的有向图为G(A).当G(A)有几个连通分支时,系统可在各支中分别讨论,因此仅研究弱连通的G(A).不失一般性,本节设A是下面定理所示的标准形式.

定理1.2.2(化下三角阵): 设A_n×n, G(A)含w个强连通支,则存在置换阵P_n×n,使得

PAP^-1=[A₁              A₁₂          …             A_1w

Phi               A₂            …             A_2w

… …             …             …

Phi               Phi          …             A_w]

记

周期阵分析与动态方程的解

定义1.6.1 若λ!=-infinity,且存在正整数n₀使得:

A^d+n=λ^dAⁿ, for all n>n₀,

则称A是d阶λ周期阵.这里D中乘法为普通加法, λ^d就是普通的dλ.

分块周期阵分析与动态方程的解

定义1.6.2 若存在一个正整数n₀及Λ阵:  Λ=

[λ₁           λ₁₂          …             λ_1w

e              λ₂            …             λ_2w

…             …             …             …

e              e              …             λ_w]

使得:

{A^n+d}=λ^d_IJ{Aⁿ}_IJ, for all n>n₀, I, J

则称A为d阶Λ分块周期阵.

定理1.6.2: 在假设(H₂)之下

实现理论

实现的定义和Cayley-Hamilton定理:

定义1.7.1 设{G(k)}_k=1^infintiy是一个单位脉冲响应矩阵序列,G(k) in D^m*p,且: G(k)={g_ij(k)}

如果存在矩阵A in D^n*n,B in D^m*n,C^n*p满足:

BA^k-1C=G(k), k=1,2,…

则称{G(k)}_k=1^infintiy是能实现的,系统Σ: X(k)=X(k-1)A⊕U(k)B

Y(k)=X(k)C

称为{G(k)}_k=1^infintiy的一个实现, Σ也可记为(A,B,C),如果(A,B,C)在所有实现中A的阶数n是最低的,则称它为一个最小实现,维数为n.

极大代数中已经建立了特征方程的概念并且证明了Cayley-Hamilton定理成立,关于这方面的理论参考文献[9].这里直接引用某些结果.

定义1.7.2(线性相关): 设X₁,X₂,…,X_n是极大代数上的n个行向量,如果存在{1,2,…,n}的一个划分(N₁,N₂)以及不完全为e的a_i, a_i in R, i=1,2,…,n,使得:

Σ_{i in N1}a_iX_i=Σ_{i in N2}a_ix_i,

则称线性相关,否则称为线性无关.

引理1.7.1(Cayley-Hamilton定理)设A in D^n*n,它的特征方程为:

其中是的一个划分,那么有:

像传统线性系统理论一样,Cayley-Hamilton定理在实现理论中有重要作用,但与一般线性代数不同的是,极大代数中没有减法,{2,…,n}的不同划分(N₁,N₂),对应方程本质上是不同的,这是传统线性系统的实现理论难以推广到DEDS中的原因所在.

能实现的条件

定理1.7.1: 给定一个单位脉冲响应矩阵序列,如果它是能实现的,那么必存在{2,…,n}的一个划分(N₁,N₂),以及不完全为e的a_i, a_i in R, i=1,2,…,n,使得下式成立: