Об алгебраическом решении задачи Ролса о размещении на плоскости с прямоугольной метрикой

Аннотация

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

Ключевые слова:

идемпотентное полуполе, спектральный радиус матрицы, полное решение, прямоугольная метрика, задача Ролса о размещении