Zurück zu den Preprints des Jahres 1997


On Standardization Problem Solution Problems

by Girlich, E., Kovalev, M., Zaporozhets, A..

Series: 1997-36, Preprints

90C10 Integer programming

We consider the standardization problem (SP) which can be formulated as
follows. There are m types of items. There exist a demand in items of n types represented
by a vector b 2 Z n
+ . There are known possibilities of replacement of some items type by
others. Producing y i items of the ith type, one becomes a profit f i (y i ), where f i : R! R
is a nondecreasing concave function for each i_2 f1,2,...,ng. It is necessary to satisfy the
demand and to maximize the total profit under the replacements condition. We show that
SP and its generalization are special cases of resource allocation problem over a network
polymatroid. An adaptation of Scaling Algorithm for SP is proposed.

Standardization problem, Resource allocation, Network polymatroid, Bipartite graph.