Алгоритм решения задачи о ранце при определенных свойствах паретовских слоев

Abstract

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