An algorithm for solving two-sided interval system of max-plus linear equations. (English) Zbl 1430.15019
Summary: We study six types of solutions (weak, strong, tolerance, control, Left-localized, and Right-localized solutions) to a two-sided interval system of max-plus linear equations with the same vector of variables on both sides of the equations and obtain their corresponding solvability conditions. These conditions are in the form of two-sided systems of max-plus linear inequalities which can be derived as a union of a number of interval inclusion linear systems. Therefore, we could work on the interval inclusion linear systems, instead of directly solving these six types of solutions themselves. An optimization problem with the two-sided interval system of max-plus linear constraints may be solved using the convexity of each solution set of the interval inclusion linear systems.
References:
| [1] | Abolmasoumi, S.; Alavi, M., A method for calculating interval linear system, J. Math. Comput. Sci., 8, 193-204 (2014) |
| [2] | Baccelli, F. L.; Cohen, G.; Olsder, G. J.; Quadrat, J. P., Synchronization and Linearity: An Algebra for Discrete Event Systems (1992), Wiley: Wiley Chichester · Zbl 0824.93003 |
| [3] | Butkovic, P.; Hegedüs, G., An elimination method for finding all solutions of the system of linear equations over an extremal algebra, Ekonomicko-matematicky Obzor, 20, 2, 203-215 (1984) · Zbl 0545.90101 |
| [4] | Butkovič, P.; Zimmermann, K., A strongly polynomial algorithm for solving two-sided linear systems in max-algebra, Discrete Appl. Math., 154, 437-446 (2006) · Zbl 1090.68119 |
| [5] | Cechlárová, K., Solutions of interval linear systems in max-plus algebra, Proceedings of SOR, 321-326 (2001) · Zbl 1016.93049 |
| [6] | Cechlárová, K.; Cuninghame-Green, R. A., Interval systems of max-separable linear equations, Linear Algebra Appl., 340, 215-224 (2002) · Zbl 1004.15009 |
| [7] | Chua, L. O.; Deng, A. C., Canonical piecewise-linear representation, IEEE Trans. Circuits Syst., 35, 1, 101-111 (1988) · Zbl 0644.94023 |
| [8] | Cuninghame-Green, R. A., Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, 166 (1979), Springer: Springer Berlin · Zbl 0399.90052 |
| [9] | Cuninghame-Green, R. A.; Butkovič, P., The equation \(A x = B y\) over \((\max, +)\), Theor. Comput. Sci., 293, 3-12 (1991) · Zbl 1021.65022 |
| [10] | De Schutter, B.; van den Boom, T. J.J., MPC for continuous piecewise-affine systems, Syst. Control Lett., 52, 3, 179-192 (2004) · Zbl 1157.93439 |
| [11] | Fiedler, M.; Nedoma, J.; Ramik, J.; Rohn, J.; Zimmermann, K., Linear Optimization Problems with Inexact Data (2006), Springer Science & Business Media · Zbl 1106.90051 |
| [12] | Gavalec, M.; Plavka, J.; Ponce, D., Tolerance types of interval eigenvectors in max-plus algebra, Inf. Sci., 367-368, 14-27 (2016) · Zbl 1427.15030 |
| [13] | Gavalec, M.; Zimmermann, K., Classification of solutions to systems of two-sided equations with interval coefficients, Int. J. Pure Appl. Math., 45, 4, 533 (2008) · Zbl 1154.65036 |
| [14] | Gonçalves, V. M.; Maia, C. A.; Hardouin, L., On max-plus linear dynamical system theory: the regulation problem, Automatica, 75, 202-209 (2017) · Zbl 1351.93090 |
| [15] | Heemels, W. P.; De Schutter, B.; Bemporad, A., Equivalence of hybrid dynamical models, Automatica, 37, 7, 1085-1091 (2001) · Zbl 0990.93056 |
| [16] | Heidergott, B.; Olsder, G. J.; Van der Woude, J., Max Plus at Work: Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and its Applications, (princeton series in applied mathematics), 2, 37 (2006), Princeton University Press · Zbl 1130.93003 |
| [17] | Kelling, B.; Oelschliägel, D., Zur lösung von linearen toleranzproblemen, Wiss. Zeitschrift TH Leuna-Merseburg, 33, 121-131 (1991) · Zbl 0739.65021 |
| [18] | Leela-apiradee, W.; Thipwiwatpotjana, P., L- and R-localized solvabilities of max-separable interval linear equations and its applications, J. Comput. Appl. Math., 279, 306-317 (2015) · Zbl 1306.15025 |
| [19] | Leela-apiradee, W.; Thipwiwatpotjana, P.; Gorka, A., Closed form of L-localized solution set of max-plus interval linear system and its application on optimization problem, J. Comput. Appl. Math., 317, 113-127 (2017) · Zbl 1357.65052 |
| [20] | Li, W.; Wang, H.; Wang, Q., Localized solutions to interval linear equations, J. Comput. Appl. Math., 238, 29-38 (2013) · Zbl 1264.65035 |
| [21] | Moore, R. E.; Kearfott, R. B.; Cloud, M. J., Introduction to Interval Analysis (2009), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia · Zbl 1168.65002 |
| [22] | Myšková, H., Interval systems of max-separable linear equations, Linear Algebra Appl., 403, 263-272 (2005) · Zbl 1077.15004 |
| [23] | Myšková, H., Control solvability of interval systems of max-separable linear equations, Linear Algebra Appl., 416, 215-223 (2006) · Zbl 1129.15003 |
| [24] | Myšková, H., Interval max-plus matrix equations, Linear Algebra Appl., 492, 111-127 (2016) · Zbl 1391.15059 |
| [25] | Neumaier, A., Tolerance analysis with interval arithmetic, Freiburger Intervall-Berichte, 5-19 (1986) |
| [26] | Neumaier, A., Interval Methods for Systems of Equations (1990), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0706.15009 |
| [27] | Nirmala, T.; Datta, D.; Kushwaha, H. S.; Ganesan, K., Inverse interval matrix: a new approach, Appl. Math. Sci., 5, 13, 607-624 (2011) · Zbl 1228.65039 |
| [28] | Nuding, E.; Wilhelm, J., Über gleichungen und über lösungen, Zeitschrift für Angewandte Mathematik und Mechanik, 52, T188-T190 (1972) · Zbl 0236.65032 |
| [29] | Oettli, W.; Prager, W., Compatibility of approximate solution of linear equations with given error bounds for coeficients and right-hand sides, Numerische Mathematik, 6, 405-409 (1964) · Zbl 0133.08603 |
| [30] | Oldser, G. J., Course Notes: Max-algebra Approach to Discrete Event Systems, 191 (1999), Notas de Matematica: Notas de Matematica Universidad de los Andes, Mérida-Venezuela |
| [31] | Ovchinnikov, S., Max-min representation of piecewise linear functions, Contrib. Algebra Geom., 43, 1, 297-302 (2002) · Zbl 0996.26007 |
| [32] | Rohn, J., Input-Output Planning with Inexact Data, 9 (1978), Freiburger Intervall-Berichte: Freiburger Intervall-Berichte Albert-Ludwigs-Universität, Freiburg · Zbl 0408.90021 |
| [33] | Schutter, B. D.; van den Boom, T. J.J., Max-plus algebra and max-plus linear discrete event systems: An introduction, Proceedings of the 9th International Workshop on Discrete Event Systems (WODES’08), 36-42 (2008) |
| [34] | Seleim, A.; Elmaraghy, H., Generating max-plus equations for efficient analysis of manufacturing flow lines, J. Manuf. Syst., 37, 426-436 (2015) |
| [35] | Shary, S. P., On controlled solution set of interval algebraic systems, Interval Comput., 6, 66-75 (1992) · Zbl 0829.65044 |
| [36] | Shary, S. P., Solving the interval linear tolerance problem, Math. Comput. Simul., 39, 53-85 (1995) |
| [37] | Shary, S. P., Controllable solution set to interval static systems, Math. Comput. Simul., 86, 185-196 (1997) · Zbl 0908.65037 |
| [38] | Vorobjov, N. N., Extremal algebra of positive matrices, Datenverarbeitung und Kybernetik, 3, 39-71 (1967) |
| [39] | Walkup, E. A.; Borriello, G., A general linear max-plus solution technique, (Gunawardena, J. (1988), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0898.68035 |
| [40] | Wang, H. L.; Wang, X. P., A polynomial algorithm for solving system of inequalities in max-plus algebra, Inf. Sci., 318, 1-13 (2015) · Zbl 1390.15088 |
| [41] | Wei, Y.; Qiu, J.; Karimi, H. R., Reliable output feedback control of discrete-time fuzzy affine systems with actuator faults, IEEE Trans. Circuits Syst. I Regul. Pap. (2016) |
| [42] | Xu, J.; van den Boom, T. J.J.; De Schutter, B., Optimistic optimization for model predictive control of max-plus linear systems, Automatica, 74, 16-22 (2016) · Zbl 1348.93192 |
| [43] | Zhang, H.; Tao, Y.; Zhang, Z., Strong solvability of interval max-plus systems and applications to optimal control, Syst. Control Lett., 96, 88-94 (2016) · Zbl 1347.93092 |
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.
