Sensitivity analysis of the knapsack sharing problem: perturbation of the weight

Résumé En Fr

In this paper, we study the sensitivity analysis of the optimum of the knapsack sharing problem (KSP) to the perturbation of the weight of an arbitrary item. We determine the interval limits of the weight of each perturbed item using a heuristic approach which reduces the original problem to a series of single knapsackk problems. A perturbed item belongs either to an optimal class, or to a non-optimal class. We evaluate the performance of the proposed heuristic on a set problem instances of the literature. Encouraging results are obtained.

Dans cet article, nous étudions la stabilité d'une solution optimale donnée du problème du partage équitable. Nous nous intéressons à l'étude de la variation/perturbation d'un poids quelconque. Nous établissons des bornes inférieures et supérieures par application d'un algorithme polynomial. Ce dernier est appliqué sur une série de problème de knapsack unidimensionnel qui n'est que le résultat de la réduction du problème original. Par la suite, nous examinons le comportement de l'algorithme ainsi que la qualité des limites obtenues sur un ensemble d'instances de la littérature. Des résultats encourageants sont obtenus.