On the linear assignment problem for special matrices

摘要

This study arises from the intersection of two application areas of management mathematics and control theory: the assignment problem and the theory of discrete-event dynamic systems (DEDS), The assignment problem is to find the cheapest one-to-one pairing between two sets (e.g. machines and operators), given a matrix (a_(ij)) of the cost of pairing the z'th machine with the jth operator. A DEDS is a system such as certain manufacturing, transportation or data-processing systems, which move from event to event in discrete steps. The realization problem for such a DEDS is that of deducing its possible structure on the basis of a stream of observations, g_0, g_1,..., known as Markov parameters. The structure is expressed in a linear-algebraic model known as a realization and for economy a realization of minimal dimension (MDR) is sought. For certain DEDS, it is convenient to work in max-algebra, in which the classsical operations of addition and multiplication are replaced by the operations max and +, respectively. Establishing a lower bound for the dimension of an MDR then turns on finding the structure of the optimal solution set of an assignment problem whose cost matrix is a Hankel matrix. This is connected to a known hard combinatorial problem and does not seem to be solved for Hankel matrices in general. However, the paper shows that a straightforward solution exists in two special cases, when the sequence {g_r} is either convex or concave.