О решении одной многомерной задачи тропической оптимизации с использованием разрежения матриц

Авторы

  • Николай Кимович Кривулин
  • Владимир Николаевич Сорокин

Аннотация

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

Скачивания

Данные скачивания пока недоступны.

Библиографические ссылки

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

Загрузки

Опубликован

19.08.2020

Как цитировать

Кривулин, Н. К., & Сорокин, В. Н. (2020). О решении одной многомерной задачи тропической оптимизации с использованием разрежения матриц. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 5(1), 91–104. извлечено от https://math-mech-astr-journal.spbu.ru/article/view/8538

Выпуск

Том 5 № 1 (2018)

Раздел

Математика

Лицензия

Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.

Наиболее читаемые статьи этого автора (авторов)