Гарантированная оценка точности для задачи о рюкзаке с выпуклыми монотонными сепарабельными функциями

Abstract

Рассмотрена задача дискретной оптимизации – задача о рюкзаке с выпуклыми монотонными сепарабельными функциями. Представлены результаты вывода гарантированной оценки точности градиентного алгоритма, реализованного на аппроксимационной решетке.

The task of the discrete optimization – knapsack problem with convex separable monotonic functions is considered. The results of the finding of the guaranteed assessing the accuracy of the gradient algorithm implemented on the approximation lattice are presented.