求解一次不定方程的Petri网方法(Ⅲ)——Frobenius问题研究

Use of Petri Nets for Solving Indeterminate Equations of the First Degree (Ⅲ)——Research of Frobenius Problem

本文分别从Ⅰ型一次不定方程网的可达性和活性出发,导出当 m≤(sum from i=2 to n)a_i(d_i-1)/d_i-(sum from i=1 to n)a_i时,不定方程a_1x_1+a_2x_2+…+a_nx_n=m有非负整数解的两个不同的充分必要条件;并根据充分必要条件的不同提法,给出求n元线性型最大不可表数的两个算法。

Two sets of necessary and suffient conditions of the existence of nonnegative integer solutions for the indeterminate equation a_1x_1+a_2x_2+…+a_nx_n=m where are presented in this paper. They are developed from the discussion of the reachability and liveness, respectively, of the Petri net model Type—Ⅰ of indeterminate equation of the first degree. According to these conditions, two kinds of algorithms for the Frobenius Problem are given.