Построение порождающих допустимых подмножеств в задаче о ранце

Abstract

Разработан метод построения группы порождающих допустимых подмножеств в задаче о ранце при условии, что величина глубины недоминирования заданного паретовского слоя больше нуля. Метод основывается на многокритериальной математической модели решения задачи о ранце при двух критериях качества и разбиении множества начальных данных задачи о ранце на отдельные паретовские слои. Предложены различные способы построения порождающих допустимых подмножеств в зависимости от соотношения между координатами элементов заданных паретовских слоев и объемом ранца. Определена структура паретовских слоев, представляющих собой группу недоминирования заданного отдельного паретовского слоя. Показано, что существует паретовский слой, начиная с которого не требуется при построении допустимых подмножеств рассматривать элементы этого слоя и всех последующих. Это следует из упорядоченности элементов множества начальных данных задачи о ранце по приоритету их вхождения в формируемые допустимые подмножества.