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

Abstract

Введено поняття гарантованого розв’язку та гарантованого наближеного (субоптимального) розв’язку багатовимірної задачі про ранець і розроблено алгоритм побудови цих розв’язків. Метод базується на зміні правих частин обмежень за принципом дихотомії. Проведено низку обчислювальних експериментів.

The concept of guaranteed solution and guaranteed approximate (suboptimal) solution of multidimensional knapsack problem is introduced and algorithm of constructing these solutions is developed. This method is based on the variation of the righthand parts of constraints by the dichotomia principle. The numerical experiments are performed.