On solution of a multidimensional tropical optimization problem using matrix sparsification

Authors

  • Nikolai K. Krivulin
  • Vladimir N. Sorokin

Abstract

В работе предлагается полное решение задачи минимизации функции, заданной на векторах с элементами из тропического (идемпотентного) полуполя. Рассматриваемая задача тропической оптимизации возникает, например, когда требуется найти наилучшее, в смысле метрики Чебышёва, приближенное решение тропических векторных уравнений, и встречается в различных приложениях, включая задачи планирования, размещения и принятия решений. Для решения задачи сначала находится минимальное значение целевой функции, предлагается описание множества решений в форме системы неравенств и приводится одно из решений. Далее с помощью разрежения матрицы задачи строится расширенное множество решений, а затем полное решение в виде некоторого семейства подмножеств. Описываются процедуры, позволяющие сократить число подмножеств, которые необходимо исследовать при построении полного решения. Показано, как полное решение задачи может быть записано в параметрическом виде в компактной векторной форме. Полученное решение обобщает известные результаты, которые обычно сводятся к получению одного из решений и не позволяют найти все множество решений задачи. Для иллюстрации основных результатов работы приводится пример численного решения задачи на множестве трехмерных векторов.

Downloads

Download data is not yet available.

References

1. Baccelli F., Cohen G., Olsder G.J., Quadrat J.-P. Synchronization and Linearity. In: Wiley Series in Probability and Statistics. Chichester: Wiley, 1993. 514 p.

2. Маслов В.П., Колокольцов В.Н. Идемпотентный анализ и его применение в оптимальном управлении. М.: Физматлит, 1994. 144 с.

3. Cuninghame-Green R.A. Minimax algebra and applications. In Ser.: Advances in Imaging and Electron Physics / ed. by P.W.Hawkes. San Diego: Academic Press, 1994. Vol. 90. P. 1-121. (08)70083-1 DOI: 10.1016/S1076-5670

4. Golan J.S. Semirings and Affine Equations over Them. In Ser.: Mathematics and Its Applications. Springer, 2003. Vol. 556. 241 p. DOI: 10.1007/978-94-017-0383-3

5. Heidergott B, Olsder G.J., van der Woude J. Max Plus at Work. In: Princeton Series in Applied Mathematics. Princeton: Princeton Univ. Press, 2006. 226 p.

6. Gondran M., Minoux M. Graphs, Dioids and Semirings. In Ser.: Operations Research / Computer Science Interfaces. New York: Springer, 2008. Vol. 41. 383 p. DOI: 10.1007/978-0-387-75450-5

7. Кривулин Н.К. Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем. СПб.: Изд-во С.-Петерб. ун-та, 2009. 256 с.

8. Glazek K. A Guide to the Literature on Semirings and Their Applications in Mathematics and Information Sciences. Springer, 2002. 392 p. DOI: 10.1007/978-94-015-9964-1

9. Воробьев Н.Н. Экстремальная алгебра положительных матриц // Elektron. Informationsverarb. Kybernet. 1967. Bd. 3, N 1. S. 39-72.

10. Cuninghame-Green R.A. Projections in minimax algebra // Math. Program. 1976. Vol. 10. P. 111-123. DOI: 10.1007/BF01580656

11. Zimmermann K. Some optimization problems with extremal operations // Mathematical Programming at Oberwolfach II. Vol. 22 of Mathematical Programming Studies / ed. by B. Korte, K. Ritter. Berlin: Springer, 1984. P. 237-251. DOI: 10.1007/BFb0121020

12. Cechl'arov'a K., Cuninghame-Green R.A. Soluble approximation of linear systems in max-plus algebra // Kybernetika. 2003. Vol. 39, N 2. P. 137-141.

13. Butkoviˇc P., Tam K.P. On some properties of the image set of a max-linear mapping // Tropical and Idempotent Mathematics. Vol. 495 of Contemporary Mathematics / ed. by G. L. Litvinov, S.N. Sergeev. Providence: AMS, 2009. P. 115-126. DOI: 10.1090/conm/495/09694

14. Кривулин Н.К. О решении линейных векторных уравнений в идемпотентной алгебре // Математические модели. Теория и приложения. Вып. 5: Сб. науч. статей / под ред. М.К.Чиркова. СПб.: ВВМ, 2004. С. 105-113.

15. Krivulin N. A new algebraic solution to multidimensional minimax location problems with Chebyshev distance // WSEAS Trans. Math. 2012. Vol. 11, N 7. P. 605-614.

16. Krivulin N. Solution of linear equations and inequalities in idempotent vector spaces // Int. J. Appl. Math. Inform. 2013. Vol. 7, N 1. P. 14-23.

17. Krivulin N., Zimmermann K. Direct solutions to tropical optimization problems with nonlinear objective functions and boundary constraints // Mathematical Methods and Optimization Techniques in Engineering / ed. by D. Biolek, and H. Walter, I. Utu, C. von Lucken. WSEAS Press, 2013. P. 86-91.

18. Krivulin N. Algebraic solution of tropical optimization problems via matrix sparsification with application to scheduling // J. Log. Algebr. Methods Program. 2017. Vol. 89. P. 150-170. DOI: 10.1016/j.jlamp.2017.03.004

19. Krivulin N. Extremal properties of tropical eigenvalues and solutions to tropical optimization problems // Linear Algebra Appl. 2015. Vol. 468. P. 211-232. DOI: 10.1016/j.laa.2014.06.044

20. Krivulin N.K., Sorokin V.N. Solution of a tropical optimization problem with linear constraints // Vestnik St. Petersburg Univ. Math. 2015. Vol. 48, N 4. P. 224-232. DOI: 10.3103/S1063454115040081

Downloads

Published

2020-08-19

How to Cite

Krivulin , N. K., & Sorokin , V. N. (2020). On solution of a multidimensional tropical optimization problem using matrix sparsification. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 5(1), 91–104. Retrieved from https://math-mech-astr-journal.spbu.ru/article/view/8538

Issue

Vol. 5 No. 1 (2018)

Section

Mathematics

License

Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.

Most read articles by the same author(s)