Licence en Recherche Opérationnelle,

3ème année, section B

Matière : Modélisation
(2020/2021)

Chapitre 3 :
Etude de cas
Le but de ce chapitre est de décrire et présenter certains types particuliers bien connus de
modèles mathématiques qui ont reçu une attention théorique considérable.

1
1 Problème du Sac à dos (Knapsack Problem, KP)

Le problème du sac à dos est défini comme suit :

• ayant un ensemble de n objets,
• à chaque objet est associé
• un poids pi
• une utilité ui,
• on dispose d’un sac-à-dos dont le poids total ne doit pas dépasser W (capacité du sac)
• déterminer quels objets prendre pour maximiser l’utilité.

Il tire son nom du problème rencontré par quelqu’un

(un randonneur) qui est contraint par un sac à dos
qui doit le remplir avec les articles les plus précieux
mais sans dépasser un poids limite.

2
Un tel problème prend la forme d’un PLVB :

M aximiser u1.x1 + u2.x2 + . . . + [Link]


 p1.x1 + p2.x2 + . . . + [Link] ≤ W
s. c.
 x , x , . . . , x ∈ {0, 1}
1 2 n

où xi = 1 si l’objet i est pris et 0 sinon, i = 1, . . . , n.

Une extension évidente à ce problème est celle où les variables sont entières. Dans ce cas,
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.

Si le nombre d’exemplaires est limité, on parlera de sac à dos borné (bounded knapsack pro-
blem, BKP), sinon on parlera de sac à dos non borné (UKP).

Le problème de base (le plus couramment utilisé) est noté 0−1 knapsack problem.

Le problème BKP peut être transformé en 01KP sans difficulté.

3
Le problème du sac à dos classique a été étudié pendant plus d’un siècle, avec les premiers
travaux remontant à 1897. Le nom problème du sac à dos remonte aux premiers travaux
du mathématicien Tobias Dantzig (1884-1956). Une application originale de ce problème est
celle de la découpe (papier, tôle, etc.) à une dimension décrite par Gilmore et Gomory (1963,
1965).

La programmation dynamique reste l’outil le plus efficace pour résoudre ce problème avec des
instances de grandes tailles.

4
Le problème se pose souvent dans des domaines très variés tels que

— le choix de projets où il y a des contraintes financières,

— le stockage de marchandises dans un entrepôt,

— le chargement d’un camion, d’un bateau ou d’un avion (sans être en surcharge),

— la découpe de matériaux : pour minimiser les chutes lors de la découpe de sections de

longueurs diverses dans des barres en fer, de rouleaux de papier ou de textile etc.

Il est étudié et utilisé dans des domaines tels que la combinatoire, l’informatique, la théorie de
la complexité, la cryptographie, les mathématiques appliquées, le sport, etc.

5
2 Problème du voyageur de commerce
(Travelling Salesman Problem, TSP)

Le problème du voyageur de commerce est défini de la manière suivante : étant donné une liste
de n villes, et des coûts (distances ou durées de parcours) entre les paires de villes, trouver la
plus courte tournée permettant de visiter toutes villes et de revenir au point de départ en ne
visitant chaque ville qu’une seule fois.

6
On peut formuler le TSP en associant à chaque couple (i, j) de villes à visiter (i, j = 1, . . . , n,
i 6= j) une distance égale à dij s’il existe un moyen d’aller directement de i à j, fixée à ∞ sinon
et une variable de décision, xij qui prend la valeur 1 si la ville j est visitée immédiatement après
la ville i dans la tournée et qui prend la valeur 0 sinon. Le TSP est alors modélisé par :

n P
P n
minimiser dij xij
i=1 j=1

 n
P



 xij = 1; j = 1, . . . , n

 i=1(i6=j)





 Pn
x = 1; i = 1, . . . , n

 j=1(j6=i) ij



s.c.




 ui − uj + n xij ≤ n − 1 i, j = 2, . . . , n (i 6= j)



xij ∈ {0, 1}; i, j = 1, . . . , n (i 6= j)








ui ∈ IN ; i = 1, . . . , n


Les deux premiers types de contraintes traduisent le fait que chaque ville doit être visitée
exactement une fois ; le troisième type interdit les solutions composées de sous-tours disjoints,
elle est généralement appelée contrainte d’élimination des sous-tours.
7
On supposons que i = 1 est le sommet initial. Le troisième type de contraintes interdit les
tours ne contenant pas le sommet 1. En effet, si on suppose l’existence d’une tour à k sommets
alors nk ≤ k(n − 1) en sommant les k contraintes, ce qui est impossible. Dans une solution
réalisable, on aura ui = j si le sommet i est le j-ième sommet de la tour à partir du sommet 1.

Pour ce troisième type de contraintes, d’autres formulations existent, nous citons :

P
xij ≥ 2; ∀S ⊂ X, S 6= ∅
i∈S,j ∈S
/

ou encore

P
xij ≤ |S| − 1; ∀S ⊂ X, S 6= ∅
i,j∈S

où X étant l’ensemble des villes.

Toutefois, elles ne peuvent pas être directement utilisées par un logiciel de résolution.

8
Le problème du voyageur du commerce a de nombreuses applications, et a d’ailleurs été motivé
par des problèmes concrets, par exemple le parcours des bus scolaires.

Un premier type d’application classique est bien sûr dans la logistique, par exemple pour la
poste, la distribution de repas à domicile, inspection d’installation, etc. On peut aussi optimiser
les mouvements de machines, par exemple, pour minimiser le temps total que met une frai-
seuse à commande numérique pour percer n points dans une plaque de tôle, ou minimiser les
mouvements des grands télescopes (qui sont très lents).

On peut citer des applications plus surprenantes, par exemple : en biologie, le problème d’aide
au séquençage du génome (pour relier des petits fragments en des chaı̂nes plus grandes), et en
production où il est utilisé pour la fabrication et le test des circuits imprimés.

Aussi, divers problèmes de recherche opérationnelle se ramènent au voyageur de commerce

9
Le problème est difficile à résoudre. Il a été formulé pour la première fois en 1930 et est l’un
des problèmes d’optimisation les plus étudiés. Jusqu’à ce jour un grand nombre d’heuristiques
et d’algorithmes exacts sont connus, de sorte que certains cas avec des dizaines de milliers de
villes peuvent être résolus complètement et même des problèmes avec des millions de villes
peuvent être approchés dans une petite fraction de 1%. Il est aussi utilisé comme référence
pour de nombreuses méthodes d’optimisation.

Variantes

Problème du voyageur de commerce orienté : Dans ce cas, on peut considérer qu’un chemin
existe dans un sens mais pas dans l’autre (exemple : routes à sens unique).

Problème du voyageur de commerce symétrique : Dans ce cas, la distance de i à j est la

même que celle de j à i.

Problème du voyageur de commerce asymétrique : Cette fois-ci, la distance entre deux

villes i et j n’est pas forcément la même qu’on aille de i à j ou bien de j à i.

10
3 Problème de Transport
Le problème de transport est défini comme suit :

• Ayant un ensemble de m sources S1, . . . , Sm avec des capacités respectives s1, . . . , sm

(offre).
• Ayant un ensemble de n destinations D1, . . . , Dn avec des demandes respectives d1, . . . , dn
(demande).
• Ayant des coûts de transport des sources vers les destinations : cij , i = 1, . . . , m; j =
1, . . . , n.

Déterminer quelles sont les quantités xij à transporter des sources vers les destinations à
moindre coût.

11
Le modèle général d’un problème de transport est :
Pm P n
minimiser cij xij
i=1 j=1

 n
P
xij ≤ si; i = 1, . . . , m





 j=1



m
s.c. P

 xij = dj ; j = 1, . . . , n

 i=1




 x ≥ 0; i = 1, . . . , m; j = 1, . . . , n
ij

m
P n
P
Si on a si = dj , le problème est dit équilibré.
i=1 j=1

Pour des raisons de résolution, il est préférable de considérer des problèmes équilibrés. Dans
ce cas, les contraintes d’offre deviennent des égalités.

12
Remarques :

• Pour équilibrer un problème de transport pour lequel il y a trop d’offre, il suffit de créer
un point de demande virtuel dont la demande correspond à l’offre excédentaire, et pour
lequel les coûts de transport sont nuls.

• Lorsque le transport n’est pas possible entre une source et une destination, il suffit de
considérer un coût infini (une valeur suffisamment grande).

• Lorsque la demande excède l’offre, il n’y a pas de solution réalisable. Mais on peut
avoir de la demande non satisfaite, en créant un point de source virtuel dont la capacité
correspond à la demande excédentaire, et pour lequel les coûts de transport sont nuls.

• Lorsque les offres et les demandes sont entières (∈ IN ) alors les quantités à transporter
seront entières (la solution est entière).

• Il existe des méthodes efficaces de résolution : Simplexe adapté avec méthode dite du
coin nord-ouest ou méthode du coût minimal.

13
4 Problème de localisation
Le problème de localisation est défini comme suit :
• Ayant un ensemble de m sites S1, . . . , Sm envisageables pour installer des entrepôts
avec des coûts respectives f1, . . . , fm.
• Ayant un ensemble de n clients C1, . . . , Cn.
• Ayant des coûts d’affectation du client j au site i : cij , i = 1, . . . , m; j = 1, . . . , n.
On souhaite décider de l’ouverture de sites et affecter les clients à un site, de sorte à minimiser
la somme des coûts d’ouverture des sites et d’affectation des clients aux sites.

14
Définissons les variables binaires suivantes :

Pour i = 1, . . . , m ; yi = 1 si et seulement si le site en i est ouvert, et yi = 0 sinon.

Pour i = 1, . . . , m et j = 1, . . . , n ; xij = 1 si le client j est affecté au site i, et xij = 0 sinon

Le modèle mathématique est :

m
P m P
P n
minimiser fi yi + cij xij
i=1 i=1 j=1


Pm
xij = 1; j = 1, . . . , n






 i=1



xij ≤ yi; i = 1, . . . , m; j = 1, . . . , n

s.c.





 xij ∈ {0, 1}; i = 1, . . . , m; j = 1, . . . , n



 y ∈ {0, 1};

i = 1, . . . , m
i

15
5 Problèmes de graphes
5.1 Ordonnancement de projets

Considérons un projet qui consiste en un ensemble de n tâches T1, T2, . . . , Tn, de durées
p1, p2, . . . , pn respectivement, liées par des contraintes de précédence qu’on peut représenter
par un graphe orienté où les sommets représentent les tâches, les arcs représentent les contraintes
de précédence et les poids sur les arcs représentent les durées de traitement. Les ressources
étant supposées disponibles en quantités illimitées. Calculer la durée minimale du projet.

Ce problème peut se formuler comme un programme linéaire en ajoutant deux tâches fictives
T0 et Tn+1 de durée nulle. La tâche T0 précède toutes les tâches sans prédécesseur et la tâche
Tn+1 succède à toutes les tâches sans successeur.

Soient les variables :

ti = date de début de traitement de la tâche Ti, pour i = 0, . . . , n + 1.

Le modèle mathématique est :

minimiser tn+1 − t0

 ti + pi ≤ tj ; si Ti précède Tj
s.c.
 t ≥ 0; i = 0, . . . , n + 1
i

16
5.2 Clique maximum

Une clique d’un graphe non orienté G = (V, E) est un sous-ensemble de sommets dont le
sous-graphe induit est complet, c’est-à-dire que deux sommets quelconques de la clique sont
adjacents. Une clique maximum d’un graphe est une clique dont le cardinal est le plus grand
(c’est-à-dire qu’elle possède le plus grand nombre de sommets).

Soient les variables :

xi = 1 si le sommet i appartient à la clique, et 0 sinon, pour i = 1, . . . , n.

Le modèle mathématique est :

n
P
maximiser xi
i=1


x + xj ≤ 1; ∀(i, j) ∈ E
 i


{deux sommets non reliés ne peuvent pas appartenir à la clique}
s.c.


xi ∈ {0, 1}; i = 1, . . . , n


17
5.3 Stable maximum

Un stable d’un graphe non orienté est un sous-ensemble de sommets non adjacents. Un stable
maximum d’un graphe est un stable dont le cardinal est le plus grand (c’est-à-dire qu’il possède
le plus grand nombre de sommets).

Soient les variables :

xi = 1 si le sommet i appartient au stable, et 0 sinon, pour i = 1, . . . , n.

Le modèle mathématique est :

n
P
maximiser xi
i=1


x + xj ≤ 1; ∀(i, j) ∈ E
 i


{deux sommets reliés ne peuvent pas appartenir au stable}
s.c.


 x ∈ {0, 1}; i = 1, . . . , n
i

18