Petri网系统的可达性研究
B．当有位置是同时某个变迁的输入和输出时， 对于V+fj－ 的每一个分量xi 都满足,0≦xi≦K(xi) ,
对于V+ fj－＋fj+ 的每一个分量xi 都满足,0≦xi≦K(xi) , 而且V+ fj－＋fj+ 就是tj在状态M下的施实结果。
4. 初状态a0?V0 =(x1,?,xn), 其中xi 表示 M0 状态下Pi中的token数。
5．一个变迁过程Mi [ti>Mi+1 映射成对状态点Vi作平移变换fi，变换到状态点Vi＋1。
tj实施时先作变换fj－，再作变换fj＋。这时将tj分解为两个平移变换，其目的是: 为了保证PNL=(LP+,TS,V0)的变迁条件与PN=(S,T,F;K,W,M0) 的变迁条件等价。 定理3-1 tj可实施的条件为?pi∈S: W(pi,tj)≤ M(pi)≤K(pi)- W(tj,pi).
与PN=(S,T,F;K,W,M0) 的变迁条件等价。
证明：根据tj的连接情况将位置点pi分为四类：
a) (pi,tj)?F并且(tj,pi)?F, W(pi,tj)＝0，W(tj,pi)＝0，M(pi)＝xi b) (pi,tj)?F并且(tj,pi)?F, W(tj,pi)＝0，M(pi)－W(pi,tj)＝xi
0≦xi≦K(xi) ? W(pi,tj)≤ M(pi)≤K(pi)
c) (pi,tj)?F并且(tj,pi)?F, W(pi,tj)＝0，M(pi)+ W(tj,pi)＝xi
0≦xi≦K(xi) ? 0≤ M(pi)≤K(pi)- W(tj,pi)
d) (pi,tj)?F并且(tj,pi)?F,
对于V+fj－ 的每一个分量xi 都满足,0≤xi 等价于W(pi,tj)≤ M(pi) 对于V+ fj－＋fj+ 的每一个分量xi 都满足, 0≤xi≤K(xi) 等价于0≤M(pi)－W(pi,tj)＋W(tj,pi)≤K(pi)
二．可达性的矩阵表达
定理3-2:对于P/T网系统，∑=（S,T；F, K,W, M0），σ=M0t1M1t2…tnMn是∑的
一个有限实施序列，其中，Mi对应的状态点为Vi，ti对应的平移变换为fi，则：Vn=V0+∑fi 。
证明：M0[t1>M1 对应的向量表示为：V1=V0＋f1，
M1[t2>M2 对应的向量表示为：V2=V1＋f2 ， ??
M0[σ>Mn对应的向量表示为: Vn=V0+∑fi。
定义 3-1变迁矩阵：对于P/T网系统，∑=（S,T；F, K,W, M0），σ=M0t1M1t2…tnMn是∑的一个有限实施序列，对应的变迁矩阵：TM=[V0 ,V1,?, Vn]每个Vi对应Mi。
定义 3-2变迁选择矩阵：
对于P/T网系统，∑=（S,T；F, K,W, M0），σ=M0t1M1t2…tnMn是∑的一个有限
16
第三章 能量优化模型
实施序列，平移变换集的个数为t，ti 对应平移变迁ft，其变迁选择矩阵为：
iTC=[X0 ,X1,?, Xn],Xi为t维列向量，其中第ti个分量为1，其它的分量为0。
定理 3-3 M0[σ>Mn ? 存在一有限平移变换序列使得V0 变换到Vn，且整个
变换过程的状态点的每一个分量xi 都满足,0≦xi≦K(xi) 。
证明：由定理3-1和定理3-2可得。 §3.2 弱可达性及其分析
一．弱可达性的引入
将定理3-3修改为较弱的命题：
M0[σ>Mn ?存在一有限平移变换序列使得V0 变换到Vn； 也就是存在一组非负整数k1,k2,?kn使得：
?Vn?V0??f1,f2,?fn???k1,k2,?kn? (1)
是M0[σ>Mn的必要条件，其中ki表示变迁ti被实施了ki次。
定义3-2 弱可达性：如果该方程组有非负整点解则称M0到Mn弱可达。 该问题转化为方程组的非负整点解的问题，这个问题又分为两个问题： a．是否有解
b．是否有非负整点解
二．弱可达性的判断 1．求解方程组
对于方程组， ?f1,f2,?fn???x1,x2,?xn?T＝Vn－V0 先三角化，再求解 1) 如果解是零维解，计算出来看是否是非负整点解；
2) 如果解是流形解，设xm,xm+1,?,xn是自由变元，原问题化为不等式方程
组的整点解的问题：
?x1?g1(xm,xm?1,?,xn)?0?x?g2(xm,xm?1,?,xn)?0?2?? (2) ???x?gm?1(xm,xm?1,?,xn)?0?m?1??xm?0,xm?1?0,?,xn?0其中：g1,g2,?,gm-1为关于xm,xm+1,?,xn的线性表达式
2．不等式方程组的整点解问题的转换
定理3-4 将 Maxx1?g1(xm,xm?1,?,xn)作为目标函数，
17
Petri网系统的可达性研究
?g2(xm,xm?1,?,xn)?0?????将 ?gm?1(xm,xm?1,?,xn)?0作为限制条件，该问题转化为整数规划的问
?x?0,x?0,?,xn?0m?1?m?是整数?x1,x2,?,xn题。如果解得x1最大值小于零则原方程无解，否则就有解。
证明： 如果解得x1最大值小于零，则方程组（2）必然无解，否则x1最大值就
大于等于零。
如果解得x1最大值大于等于零，则取该最优值时的各变量取值也满足 方程组（2），即方程组（2）有解。
定义3-2 最短可达距离 (状态间距离下界)
假设方程组（2）有解，将 Min D=x1+x2+?＋xn 作为目标函数，
?g1(xm,xm?1,?,xn)?0?g(x,x,?,xn)?0?2mm?1????将 ?
gm?1(xm,xm?1,?,xn)?0??xm?0,xm?1?0,?,xn?0??是整数?x1,x2,?,xn作为限制条件，该问题又转化为整数规划的问
题。Min D 就称为最短可达距离。其含义是从一种系统状态变迁到另一种系统
状态，在不考虑“越界”情况下，从M0达到Mn所需的最少步骤。也是M0到Mn的状态间距离下界。根据其定义，不难证明。同时解出x1,x2,?,xn，即计算出每个变迁ti被实施的次数。这个状态间距离下界将作为能量优化模型中初始变迁步数设定的一个参考量。
三．整数规划方法介绍[17] 1．数学模型
minf(x)?c1x1?c2x2???cnxn
(p)
?a1,1x1?a1,2x2???a1,nxn?b1?ax?a2,2x2???a2,nxn?b2?2,11?s.t. ???
?ax?ax???ax?bm,22m,nnm?m,11??xi?0且为整数，i?1,2,?,n
相应的线性规划问题（即不考虑整数条件）为 min f (x) =cX
18
第三章 能量优化模型
(p?)
s,t. ??AX?b?X?0 X表示未知变元构成的向量。
称p?为P的松弛问题，P为p?的一个限制。
2．分支定界算法
第一步，求解p?。若p?没有最优解，则停止计算，P也无最优解；否则转入
下一步。
第二步，若求得p?的最优解满足整数条件，则它就是P的最优解，停止计算；否则，转入下一步。
第三步，在p?的解中，任选一个不是整数的变量xj，如xj的值为bj，作两
个后继问题，即对问题p?增加一个约束条件xj 小于bj的最大整数或xj大于bj的最小整数，不考虑整数条件，求解这两个后续问题。
第四步，在现有的且未分解出后续问题的可行问题中，选目标函数值为最小的问题重新称为问题p?，返回第二步。
3．线性规划问题
对于问题p?，即线性规划问题有许多方法，在此对算法本身不作详细介绍，只简单说明一下方法的思想。
? 单纯形法[17]： 对于标准形式的线性规划问题,若有有限最优值，则目标函数的最优值必在某一基本可行解处达到，因而只需在基本可行解中寻找最优解。单纯形法的基本思想就是先找一个基本可行解，检验是否为最优解，否则，再找一个使目标函数值有改进的基本可行解进行检验，反复进行迭代，直到找到最优解，或判断问题无界（即无有限最优值）。
? Karmarkar投影尺度算法[33]： 1984年AT&T贝尔实验室的N. K. Karmarkar，提出一个新的解决线性规划的多项式时间算法，成为线性规划突破性进展，以后几乎被所有现代LP(线性规划linear programs)解决方案所采用。这种算法不同于单纯形方法，每次迭代不是从一个极点出发求改进的极点，而是使迭代点保持在单纯形内部，因此是一种内点算法。其基本思想是，给定一个可行内点，对解空间进行变换，使得现行解位于变换空间中多胞形的中心附近，然后使它沿着最速下降方向移动，求得一个改进的可行内点，再做变换，将在变换空间中求得的点映射回原来的解空间，得到新的内点，重复以上过程，直至求出满足精度要求的最优解。算法的总复杂度为 O(n3.5L2 lnL lnlnL),其中n是变量数，L是方程个数。
19
Petri网系统的可达性研究
五．整数规划常用数学软件
MATLAB[16]是一个高性能的科技计算软件，广泛应用于数学计算、算法开发、数学建模、系统仿真、数据分析处理及可视化、科学和工程绘图、应用系统开发，包括建立用户界面。当前它的使用范围涵盖了工业、电子、医疗、建筑 等各领域。MATLAB是英文Matrix Laboratory(矩阵实验室)的缩写，最早是由C.Moler用Fortran语言编写的，用来方便地调用LINPACK和EISPACK矩阵代数软件包的程序。后来他创立了MATHWORKS公司，对MATLAB作了大量的、坚持不懈的改进。现在MATLAB已经更新至6.x版，MATLAB提供的工具箱已覆盖信号处理、系统控制、统计计算、优化计算、神经网络、小波分析、偏微分方程、模糊逻辑、动态系统模拟、系统辨识和符号运算等领域。
目前在欧美各国MATLAB的使用十分普及。在大学的数学、工程和科学系科，MATLAB被用作许多课程的辅助教学手段；在科研机构和工业界，MATLAB是高质量新产品研究、开发和分析的主要工具之一。1997年，MATHWORKS公司总裁兼首席科学家Moler因其对MATLAB的贡献当选为美国工程科学院院士。 相关资料请浏览MATHWORKS公司主页：http://www.mathworks.com
LINDO是一种专门用于求解数学规划问题的软件包。由于LINDO执行速度很快、易于方便输入、求解和分析数学规划问题。因此在数学、科研和工业界得到广泛应用。LINDO主要用于解线性规划、非线性规划、二次规划和整数规划等问题。也可以用于一些非线性和线性方程组的求解以及代数方程求根等。LINDO中包含了一种建模语言和许多常用的数学函数（包括大量概论函数），可供使用者建立规划问题时调用。 一般用LINDO（Linear Interactive and Discrete Optimizer）解决线性规划（LP—Linear Programming）。整数规划（IP—Integer Programming）问题。其中LINDO 6 .1 学生版至多可求解多达300个变量和150个约束的规划问题。其正式版（标准版）则可求解的变量和约束在1量级以上。LINDO有多种组件和版本，版权由美国Lindo System Inc.拥有，有关该软件的发行版本、发行价格和最新信息可从该公司网站http://www.lindo.com获取
§3.3 能量优化模型建立和分析
一．N步可达性
定义3-3 状态间距离上界：
P/T系统∑=(S,T,F,K,W, M0)的可达标识集[M0>，可达标识集中任意两个状态Mi ,Mj，如果从Mi 可达到Mj, 则将实施序列长度记为: length (Mi ,Mj)， 令状态间距离上界 D(∑)=max{ length (Mi ,Mj) | Mi ,Mj ?[M0> } 定义3-4 N步可达性
对于P/T网系统，∑=（S,T；F, K,W, M0），和状态标识M，对于给定的步数上界N，如果存在σ=M0t1M1t2…tnMn是∑的一个有限实施序列，Mn=M， 且n 很明显N步可达性的条件比可达性强，当然由于状态间距离上界不知道，所以很难确定N, 规定一个N步可达性其原因在于： 1. 在实际的变迁中或随机Petri网中，当实施步骤越多，发生的概率越小； 2． 在能量优化模型中必须有这么一个变迁步数的上界便于分析。 20