基于Petri网的电子商务建模分析

基于Petri 网的电子商务建模分析

董　岗,傅铅生

(南京航空航天大学经济与管理学院,江苏南京210016)

摘要:针对电子商务系统中事件是随机并行发生的特点,提出了利用Petri 网理论来化解

事件冲突的观点,并对电子商务系统进行Petri 网建模,利用矩阵方程对模型进行分析研究,以提升电子商务系统的整体运作效率。

关键词:Petri 网;并发;建模;矩阵方程中图分类号:TP311.5文献标识码:A 文章编号:1672-0334(2004)01-0072-04

Study Simultaneous H appening Function of E -commerce

System on the B asis of Petri N et

DON G G ang ,FU Qian 2sheng (College of Economics and Management ,

Nanjing University of Aeronautics and Astronautics ,Nan jing 210016,China )

Abstract :The main characteristic of in the E -commerce s ystem is the random and simultaneous ha ppn 2ing of incidents ,the paper has proposed the view of utilizing Petri net ′s theory to dissolve the incident con 2flict.Petri net model is established in the E -commerce s ystem.The dynamic and simultaneous happening features of the model are analyzed in the hope of improving the efficiency of the E -commerce system.

K eyw ords :Petri net ;Simultaneous happening ;Setting up model ;Matrix equations

　收稿日期:2003-05-22

　作者简介:董岗(1979-),男,安徽太和人,南京航空航天大学硕士研究生,研究方向:电子商务。

1　引言

电子商务是基于通信网络技术和商务理论的商务模式,由于其具有“突破时空限制,让企业与客户、供应商紧密接触并把有限选择变成无限要求”的主要特征,所以众多企业纷纷投入到电子商务的建设中去。但目前一些电子商务系统还未能很好解决流程中断问题,原因主要是在以往的电子商务系统设

计中,主要采用结构化设计法或面向对象的设计方法,这些方法能够清晰的描述系统中功能层次结构和功能模块间的信息流向以及数据结构等,尤其是面向对象法还能较好的解决软件中重要问题,这些设计方法考虑的是按顺序发生的事件。但在系统运

第17卷第1期2004年2月 管　理　科　学MANA GEMEN T SCIENCES IN CHINA

Vol.17No.1

February ,2004

行时,事件的发生往往是随机的,大多是并行发生的,所以仅仅采用上述方法还不能保证很好的实现用户对系统的性能要求。电子商务系统通常有很多事件同时发生,一个任务描述一个事件,整个系统的并发机制是通过让很多任务并行运行而实现的。一个强调并发任务的系统设计通常都会显得更加清楚并且易于理解,而利用Petri 网理论所建立的模型能

够达到这一要求。[1]

Petri 网是完全从过程的角度出发,通过对复杂系统的描述与分析而进行设计的一种有效模型工具,它在描述并发、冲突、同步等重要行为现象所表现出的优势以及具有形式化步骤与数学图论相支持的理论严密性,特别是其图形表达直观和便于编程实现的技术特点尤其适合并发任务系统的设计。利用Petri 网所建立的模型不但可以达到宏观控制效果,而且可以从微观上反馈这些支付流程的每一细节。此外,它还着眼于系统中的变化、变化发生的条件和发生后的影响、变化间的关系等。所以把Petri 网理论用在电子商务系统的描述中,通过建模分析研究,解决并发事件的冲突,这对提升电

子商务系统的整体运作效率具有很大的作用。

[2]

2　Petri 网的基本定义

一般Petri 网定义为六元组

∑=

(P

,T ;F

,K ,W ,

M 0)[3]

其中,P 为位置的集合(每一位置代表一种资源),用圆圈代表,表示系统的状态;T 为转移的集合,用空心矩形代表,表示系统中的事件;F 称为流关系,其规定资源的流动;K 、W 和M 依次是N 上的容量函数、权函数和标识,M 0称为

∑的初始标识。

常见的流程包括顺序、迭代、并发和选择,其Petri 网的表示分别见图1、图2、图3、图4。

图1　顺序流程

图2　迭代流程

图3　并发流程

图4　选择流程

利用Petri 网建模具有以下优点。

(1)从控制和管理的角度模拟系统,不涉及系统所依赖的物理化学原理,这样可以简化某些细节,易于理解;

(2)精确描述系统中事件的依赖关系和不依赖关系,这是事件之间存在的、不依赖于观察的关系;

(3)具有统一的语言描述系统结构和行为,方便建模仿真,从而起到沟通不同子系统间桥梁的作用;

(4)与顺序模型不同,Petri 网系统比其他图形建模工具更适于描述同步并发系统,并为解决一些问题提供了新途径,如属于不同系统的事件之间的并发问题、局部目标和全局目标之间的冲突问题、资源有限带来的限制问题、不同类型信息流的统一描述问题、不同机器和不同用户之间的不同类型接口问题等。

3　利用Petri 网对电子商务进行建模

Petri 网理论在许多领域得到了广泛的应用,它既可用来描述系统中物质资源的流动(如在柔性制

造系统中的原料、半成品的加工过程,此时系统中的令牌(Token )表现为一种物质资源),又可用于描述信息资源。许多复杂信息系统,尤其是具有分布、并发、异步等特性的电子支付系统,为了分析、评价、开发电子支付系统,必须首先用某种恰当的数学模型描述系统的功能、系统的结构、系统的动态行为、系统各部分之间及其与环境之间的交互作用,我们一般用Petri 网中的基本网系统来描述信息资源的流动,信息资源的流动不同于物质资源的流动,它主要是质的变化。由于系统分析的根本目的是分析出信息合理的流动、处理、存储的过程,图形建模分析技术Petri 网采用二维图形的方法描述系统,利用网图

3

7第1期 基于Petri 网的电子商务建模分析

图5　电子商务系统的Petri 网模型

元素约束机制映射系统的内部关系,对并发系统提供了一种相似化的建模方法,较好的克服了一般建模技术对并发系统建模的缺点,且便于用户理解,对系统所出现的事件冲突问题可以更好的加以解决。系统的Petri 网观点可简单的归纳到两个基本概念:事件和条件,许多系统均可从事件与条件的观点去建模。事件是系统中的动作,事件的出现是由系

统状态控制的;系统状态可描述为一组条件,条件就

是系统状态的谓词或逻辑描述;条件可以成立(为

真),也可以不成立(为假)。由于事件是动作,所以

它可以发生。为了使事件发生,必须使某些条件成

立,这种条件称为事件的前条件;事件的发生可能破

坏前条件而使另外的条件成立,这种条件称为事件

的后条件。

本文用上述观点来研究电子商务系统的建模问

题。一般电子商务的流程可用语言描述为:客户通

过浏览信息向商家提交订单,然后输入用于电子支付的信用卡号和密码;商家接到提交的订单后,通过

查看库存信息形成可供订单;得到银行的支付确认

后,商家将可供订单转为有效订单,并修改库存信

息;再按有效订单配送货物,接着商家进行下次交易

的处理。

这个系统的条件(状态)可概括为:

P 1:客户;P 2:可供订单;

P 3:有效订单和库存信息;P 4:商家

事件(转移)可概括为

:

T 1:支付确认;T 2:查看库存;T 3

:配送货物。

所研究系统的事件和条件见表1。表1　电子商务系统的事件和条件表事件前条件后条件

T 1P 1

,P 2P 1,P 3T 2P 4

P 2T 3P 3P 4

上述系统很容易用Petri 网建模,

条件用Petri 网

的位置表示,事件用Petri 网的转移表示,转移的输

入是转移所对应事件的前条件,转移的输出是转移所对应事件的后条件。事件的发生对应于转移的点火。条件为真,用条件所对应的位置中的令牌来表

示。[4]

根据上述思想,对电子商务系统建立的Petri

网模型见图5。4　利用矩阵方程对所建Petri 网模型进行分析研究用矩阵方程对所建立的电子商务系统Petri 网模

型进行分析研究,为了建立矩阵方程,用两个矩阵

C -和C +表示Petri 网中的流关系。矩阵C -表示与输入位置的连接关系,矩阵C +表示与输出位置的连

接关系,而Petri 网的关联矩阵C 为(C +-C -)。矩

阵方程是分析Petri 网的一种很有前途的方法,它不

仅能研究Petri 网的守恒问题,还能研究Petri 网中的

可达问题。

[5]

(1)Petri 网守恒条件

当且仅当存在一个正权矢量W ,使C ?W =0;

(2)Petri 网可达条件

设一个标识M ′是可从M 达到的,则存在一个转

移的点火序列бM 使标识从M 到M ′,即意味着下列

方程存在一个解———F [б]。

M ′=M +X ?C

根据以上规则对所建立的电子商务系统Petri 网

模型进行分析研究。

此Petri 网的关联矩阵为

C -[j ,i ]=W (p i ,t j )=1100

00010010

C +[j ,i ]=W (t j ,p i )=1020

0100

0001C =C +-C -=102001000001-1100

00010010

=0-120

010-1

00-11

分析网的执行情况:在给出网系统的静态特征的基础上,再定义转移发生的条件和后果,就能描述47管理科学 2004年2月

网的动态运行。但网要实现动态执行,M0必须具有发生权的转移的点火,使令牌在网内重新分布,使网达到新的状态M′,当不存在有发生权的转移时,执行过程停止。

本Petri网的起始标识M0=(1,0,0,1),表示P1为输入用于电子支付的卡号与密码;P2为接到订单的商家。

首先,判断所建Petri网是否可以点火。

T1:′T1={P1,P2}

因为M(P2)=0

T3:′T3={P3}

因为M(P3)=0

T2: ′T2={P4}

M(P4)=1=W(P4,T2)=1

T′2={P2}

M(P2)+W(T2,P2)=0+1=1=

K(P2)

所以T2有发生权。

通过判断,只有T2有发生权,求出T2点火后的标识M′

M′=M0+F[б]?C=(1,0,0,1)+

(0,1,0)0-12

0 010-1 00-11

=(1,1,0,0)

表示接到订单的商家,通过查看库存信息,形成可供订单,即P2中有令牌。

若转移点火序列б=T2,T1,T3,T2,T1,则点火矢量T(б)=(2,2,1),经过б后产生的标识M”为

M″=(1,0,0,1)+(2,2,1)0-1

20 010-1 00-11

=(1,0,3,0)

为了证明从(1,0,0,1)可以到达(1,6,1,1),可写出下列方程

(1,6,1,1)=(1,0,0,1)+

X 0-1

20 010-1 00-11

解得X=(7,13,13)

同理,可以证明从(1,0,0,1)到(1,6,0,1)是否可以到达,解下列方程

(1,6,0,1)=(1,0,0,1)+

X 0-

120

010-1

00-11

解得X=(6,12,-12)

由于T3的点火次数是-12次,不合题意。所以

从(1,0,0,1)到(1,6,0,1)是不可到达的。

矩阵方程是分析Petri网的一种很有效的方法,

但也有其不足之处。

(1)它不能表示有自环的Petri网。因为C=C+

-C-,减去了自环,如C(1,1)=C+[1,1]-C-[1,

1]=0。

(2)点火矢量中缺少转移点火顺序信息。如点火

矢量F[б]=(1,2,2),它对应的点火序列是б=

T2,T3,T1,T2,T3还是б=T2,T3,T2,T3,T1不

能确定。

(3)方程M′=M+X?C是可达的必要条件,

但不是充分条件。

5　结束语

现实中运行的电子商务流程必须是正确的,因

为有些设计错误在实际运行中很难跟踪,并且需要

用昂贵的实践代价去弥补损失。因此,电子支付系

统的设计者需要对其流程采用一定的模型去模拟实

验。Petri网是完全从过程的角度出发为复杂系统的

描述与分析而设计的一种有效模型工具,它在描述

并发、冲突、同步等重要行为现象所表现出的优势以

及具有形式化步骤与数学图论相支持的理论严密

性,特别是其图形表达直观和便于编程实现的技术

特点尤其适合并发任务系统的设计。但其运用于电

子商务系统的设计,目前所见到的文献较少。但

Petri网所能描述的复杂系统的开发、异步、冲突等行

为在系统设计中很常见,尤其是电子商务系统。所

以利用Petri网建立模型,并进行有效的分析研究,

就可在真正实施电子商务之前对电子商务系统的运

行效率作出评价、比较,得到定量化的结论作参考,

尽量避免付出巨大的实践代价,积极推进我国电子

商务的广泛应用,以提高我国企业的国际竞争力。

参考文献:

[1]张维明,邓苏,罗雪山,肖卫东.信息系统建模技

术与应用[M].北京:电子工业出版社,1997.99

-122.

[2]王行仁.建模与仿真的回顾及展望[J].系统仿

真学报,1999,(5):309-311.

[3]张维明,刘忠,肖卫东.信息系统建模[M].北

京:电子工业出版社,2002.132-146.

[4]王红卫.建模与仿真[M].北京:科学出版社,

2002.222-229.

[5]中国系统工程学会.物流系统三色Petri网建模

与分析[J].系统工程理论与实践,2003,(2):73-

79.□

57

第1期 基于Petri网的电子商务建模分析

Petri网发展综述

1． Petri 网发展综述 Petri 网模型时C 。A 。petri 博士于1962年提出来的，他的提出专门应用这样一类系统，即系统中国含有相互作用的并行分支。作为研究系统的一种工具，petri 网理论用一个petri 网作为以恶系统的模型——系统的数学表示。从petri 网的观点来看待一个系统，集中地表现为两个本原的概念，即事件和条件。事件是系统中大声地动作，条件即系统的状态。系统中的动作的发生是由系统的状态来决定的，协调的状态演变是由系统的事件来驱动的。而这些状态可以用一组条件来描述。条件满足动作即可发生，动作发生后达到下一状态，它可以揭示出被模拟的系统的结构和动态行为方面的重要信息。这些信息可以用来对被模拟的系统进行估价并提出改进系统的建议。六十年代petri 网的研究以孤立的网系统为对象，以分析技术和应用方法为目标，通过网论丛七十年代开始研究，主要内容为网系统的分类及各网类之间的关系，包括：并发论，同步论，网逻辑和网拓扑，八十年代petri 网的研究在世界及中国有了较大的发展，近年来国内的主要研究集中在petri 网的语义，公平性，活性，网运算，网化简，PN 机理论等等。 当今计算机技术的发展日新月异，计算机计算能力的发展促进了模拟技术的应用和发展，用一个数学模型，比如petri 网来表示一个系统，然后，通过一定的算法让计算机对模型分析，就可以得到有关系统的性质。由于计算机计算的高速性和准确性，这就使得对巨大，复杂人工难以胜任的系统的模拟成为可能。 随着科学技术的发展出现了许多大规模的信息处理系统，如：并行程序，分布式操作系统，大规模的通信网络系统等等。由于petri 网可以精确描述系统事件之间的顺序并发关系，所以它是分析并发系统的强有力的工具。 Petri 网的研究工作沿着两个方向发展。第一，纯petri 网理论；第二，应用petri 网理论。 纯petri 网理论是为发展应用petri 网理论所需要的基本概念，技术和手段所做的研究。近年来petri 网理论的研究取得了不少研究成果，如petri 网的结构性质；petri 网语言：随机网，颜色网；谓词变迁系统等等。有国内吴哲辉教授和美国的T 。Murata 教授共同提出的petri 网的公平性取得了十分完整的结果，对于解决网系统中两个变迁（变迁组）的发生的关系提出了理论依据。蒋昌俊教授建立了PN 机理论构架，在交叠语义和偏序语义下获得反映真并发行为的文法及其PN 机结构，揭示它们的计算能力及其相互关系。 应用petri 网理论主要从事用petri 网模拟，分析和洞察系统的研究。这方面不单要求对petri 网及其模拟技术有深厚的知识，而且必须对应用领域相当熟悉。结合当今技术的发展越来越多地应用到通讯系统，分布式系统，并行计算机系统及自然科学社会科学的很多方面。 应用petri 网理论的一个重要方面就是并发系统petri 网分析工具的构造。Petri 网被应用于分析和设计系统时，如果系统规模较大则其对应模型必将十分复杂。人工分析显然是低效且不十分可靠的。因此，分析中若能有效地使用计算机则可十分迅速可靠的得到petri 网的性质。 2．Petri 网 Petri 网是用于描述分布式系统的一种模型。它既能描述系统的结构，又能模拟系统的运行。描述系统结构的部分称为网。从形式上看，一个网就是一个没有孤立结点的有向二分图。 定义1 满足下列条件的三元组N=（S ，T ；F ）称作一个网： 1） φ≠T S （1.1）

petri网的理论及应用

Petri网的综述及应用 蔡振宇 摘要： 一、Petri网的发展 Carl Adam Petri于1962年在他的博士论文中首次提出了有关Petri网的概念。自上世纪八十年代第一次Petri网理论和应用的国际研讨会的召开以来,与之相关研讨会在世界范围内就开始以一年一度的频率召开。人们通常称赞Petri网描述异步并发与图形表示的能力，而这两个特点来源于其网状结构。世间万物皆由网构成，只是这个网是有形的或是无形的，万事万物在这些网上发生着变化。事物间依赖关系，正是Petri网的完美体现。描述物理世界的客观存在，使客观存在成为论文的研究对象，同时还必须保证凡是用其描述的系统都能转换为客观存在。前者称为系统模型的仿真性，后者则是系统模型的可实现性。目前Petri 网己扩展成多种形式，如基础Petri网、时间Petri网、层次Petri网、有色Petri网等等[}z6-3 y。 一个Petri网的结构元素包括:库所(place)、变迁(transition)和弧(acr)。库所也称位置，它是一个抽象的词语，不是具体指哪个确定位置，而是建模中恰巧画的位置，它主要的作用是描述网中的一个局部资源状态或者是条件。变迁是用于描述变化着的系统事件，它表示的是一种资源相互作用的事件发生关系。弧的意义是描述资源的使能转化方向，是库所中消耗和产生的依据。如图2-1中，以红点来显示的是托肯(token)或者称为标记，它存在于库所中，呈现库所的资源数量，是Petri网中的一个重要概念。托肯在网中的动态变化意味着网的不同状态。一个简单的网系统模型，如图2-1所示。 -+Petri网从客观的角度对系统的发生进行定性和定量的描述，并能呈现出有规律的定性和定量的改变。在Petri网中，把对象统称为资源。定性相同的资源定为一类，用一个状态元素P来表示。托肯的数量代表了库所P的状态。尸的定性和定量的改变也就是上面所称的变迁T。在建模中库所P用圆圈来表示，变迁T用方框来表示，有向弧用箭头来表示。建模中箭头由圆圈指向方框意味着消