TY - JOUR

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

AU - Кривулин, Н.К.

AU - Сорокин, В.Н.

N1 - Кривулин Н. К., Сорокин В. Н. О решении одной многомерной задачи тропической оптимизации с использованием разрежения матриц // Вестник СПбГУ. Математика. Механика. Астрономия. 2018. Т. 5 (63). Вып. 1. С. 91–104. https://doi.org /10.21638/11701/spbu01.2018.110

PY - 2018

Y1 - 2018

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

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

KW - idempotent semifield

KW - tropical optimization

KW - Chebyshyov approximation

KW - complete solution

KW - matrix sparsification

KW - идемпотентное полуполе

KW - тропическая оптимизация

KW - чебышёвская аппроксимация

KW - полное решение

KW - разрежение матриц

M3 - статья

VL - 5 (63)

SP - 91

EP - 104

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

SN - 1025-3106

IS - 1

ER -