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

Н.К. Кривулин, У.Л. Баско

Результат исследований: Научные публикации в периодических изданияхстатья

Аннотация

Рассматривается многомерная задача оптимизации, которая формулируется и решается в терминах тропической математики, изучающей теорию и приложения полуколец с идемпотентным сложением. Для решения задачи, целевая функция которой задается при помощи некоторой матрицы, используются методы и результаты идемпотентной алгебры и тропической оптимизации. Сначала строится точная нижняя оценка для целевой функции задачи, что позволяет определить минимальное значение целевой функции. Затем составляется и решается уравнение для целевой функции и ее минимального значения, откуда находится полное решение в виде множества всех собственных векторов матрицы задачи. В качестве приложения полученного результата приводится решение в явном виде задачи составления оптимального плана проекта, который состоит в выполнении некоторого набора работ при заданных ограничениях на время их начала и завершения. Критерий оптимальности плана определяется как минимум максимального разброса времени рабочего цикла по всем работам, которое задано как интервал между временем начала и завершения работы. Полученный аналитический результат расширяет и дополняет существующие алгоритмические численные решения задач оптимального планирования. Представлен иллюстративный пример применения этого результата к решению задачи планирования проекта, состоящего из трех работ.
Переведенное названиеSolving a tropical optimization problem with application to optimal scheduling
Язык оригиналарусский
Страницы (с-по)440-451
ЖурналВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ
Том6 (64)
Номер выпуска3
СостояниеОпубликовано - 2019

Предметные области Scopus

  • Теория оптимизации
  • Алгебра и теория чисел
  • Теория управления и исследование операций

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

  • идемпотентное полуполе
  • (max, +)-алгебра
  • собственные число и вектор матрицы
  • тропическая оптимизация
  • задача планирования

Fingerprint Подробные сведения о темах исследования «Решение задачи тропической оптимизации с приложением к оптимальному планированию». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать