ISSN 2071-8594

Российская академия наук

Главный редактор

Академик С. В. Емельянов

М.Ш. Левин, А.В. Сафонов "Эвристический алгоритм для многокритериальной блочной задачи о рюкзаке"

Аннотация.

Предлагается эвристический аппроксимационный подход к решению многокритериальной блочной задаче о рюкзаке (multicriteria multiple choice problem). Приведены результаты численного эксперимента по сравнению предложенного алгоритма с точным переборным алгоритмом. Подробно рассматривается влияние параметров числа групп и числа элементов на эффективность использования эвристического алгоритма по сравнению с точным алгоритмом решения. Изучается влияние ресурсного ограничения на работу алгоритмов. В работе приведены результаты вычислительных экспериментов на различных наборах сгенерированных начальных данных и даны рекомендации по использованию предложенного аппроксимационного алгоритма в реальных задачах.

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

комбинаторная оптимизация, многокритериальная блочная задача о рюкзаке, эвристики, переборные алгоритмы, приближенные алгоритмы, динамическое программирование, вычислительный эксперимент.

 Полная версия статьи в формате pdf.