Канд. физ.-мат. наук, ст. науч. сотр.
Sergey V. Chebakov, Cand. Sci. (Phys. and Math.), Senior Researcher
Minsk
Серебряная Лия Валентиновна, канд. техн. наук, доц. каф. программного обеспечения информационных технологий, Белорусский государственный университет информатики и радиоэлектроники, зав. каф. экономической информатики Белорусского государственного экономического университета
220013, Минск, ул. П. Бровки, 6
Liya V. Serebryanaya, Cand. Sci. (Tech.), Associate Professor at the Department of Software for Information Technology, Belarusian State University of Informatics and Radioelectronics, Head of the Department of Economic Informatics at the Belarus State Economic University
220013, Minsk, P. Brovki St., 6
Разработан метод построения группы порождающих допустимых подмножеств в задаче о ранце при условии, что величина глубины недоминирования заданного паретовского слоя больше нуля. Метод основывается на многокритериальной математической модели решения задачи о ранце при двух критериях качества и разбиении множества начальных данных задачи о ранце на отдельные паретовские слои. Предложены различные способы построения порождающих допустимых подмножеств в зависимости от соотношения между координатами элементов заданных паретовских слоев и объемом ранца. Определена структура паретовских слоев, представляющих собой группу недоминирования заданного отдельного паретовского слоя. Показано, что существует паретовский слой, начиная с которого не требуется при построении допустимых подмножеств рассматривать элементы этого слоя и всех последующих. Это следует из упорядоченности элементов множества начальных данных задачи о ранце по приоритету их вхождения в формируемые допустимые подмножества.
A method for constructing a group of generating feasible subsets in the knapsack problem under the condition that the non-dominance depth of a given Pareto layer is greater than zero is developed. The method is based on a multicriterial mathematical model for solving the knapsack problem with two quality criteria and partitioning the initial data set of the knapsack problem into separate Pareto layers. Various methods for constructing generating feasible subsets are proposed depending on the relationship between the coordinates of the elements of the given Pareto layers and the knapsack volume. The structure of the Pareto layers, which are a non-dominance group of a given individual Pareto layer, is determined. It is shown that there is a Pareto layer, starting from which it is not necessary to consider the elements of this layer and all subsequent ones when constructing feasible subsets. This follows from the ordering of the elements of the initial data set of the knapsack problem according to the priority of their inclusion in the feasible subsets.
The authors declare that there are no conflicts of interest present.