Russian Universities Reports. MathematicsRussian Universities Reports. MathematicsВестник российских университетов. Математика2686-96672782-3342Tambov State University - G.R. Derzhavin29732910.20310/2686-9667-2019-24-128-393-431ArticlesСтатьиResearch ArticleUniversal algorithms for solving discrete stationary Bellman equationsУниверсальные алгоритмы решения дискретных стационарных уравнений БеллманаLitvinovGrigory L.ЛитвиновГригорий Лазаревич

Doctor of Physics and Mathematics, Professor

доктор физико-математических наук, профессор

glitvinov@gmail.comRodionovАnatoliy Ya.РодионовАнатолий Яковлевич

Teacher

преподаватель

ayarodionov@yahoo.comSergeevSerge˘ıСергеевСергей

Associate Professor of the Mathematics School

доцент Школы математики

sergeevs@maths.bham.ac.ukSobolevskyAndrei N.СоболевскийАндрей Николаевич

Doctor of Physics and Mathematics, Professor of RAS, Director of the Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute)

доктор физико-математических наук, профессор РАН, директор Института проблем передачи информации имени А.А. Харкевича РАН

sobolevski@iitp.ruInstitute for Information Transmission Problems of the Russian Academy of SciencesФГБУН «Институт проблем передачи информации им. А.А. Харкевича Российской академии наук»Moscow Center for Continuous Mathematical EducationМосковский центр непрерывного математического образованияUniversity of Birmingham, School of MathematicsУниверситет Бирмингема, Школа Математики1001202024128VOL 24, NO128 (2019)ТОМ 24, №128 (2019)39343120062025Copyright ©; 2025, Litvinov G.L., Rodionov А.Y., Sergeev S., Sobolevsky A.N.Copyright ©; 2025, Литвинов Г.Л., Родионов А.Я., Сергеев С., Соболевский А.Н.2025Litvinov G.L., Rodionov А.Y., Sergeev S., Sobolevsky A.N.Литвинов Г.Л., Родионов А.Я., Сергеев С., Соболевский А.Н.https://creativecommons.org/licenses/by/4.0https://journals.rcsi.science/2686-9667/article/view/297329

This paper investigates algorithms for solving discrete stationary (or) matrix Bellman equations over semirings, in particular over tropical and idempotent semirings, Also there are presented some original algorithms, applications and programmed realization.

В настоящей работе исследуются алгоритмы решения дискретных стационарных (или) матричных уравнений Беллмана над полукольцами, в особенности над тропическими и идемпотентными полукольцами. Также приведены оригинальные алгоритмы, приложения и программная реализация.

tropical linear algebraidempotent semiringsmatrix Bellman equationsuniversal algorithmsтропическая линейная алгебраидемпотентные полукольцаматричные уравнения Беллманауниверсальные алгоритмыДж. Голуб, Ч.Ван Лоун, Матричные вычисления, Мир, М., 2000.Н.К. Кривулин, Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем, Изд-во СПбГУ, Санкт-Петербург, 2009.Г. Л. Литвинов, А.Н. Соболевский, “Точныеинтервальные решения дискретного уравнения Беллмана и полиномиальная сложность задач идемпотентной линейной алгебры”, Доклады РАН , 374:3 (2000), 304-306, arXiv:org/abs/math.LA/0101041.В.П. Маслов, “Новыйподход к обобщённым решениям нелинейных систем”, Доклады АН СССР, 292:1 (1987), 29-33.В.П. Маслов, “Оновом принципе суперпозиции для задач оптимизации”, УМН, 42:3(255) (1987), 39-48.В.П. Маслов, В.Н. Колокольцов, Идемпотентный анализ и его применение в оптимальном управлении, Наука, М., 1994.Р. Седжвик, Алгоритмы на C++, часть 5: Алгоритмы на графах, Диасофт, Киев, 2002.S. Sergeev, “Universal algorithms for generalized discrete matrix Bellman equations with symmetric Toeplitz matrix”, Tambov University Reports. Series: Natural and Technical Sciences, 16:6-2 (2011), 1751-1758, arXiv:org/abs/math/0612309.С.Н. Сергеев, А.В. Чуркин, “Программадля демонстрации универсальных алгоритмов решения дискретного уравнения Беллмана в различных полукольцах”, Idempotent and tropical mathematics and problems of mathematical physics. II, Международный семинар «Idempotent and Tropical Mathematics and Problems of Mathematical Physics» (Независимый московский университет, российско-французская лаборатория «J.-V. Poncelet», Россия, 25-30 августа), Независимый московский университет, М., 2007, 107-109, arXiv: org/abs/0709.4119.А.Н. Соболевский, “Интервальнаяарифметика и линейная алгебра над идемпотентными полукольцами”, Доклады РАН, 369:6 (1999), 747-749.Д.К. Фаддеев, В.Н. Фаддеева, Вычислительные методы линейной алгебры, 3-е изд., Издво «Лань», Санкт-Петербург, 2002.G. Alefeld and J. Herzberger, Introduction to interval computations , Academic Press, New York, 1983.F.L. Baccelli, G. Cohen, G.J. Olsder and J.P. Quadrat, Synchronization and Linearity: an Algebra for Discrete Event Systems, Wiley and Sons, 1992.R.C. Backhouse, B.A. Carr´e, “Regular algebra applied to path-finding problems”, Journal of the Institute of Mathematics and its Applications, 15 (1975), 161-186.W. Barth, E. Nuding, “Optimale L¨osung von Intervalgleichungsystemen”, Computing, 12 (1974), 117-125.P. Butkoviˇc, Max-linear Systems: Theory and Algorithms , Springer, London, 2010.P. Butkoviˇc, H. Schneider and S. Sergeev, “Z -matrix equations in max algebra, nonnegative linear algebra and other semirings”, 2011, arXiv:org/abs/1110.4564.B.A. Carr´e, “An algebra for network routing problems”, Journal of the Institute of Mathematics and its Applications, 7 (1971), 273-294.B.A. Carr´e, Graphs and Networks, Oxford Univ. Press, Oxford, 1979.K. Cechl´arov´a and R. A. Cuninghame-Green, “Interval systems of max-separable linear equations”, Linear Algebra and its Applications, 340:1-3 (2002), 215-224.R.A. Cuninghame-Green, Minimax Algebra , Lecture Notes in Economics and Mathematical Systems, 166, Springer, Berlin, 1979.M. Fiedler, J. Nedoma, J. Ram´ık, J. Rohn and K. Zimmermann, Linear optimization problems with inexact data, Springer, New York, 2006.J. Golan, Semirings and Their Applications, Kluwer Academic Publishers, 2000.M. Gondran, “Path algebra and algorithms”, Combinatorial Programming: Methods and Applications, Proceedings of the NATO Advanced Study Institute held at the Palais des Congres (Versailles, France, 2-13 September, 1974), Reidel, Dordrecht, 1975, 137-148.M. Gondran and M. Minoux, Graphs et Algorithms , ´ Editions Eylrolles, Paris, 1979.M. Gondran and M. Minoux, Graphs, Dioids and Semirings, Springer, New York, 2010.J. Gunawardena, Idempotency, Cambridge Univ. Press, Cambridge, 1998.L. Hardouin, B. Cottenceau, M. Lhommeau, and E. Le Corronc, “Interval systems over idempotent semiring”, Linear Algebra and its Applications, 431 (2009), 855-862.V. Kreinovich, A. Lakeev, J. Rohn, and P. Kahl, Computational complexity and feasibility of data processing and interval computations, Applied Optimization, Kluwer Academic Publishers, Dordrecht, 1998.D.J. Lehmann, “Algebraic structures for transitive closure”, Theoretical Computer Science, 4 (1977), 59-76.G. L. Litvinov, “The Maslov dequantization, idempotent and tropical mathematics: a brief introduction”, Journal of Mathematical Sciences, 141:4 (2007), 1417-1428, arXiv: org/abs/ math.GM/0507014.G.L. Litvinov and V.P. Maslov, “1210-1211”, Russian Mathematical Surveys, 51 (1996).G. L. Litvinov and V. P. Maslov, “The correspondence principle for idempotent calculus and some computer applications”, Idempotency, Cambridge Univ. Press, Cambridge, 1998, 420- 443, arXiv: org/abs/math.GM/0101021.G.L. Litvinov and V.P. Maslov, Idempotent mathematics and mathematical physics, 307, AMS Contemporary Mathematics, Providence, 2005.G. L. Litvinov, V. P. Maslov, A. Ya. Rodionov, and A. N. Sobolevski˘ı, Universal algorithms, mathematics of semirings and parallel computations, Lecture Notes in Computational Science and Engineering, 75, 2011, arXiv: org/abs/1005.1252.G. L. Litvinov and E. V. Maslova, “Universal numerical algorithms and their software implementation”, Programming and Computer Software, 26:5 (2000), 275-280, arXiv: org/abs/ math.SC/0102114.G.L. Litvinov, A.Ya. Rodionov and A.V. Tchourkin, “Approximate rational arithmetic and arbitrary precision computations for universal algorithms”, International Journal of Pure and Applied Mathematics, 45:2 (2008), 193-204, arXiv:org/abs/math.NA/0101152.G.L. Litvinov and S.N. Sergeev, Tropical and Idempotent Mathematics, 495, AMS Contemporary Mathematics, Providence, 2009.G.L. Litvinov and A.N. Sobolevski˘ı, “Idempotent interval analysis and optimization problems”, Reliable Computing, 7:5 (2001), 353-377, arXiv:org/abs/math.SC/0101080.G.L. Litvinov, V.P. Maslov and A.Ya. Rodionov, “A unifying approach to software and hardware design for scientific calculations and idempotent mathematics”, 2000, arXiv: org/abs/math.SC/0101069.M. Lorenz, Object oriented software: a practical guide, Prentice Hall Books, Englewood Cliffs, New Jersey, 1993.G. Mikhalkin, “Tropical geometry and its applications”, Proceedings of the Madrid ICM. V.2, 2006, 827-852, arXiv:org/abs/math.AG/0601041.R.E. Moore, Methods and applications of interval analysis, SIAM Studies in Applied Mathematics, SIAM, Philadelphia, 1979.H. Myˇskova, “Interval systems of max-separable linear equations”, Linear Algebra and its Applications, 403 (2005), 263-272.H. Myˇskova, “Control solvability of interval systems of max-separable linear equations”, Linear Algebra And Its Applications, 416:2-3 (2006), 215-223.A. Neumaier, Interval methods for systems of equations , Cambridge University Press, Cambridge, 1990.I. Pohl, Object-Oriented Programming Using C++, 2nd ed., Addison-Wesley, Reading, 1997.G. Rote, “A systolic array algorithm for the algebraic path problem”, Computing, 34 (1985), 191-219.S. Sergeev, “Max-algebraic attraction cones of nonnegative irreducible matrices”, Linear Algebra And Its Applications, 435:7 (2011), 1736-1757, arXiv:org/abs/math.AG/0903.3960.S. Sergeev and H. Schneider, “CSR expansions of matrix powersin max algebra”, Transactions of Amer. Math. Soc., 364 (2012), 5969-5994, arXiv:org/abs/math.AG/0912.2534.I. Simon, “Recognizable sets with multiplicities in the tropical semiring”, Lecture Notes in Computer Science, 324 (1988), 107-120.A. Stepanov and M. Lee, The Standard Template Library, Hewlett-Packard Company, Palo Alto, 1994.O. Viro, “Dequantization of real algebraic geometry on logarithmic paper”, European Congress of Mathematics, European Congress of Mathematics (Barcelona, 2000, July 10-14), Progress in Mathematics, Birkh¨auser, Basel, 135-146, arXiv:org/abs/math/0005163.O. Viro, “From the sixteenth Hilbert problem to tropical geometry”, Japanese Journal of Mathematics, 3:2 (2008), 185-214.V.V. Voevodin, Mathematical Foundations of Parallel Computings, World Scientific Publ. Co., Singapore, 1992.