52372

Автор(ы): 

Автор(ов): 

1

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Многомерная задача о рюкзаке: эффективный метод решения и возможные приложения

DOI: 

10.14357/20790279190206

Наименование источника: 

  • Труды Института системного анализа Российской академии наук

Обозначение и номер тома: 

Т. 69, вып. 2

Город: 

  • Москва

Издательство: 

  • ФИЦ "Информатика и управление" РАН

Год издания: 

2019

Страницы: 

54-64
Аннотация
В последнее время возникает настоятельная потребность в разработке эффективного модельного и алгоритмического аппарата для верхнего уровня системы проектного управления, на котором должна быть подсистема отбора и управления портфелем проектов, подлежащих реализации. В данной работе рассмотрен оптимальный отбор портфеля проектов и распределение ресурсов на его выполнение в виде задачи дискретной оптимизации – многомерной задачи о рюкзаке. В статье приводятся известные теоретические результаты для жадного алгоритма решения задачи об одномерном рюкзаке; необходимые и достаточные условия оптимальности; оценка погрешности алгоритма и его асимптотическая погрешность для поведения в среднем. Предлагается прямой жадный алгоритм по удельной полезности решения многомерной задачи о рюкзаке. Для повышения его эффективности применяется локальный ограниченный перебор, улучшающий жадное решение, а также дополнение и локальная оптимизация предыдущих этапов. Жадные алгоритмы являются быстрыми, с полиномиальной временной сложностью.

Библиографическая ссылка: 

Топка В.В. Многомерная задача о рюкзаке: эффективный метод решения и возможные приложения // Труды Института системного анализа Российской академии наук. 2019. Т. 69, вып. 2. С. 54-64.