http://creativecommons.org/licenses/by/
Tarik Belgacem et al., « Sensitivity analysis of the knapsack sharing problem: perturbation of the profit », HAL-SHS : économie et finance, ID : 10670/1.3bhjt3
Dans cet article, nous étudions la sensibilité de l'optimum d'un problème d'optimisation combinatoire de max-min, à savoir le problème du partage équitable, noté KSP (en anglais Knapsack Sharing Problem), soumis à la perturbation du profit d'un élément quelconque. Nous établissons principalement les limites de l'intervalle de sensibilité pour chaque profit en utilisant la réduction du problème initial en une série de problèmes de sac à dos. Nous proposons un algorithme permettant le calcul de ces limites en temps polynomial. On distingue plusieurs cas suivant que l'élément perturbé appartient ou pas à une classe optimale et suivant que l'instance du problème admet une unique ou plusieurs classes optimales. Enfin, nous évaluons l'efficacité des intervalles obtenus par cette procédure sur plusieurs instances de la littérature.