Problème De Sac à Dos

Institut National des Sciences Comptables et de l’Administration d’Entreprise

PROBLEME DE SAC A DOS

Dans le cadre de la matière

RECHERCHE OPERATIONNELLE

SOMMAIRE

INTRODUCTION 1

I. ENONCE MATHEMATIQUE 2

II. METHODE RESOLUTION 4

A. METHODE APPROCHEE 4

1. L’algorithme de glouton 4

a) Exemple 5

B. METHODE EXACTE 6

1. Procédure par séparation et évaluation (PSE) 6

a) Exemple 1 7

b) Exemple 2: 9

c) Exemple 3: 11

CONCLUSION 12

INTRODUCTION

Découvrir le plus court chemin pour se rendre à un endroit précis, concevoir un circuit électronique, placer des antennes pour diffuser des chaînes de télévision, ou des relais pour les réseaux de téléphonie mobile, reconstruire le code génétique des êtres humains, décider de l’implantation d’un site de production,…

Cette liste peut paraître hétérogène et provenant de domaines très différents, mais elle contient des problèmes qui ont tous une structure combinatoire. En effet, chacun d’entre eux revient à choisir la meilleure combinaison parmi une quantité bien connue mais souvent exponentiellement grande de possibilités.

Informellement, ce problème est défini de la manière suivante : durant un cambriolage un voleur possède un sac dont la capacité est limitée. Il se trouve face à un ensemble d'objets qu'il peut dérober. Chacun de ces objets est caractérisé par sa valeur et son poids. Le voleur souhaite optimiser la valeur totale des objets qu'il va dérober tout en ne dépassant pas le poids maximal supporté par son sac.

Ce problème est une abstraction pour un grand nombre d'autres problèmes d'optimisation.

Il est aussi utilisé en cryptographie comme une base pour différents schémas de chiffrement. Il faut cependant noter que la plupart de ces schémas de chiffrement ne sont plus actuellement considérés comme sûrs.

L’énoncé de ce problème 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 ? ».

La résolution des problèmes d’optimisation combinatoires (POC) nécessite une modélisation efficace et adaptée.

I. ENONCE MATHEMATIQUE

Les données du problème peuvent être exprimées en termes mathématiques. Les objets sont numérotés par l'indice i variant de 1 à n. Les nombres et représentent respectivement le poids et la valeur de l'objet numéro i. La capacité du sac sera notée W.

Il existe de multiples façons de remplir le sac à dos. Pour décrire l'une d'elles il faut indiquer pour chaque élément s'il est pris ou non. On peut utiliser un codage binaire : l'état de l’i-ème élément vaudra si l'élément est mis dans le sac, ou s'il est laissé de côté. Une façon de remplir le sac est donc complètement décrite par un vecteur, appelé vecteur contenu, ou simplement contenu : ; et le poids associé, ainsi que la valeur associée, à ce remplissage, peuvent alors être exprimés comme fonction du vecteur contenu.

Pour un contenu X donné, la valeur totale contenue dans le sac est naturellement :

De même, la somme des poids des objets choisis est :

Le problème peut alors être reformulé comme la recherche d'un vecteur contenu (les composantes valant 0 ou 1), réalisant le maximum de la fonction valeur totale , sous la contrainte :

C'est-à-dire que la somme des poids des objets choisis ne dépasse pas la capacité du sac à dos.

En général, on ajoute les contraintes suivantes afin d'éviter les cas singuliers :

• : on ne peut pas mettre tous les objets ;

• : aucun objet n'est plus lourd que ce que le sac peut porter ;

• : tout objet a une valeur et apporte un gain ;

• : tout objet a un certain poids et consomme des ressources.

Terminologie :

• est appelée fonction objectif ;

• tout vecteur vérifiant la contrainte est dit réalisable ;

• si la valeur de est maximale, alors est dit optimal.

II. METHODE RESOLUTION

Il existe deux grandes catégories de méthodes de résolution de problèmes d’optimisation combinatoire : les méthodes exactes et les méthodes approchées. Les méthodes exactes permettent d’obtenir la solution optimale à chaque fois, mais le temps de calcul peut être long si le problème est compliqué à résoudre. Les méthodes approchées, encore appelées heuristiques, permettent d’obtenir rapidement une solution approchée, donc pas nécessairement optimale. Nous allons détailler un exemple d’algorithme de résolution de chaque catégorie.

A. METHODE APPROCHEE

Une méthode approchée a pour but de trouver une solution avec un bon compromis entre la qualité de la solution et le temps de calcul. Pour le problème du sac à dos, voici un exemple d’algorithme de ce type :

1. L’algorithme

...