Оптимальные пути в ориентированных графах и собственные векторы в $\max$-$\oplus$ системах

В задачах исследования операций и математической экономики возникают аналоги линейного оператора, где операции сложения и умножения чисел заменены соответственно на взятие максимума и некоторую бинарную операцию $\otimes$. Ранее изучались, в основном, два примера (и их обобщения), где в качестве $\otimes$ выступают сложение и минимум. В статье вводится в рассмотрение два других примера, где $\otimes$ – это сложение с дисконтированием (известное по экономической модели Рамсея–Касса–Купманса) и минимум с дисконтированием. Для исследования всех четырех примеров предлагается метод, в основе которого лежат операции над характеристическими парами путей в ориентированном графе. Характеристическая пара путей определена как пара чисел, одно из которых представляет собой вес пути (он определен посредством операции $\otimes$), а другой – число дуг пути. Основное внимание уделяется вычислению и свойствам собственного вектора оператора, он представляет собой функцию-значение Беллмана для соответствующей оптимизационной задачи о путях на графе.