Рассматривается многомерная задача оптимизации, которая формулируется и решается в терминах тропической математики, изучающей теорию и приложения полуколец с идемпотентным сложением. Для решения задачи, целевая функция которой задается при помощи некоторой матрицы, используются методы и результаты идемпотентной алгебры и тропической оптимизации. Сначала строится точная нижняя оценка для целевой функции задачи, что позволяет определить минимальное значение целевой функции. Затем составляется и решается уравнение для целевой функции и ее минимального значения, откуда находится полное решение в виде множества всех собственных векторов матрицы задачи. В качестве приложения полученного результата приводится решение в явном виде задачи составления оптимального плана проекта, который состоит в выполнении некоторого набора работ при заданных ограничениях на время их начала и завершения. Критерий оптимальности плана определяется как минимум максимального разброса времени рабочего цикла по всем работам, которое задано как интервал между временем начала и завершения работы. Полученный аналитический результат расширяет и дополняет существующие алгоритмические численные решения задач оптимального планирования. Представлен иллюстративный пример применения этого результата к решению задачи планирования проекта, состоящего из трех работ.
Translated title of the contributionSolving a tropical optimization problem with application to optimal scheduling
Original languageRussian
Pages (from-to)440-451
JournalВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ
Volume6 (64)
Issue number3
StatePublished - 2019

    Scopus subject areas

  • Control and Optimization
  • Algebra and Number Theory
  • Management Science and Operations Research

    Research areas

  • Idempotent semifield, (max, +)-algebra, eigenvalue and eigenvector of matrix, tropical optimization, scheduling problem

ID: 46020099