I-INTRODUCTION

II- Classication de problème d'optimisation

III- Méthodes de résolution

Chapitre 1: INTRODUCTION A

L'OPTIMISATION COMBINATOIRE

Ghislain PANDRY
Chercheur, Traitement du signal et des images

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

Domaines d'application
L'optimisation combinatoire intervient sur toute situation
nécessitant une planication ou une organisation ecace. Elle est
liée à la minimisation de risque, du temps ou du coût ainsi qu'à la
maximisation de la qualité, du prot ou de l'ecacité. L'industrie et
l'ingénierie sont les domaines qui protent le plus des études de
l'optimisation combinatoire. On cite quelques exemples :
La conception de réseaux (électriques, téléphoniques, etc) ;
La planications des tâches des employés d'une entreprise ;
Le calcul d'itinéraire pour les applications de géolocalisation ;
La planication du trac aérien ou routier ;
L'allocation de ressources matérielles et humaines ;
L'ordonnancement et la planication de la production ;
La gestion de portefeuilles ;
Maximisation du prot et minimisation du coût.
Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB
 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-1-1 : Dénition Étymologique

L'optimisation est un nom féminin qui dénit une action du verbe
optimiser. C'est la démarche consistant à rendre optimal le
fonctionnement d'un système : Donner à quelque chose (à une
machine, à une entreprise, etc.) le rendement optimal en créant les
conditions les plus favorables ou en tirant le meilleur parti possible..

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-1-2 : Dénition en RO
L'optimisation appartient au domaine de la Recherche
Opérationnelle qui représente la science de prise de décision. Un
problème d'optimisation en mathématique consiste à trouver la
meilleure solution possible pour un problème donné.

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-1-3 : Dénition Mathématique

Soit n ∈ N∗ un entier strictement positif,
X ⊂ Rn un sous-ensemble non vide
f : X → R une fonction à valeur réelle.
Un problème d'optimisation consiste à trouver la meilleure
solution x ∈ X appelée solution globale.
La meilleure solution du problème varie selon l'objectif. On parle
d'une minimisation ou une maximisation de la fonction f sur
l'ensemble X . On note : x = minx∈X f (x) ou x = maxx∈X f (x).

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-2-1 :Variables de décision

Le vecteur x ∈ X est appelé vecteur de décision. Les éléments
formants le vecteur de décision sont appelés variables de décision.
Ce sont les variables recherchées dans le problème.

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-2-2 :Dimension de problème

La dimension du problème est représentée par le nombre entier
n ∈ N∗ . Elle représente le nombre de variables de décision. Une
solution à un problème de 2 dimensions est un vecteur de 2
éléments (2-uplet).

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-2-3 :Espace de recherche et Solution admissible

L'ensemble X de dimension n contient les valeurs que le vecteur x
peut prendre. Ces dernières sont appelées solutions admissibles ou
faisables (ou encore solutions candidates). Une solution admissible
est une aectation de toutes les variables de décision , qui répond
aux contraintes du problème. L'ensemble X est connu sous
diérentes appellations : ensemble admissible, espace de solution,
espace de recherche, domaine de recherche etc..

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-2-5 :Contraintes
L'espace de recherche X est limité par quelques règles. Une
contrainte est une condition que doivent respecter les vecteurs de
décision du problème.

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-2-6 :Solution optimale

C'est la meilleure solution x ∈ X du problème. . Elle est appelée
solution globale ou optimale.

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-2-7 :Fonction objectif

la fonction f , à valeur scalaire, sert de critère pour déterminer la
meilleure solution du problème. Elle est appelée fonction d'objectif
(fonction tness, critère, etc). Elle attribue à chaque solution
x ∈ X de l'espace de recherche, un nombre réel indiquant sa valeur
(son score).

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-2-8 :Minimisation
Une minimisation revient à trouver un élément x de X tel que :
∀ ∈ X : f (x) ≤ f (x). On dit qu'on cherche à minimiser la fonction
f sur l'ensemble X . Dans ce cas la fonction d'objectif f est connue
comme une fonction de coût. Le vecteur x est une borne inférieure
de l'ensemble X .

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-2-9 :Maximisation
Une minimisation revient à trouver un élément x de X tel que :
∀ ∈ X : f (x)gleqf (x). On dit qu'on cherche à maximiser la
fonction f sur l'ensemble X . Dans ce cas la fonction d'objectif f est
connue comme une fonction d' utilité ou de prot. Le vecteur x
est une borne supérieure de l'ensemble X .

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-2-10 :Minimum et maximum stricte

On parle d'un minimum stricte (respectivement un maximum
stricte) si : ∀ ∈ X : f (x) < f (x) (respectivement f (x) > f (x)).

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-2-11 :Voisinage
Une solution voisine d'une solution x est dénit comme une légère
modication de la solution x . Cette modication est appelée aussi
mouvement. Le voisinage de la solution x est l'ensemble des
solutions de voisines de x .

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION I-1 : Problème d'optimisation
II- Classication de problème d'optimisation I-2 : Terminologie
III- Méthodes de résolution

I-2-12 :Optimum global et local

Un optimum global est la valeur de la fonction objectif de la
solution globale. On peut avoir plusieurs solutions globales mais un
seul optimum globale . Un optimum local reète la meilleure
solution dans un entourage voisin. Dans la gure, on remarque qu'il
existe deux solutions diérentes x et x qui reètent un seul
1 2

optimum global f = f . La solution x représente une solution

1 2 3

locale reétant un optimum local.

Figure  Optimum local et global

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB
 I-INTRODUCTION II-1 :Optimisation Continue et Optimisation Discrète
II- Classication de problème d'optimisation II-2 :Caractéristiques
III- Méthodes de résolution

II-1 : Familles
Il existe plusieurs familles d'optimisation. Il est important de bien
identier à quelle catégorie appartient le problème pour pouvoir
choisir la conduite de la résolution. Les problèmes d'optimisation
dièrent selon l'espace de recherche, les contraintes, les objectifs,
etc. Selon la nature de l'ensemble de recherche X on distingue deux
classes d'optimisation : l'optimisation continue et l'optimisation
discrète.

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION II-1 :Optimisation Continue et Optimisation Discrète
II- Classication de problème d'optimisation II-2 :Caractéristiques
III- Méthodes de résolution

II-1-1 :Optimisation Continue

On parle d'Optimisation continue, si l'espace de recherche X est
continu (par exemple l'ensemble des nombres réels R). La fonction
objectif est aussi continue. La
Pfonction sphère est une fonction
continue dénie par f (x) = i= xi . La minimisation de cette
n
0
2

fonction est une optimisation continue.

Figure  Fonction objectif continue

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION II-1 :Optimisation Continue et Optimisation Discrète
II- Classication de problème d'optimisation II-2 :Caractéristiques
III- Méthodes de résolution

II-1-2 :Optimisation Discrète

On parle d'Optimisation discrète, si l'espace de recherche X est
discret et inni. La fonction objectif qui dénit un tel problème est
représentée par un nuage de points. Les problèmes de cette classe
d'optimisation sont plus diciles que ceux de l'optimisation
continue.

Figure  Fonction objectif discrète

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION II-1 :Optimisation Continue et Optimisation Discrète
II- Classication de problème d'optimisation II-2 :Caractéristiques
III- Méthodes de résolution

II-1-2 :Optimisation combinatoire

L'optimisation combinatoire est une branche de l'optimisation
discrète dont l'espace de recherche est ni et dénombrable.

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION II-1 :Optimisation Continue et Optimisation Discrète
II- Classication de problème d'optimisation II-2 :Caractéristiques
III- Méthodes de résolution

II-2-1 : Optimisation avec et sans contraintes

L'espace de recherche peut être limité par des contraintes. Ces
dernières peuvent être des bornes inférieures ou supérieures, ou un
ensemble d'équations dénissant des situations précises.
L'optimisation avec contraintes est plus compliquée à résoudre.
Dans le cas contraire, l'espace de recherche n'est pas limité par des
contraintes. Il est alors inni et toutes les solutions incluses sont
candidates. L'optimisation sans contraintes est plus facile à
résoudre.

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION II-1 :Optimisation Continue et Optimisation Discrète
II- Classication de problème d'optimisation II-2 :Caractéristiques
III- Méthodes de résolution

II-2-2 : Optimisation mono ou multi-objectifs

Un problème d'optimisation peut avoir un ou plusieurs objectifs. Un
problème monoobjectif est déni par une unique fonction objectif.
S'il se trouve plusieurs objectifs qui génèrent une contradiction
entre eux, on parle alors d'un problème multi-objectifs. Pour des
raisons de simplication, un problème multi-objectif peut être
reformulé avec une seule fonction objectif ou en transformant des
objectifs sous forme de contraintes.

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION III-1 : Introduction
II- Classication de problème d'optimisation III-2 :Classication des méthodes de résolution
III- Méthodes de résolution

III-1-1 : Introdcution
Face à un problème d'optimisation combinatoire donné, la question
à laquelle on doit répondre est la résolution du problème. Ce dernier
possède généralement un nombre énorme de solutions réalisables.
La résolution la plus évidente est de lister toutes les combinaisons
possibles an de trouver celles qui sont valides et meilleures. On
appelle ce type d'algorithme : Algorithmes Exhaustifs.
Ces algorithmes sont très gourmands en terme de complexité. Ils
passent d'algorithmes polynomiaux à non-polynomiaux avec
l'augmentation de la dimension du problème à traiter.

Ghislain PANDRY Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB

 I-INTRODUCTION III-1 : Introduction
II- Classication de problème d'optimisation III-2 :Classication des méthodes de résolution
III- Méthodes de résolution

III-2-1 : Classes de familles

Les méthodes de l'optimisation combinatoire peuvent être classées
en deux grandes familles de classes : les méthodes exactes et les
méthodes approchées.

Figure
Ghislain  Type de
PANDRY méthodes
Chapitre 1: INTRODUCTION A L'OPTIMISATION COMB