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

Abstract

RU: Актуальность. Рассмотрена задача построения гарантированного субоптимального (приближенного) решения по функционалу в одномерной и многомерной задачах о ранце. Объектом исследования являлась модель с приращением коэффициентов целевой функции. Цель работы. Разработка методов построения гарантированного субоптимального решения по функционалу в одномерной и многомерной задачах о ранце, т. е. найти такие минимальные изменения коэффициентов функционала в заданных интервалах, чтобы найденное решение гарантировало значения функционала не меньше, чем заранее фиксированного. Метод. Введены понятия допустимого, гарантированного и гарантированного субоптимального решений по функционалу в многомерной задаче о ранце. В заданных интервалах необходимо найти такие минимальные изменения коэффициентов функционала, чтобы найденное решение гарантировало значение функционала не меньше, чем заранее фиксированного. Такое решение называем гарантированным решением по функционалу для одномерной и многомерной задачи о ранце. Разработаны методы их построения. Составлен программный комплекс для нахождения этих решений и проведены многочисленные вычислительные эксперименты над случайными задачами большой размерности. Результаты. Разработан алгоритм для построения гарантированного субоптимального решения по функционалу в одномерной и многомерной задачах о ранце. Выводы. Составлен программный комплекс для нахождения гарантированного субоптимального решения по функционалу и проведены многочисленные вычислительные эксперименты над случайными задачами большой размерности. UK: Актуальність. Розглянуто задачу побудови гарантованого субоптимального (наближеного) рішення по функціоналу в одновимірній та багатовимірній задачах про ранець. Об’єктом дослідження є модель з приростом коефіцієнтів цільової функції. Мета роботи. Розробка методів побудови гарантованого субоптимального рішення по функціоналу в одновимірній та багатовимірній задачах про ранець, тобто знайти такі мінімальні зміни коефіцієнтів функціонала в заданих інтервалах, щоб знайдене рішення гарантувало значення функціоналу не менше, ніж заздалегідь фіксоване. Метод. Введено поняття допустимого, гарантованого і гарантованого субоптимального рішень по функціоналу в багатовимірній задачі про ранець. У заданих інтервалах необхідно знайти такі мінімальні зміни коефіцієнтів функціонала, щоб знайдене рішення гарантувало значення функціоналу не менш, ніж заздалегідь фіксоване. Таке рішення називаємо гарантованим рішенням по функціоналу для одновимірної і багатовимірної задачі про ранець. Розроблено методи їх побудови. Створено програмний комплекс для знаходження цих рішень і проведені численні обчислювальні експерименти над випадковими завданнями великої розмірності. Результати. Розроблено алгоритм для побудови гарантованого субоптимального рішення по функціоналу в одновимірній та багатовимірній задачах про ранець. Висновки. Створено програмний комплекс для знаходження гарантованого субоптимального рішення по функціоналу і проведені численні обчислювальні експерименти над випадковими завданнями великої розмірності. EN: Contex. The problem of constructing a guaranteed suboptimal (approximate) solution with respect to a functional in one-dimensional and multidimensional knapsack problems is considered. The object of the study was a model with an increment of the coefficients of the objective function. Objective. The methods of constructing guaranteed suboptimal solution through the functional in one-dimensional and multidimensional knapsack problem has been developed. That is it is necessary to find such minimal changes coefficient of the objective function in the set of integer intervals so that the solution found guarantees the value of the functional not less than the predetermined value. Method. The concept of guaranteed solution and guaranteed suboptimal solution relative to the objective function in the satchel problem is introduced. It is necessary to find such minimal changes coefficient of the objective function in the set of integer intervals so that the solution found guarantees the value of the functional not less than the predetermined value. Such kind of solution we name as guaranteed solution through the functional for one-dimensional and multidimensional knapsack problem. The methods of their construction has been developed. A software package was developed to find these solutions and numerous computational experiments were performed on random large-dimensional problems. Results. The algorithm of constructing guaranteed suboptimal solution through the functional in one-dimensional and multidimensional knapsack problem has been developed. Conclusions. A software package was developed to find the concept of guaranteed solution and guaranteed suboptimal solutions and numerous computational experiments were performed on random large-dimensional problems.