Using tropical optimization to solve minimax location problems with rectilinear metric on the line

Abstract

Методы тропической (идемпотентной) математики применяются для решения минимаксных задач размещения с прямоугольной метрикой при наличии ограничений на допустимую область размещения. Сначала рассматривается задача тропической оптимизации с ограничениями, сформулированная в терминах некоторого общего полуполя с идемпотентным сложением. Для решения задачи оптимизации вводится параметр, который обозначает минимум целевой функции, а затем задача сводится к параметризованной системе неравенств. Значение параметра определяется из условий существования решений системы, а решения системы при найденном значении параметра берутся в качестве решений исходной задачи оптимизации. Затем формулируется минимаксная задача размещения одиночного объекта на отрезке прямой на плоскости с прямоугольной метрикой. При отсутствии ограничений эта задача, которая также известна как задача Ролса или задача посыльного, имеет известные геометрическое и алгебраическое решения. Для задач размещения, в которых область размещения ограничена отрезком прямой, получено новое решение на основе представления этих задач в форме изученной выше задачи тропической оптимизации. Приведены решения в явном виде задач размещения для различных положений прямой, записанные как в терминах тропической математики, так и в обычной форме. Библиогр. 16 назв.