Kybernetika 47 no. 2, 241-250, 2011

Simultaneous solution of linear equations and inequalities in max-algebra

Abdulhadi Aminu

Abstract:

Let $a \oplus b=\max(a,b)$ and $a \otimes b = a+b$ for $a,b\in{\mathbb{R}}$. Max-algebra is an analogue of linear algebra developed on the pair of operations $(\oplus, \otimes)$ extended to matrices and vectors. The system of equations $A \otimes x=b$ and inequalities $C \otimes x \leq 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.

Keywords:

max-algebra, linear equations and inequalities, max-linear programming

Classification:

15A06, 15A39, 90C26, 90C27

References:

  1. A. Aminu: Max-algebraic Linear Systems and Programs. PhD Thesis, University of Birmingham 2009.   CrossRef
  2. F. L. Bacelli, G. Cohen, G. J. Olsder and J. P. Quadrat: Synchronization and Linearity, An Algebra for Discrete Event Systems. Wiley, Chichester 1992.   CrossRef
  3. P. Butkovič: Max-linear Systems: Theory and Algorithms. Springer Monographs in Mathematics, Springer-Verlag 2010.   CrossRef
  4. P. Butkovič: Max-algebra: the linear algebra of combinatorics? Linear Algebra \   CrossRef
  5. P. Butkovič and A. Aminu: Introduction to Max-linear programming. IMA J. Management Math. 20 (2009), 3, 233-249.   CrossRef
  6. P. Butkovič and G. Hegedüs: An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekonom. mat. Obzor. 20 (1984), 203-215.   CrossRef
  7. R. A. Cuninghame-Green: Minimax Algebra (Lecture Notes in Econom. and Math. Systems 166). Springer, Berlin 1979.   CrossRef
  8. B. Heidergott, G. J. Olsder and J. van der Woude: 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.   CrossRef
  9. N. N. Vorobyov: Extremal algebra of positive matrices (in Russian). Elektron. Datenverarbeitung Kybernet. 3 (1967), 39-71.   CrossRef
  10. E. A. Walkup and G. Boriello: A general linear max-plus solution technique. In: Idempotency (Gunawardena, ed.), Cambridge University Press 1988, pp. 406-415.   CrossRef
  11. K. Zimmermann: Extremální algebra (in Czech). Výzkumná publikace Ekonomicko-matematické laboratoře při Ekonomickém ústavu ČSAV, 46, Praha 1976.   CrossRef