Дата публикации: 2022

Дата публикации в реестре: 2023-02-06T15:01:15Z

Аннотация:

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

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2022. № 58. С. 112-124