Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Problème sac à dos Problématique - Capacité illimité - Chaque objet possède un

Problème sac à dos Problématique - Capacité illimité - Chaque objet possède un poids et une valeur - La valeur doit optimiser la valeur totale des objets L’énoncé de ce problème fameux est simple : « Étant donné plusieurs objets possédant chacun un poids et une valeur et étant donné un poids maximum pour le sac, quels objets faut-il mettre dans le sac de manière à maximiser la valeur totale sans dépasser le poids maximal autorisé pour le sac ? » Formulation mathématique Toute formulation commence par un énoncé des données Problème : choisir un sous ensemble d’objet d’utilité maximale a placé dabs un sac tel la capacité de sac soit respectée Données W : capacité maximale de sac I : l’ensemble de n objets Pi : pour chaque objets i € I pi représente son utilité Wi : chaque objet i a un poids w Contraintes: respectée? x1.W1 + x2.W2 + x3.W3 + x4.W4 ≤ W Forumule Enfin, il faut exprimer la fonction qui traduit notre objectif : maximiser la valeur totale des objets dans le sac. Pour n objets, cela s’écrit : Nous parlons alors de solution réalisable mais ce n’est pas nécessairement la meilleure solution Les Différents Variantes Variable entiers : Dans le problème de sac à dos en variables entières, on considère que l'on a plusieurs exemplaires de chaque objet. Le problème consiste donc à trouver le nombre d'exemplaires à prendre pour chacun. Sac à dos multidimensionnel : On considère ici que le sac à dos a d dimensions, avec d > 0 (d-KP). Par exemple, on peut imaginer une boîte. Chaque objet a trois dimensions, et il ne faut déborder sur aucune des dimensions. La contrainte (1) est alors remplacée par: En pratique, la version multidimensionnelle peut servir à modéliser et résoudre le problème du remplissage d'un container dont le volume et la charge maximale sont limitées. Sac à dos multi-objectif : Une variante du problème consiste, à partir d'objets ayant plusieurs valeurs, à maximiser plusieurs fonctions objectives, c'est le problème du sac à dos multi-objectif (MOKP). On rentre donc dans le domaine de l'optimisation multi-objectif. Sac à dos quadratique : Le problème de sac à dos quadratique est noté QKP. On a ici un gain gij supplémentaire lorsque deux objets (i et j) sont pris simultanément. Par exemple, disons qu'on souhaite maximiser la qualité du café lors d'une expédition avec un sac à dos Sac à dos à choix multiple : Dans le problème de sac à dos à choix multiple (MCKP), les objets sont regroupés en classes, et il ne faut prendre qu'un seul représentant pour chaque classe. Les domaines d’application On I ‘utilise le problème de sac a dos multidimensionnelle pour modéliser plusieurs situations nous citons - dans des systèmes d'aide à la gestion de portefeuille. pour équilibrer sélectivité et diversification dans le but de trouver le meilleur rapport entre rendement et risque pour un capital placé sur plusieurs actifs financiers. - dans le chargement de bateau ou d’avion. Exemple de résolution du problème Pour quatre objets (n = 4) et un sac à dos d'un poids maximal de 30 kg (P = 30), nous avons par exemple les données suivantes : Objets 1 2 3 4 Pi 7 4 3 3 Wi 13 12 8 10 Ensuite, il nous faut définir les variables qui représentent en quelque sorte les actions ou les décisions qui amèneront à trouver une solution. On définit la variable xi associée à un objet i de la façon suivante : - Xi= 1 si l’objet i est mis dans le sac - Xi = 0 si l’objet i n’est pas mis dans le sac. Dans notre exemple, une solution réalisable est de mettre tous les objets dans le sac à dos sauf le premier, nous avons donc : x1 = 0, x2 = 1 x3 = 1 x4 = 1 Puis il faut définir les contraintes du problème. x1.p1 + x2.p2 + x3.p3 + x4.p4 ≤ P Et pour n objets : Pour vérifier que la contrainte est respectée dans notre exemple, il suffit de calculer cette somme : 0 × 13 + 1 × 12 + 1 × 8 + 1 ×10 = 30 donc la contrainte est respectée Les algorithmes proposés pour résoudre le problème étudié : Les Méthodes exactes : permettent d’obtenir la solution optimale à chaque fois, mais le temps de calcul peut être non si le problème est compliqué à résoudre Les Méthodes approchées : - en cours appelée heuristiques, permettent d’obtenir rapidement une solution approchée, donc pas nécessairement optimale - A pour but de trouver une solution avec un bon compromis entre la qualité de la solution et le temps de calcul. 1. Best Fit Decreasing (BFD) (meilleur remplissage par ordre décroissant) 2. Algorithme de recherche Tabou 3. Algorithme génétique uploads/Voyage/ seance-1.pdf