Optimal paths in oriented graphs and eigenvectors in $\max$-$\oplus$ systems

V. D. Matveenko

Diskretnaya Matematika, Tome 21 (2009) no. 3, pp. 79-98

Résumé

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.