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

本文研究了求解各种离散事件动力系统的典型模型之一的位置-转移Petri网可达性问题的数学规划方法。利用广义离散庞特里亚金最小最小原理（即“PMP+LP”），给出了子标记可达性问题（即SMR）中可执行射击序列的最短长度算法。在已知射击次数的基本标记可达性问题中，得到了具有规定长度的可执行射击序列的算法。向量（即MR-FV）通过特殊的“PMP+LP”以及“DP+LP”（即动态规划包括线性规划）。这些算法将原始问题分解为d个更小的子问题，并且在忽略检验临界虹吸的情况下具有半多项式的时间复杂度，这是一个重要的未来研究问题，其中d为跃迁触发序列的长度。请注意，SMR （MF-FV，等）是最基本的可达性问题，没有（有，等）已知的Petri网si-ate方程中的发射计数向量。对于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.