Resource allocation among competing activities: A lexicographic minimax approach. (English) Zbl 0627.90068

The minmax linear programming problem \[ \min_{x}\max_{j}a_ j[d_ j-x_ j)/d_ j] \] subject to \[ \sum^{n}_{j=1}a_{ij}x_ j\leq b_ i,\quad i=1,2,...,m,\quad 0\leq x_ j\leq d_ j \] is examined and a fast non-simplex algorithm developed which requires at most \(2n(m+1)\) divisions and multiplications. Then the idea of a lexicographic minmax algorithm for solving the original problem with the objective function \[ lex\min_{x}\{\max_{j}a_ j[(d_ j-x_ j)/d_ j] \] is proposed that improves the result from the point of view of the vector of weighted deviations. The proposed algorithms promise to be effective for a given class of large scale resource allocation and production planning problems.
Reviewer: F.Turnovec


90C06 Large-scale problems in mathematical programming
90B30 Production models
Full Text: DOI


[1] Bazaraa, M. S.; Goode, J. J., An algorithm for solving linearly constrained minimax problems, European J. of Operational Research, 11, 158-166 (1982) · Zbl 0494.90064
[2] Chaddha, R. L.; Hardgrave, W. W.; Hudson, D. J.; Segal, M.; Suurballe, J. W., Allocation of total sample size when only the stratum means are of interest, Technometrics, 13, 817-831 (1971) · Zbl 0223.62021
[3] Charnes, A.; Cooper, W. W., The theory of search: Optimum distribution of search effort, Management Science, 5, 44-49 (1958) · Zbl 0995.90543
[4] Dantzig, G. B., Linear Programming and Extensions (1963), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0108.33103
[5] Federgruen, A.; Zipkin, P., Solution techniques for some allocation problems, Mathematical Programming, 25, 13-24 (1983) · Zbl 0492.90053
[6] Francis, R. L.; White, J. A., Facility Layout and Location: An Analytical approach (1974), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[7] Hax, A. R.; Candea, D., Production and Inventory Management, ((1984), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ)
[8] Hwang, C.-L; Masud, A. S.M, Multiple Objective Descision Making — Methods and Applications; A State-of-the-Art (1979), Springer: Springer New York · Zbl 0397.90001
[9] Luss, H., Allocation of marketing effort among P substitutional products in \(N\) territories, Operational Research Quarterly, 25, 77-88 (1974) · Zbl 0275.90008
[10] Luss, H.; Gupta, S. K., Allocation of effort among competing activities, Operations Research, 23, 360-366 (1975) · Zbl 0298.90015
[11] Mjelde, K. M., Methods of Allocation of Limited Resources (1983), Wiley: Wiley New York · Zbl 0511.90076
[12] Tang, C. S., A component storage space allocation model for a flexible component insertion machine, (ORSA/TIMS Joint National Meeting. ORSA/TIMS Joint National Meeting, Atlanta, GA (Nov. 1985))
[13] Tansel, B. C.; Francis, R. L.; Lowe, J. J., Location on networks: A survey, Management Science, 29, 482-511 (1983) · Zbl 0513.90023
[14] Watson, G. A., Approximation Theory and Numerical Methods (1980), Wiley: Wiley New York · Zbl 0442.65005
[15] Zipkin, P., Simple ranking methods for allocation of one resource, Management Science, 26, 34-43 (1980) · Zbl 0448.90049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.