97-36
On Standardization Problem Solution Problems
by Girlich, E.; Kovalev, M.; Zaporozhets, A.
Preprint series: 97-36, Preprints
- MSC:
- 90C10 Integer programming
Abstract: 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.
Keywords: Standardization problem, Resource allocation, Network polymatroid, Bipartite graph.
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.