Geodesic
Optimal paths in oriented graphs and eigenvectors in $\max$-$\oplus$ systems
Diskretnaya Matematika, Tome 21 (2009) no. 3, pp. 79-98.

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

In problems of operation research and mathematical economics, analogues of linear operators appear, where the operations of addition and multiplication of numbers are replaced by the operation of taking maximum and some binary operation $\otimes$ respectively. Earlier, two examples (and their generalisations) were considered, where the addition and the operation of taking minimum were taken as $\otimes$. In this paper, we consider two other examples, where $\otimes$ is an addition with discounting (such an operation makes its appearance in the Ramsey–Cass–Koopmans economic model) and the operation of taking minimum with discounting. To investigate all these four examples, a method is suggested which is based on some operations over characteristic pairs of paths in a certain oriented graph. A characteristic pair of a path is defined as a pair of numbers one of which is the weight of the path (it is defined with the use of the operation $\otimes$), and the other is the number of edges in the path. The emphasis is on the calculation and properties of the eigenvector of the operator known as the Bellman value function for the corresponding optimisation problem on paths of the graph. 
@article{DM_2009_21_3_a7,
     author = {V. D. Matveenko},
     title = {Optimal paths in oriented graphs and eigenvectors in $\max$-$\oplus$ systems},
     journal = {Diskretnaya Matematika},
     pages = {79--98},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2009_21_3_a7/}
}
TY  - JOUR
AU  - V. D. Matveenko
TI  - Optimal paths in oriented graphs and eigenvectors in $\max$-$\oplus$ systems
JO  - Diskretnaya Matematika
PY  - 2009
SP  - 79
EP  - 98
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2009_21_3_a7/
LA  - ru
ID  - DM_2009_21_3_a7
ER  - 
%0 Journal Article
%A V. D. Matveenko
%T Optimal paths in oriented graphs and eigenvectors in $\max$-$\oplus$ systems
%J Diskretnaya Matematika
%D 2009
%P 79-98
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2009_21_3_a7/
%G ru
%F DM_2009_21_3_a7
V. D. Matveenko. Optimal paths in oriented graphs and eigenvectors in $\max$-$\oplus$ systems. Diskretnaya Matematika, Tome 21 (2009) no. 3, pp. 79-98. http://geodesic.mathdoc.fr/item/DM_2009_21_3_a7/

[1] Bellman R., Dinamicheskoe programmirovanie, IL, Moskva, 1960 | MR

[2] Vorobev N. N., “Ekstremalnaya algebra polozhitelnykh matrits”, Elektron. Inform.-verarb. Kybernetik, 3 (1967), 39–71 | MR

[3] Vorobev N. N., “Ekstremalnaya algebra neotritsatelnykh matrits”, Elektron. Inform.-verarb. Kybernetik, 6 (1970), 303–312 | MR

[4] Romanovskii I. V., “Optimizatsiya statsionarnogo upravleniya diskretnym determinirovannym protsessom”, Kibernetika, 1967, no. 2, 66–78 | MR

[5] Romanovskii I. V., Algoritmy resheniya ekstremalnykh zadach, Nauka, Moskva, 1977 | MR

[6] Cuninghame-Green R., Minimax algebra, Springer, Berlin, 1979 | MR | Zbl

[7] Matveenko V. D., “Optimalnye traektorii skhemy dinamicheskogo programmirovaniya i ekstremalnye stepeni neotritsatelnykh matrits”, Diskretnaya matematika, 2:1 (1990), 59–71 | MR | Zbl

[8] Matveenko V. D., “O diskretnykh sublineinykh i superlineinykh operatorakh”, Diskretnaya matematika, 10:2 (1998), 87–100 | MR | Zbl

[9] Matveenko V. D., “Development with positive externalities: the case of the Russian economy”, J. Policy Modeling, 17:3 (1995), 207–221 | DOI

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

[11] Butkovič P., Cechlárová K., Szabó P., “Strong linear independence in bottleneck algebra”, Linear Algebra Appl., 94 (1987), 133–155 | DOI | MR | Zbl

[12] Cechlárová K., “Eigenvectors in bottleneck algebra”, Linear Algebra Appl., 175 (1992), 63–73 | DOI | MR | Zbl

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

[14] Matveenko V. D., “Struktura optimalnykh traektorii diskretnoi determinirovannoi skhemy s diskontirovaniem”, Diskretnaya matematika, 10:3 (1998), 100–114 | MR | Zbl

[15] Matveenko V. D., “Struktura traektorii i vtoraya funktsiya-znachenie v optimizatsionnykh dinamicheskikh sistemakh s diskontirovaniem”, Avtomatika i telemekhanika, 1999, no. 1, 26–34 | MR | Zbl

[16] Vagner G., Osnovy issledovaniya operatsii, Mir, Moskva, 1973

[17] Dudnikov P. I., Samborskii S. N., Endomorfizmy polumodulya nad polukoltsom s idempotentnoi operatsiei, Preprint, IM AN USSR, Kiev, 1987 | MR

[18] Dudnikov P. I., Samborskii S. N., “Endomorfizmy polumodulei nad polukoltsami s idempotentnoi operatsiei”, Izv. AN SSSR. Ser. matem., 55:1 (1991), 93–109 | MR | Zbl

[19] Maslov V. P., Kolokoltsev V. N., Idempotentnyi analiz i ego primenenie v optimalnom upravlenii, Fizmatlit, Moskva, 1994

[20] Zimmermann U., “Linear and combinatorial optimization in ordered algebraic structures”, Ann. Discrete Math., 10 (1981), 1–380 | DOI | MR

[21] Seneta E., Nonnegative matrices. An introduction to theory and applications, Allen Unwin, London, 1973 | MR | Zbl

[22] Ashmanov S. A., Vvedenie v matematicheskuyu ekonomiku, Nauka, Moskva, 1984 | MR | Zbl