×

Solution of some convex separable resource allocation and production planning problems with bounds on the variables. (English) Zbl 1220.90091

Summary: We consider the problems of minimizing convex separable functions of two specific forms over a feasible region defined by a linear inequality or linear equality constraint, and two-sided bounds on the variables (box constraints). These problems are interesting from both theoretical and practical point of view because they arise in some mathematical programming problems and in various practical problems, for example, resource allocation and production planning problems. Necessary and sufficient condition is proved for a feasible solution to be an optimal solution to a more general convex separable problem consisting in minimizing a strictly convex separable function subject to a linear inequality constraint and box constraints. Necessary and sufficient conditions for a feasible solution to be an optimal solution to the two problems under consideration are obtained as corollaries of this more general result. Iterative algorithms of polynomial complexity for solving such problems are proposed and their convergence is proved. Some examples and results of numerical experiments are also presented.

MSC:

90C25 Convex programming
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
90B30 Production models

Software:

WinGULF
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Almogy Y., , Operations Research 19 pp 57– (1971) · Zbl 0257.90042 · doi:10.1287/opre.19.1.57
[2] Bajalinov E. B., Linear-Fractional Programming: Theory, Methods, Applications and Software (2003) · Zbl 1067.90154
[3] Barros A. I., Mathematical Programming 72 (2) pp 147– (1996) · Zbl 0853.90106 · doi:10.1007/BF02592087
[4] Bitran G. R., Decision Sciences 8 pp 28– (1977) · doi:10.1111/j.1540-5915.1977.tb01066.x
[5] Bitran G. R., Management Science 27 (4) pp 431– (1981) · Zbl 0454.90059 · doi:10.1287/mnsc.27.4.431
[6] Bitran G. R., Operations Research 24 (4) pp 675– (1976) · Zbl 0361.90073 · doi:10.1287/opre.24.4.675
[7] Cambini A., Journal of Information and Optimization Sciences 10 (1) pp 65– (1989) · Zbl 0676.90081 · doi:10.1080/02522667.1989.10698952
[8] Craven B. D., Fractional Programming (1988) · Zbl 0649.90098
[9] Crouzeix J.-P., Mathematical Programming 52 (2) pp 191– (1991) · Zbl 0748.90067 · doi:10.1007/BF01582887
[10] Crouzeix J.-P., Mathematical Programming 27 (3) pp 342– (1983) · Zbl 0526.90083 · doi:10.1007/BF02591908
[11] Crouzeix J.-P., Journal of Optimization Theory and Applications 47 (1) pp 35– (1985) · Zbl 0548.90083 · doi:10.1007/BF00941314
[12] Dussault J.-P., Mathematical Programming 36 (1) pp 90– (1986) · Zbl 0633.90057 · doi:10.1007/BF02591992
[13] Falk J. E., in Recent Advances in GlobalOptimization pp 221– (1992)
[14] Goedhart M. H., European Journal of Operational Research 82 (1) pp 111– (1995) · Zbl 0904.90162 · doi:10.1016/0377-2217(94)00034-A
[15] Helgason R., Mathematical Programming 18 (3) pp 338– (1980) · Zbl 0452.90054 · doi:10.1007/BF01588328
[16] Ikeda S., International Journal of Systems Science 8 pp 1429– (1977) · Zbl 0372.93029 · doi:10.1080/00207727708942132
[17] Ishii H., Mathematical Programming 13 (3) pp 255– (1977) · Zbl 0378.90071 · doi:10.1007/BF01584342
[18] Jagannathan R., Journal of Optimization Theory and Applications 41 (3) pp 417– (1983) · Zbl 0502.90079 · doi:10.1007/BF00935361
[19] Jo C. L., Optimization 29 (3) pp 205– (1994) · Zbl 0818.90099 · doi:10.1080/02331939408843950
[20] Katoh N., Journal of the Operational Research Society 30 (5) pp 449– (1979) · doi:10.1057/jors.1979.105
[21] Konno H., in Recent Advances in Global Optimization pp 259– (1992)
[22] Kornbluth J. S. H., Management Science 27 (9) pp 1024– (1981) · Zbl 0467.90064 · doi:10.1287/mnsc.27.9.1024
[23] Luss H., Operations Research 23 (2) pp 360– (1975) · Zbl 0298.90015 · doi:10.1287/opre.23.2.360
[24] Martos B., Naval Research Logistics Quarterly 11 pp 135– (1964) · Zbl 0131.18504 · doi:10.1002/nav.3800110204
[25] Mukherjee R. N., Journal of Mathematical Analysis and Applications 162 (2) pp 309– (1991) · Zbl 0751.90075 · doi:10.1016/0022-247X(91)90151-O
[26] Nemirovskii A., Mathematical Programming 73 (2) pp 175– (1996) · Zbl 0853.90107 · doi:10.1007/BF02592102
[27] Nemirovskii A., Mathematical Programming 77 (2) pp 191– (1997)
[28] Nesterov Y. E., Mathematical Programming 69 (1) pp 177– (1995)
[29] Nykowski I., European Journal of Operational Research 19 (1) pp 91– (1985) · Zbl 0555.90098 · doi:10.1016/0377-2217(85)90312-1
[30] Patriksson M., European Journal of Operational Research 185 pp 1– (2008) · Zbl 1146.90493 · doi:10.1016/j.ejor.2006.12.006
[31] Saad O. M., Journal of Information and Optimization Sciences 14 (1) pp 87– (1993) · Zbl 0784.90087 · doi:10.1080/02522667.1993.10699139
[32] Schaible S., Operations Research 24 (3) pp 452– (1976) · Zbl 0348.90120 · doi:10.1287/opre.24.3.452
[33] Schaible S., European Journal of Operational Research 7 (2) pp 111– (1981) · Zbl 0452.90079 · doi:10.1016/0377-2217(81)90272-1
[34] Scott C. H., Journal of Australian Mathematical Society 21 (4) pp 398– (1980) · Zbl 0437.90093 · doi:10.1017/S0334270000002095
[35] Scott C. H., Journal of Optimization Theory and Applications 91 (1) pp 115– (1996) · Zbl 0874.90183 · doi:10.1007/BF02192285
[36] Sniedovich M., European Journal of Operational Research 33 (3) pp 334– (1988) · Zbl 0637.90093 · doi:10.1016/0377-2217(88)90177-4
[37] Stancu-Minasian I. M., Fractional Programming: Theory, Methods and Applications (1997) · Zbl 0899.90155 · doi:10.1007/978-94-009-0035-6
[38] Stefanov S. M., Yugoslav Journal of Operations Research 10 (2) pp 235– (2000)
[39] Stefanov S. M., Applied Mathematics Research Express 2004 (1) pp 17– (2004) · Zbl 1141.90497 · doi:10.1155/S168712000402009X
[40] Stefanov S. M., International Journal of Mathematics and Mathematical Sciences (9) pp 1339– (2005) · Zbl 1111.90086 · doi:10.1155/IJMMS.2005.1339
[41] Stefanov S. M., Journal of Interdisciplinary Mathematics 9 (1) pp 207– (2006) · Zbl 1137.90641 · doi:10.1080/09720502.2006.10700438
[42] Zipkin P.H., Management Science 26 (1) pp 34– (1980) · Zbl 0448.90049 · doi:10.1287/mnsc.26.1.34
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.