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

Abstract

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