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

Аннотация

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

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

тропическая математика, идемпотентное полуполе, спектральный радиус