基于Petri网的网络最小费用最大流算法.pdfVIP

第 3O卷 第 3期 兰 州 交 通 大 学 学 报 VO1．3ONo．3 2011年 6月 JournalofLanzhouJiaotongUniversity June2011 文章编号：1O01—4373(2O11)03—0067—04 基于Petri网的网络最小费用最大流算法 宋宇博 ， 蒋兆远 ， 牟海波 (1．兰州交通大学 机电技术研究所，甘肃 兰州 730070；2．兰州交通大学交通运输学院，甘肃 兰州 730070) 摘 要：将Petri网方法应用于求解网络的最小费用最大流问题，提出费用Petri网的定义，设计费用Petri网的变 迁使能规则并提出求解最小费用最大流问题的Petri网算法．与以往的算法不同，该算法通过对库所进行标号寻找 变迁的触发序列，并在该序列上增流．最后举例说明算法的应用． 关键词：最小费用最大流；费用Petri网 Petri网算法；触发序列 中图分类号：TP3910224 文献标志码：A 形式化描述方法．由于刻画系统的需要，一些专家和 0 引言 学者又定义和研究了含各种因素的Petri网，使得 最小费用最大流问题是运筹学中的经典问题， Petri网的应用领域进一步扩大[10-14]． 在交通运输、物流等领域应用非常广泛．从理论上来 本文将Petri网应用于求解最小费用最大流问 说这个问题已有多种算法，较为经典的一种算法是 题，设计了相应的求解算法． 用最短路算法求最小费用的增广链 ，并首先在这条 1 有向网络的费用 Petri网表示 链上增加流量，即始终保持费用最优而逐步调整至 最大流．另一种算法是先求得最大流，然后调整流在 1．1 Petri网的定义 各条边上的分配情况使费用降低，最终得到最小费 文献E15：]中对 Petri网(PN)的定义为 用最大流[1]．但是，这些经典算法存在着步骤繁复、 Petri网是一个五元组 ∑一 (P，T，Pre，Post， 计算量大、速度慢等问题，因此实用性不能令人满 Mo)，其中： 意．近年来，一些学者针对这一问题，提出了新的求 1)P一 {P1，P2，…，P)，为有限的库所集． 解方法．文献E31研究了带容量限制的带固定费用和 2)T一 {t，t2，…，t)，为有限的变迁集，且Pn 可变费用的最小费用流问题 ，并针对最优解的结构 T==： ，PUT≠ ． 特点设计遗传算法求解．文献1-43提出了一种寻找最 3)肌 ：P×T—N为前向关联函数，N是非负 小费用增广链的改进标号法，文献E53提出最小费用 整数集． 流参数的数据库存贮方式，借助SQL语言的优点提 4)Post：P×T— N为后向关联函数． 出了一种求解最小费用流的简便算法．文献[6—9]分 5)Mo：P—N为初始标识，用托肯表示． 别提出求解各种最小费用流问题的算法．如果最小 ()和O()定义为变迁的输入和输出库所，其 费用流问题中给定的流值为最大流，则为最小费用 中：I(￡)一 {P lP (夕，￡) 0)，O(￡)一 {P l 最大流问题． Post( ，)O}．为了使PN能表示G中与弧的费用 Petri网是 1962年德国的CA．Petri博士首先 有关的数值，引入费用Petri网(CostPetriNet，简记 提出的，它是一种系统建模与分析的工具，适合于描