Problème de Sac à dos

sac


1. Données

Pour télécharger les données de ce cas d'utilisation et la version d'essai de XLOPTIM, veuillez cliquer sur les liens suivants:

Télécharger les données du problème de sac à dos

Télécharger la version d'essai

2. Le Problème

Dans le problème de sac à dos, nous avons un nombre donné d’objets qui ont tous des poids différents, et qui généreront après leur vente des profits différents. La capacité du sac nous empêche de choisir tous les objets : se dessine alors un problème d’optimisation mathématique dans lequel l’objectif sera de maximiser le profit total des objets choisis tout en respectant la capacité du sac.

Le problème de sac à dos peut être également généralisé à plusieurs sacs, le nombre de combinaisons devenant combinatoires à partir d’un certains nombres d’objets, il donne souvent lieu à des études pour de nombreux chercheurs. Ce problème peut être utilisé pour modéliser des problèmes de chargements de marchandise, mais également des problèmes de découpe industrielle très souvent enrichis de contraintes qui complexifient le problème initial.

La capacité du sac est ici de 25 000. Pour chacun des 190 objets, nous connaissons leur poids, donné dans le tableau ci-dessous :

table1

Nous cherchons à proposer une modélisation linéaire de ce problème de sac à dos, ainsi qu’un outil d’aide à la décision dans XLOPTIM®.

3. Modélisation

Nous proposons une modélisation suivant les 5 étapes suivantes :

Étape #1 : Quels sont les dimensions / indices du problème ?

  • i : 1.. 190 : les objets

Étape #2 : Quelles sont les données du problème ?

  • Le poids de chaque objet :

$$W_i$$

  • Le profit de chaque objet :

$$P_i$$

  • La capacité maximale du sac :

$$K$$

Étape #3 : Quelles sont les variables de décision ?

  • Est-ce que je sélectionne l’objet i dans mon sac ou pas :

$$X_{i}$$

Étape #4 : Quelles sont les contraintes ?

  • Le poids total du sac ne doit pas dépasser sa capacité :

$$\forall \,\ j \in [1;190], \sum_{i=1}^{190}{(X_i.W_i)} \leqslant K$$

Étape #5 : Quel est l’objectif du problème ?

Maximiser le profit total

$$Max\sum_{i=1}^{190}{(X_i.P_i)}$$

4. Traduction en XLOPTIM®

xloptim1

Définition des variables de décision principales booléennes :

xloptim2

Ajout de la contrainte “Le poids total du sac ne doit pas dépasser sa capacité” :

xloptim3

Fixation de l’objectif (Maximiser le profit total) :

xloptim4

Calcul de la solution optimale:

xloptim5

qui donne une valeur de la fonction objectif optimale suivante :

xloptim6

5. Conclusion

En décidant de garder ces objets dans le sac, le profit total généré par les objets s'élèvera à hauteur de 30 975 € . Le résultat affiché est optimal et obtenu après 2 secondes.

Cette étude de cas vous a permis de découvrir un exemple de problème de sac à dos. Ils sont fréquents dans les problèmes industriels de chargement mais également de découpe. Vous pouvez faire varier la taille du problème et modifier les hypothèses pour obtenir différentes solutions. N'hésitez pas à nous contacter si vous avez des questions suite à l'utilisation de notre solver XLOPTIM®.