Решение задачи тропической оптимизации с приложением к оптимальному планированию

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