Аннотация.

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

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

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