Optimal paths in oriented graphs and eigenvectors in \(\max\)-\(\otimes\) systems. (English. Russian original) Zbl 1261.90080
Discrete Math. Appl. 19, No. 4, 389-409 (2009); translation from Diskretn. Mat. 21, No. 3, 79-98 (2009).
Summary: 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.
MSC:
| 90C35 | Programming involving graphs or networks |
| 05C38 | Paths and cycles |
| 91B02 | Fundamental topics (basic mathematics, methodology; applicable to economics in general) |
| 91B62 | Economic growth models |
References:
| [1] | Vorob’ev N. N., Elektron. Inform.-verarb. Kybernetik 3 pp 39– (1967) |
| [2] | Vorob’ev N. N., Elektron. Inform.-verarb. Kybernetik 6 pp 303– (1970) |
| [3] | Romanovskii I. V., Kibernetika 2 pp 66– (1967) |
| [4] | Matveenko V. D., Diskretnaya Matematika 2 (1) pp 59– (1990) |
| [5] | Matveenko V. D., Discrete Math. Appl. 8 pp 201– (1998) · Zbl 0976.47030 · doi:10.1515/dma.1998.8.2.201 |
| [6] | Matveenko V. D., J. Policy Modeling 17 (3) pp 207– (1995) · doi:10.1016/0161-8938(94)00028-E |
| [7] | Sanchez E., Fuzzy Sets Syst. 1 pp 69– (1978) · Zbl 0366.04001 · doi:10.1016/0165-0114(78)90033-7 |
| [8] | Butkovič P., Linear Algebra Appl. 94 pp 133– (1987) · Zbl 0629.90093 · doi:10.1016/0024-3795(87)90085-1 |
| [9] | Cechlárová K., Linear Algebra Appl. 175 pp 63– (1992) · Zbl 0756.15014 · doi:10.1016/0024-3795(92)90302-Q |
| [10] | Cechlárová K., Tatra Mt. Math. Publ. 12 pp 73– (1997) |
| [11] | Matveenko V. D., Discrete Math. Appl. 8 pp 637– (1998) · Zbl 1005.49020 · doi:10.1515/dma.1998.8.6.637 |
| [12] | Matveenko V. D., Autom. Remote Control 60 pp 20– (1999) |
| [13] | Dudnikov P. I., Math. USSR Izv. 38 pp 91– (1992) · Zbl 0746.16034 · doi:10.1070/IM1992v038n01ABEH002188 |
| [14] | Zimmermann U., Ann. Discrete Math. 10 pp 1– (1981) · doi:10.1016/S0167-5060(08)70423-0 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
