| Title:
|
Simultaneous solution of linear equations and inequalities in max-algebra (English) |
| Author:
|
Aminu, Abdulhadi |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
47 |
| Issue:
|
2 |
| Year:
|
2011 |
| Pages:
|
241-250 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
max-algebra |
| Keyword:
|
linear equations and inequalities |
| Keyword:
|
max-linear programming |
| MSC:
|
15A06 |
| MSC:
|
15A39 |
| MSC:
|
90C26 |
| MSC:
|
90C27 |
| idZBL:
|
Zbl 1222.15002 |
| idMR:
|
MR2828575 |
| . |
| Date available:
|
2011-06-06T14:55:54Z |
| Last updated:
|
2013-09-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/141570 |
| . |
| Reference:
|
[1] Aminu, A.: Max-algebraic Linear Systems and Programs.PhD Thesis, University of Birmingham 2009. |
| Reference:
|
[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 |
| Reference:
|
[3] Butkovič, P.: Max-linear Systems: Theory and Algorithms.Springer Monographs in Mathematics, Springer-Verlag 2010. Zbl 1202.15032, MR 2681232, 10.1007/978-1-84996-299-5_7 |
| Reference:
|
[4] Butkovič, P.: Max-algebra: the linear algebra of combinatorics? Linear Algebra & Appl.367 (2003), 313–335. MR 1976928, 10.1016/S0024-3795(02)00655-9 |
| Reference:
|
[5] Butkovič, P., Aminu, A.: Introduction to Max-linear programming.IMA J. Management Math. 20 (2009), 3, 233–249. Zbl 1169.90396, MR 2511497, 10.1093/imaman/dpn029 |
| Reference:
|
[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 |
| Reference:
|
[7] Cuninghame-Green, R. A.: Minimax Algebra (Lecture Notes in Econom.and Math. Systems 166). Springer, Berlin 1979. MR 0580321 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[10] Vorobyov, N. N.: Extremal algebra of positive matrices (in Russian).Elektron. Datenverarbeitung Kybernet. 3 (1967), 39–71. MR 0216854 |
| Reference:
|
[11] Walkup, E. A., Boriello, G.: A general linear max-plus solution technique.In: Idempotency (Gunawardena, ed.), Cambridge University Press 1988, pp. 406–415. |
| Reference:
|
[12] Zimmermann, K.: Extremální algebra (in Czech).Výzkumná publikace Ekonomicko-matematické laboratoře při Ekonomickém ústavu ČSAV, 46, Praha 1976. |
| . |
