Решение задачи о ранце: постоптимальный анализ и метод ветвей и границ

Abstract

Запропоновано алгоритм постоптимального аналізу для визначення точних розв’язків сімейства споріднених задач про ранець, до яких належить вихідна задача. Обчислювальний експеримент показує, що середній час розв’язання задачі сімейства принаймні в десять разів менший за час розв’язання вихідної задачі методом гілок і меж.

An algorithm of postoptimality analysis for determining exact solutions of a family of knapsack problems including an initial problem is proposed. Computational experiments show that the average time of solving a problem of the family is at least ten times less than the time of solving the initial problem by the branch and bound method.