数理計画法による離散事象システムの動作解析とその応用

本文研究了离散事件动态系统的典型模型之一-位置变迁Petri网的可达性问题的数学规划方法，利用包含线性规划的广义离散时间Pontryagin极小值原理（即，在基本的标记可达性问题中，我们也得到了在已知触发次数的情况下，具有指定长度的可执行触发序列的算法。矢量（即，MR-FV）通过特殊的“PMP+LP”以及“DP+LP”（即，这些算法将原问题分解为d个更小的子问题，并具有半多项式的时间复杂度，其中d是触发转移序列的长度。是最基本的可达性问题，而不需要（分别）对于MR-FV，给出了一个新的可达性判据，即由于MR-FV中的触发计数向量是预先确定的，因此对于每个强连通的最大虹吸，给定的Petri网的可达性约为1.利用T-不变量和状态方程的扩展特解求MR-FV中可执行触发序列的另一种方法。这种方法有望对自由选择Petri网的可达性问题的研究有所帮助。

In this research, we obtained some mathematical programming approaches to reachability problems for place-transition Petri nets which are one of typical models for various kinds of discrete event dynamical systems.An algorithm for the executable firing sequence with the shortest length in the submarking reachability problems (i.e. SMR) is given by general discrete-time Pontryagin s mini mum principle included linear programmings (i.e., "PMP+LP" ).We also obtained algorithms for the executable firing sequence with the prescribed length in the basic marking reachability problems with the known firing count. vector (i.e., MR-FV) via special "PMP+LP" as well as "DP+LP" (i.e., the dynamic programming included linear programmings).These algorithms divide die original problem into d smaller subproblems and have semi-polynomial time complexity provided that checking critical siphons, which is an important future research problem, is neglected, where d is the length of firing sequence of transitions.Note that SMR (MF-FV, resp.) is the most, fundamental reachability problem without (with, resp.) the known firing count vector in si-ate equation of Petri nets.For MR-FV, a new reachability criterion is also given, that is, the reachability for a given Petri net is reduced to one for each strongly-connected and maximal siphon because the firing count vector in MR-FV is in advance specified. Another approach to finding the executable firing sequence in MR-FV by using T-invariants and the extended particular solution of state equation. This approach is expected to be useful for reachability problems of live free-choice Petri nets.