Article
Full entry |
PDF
(0.4 MB)
Feedback
Keywords:
attainable sets; adaptive thresholding technique; (max;min)-separable equations
attainable sets; adaptive thresholding technique; (max;min)-separable equations
Summary:
This article develops a parametric method depend on threshold technique for solving some optimization problems on attainable sets of so called (max, min)-separable linear systems. The concept of attainable set for (max, min)-separable linear equation systems will be introduced. Properties of the attainable sets will be studied in detail. The (max, min) - separable linear equation systems, in which the function of unknown variable occur only on one side, will be consider. The main idea of the proposed algorithm is that we will begin the calculations with the maximum element and we will try to decrease the value of the objective function of our problem, by decreasing its components in such a way that they stay within attainable set. Optimization problem consisting in finding the nearest point of an attainable set to a given fixed point will be considered. An algorithm for solving the optimization problem will be proposed. Motivational example from the area of operations research, which shows possible applications of the optimization problem solved in this paper, will be given. Numerical example illustrating the proposed algorithm is included.
References:
[1] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer Monographs in Mathematics and Springer-Verlag, London - Dodrecht - Heudelberg - New York 2010. DOI 10.1007/978-1-84996-299-5 | MR 2681232 | Zbl 1202.15032
[2] Cuninghame-Green, R. A.: Minimax Algebra, Lecture Notes in Economics and Mathematical Systems. Springer-Verlag 166, Berlin 1979. DOI 10.1007/978-3-642-48708-8 | MR 0580321
[3] Eremin, I. I., Mazurov, V. D., Astafev, N. N.: Linear Inequalities in mathematical programming and pattern recognition. Ukr. Math. J. 40 (1988), 3, 243-251. Translated from Ukr. Mat. Zh. 40 (1988), 3, 288-297. DOI 10.1007/bf01061299 | MR 0952114
[4] Gad, M.: Optimization problems under one-sided $(\max, \min)$-linear equality constraints. In: WDS'12 Proc. Contributed Papers Part I, 2012, pp. 13-19. 21st Annual Student Conference, Week of Doctoral Students Charles University, Prague 2012.
[5] Gad, M.: Optimization problems under two-sided $(\max, \min)$-linear inequalities constraints. Academic Coordination Centre J. 18 (2012), 4, 84-92. In: International Conference Presentation of Mathematics Conference ICPM'12, Liberec 2012.
[6] Gad, M., Jablonský, J., Zimmermann, K.: Incorrectly posed optimization problems under extremally linear equation constraints. In: Proc. 34th International Conference of Mathematical Methods in Economics MME 2016, Liberec 2016, pp. 231-236.
[7] Gavalec, M., Gad, M., Zimmermann, K.: Optimization problems under $(\max, \min)$-linear equations and / or inequality constraints. J. Math. Sci. 193 (2013), 5, 645-658. Translated from Russian Journal Fundamentalnaya i Prikladnaya Matematika(Fundamental and Applied Mathematics) 17 (2012), 6, 3-21. DOI 10.1007/s10958-013-1492-5
[8] Zimmernann, K.: Extremální algebra (in Czech). Ekon. ústav ČSAV, Praha 1976.
[9] Zimmermann, K., Gad, M.: Optimization problems under one-sided $(\max, +)$-linear constraints. In: Conference Presentation of Mathematics ICPM'11, Liberec 2011, pp. 159-165.
Search
Partner of