Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
max-algebra; linear equations and inequalities; max-linear programming
max-algebra; linear equations and inequalities; max-linear programming
Summary:
Let $a øplus b=\max(a,b)$ and $a øtimes b = a+b$ for $a,b\in{\mathbb{R}}$. Max-algebra is an analogue of linear algebra developed on the pair of operations $(øplus, øtimes)$ extended to matrices and vectors. The system of equations $A øtimes x=b$ and inequalities $C øtimes x łeq d$ have each been studied in the literature. We consider a problem consisting of these two systems and present necessary and sufficient conditions for its solvability. We also develop a polynomial algorithm for solving max-linear program whose constraints are max-linear equations and inequalities.
References:
[1] Aminu, A.: Max-algebraic Linear Systems and Programs. PhD Thesis, University of Birmingham 2009.
[2] Bacelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J. P.: Synchronization and Linearity, An Algebra for Discrete Event Systems. Wiley, Chichester 1992. MR 1204266
[3] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer Monographs in Mathematics, Springer-Verlag 2010. DOI 10.1007/978-1-84996-299-5_7 | MR 2681232 | Zbl 1202.15032
[4] Butkovič, P.: Max-algebra: the linear algebra of combinatorics? Linear Algebra & Appl. 367 (2003), 313–335. DOI 10.1016/S0024-3795(02)00655-9 | MR 1976928
[5] Butkovič, P., Aminu, A.: Introduction to Max-linear programming. IMA J. Management Math. 20 (2009), 3, 233–249. DOI 10.1093/imaman/dpn029 | MR 2511497 | Zbl 1169.90396
[6] Butkovič, P., Hegedüs, G.: An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekonom. mat. Obzor. 20 (1984), 203–215. MR 0782401
[7] Cuninghame-Green, R. A.: Minimax Algebra (Lecture Notes in Econom. and Math. Systems 166). Springer, Berlin 1979. MR 0580321
[8] Cuninghame-Green, R. A., Butkovič, P.: The equation $A\otimes {x}=B\otimes {y}$ over $(\max ,+)$. Theoret. Comput. Sci. 293 (1991), 3–12. MR 1957609
[9] Heidergott, B., Olsder, G. J., Woude, J. van der: Max-plus at work, Modelling and Analysis of Synchronized Systems: A course on Max-Plus Algebra and Its Applications. Princeton University Press, New Jersey 2006. MR 2188299
[10] Vorobyov, N. N.: Extremal algebra of positive matrices (in Russian). Elektron. Datenverarbeitung Kybernet. 3 (1967), 39–71. MR 0216854
[11] Walkup, E. A., Boriello, G.: A general linear max-plus solution technique. In: Idempotency (Gunawardena, ed.), Cambridge University Press 1988, pp. 406–415.
[12] Zimmermann, K.: Extremální algebra (in Czech). Výzkumná publikace Ekonomicko-matematické laboratoře při Ekonomickém ústavu ČSAV, 46, Praha 1976.
Search
Partner of
