The behavior of discrete-event systems, in which the individual components move from event to event rather than varying continuously through time, is often described by systems of linear equations in max-min algebra, in which classical addition and multiplication are replaced by $ \oplus $ and $ {\otimes} $, representing maximum and minimum, respectively. Max-min equations have found a broad area of applications in causal models, which emphasize relationships between input and output variables. Many practical situations can be described using max-min systems of linear equations. We shall deal with a two-sided max-min system of linear equations with unknown column vector $ x $ of the form $ A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d $, where $ A $, $ B $ are given square matrices, $ c $, $ d $ are column vectors and operations $ \oplus $ and $ {\otimes} $ are extended to matrices and vectors in the same way as in the classical algebra. We give an equivalent condition for its solvability. For a given max-min objective function $ f $, we consider optimization problem of type $ f^\top{\otimes} x\rightarrow \max\text{ or } \min $ constraint to $ A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d $. We solve the equation in the form $ f(x) = v $ on the set of solutions of the equation $ A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d $ and extend the problem to the case of an interval function $ {{\boldsymbol{f}}} $ and an interval value $ {{\boldsymbol{v}}} $. We define several types of the reachability of the interval value $ {{\boldsymbol{v}}} $ by the interval function $ {{\boldsymbol{f}}} $ and provide equivalent conditions for them.
Citation: Helena Myšková, Ján Plavka. Optimizing the max-min function with a constraint on a two-sided linear system[J]. AIMS Mathematics, 2024, 9(4): 7791-7809. doi: 10.3934/math.2024378
The behavior of discrete-event systems, in which the individual components move from event to event rather than varying continuously through time, is often described by systems of linear equations in max-min algebra, in which classical addition and multiplication are replaced by $ \oplus $ and $ {\otimes} $, representing maximum and minimum, respectively. Max-min equations have found a broad area of applications in causal models, which emphasize relationships between input and output variables. Many practical situations can be described using max-min systems of linear equations. We shall deal with a two-sided max-min system of linear equations with unknown column vector $ x $ of the form $ A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d $, where $ A $, $ B $ are given square matrices, $ c $, $ d $ are column vectors and operations $ \oplus $ and $ {\otimes} $ are extended to matrices and vectors in the same way as in the classical algebra. We give an equivalent condition for its solvability. For a given max-min objective function $ f $, we consider optimization problem of type $ f^\top{\otimes} x\rightarrow \max\text{ or } \min $ constraint to $ A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d $. We solve the equation in the form $ f(x) = v $ on the set of solutions of the equation $ A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d $ and extend the problem to the case of an interval function $ {{\boldsymbol{f}}} $ and an interval value $ {{\boldsymbol{v}}} $. We define several types of the reachability of the interval value $ {{\boldsymbol{v}}} $ by the interval function $ {{\boldsymbol{f}}} $ and provide equivalent conditions for them.
| [1] |
A. Aminu, P. Butkovič, Introduction to max-linear programming, IMA J. Manag. Math., 20 (2009), 233–249. https://doi.org/10.1093/imaman/dpn029 doi: 10.1093/imaman/dpn029
|
| [2] |
P., M. MacCaig, On the integer max-linear programming problem, Discrete Appl. Math., 162 (2014), 128–141. https://doi.org/10.1016/j.dam.2013.08.007 doi: 10.1016/j.dam.2013.08.007
|
| [3] | R. Cuninghame-Green, Minimax algebra, Berlin: Springer, 1979. https://doi.org/10.1007/978-3-642-48708-8 |
| [4] | M. Fiedler, J. Nedoma, J. Ramík, J. Rohn, K. Zimmermann, Linear optimization problems with inexact data, New York: Springer, 2006. https://doi.org/10.1007/0-387-32698-7 |
| [5] | M. Gavalec, J. Plavka, Monotone interval eigenproblem in max-min algebra, Kybernetika, 46 (2010), 387–396. |
| [6] | M. Gavalec, K. Zimmermann, Solving systems of two-sided (max, min)-linear equations, Kybernetika, 46 (2010), 405–414. |
| [7] |
M. Hladík, On approximation of the best case optimal value in interval linear programming, Optim. Lett., 8 (2014), 1985–1997. https://doi.org/10.1007/s11590-013-0715-5 doi: 10.1007/s11590-013-0715-5
|
| [8] |
M. Hladík, How to determine basis stability in interval linear programming, Optim. Lett., 8 (2014), 375–389. https://doi.org/10.1007/s11590-012-0589-y doi: 10.1007/s11590-012-0589-y
|
| [9] |
J. Loetamonphong, S. C. Fang, R. E. Young, Multi-objective optimization problem with fuzzy relation equations constraints, Fuzzy Set. Syst., 127 (2002), 141–164. https://doi.org/10.1016/S0165-0114(01)00052-5 doi: 10.1016/S0165-0114(01)00052-5
|
| [10] |
H. Myšková, Interval systems of max-separable linear equations, Linear Algebra Appl., 403 (2005), 263–272. https://doi.org/10.1016/j.laa.2005.02.011 doi: 10.1016/j.laa.2005.02.011
|
| [11] |
H. Myšková, Control solvability of interval systems of max-separable linear equations, Linear Algebra Appl., 416 (2006), 215–223. https://doi.org/10.1016/j.laa.2005.11.008 doi: 10.1016/j.laa.2005.11.008
|
| [12] | H. Myšková, An iterative algorithm for testing solvability of max-min interval systems, Kybernetika, 48 (2012), 879–889. |
| [13] | H. Myšková, On an algorithm for testing T4 solvability of max-min interval systems, Kybernetika, 48 (2012), 924–938. |
| [14] |
H. Myšková, Interval max-plus systems of linear equations, Linear Algebra Appl., 437 (2012), 1992–2000. https://doi.org/10.1016/j.laa.2012.04.051 doi: 10.1016/j.laa.2012.04.051
|
| [15] |
J. Plavka, On eigenproblem for circulant matrices in max-algebra, Optimization, 50 (2001), 477–483. https://doi.org/10.1080/02331930108844576 doi: 10.1080/02331930108844576
|
| [16] | E. Sanchez, Medical diagnosis and composite advances, In: Fuzzy set theory and applications, 1979,437–444. |
| [17] | Y. Tsukamoto, T. Terano, Failure diagnosis by using fuzzy logic, In: 1977 IEEE conference on decision and control including the 16th symposium on adaptive processes and a special symposium on fuzzy set theory and applications, New Orleans, 1977, 1390–1395. https://doi.org/10.1109/CDC.1977.271521 |
| [18] | N. N. Vorobjov, Extremal algebra of positive matrices, Elektronische Datenverarbeitung und Kybernetik, 3 (1967), 39–71. |
| [19] |
Y. K. Wu, S. M. Guu, Minimizing a linear function under a fuzzy max-min relational equation constraint, Fuzzy Set. Syst., 150 (2005), 147–162. https://doi.org/https://doi.org/10.1016/j.fss.2004.09.010 doi: 10.1016/j.fss.2004.09.010
|
| [20] | L. A. Zadeh, Toward a theory of max-min systems, In: Aspects of network and systems theory, 1971. |
| [21] | K. Zimmermann, Extremální algebra (in Czech), 1976. |
Figures(1)
Helena Myšková, Ján Plavka. Optimizing the max-min function with a constraint on a two-sided linear system[J]. AIMS Mathematics, 2024, 9(4): 7791-7809. doi: 10.3934/math.2024378
DownLoad: