论文部分内容阅读
近年来，政府采购规模不断扩大，招标方式也趋于多样化，如何优化采购业务流程、提高效率成为政府采购领域的重要研究内容之一。本文以竞争性谈判为例，采用广义随机Petri网（GSPN）模型对政府采购业务流程进行建模，并利用GSPN与马尔可夫链的同构关系，分析了竞争性谈判的一些动态性能。结果表明，发布采购公告、接收文件、审核、签发合同等变迁的触发与后面相邻变迁的触发之间有较长的时间间隔，核心环节的平均执行时间约为2.97倍单位时间
一、引言
政府采购是指各级国家机关、事业单位和团体组织，使用财政性资金采购依法制定的集中采购目录以内的或者采购限额标准以上的货物、工程和服务的行为。近年来，我国政府采购规模日益扩大，采购金额从2009年的7413.2亿元增长到2012年的13900多亿元。通过对其业务流程进行建模与分析不仅有助于提高采购效率，也能在一定程度上减小寻租的可能性，因此其业务流程建模与分析成了政府采购领域的重要研究内容之一。
常见业务流程建模方法有： CPM /PERT方法、IDEF3方法、随机网络方法、事件驱动的过程链方法、Petri网模型等。其中Petri网模型对于描述系统动态特性、测试业务流程的变化情况非常方便。它既有严格的形式定义， 又有直观的图形表示， 具有丰富的系统描述手段和系统行为分析技术， 是一种适用于多种系统的图形化、数学化建模工具， 为描述并行、异步、分布式和随机性等特性的复杂系统提供了强有力的手段[1]。少数学者也曾基于Petri网对政府采购流程进行建模与分析，如曹萍等利用Petri网对电子政府采购工作流建模并对其可达性和合理性进行了分析[2]，童吉采用基于Petri网的工作流技术对高校设备采购流程进行建模，并提出了一种工作流合理性验证算法和工作流的优化算法[3]。而广义随机Petri网（Generalized Stochastic Petri Nets，GSPN）作为随机Petri网的扩充，它与时间连续的齐次马尔可夫链是同构的，具有很好的数学特性，便于进行定量化的分析。因此，本文试图以竞争性谈判为例，采用GSPN模型对采购业务流程建模，并利用马尔可夫链的计算特性，分析业务流程的一些动态性能。
二、广义随机Petri网（GSPN）的基本原理
随机Petri网（SPN）是Molloy等人基于将变迁与随机的指数实施延时联系起来的思想提出的，它给Petri网的每个变迁关联一个点火速率[4]。广义随机Petri网是SPN的一种扩充，它将变迁分为两类，一类是瞬时变迁与随机开关相关联，实施延时为零，另一种为时延变迁与指数随机分布的实施延时相关联。
根据[5]中GSPN的定义（崔政东，刘晋，2005），GSPN与时间连续的齐次马尔可夫链是同构的，因此可以通过构造相应的马尔可夫链，在存在平稳分布的情况下，即可求出系统的稳定状态概率。用行向量P*= （P*（M1），P*（M2），……，P*（Mk））标识各显状态的稳态概率，则
， （1）
其中，矩阵Q称为马尔可夫过程的激发率矩阵。矩阵Q中非对角线上的元素，即qij（i≠j）取决于马尔可夫链的可达状态图，当图中从标识Mi到标识Mj之间存在一条有向弧时，qij为弧上的点火速率值；当没有弧时qij为零。矩阵Q中对角线上的元素，即 （2）
三、基于GSPN的竞争性谈判业务流程建模与分析
第一步：建立与竞争性谈判相对应的GSPN模型。如图1所示，整个模型由16个库所和16个变迁组成，t1，t2，t3，……，t16均为时延变迁，令其速率分别为λ1，λ2，……，λ16，各库所和变迁的意义如表1和表2所示。
图1 竞争性谈判GSPN模型
第二步：利用马尔可夫链性质对模型进行定量分析。通过分析中国政府采购网上相关数据资料，可知点火速率λ=（4，4，6，4，5，4，4，6，3，2，5，6，2，4，2，1）为变迁t1，t2，……，t16服从指数分布的随机时间参数如下：
表2竞争性谈判GSPN中变迁的意义
变迁 意义 变迁 意义
t1 采购人申报 t9 接收谈判响应文件
t2 采购办审核 t10 谈判实施
t3 委派代理机构 t11 审阅报价文件
t4 成立谈判小组 t12 报送采购人
t5 制作招标文件 t13 公布并接受质疑
t6 采购人审核 t14 签发合同
t7 邀请三家以上供应商 t15 采购资料整理归档
t8 发布采购公告 t16 产生新的采购需求
表1 竞争性谈判GSPN中库所的意义
库所 意义 库所 意义
P1 采购人有采购需求 P9 采购公告已发布
P2 采购请求 P10 完成谈判响应文件接收
P3 采购办审核通过 P11 谈判完成
P4 谈判准备阶段 P12 得出评审结果
P5 谈判小组已成立 P13 采购人完成审核
P6 完成谈判文件制作 P14 未受到质疑
P7 采购人审核通过 P15 完成合同签发
P8 邀请供应商数超过三家 P16 采购结束
其中，在M1状态下只有库所P1下具有一个令牌，随着变迁的触发进入不同的状态。由（1）式可写出激发率矩阵Q，设X=（x1，x2，……，x18）为上述18个可达状态的稳定概率，根据马尔可夫过程有下列方程组：，。使用Excel求解此线性方程组，可得：
可知M10、M11、M14、M16、M17、M18的稳态概率较大（大于等于0.05），说明发布采购公告、接收文件、审核、签发合同等变迁的触发与后面相邻变迁的触发之间有较长的时间间隔。定义广义随机Petri网的一个子系统：PN′=（P′，T′，F′，M0，λ′），其中P′=P-{P1，P2，P3，P4，P15，P16}，F′为F中去除同库所{P1，P2，P3，P4，P15，P16}相连的有向弧后得到的有向弧集，T′和λ′与原网络相同。可以看出，单位时间进入该子系统的令牌数等于单位时间离开库所P4的令牌数。因此，该子系统的平均执行时间就是竞争性谈判核心环节的平均执行时间，计算可得竞争性谈判核心环节的平均执行时间约为2.97倍单位时间。
四、总结
本文采用广义随机Petri网（Generalized Stochastic Petri Nets，GSPN）建立政府采购竞争性谈判业务流程模型，并利用GSPN与马尔可夫链的同构关系，分析出竞争性谈判中的一些动态性能。结果表明，发布采购公告、接收文件、审核、签发合同等变迁的触发与后面相邻变迁的触发之间有较长的时间间隔，其核心环节的平均执行时间约为2.97倍单位时间。GSPN 虽然在一定程度上简化了状态空间，但随着标志数的增加和网的增大，状态数目呈指数增加，给分析带来困难，因此，为了快速求解，还应该在模型同构和压缩上做进一步研究。
参考文献
[1]叶玉全等， 基于Petri网的采购业务流程建模及仿真优化. 计算机应用， 2009（10）： 第2871-2874页.
[2]曹萍，陈福集， 基于Petri网的电子政府采购的工作流建模. 福州大学学报，2009（2）：第18-22页.
[3]童吉， 基于 Petri 网的高校设备采购工作流建模分析和优化. 实验室研究与探索，2012（4）：第188-191页.
[4]Molly，M.K. Performance Analysis Using Stochastic Petri Nets. Computers，IEEE transactions，1982（9）.
[5]崔政东，刘晋， 基于广义随机Petri网的供应链建模与分析. 系统工程理论与实践， 2005（12）： 第18-24页.
（作者单位：中央财经大学信息学院）
作者简介
曾斌（1990-），男，汉族，中央财经大学信息学院，硕士研究生；
朱雷（1973-），男，汉族，中央财经大学信息学院，讲师，博士；宗泽（1990-），男，汉族，中央财经大学信息学院，硕士研究生。
资助项目：中央财经大学学科建设基金
一、引言
政府采购是指各级国家机关、事业单位和团体组织，使用财政性资金采购依法制定的集中采购目录以内的或者采购限额标准以上的货物、工程和服务的行为。近年来，我国政府采购规模日益扩大，采购金额从2009年的7413.2亿元增长到2012年的13900多亿元。通过对其业务流程进行建模与分析不仅有助于提高采购效率，也能在一定程度上减小寻租的可能性，因此其业务流程建模与分析成了政府采购领域的重要研究内容之一。
常见业务流程建模方法有： CPM /PERT方法、IDEF3方法、随机网络方法、事件驱动的过程链方法、Petri网模型等。其中Petri网模型对于描述系统动态特性、测试业务流程的变化情况非常方便。它既有严格的形式定义， 又有直观的图形表示， 具有丰富的系统描述手段和系统行为分析技术， 是一种适用于多种系统的图形化、数学化建模工具， 为描述并行、异步、分布式和随机性等特性的复杂系统提供了强有力的手段[1]。少数学者也曾基于Petri网对政府采购流程进行建模与分析，如曹萍等利用Petri网对电子政府采购工作流建模并对其可达性和合理性进行了分析[2]，童吉采用基于Petri网的工作流技术对高校设备采购流程进行建模，并提出了一种工作流合理性验证算法和工作流的优化算法[3]。而广义随机Petri网（Generalized Stochastic Petri Nets，GSPN）作为随机Petri网的扩充，它与时间连续的齐次马尔可夫链是同构的，具有很好的数学特性，便于进行定量化的分析。因此，本文试图以竞争性谈判为例，采用GSPN模型对采购业务流程建模，并利用马尔可夫链的计算特性，分析业务流程的一些动态性能。
二、广义随机Petri网（GSPN）的基本原理
随机Petri网（SPN）是Molloy等人基于将变迁与随机的指数实施延时联系起来的思想提出的，它给Petri网的每个变迁关联一个点火速率[4]。广义随机Petri网是SPN的一种扩充，它将变迁分为两类，一类是瞬时变迁与随机开关相关联，实施延时为零，另一种为时延变迁与指数随机分布的实施延时相关联。
根据[5]中GSPN的定义（崔政东，刘晋，2005），GSPN与时间连续的齐次马尔可夫链是同构的，因此可以通过构造相应的马尔可夫链，在存在平稳分布的情况下，即可求出系统的稳定状态概率。用行向量P*= （P*（M1），P*（M2），……，P*（Mk））标识各显状态的稳态概率，则
， （1）
其中，矩阵Q称为马尔可夫过程的激发率矩阵。矩阵Q中非对角线上的元素，即qij（i≠j）取决于马尔可夫链的可达状态图，当图中从标识Mi到标识Mj之间存在一条有向弧时，qij为弧上的点火速率值；当没有弧时qij为零。矩阵Q中对角线上的元素，即 （2）
三、基于GSPN的竞争性谈判业务流程建模与分析
第一步：建立与竞争性谈判相对应的GSPN模型。如图1所示，整个模型由16个库所和16个变迁组成，t1，t2，t3，……，t16均为时延变迁，令其速率分别为λ1，λ2，……，λ16，各库所和变迁的意义如表1和表2所示。
图1 竞争性谈判GSPN模型
第二步：利用马尔可夫链性质对模型进行定量分析。通过分析中国政府采购网上相关数据资料，可知点火速率λ=（4，4，6，4，5，4，4，6，3，2，5，6，2，4，2，1）为变迁t1，t2，……，t16服从指数分布的随机时间参数如下：
表2竞争性谈判GSPN中变迁的意义
变迁 意义 变迁 意义
t1 采购人申报 t9 接收谈判响应文件
t2 采购办审核 t10 谈判实施
t3 委派代理机构 t11 审阅报价文件
t4 成立谈判小组 t12 报送采购人
t5 制作招标文件 t13 公布并接受质疑
t6 采购人审核 t14 签发合同
t7 邀请三家以上供应商 t15 采购资料整理归档
t8 发布采购公告 t16 产生新的采购需求
表1 竞争性谈判GSPN中库所的意义
库所 意义 库所 意义
P1 采购人有采购需求 P9 采购公告已发布
P2 采购请求 P10 完成谈判响应文件接收
P3 采购办审核通过 P11 谈判完成
P4 谈判准备阶段 P12 得出评审结果
P5 谈判小组已成立 P13 采购人完成审核
P6 完成谈判文件制作 P14 未受到质疑
P7 采购人审核通过 P15 完成合同签发
P8 邀请供应商数超过三家 P16 采购结束
其中，在M1状态下只有库所P1下具有一个令牌，随着变迁的触发进入不同的状态。由（1）式可写出激发率矩阵Q，设X=（x1，x2，……，x18）为上述18个可达状态的稳定概率，根据马尔可夫过程有下列方程组：，。使用Excel求解此线性方程组，可得：
可知M10、M11、M14、M16、M17、M18的稳态概率较大（大于等于0.05），说明发布采购公告、接收文件、审核、签发合同等变迁的触发与后面相邻变迁的触发之间有较长的时间间隔。定义广义随机Petri网的一个子系统：PN′=（P′，T′，F′，M0，λ′），其中P′=P-{P1，P2，P3，P4，P15，P16}，F′为F中去除同库所{P1，P2，P3，P4，P15，P16}相连的有向弧后得到的有向弧集，T′和λ′与原网络相同。可以看出，单位时间进入该子系统的令牌数等于单位时间离开库所P4的令牌数。因此，该子系统的平均执行时间就是竞争性谈判核心环节的平均执行时间，计算可得竞争性谈判核心环节的平均执行时间约为2.97倍单位时间。
四、总结
本文采用广义随机Petri网（Generalized Stochastic Petri Nets，GSPN）建立政府采购竞争性谈判业务流程模型，并利用GSPN与马尔可夫链的同构关系，分析出竞争性谈判中的一些动态性能。结果表明，发布采购公告、接收文件、审核、签发合同等变迁的触发与后面相邻变迁的触发之间有较长的时间间隔，其核心环节的平均执行时间约为2.97倍单位时间。GSPN 虽然在一定程度上简化了状态空间，但随着标志数的增加和网的增大，状态数目呈指数增加，给分析带来困难，因此，为了快速求解，还应该在模型同构和压缩上做进一步研究。
参考文献
[1]叶玉全等， 基于Petri网的采购业务流程建模及仿真优化. 计算机应用， 2009（10）： 第2871-2874页.
[2]曹萍，陈福集， 基于Petri网的电子政府采购的工作流建模. 福州大学学报，2009（2）：第18-22页.
[3]童吉， 基于 Petri 网的高校设备采购工作流建模分析和优化. 实验室研究与探索，2012（4）：第188-191页.
[4]Molly，M.K. Performance Analysis Using Stochastic Petri Nets. Computers，IEEE transactions，1982（9）.
[5]崔政东，刘晋， 基于广义随机Petri网的供应链建模与分析. 系统工程理论与实践， 2005（12）： 第18-24页.
（作者单位：中央财经大学信息学院）
作者简介
曾斌（1990-），男，汉族，中央财经大学信息学院，硕士研究生；
朱雷（1973-），男，汉族，中央财经大学信息学院，讲师，博士；宗泽（1990-），男，汉族，中央财经大学信息学院，硕士研究生。
资助项目：中央财经大学学科建设基金