Optimization of mean values on oriented graphs. Paper from the 29th Brazilian mathematics colloquium -- 29\(^{\text o}\) Colóquio Brasileiro de Matemática, Rio de Janeiro, Brazil, July 22 -- August 2, 2013 (Q2848165)

These lecture notes on optimization of mean values on oriented graphs were conceived for the students of the 29th Brazilian Mathematics Colloquium held in July 2013.NEWLINENEWLINEThey are divided into 5 chapters. In the first, the pickup and delivery problem is introduced. Some elementary notions of graph theory are presented. The next chapter is devoted to the optimization of mean values. The main notion of minimum cycle mean is presented and the algorithm by \textit{R. M. Karp} [Discrete Math. 23, 309--311 (1978; Zbl 0386.05032)] is discussed. In the third chapter the authors present the Lax-Oleinik operator and describe the two stage numerical procedure for solving a minimization eigenvalue problem by \textit{L. M. Floría} and \textit{R. B. Griffiths} [Numer. Math. 55, No. 5, 565--574 (1989; Zbl 0664.65032)]. In the last core chapter, the separating and calibrating correctors are analyzed.NEWLINENEWLINEThere is an extra chapter devoted to the eigenpair problem defined on a min-plus algebra. The equivalence to the previous optimization of mean values problem is examined.