Simultaneous solution of linear equations and inequalities in max-algebra

Abdulhadi Aminu

Kybernetika (2011)

  • Volume: 47, Issue: 2, page 241-250
  • ISSN: 0023-5954

Abstract

top
Let a ø p l u s b = max ( a , b ) and a ø t i m e s b = a + b for a , b ∈ ℝ . Max-algebra is an analogue of linear algebra developed on the pair of operations ( ø p l u s , ø t i m e s ) extended to matrices and vectors. The system of equations A ø t i m e s x = b and inequalities C ø t i m e s x ł e q 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.

How to cite

top

Aminu, Abdulhadi. "Simultaneous solution of linear equations and inequalities in max-algebra." Kybernetika 47.2 (2011): 241-250. <http://eudml.org/doc/196900>.

@article{Aminu2011,
abstract = {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.},
author = {Aminu, Abdulhadi},
journal = {Kybernetika},
keywords = {max-algebra; linear equations and inequalities; max-linear programming; max-algebra; linear equations; linear inequalities; max-linear programming},
language = {eng},
number = {2},
pages = {241-250},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Simultaneous solution of linear equations and inequalities in max-algebra},
url = {http://eudml.org/doc/196900},
volume = {47},
year = {2011},
}

TY - JOUR
AU - Aminu, Abdulhadi
TI - Simultaneous solution of linear equations and inequalities in max-algebra
JO - Kybernetika
PY - 2011
PB - Institute of Information Theory and Automation AS CR
VL - 47
IS - 2
SP - 241
EP - 250
AB - 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.
LA - eng
KW - max-algebra; linear equations and inequalities; max-linear programming; max-algebra; linear equations; linear inequalities; max-linear programming
UR - http://eudml.org/doc/196900
ER -

References

top
  1. Aminu, A., Max-algebraic Linear Systems and Programs, PhD Thesis, University of Birmingham 2009. (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. (1992) MR1204266
  3. Butkovič, P., 10.1007/978-1-84996-299-5_7, Springer Monographs in Mathematics, Springer-Verlag 2010. (2010) Zbl1202.15032MR2681232DOI10.1007/978-1-84996-299-5_7
  4. Butkovič, P., 10.1016/S0024-3795(02)00655-9, 367 (2003), 313–335. (2003) MR1976928DOI10.1016/S0024-3795(02)00655-9
  5. Butkovič, P., Aminu, A., 10.1093/imaman/dpn029, IMA J. Management Math. 20 (2009), 3, 233–249. (2009) Zbl1169.90396MR2511497DOI10.1093/imaman/dpn029
  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. (1984) MR0782401
  7. Cuninghame-Green, R. A., Minimax Algebra (Lecture Notes in Econom, and Math. Systems 166). Springer, Berlin 1979. (1979) MR0580321
  8. Cuninghame-Green, R. A., Butkovič, P., The equation A ⊗ x = B ⊗ y over ( max , + ) , Theoret. Comput. Sci. 293 (1991), 3–12. (1991) MR1957609
  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. (2006) MR2188299
  10. Vorobyov, N. N., Extremal algebra of positive matrices (in Russian), Elektron. Datenverarbeitung Kybernet. 3 (1967), 39–71. (1967) MR0216854
  11. Walkup, E. A., Boriello, G., A general linear max-plus solution technique, In: Idempotency (Gunawardena, ed.), Cambridge University Press 1988, pp. 406–415. (1988) 
  12. Zimmermann, K., Extremální algebra (in Czech), Výzkumná publikace Ekonomicko-matematické laboratoře při Ekonomickém ústavu ČSAV, 46, Praha 1976. (1976) 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.