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

Algorithm for Seeking the Minimal Cost and Maximal Flow Based on Petri Net

将Petri网方法应用于求解网络的最小费用最大流问题,提出费用Petri网的定义,设计费用Petri网的变迁使能规则并提出求解最小费用最大流问题的Petri网算法.与以往的算法不同,该算法通过对库所进行标号寻找变迁的触发序列,并在该序列上增流.最后举例说明算法的应用.

In this paper,Petri net is adopted for seeking the minimal cost and maximal flow of a network. The cost Petri net is proposed and the enabled rules of transitions are given. In addition,an algorithm for obtaining the minimal cost and maximal flow based on cost Petri net is developed. The proposed algorithm, which is different from the others,is to find the firing sequence of transitions by labeling places and to increase flows in this sequence. Finally, an example is given to demonstrate the application of the algorithm.