Solving a tropical optimization problem with application to optimal scheduling
Abstract
Рассматривается многомерная задача оптимизации, которая формулируется и решается в терминах тропической математики, изучающей теорию и приложения полуколец с идемпотентным сложением. Для решения задачи, целевая функция которой задается при помощи некоторой матрицы, используются методы и результаты идемпотентной алгебры и тропической оптимизации. Сначала строится точная нижняя оценка для целевой функции задачи, что позволяет определить минимальное значение целевой функции. Затем составляется и решается уравнение для целевой функции и ее минимального значения, откуда находится полное решение в виде множества всех собственных векторов матрицы задачи. В качестве приложения полученного результата приводится решение в явном виде задачи составления оптимального плана проекта, который состоит в выполнении некоторого набора работ при заданных ограничениях на время их начала и завершения. Критерий оптимальности плана определяется как минимум максимального разброса времени рабочего цикла по всем работам, которое задано как интервал между временем начала и завершения работы. Полученный аналитический результат расширяет и дополняет существующие алгоритмические численные решения задач оптимального планирования. Представлен иллюстративный пример применения этого результата к решению задачи планирования проекта, состоящего из трех работ.
Downloads
References
Downloads
Published
How to Cite
Issue
Section
License
Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.