Geodesic
Simultaneous solution of linear equations and inequalities in max-algebra
Kybernetika, Tome 47 (2011) no. 2, pp. 241-250 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 15A06, 15A39, 90C26, 90C27
Keywords: max-algebra; linear equations and inequalities; max-linear programming 
@article{KYB_2011_47_2_a4,
     author = {Aminu, Abdulhadi},
     title = {Simultaneous solution of linear equations and inequalities in max-algebra},
     journal = {Kybernetika},
     pages = {241--250},
     year = {2011},
     volume = {47},
     number = {2},
     mrnumber = {2828575},
     zbl = {1222.15002},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2011_47_2_a4/}
}
TY  - JOUR
AU  - Aminu, Abdulhadi
TI  - Simultaneous solution of linear equations and inequalities in max-algebra
JO  - Kybernetika
PY  - 2011
SP  - 241
EP  - 250
VL  - 47
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/KYB_2011_47_2_a4/
LA  - en
ID  - KYB_2011_47_2_a4
ER  - 
%0 Journal Article
%A Aminu, Abdulhadi
%T Simultaneous solution of linear equations and inequalities in max-algebra
%J Kybernetika
%D 2011
%P 241-250
%V 47
%N 2
%U http://geodesic.mathdoc.fr/item/KYB_2011_47_2_a4/
%G en
%F KYB_2011_47_2_a4
Aminu, Abdulhadi. Simultaneous solution of linear equations and inequalities in max-algebra. Kybernetika, Tome 47 (2011) no. 2, pp. 241-250. http://geodesic.mathdoc.fr/item/KYB_2011_47_2_a4/

[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

[3] Butkovič, P.: Max-linear Systems: Theory and Algorithms. Springer Monographs in Mathematics, Springer-Verlag 2010. | DOI | MR | Zbl

[4] Butkovič, P.: Max-algebra: the linear algebra of combinatorics? Linear Algebra & Appl. 367 (2003), 313–335. | DOI | MR

[5] Butkovič, P., Aminu, A.: Introduction to Max-linear programming. IMA J. Management Math. 20 (2009), 3, 233–249. | DOI | MR | Zbl

[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

[7] Cuninghame-Green, R. A.: Minimax Algebra (Lecture Notes in Econom. and Math. Systems 166). Springer, Berlin 1979. | MR

[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

[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

[10] Vorobyov, N. N.: Extremal algebra of positive matrices (in Russian). Elektron. Datenverarbeitung Kybernet. 3 (1967), 39–71. | MR

[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.