Geodesic
Optimization problems under $(\max,\min)$-linear equation and/or inequality constraints
Fundamentalʹnaâ i prikladnaâ matematika, Tome 17 (2012) no. 6, pp. 3-21 
M. Gavalec; M. Gad; K. Zimmermann. Optimization problems under $(\max,\min)$-linear equation and/or inequality constraints. Fundamentalʹnaâ i prikladnaâ matematika, Tome 17 (2012) no. 6, pp. 3-21. http://geodesic.mathdoc.fr/item/FPM_2012_17_6_a0/
@article{FPM_2012_17_6_a0,
     author = {M. Gavalec and M. Gad and K. Zimmermann},
     title = {Optimization problems under $(\max,\min)$-linear equation and/or inequality constraints},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {3--21},
     year = {2012},
     volume = {17},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2012_17_6_a0/}
}
TY  - JOUR
AU  - M. Gavalec
AU  - M. Gad
AU  - K. Zimmermann
TI  - Optimization problems under $(\max,\min)$-linear equation and/or inequality constraints
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2012
SP  - 3
EP  - 21
VL  - 17
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/FPM_2012_17_6_a0/
LA  - ru
ID  - FPM_2012_17_6_a0
ER  - 
%0 Journal Article
%A M. Gavalec
%A M. Gad
%A K. Zimmermann
%T Optimization problems under $(\max,\min)$-linear equation and/or inequality constraints
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2012
%P 3-21
%V 17
%N 6
%U http://geodesic.mathdoc.fr/item/FPM_2012_17_6_a0/
%G ru
%F FPM_2012_17_6_a0

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper is a survey of recent results concerning optimization problems whose set of feasible solutions is described by a finite system of so-called $(\max,\min)$-linear equations and/or inequalities. The objective function is equal to the maximum of a finite number of continuous unimodal functions $f_j\colon R\to R$ each depending on one variable $x_j\in R=(-\infty,+\infty)$. Motivation problems from the area of operations research, illustrative numerical examples, and hints for further research are included.

[1] Baccelli F. L., Cohen G., Olsder G. J., Quadrat J. P., Synchronization and Linearity. An Algebra for Discrete Event Systems, Wiley, Chichester, 1992 | MR | Zbl

[2] Butkovič P., Max-Linear Systems: Theory and Algorithms., Springer Monographs Math., Springer, London, 2010 | DOI | MR | Zbl

[3] Butkovič P., Hegedüs G., “An elimination method for finding all solutions of the system of linear equations over an extremal algebra”, Ekonomicko-matematický obzor., 20 (1984), 203–215 | MR | Zbl

[4] Butkovič P., Zimmermann K., “A strongly polynomial algorithm for solving two-sided linear systems in max-algebra”, Discrete Appl. Math., 154 (2006), 437–446 | DOI | MR | Zbl

[5] Cechlárová K., “Efficient computation of the greatest eigenvector in fuzzy algebra”, Tatra Mt. Math. Publ., 12 (1997), 73–79 | MR | Zbl

[6] Cuninghame-Green R. A., Minimax Algebra, Lect. Notes Economics Math. Systems, 166, Springer, Berlin, 1979 | DOI | MR | Zbl

[7] Cuninghame-Green R. A., Zimmermann K., “Equation with residual functions”, Comment. Math. Univ. Carolin., 42 (2001), 729–740 | MR | Zbl

[8] Gavalec M., Zimmermann K., “Solving systems of two-sided $(\max,\min)$-linear equations”, Kybernetika, 46 (2010), 405–414 | MR | Zbl

[9] Gavalec M., Zimmermann K., “Optimization problems with two-sided systems of linear equations over distributive lattices”, Proc. Conf. Math. Methods in Economics, 2010, 172–176

[10] Litvinov G. L., Maslov V. P., Sergeev S. N. (eds.), Idempotent and Tropical Mathematics and Problems of Mathematical Physics, v. 1, Nezavis. Univ., Moscow, 2007

[11] Maslov V. P., Samborskij S. N., Idempotent Analysis, Adv. Sov. Math., 13, Amer. Math. Soc., Providence, 1992

[12] Sanchez E., “Resolution of eigen fuzzy sets equations”, Fuzzy Sets Systems, 1:1 (1978), 69–74 | DOI | MR | Zbl

[13] Sanchez E., “Inverses of fuzzy relations. Applications to possibility distributions and medical diagnosis”, Fuzzy Sets Systems, 2 (1979), 77–86 | DOI | MR

[14] Vorobjov N. N., “Extremal algebra of positive matrices”, Datenverarbeitung und Kybernetik, 3 (1967), 39–71 | MR

[15] Zimmermann K., “Disjunctive optimization problems, max-separable problems and extremal algebras”, Theor. Comput. Sci., 293 (2003), 45–54 | DOI | MR | Zbl