Cours MOP 2019

Université Mohamed Elbachir Elibrahimi de B.B.
A
Faculté des mathématiques et d’informatique
Département de Recherche Opérationnelle
M L
J K
Cours d’optimisation
multiobjectifs
Par : RAMDANI Zoubir
[email protected]
2018-1019
Table des matières
1 Introduction et concepts de base 2

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Notions fondamentales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Exemple d’aide à la décision multicritères . . . . . . . . . . . . . . 3
1.2.2 Ensemble et fonction convexe . . . . . . . . . . . . . . . . . . . . . 4
1.2.3 Optimum local et global . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.4 Qu’est-ce qu’un problème d’optimisation multiobjectifs . . . . . . . 6
1.2.5 Solution efficace et relation de dominance . . . . . . . . . . . . . . . 8
1.2.6 Front de Pareto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.7 Les points caractéristiques . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.8 Exemple illustratif . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Caractérisation des solutions efficaces . . . . . . . . . . . . . . . . . . . . 13
1.3.1 Technique de pondération des fonctions objectifs . . . . . . . . . . . 13
1.3.2 Technique de test d’efficacité d’une solution . . . . . . . . . . . . . 15
1.3.3 Techniques utilisant les distances . . . . . . . . . . . . . . . . . . . 16
1.4 Classification des méthodes de résolution . . . . . . . . . . . . . . . . . . . 17
1.5 Série d’exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.6 Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 Méthodes de scalaires 30
2.1 Méthode de pondération des fonctions objectif . . . . . . . . . . . . . . . . 30
2.1.1 Exemple pour la méthode de pondération . . . . . . . . . . . . . . 35
2.2 Méthode -contrainte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.2.1 Exemple pour la méthode -contrainte . . . . . . . . . . . . . . . . 39
2.3 Méthode hybride . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.4 Série d’exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
1
2.5 Corrigés des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
bibliographie 48
2
CHAPITRE 1
Introduction et concepts de base
1.1 Introduction
Dans la plupart des problèmes du monde réel, il ne s’agit pas d’optimiser seulement
une seule fonction objectif (critère) mais plutôt d’optimiser simultanément plusieurs fonc-
tion (critères) et qui sont généralement conflictuels ou contradictoires. Dans les problèmes
de gestion de production, par exemple, il faut le plus souvent maximiser les bénéfices et
minimiser les coûts (Achat de matières premières, salaires, économiser l’énergie.....).
Cette philosophie de multiplicité d’objectifs où l’optimisation multiobjectifs dite en an-
glais ”multiobjective optimization” qu’on note souvent (M OP ) semble très raisonnable
et contribue efficacement à l’élaboration de nouveaux systèmes d’aide à la décision, qui
visent à faciliter la tâche des décideurs en anglais ”Decision Maker” qu’on note (DM )
devant des choix complexes, qui s’avèrent souvent être conflictuels.
Contrairement en optimisation classique mono-objectif, où il s’agit de chercher une

solution réalisable dite optimale, dans l’optimisation multiobjectifs la solution optimale
n’est pas unique, il s’agit d’un ensemble dit ”ensemble de solutions efficaces” où ”Solutions
de Pareto 1 ”. En effet, c’est après avoir trouvé les solutions du problème multiobjectifs que
d’autres difficultés surviennent : il faut sélectionner une solution de de cet ensemble. La
solution qui sera choisie par l’utilisateur va refléter les compromis opérés par le décideur
(DM ) vis-à-vis des fonctions objectifs considérées.
Pour fixer les idées, supposons que vous vous apprêtiez à partir en voyage en Tunisie.
Vous pouvez partir à pied ou en auto-stop, économisant ainsi votre monnaie au détriment
1. Vilfredo Pareto(1848 -1923) un sociologue et économiste italien
3
de la durée, ou alors partir en première classe dans un avion sur une compagnie luxueuse,
profitant ainsi d’un temps de voyage minimum, au détriment de votre porte-monnaie. Ou
encore, vous pouvez trouver une combinaison intermédiaire (vélo, train puis bateau puis
voiture, etc.).
Où acheter une voiture, une voiture de haute gamme (puissante, confortable, chère...),
une voiture ordinaire( pas chère, non robuste....).
1.2 Notions fondamentales

1.2.1 Exemple d’aide à la décision multicritères
Pour mieux comprendre l’optimisation avec plusieurs critères (fonctions objectif), voici
un exemple tiré de livre [2] .
Exemple 1. Nous voulons acheter une voiture neuve, nous nous somme intéressés par
quatre marques VW Golf, Opel Astra, Ford Focus et Toyota Corolla. Notre décision est
accordée sur trois objectifs où critères à savoir
1. Prix d’achat qui à minimiser ;
2. Consommation (carburant) qui est aussi à minimiser ;
3. La puissance du moteur qui est souvent de type maximiser.
Ce simple exemple est un problème de décision qui contient 4 solutions alternatives avec
trois critères à optimiser. Les données de cet exemple sont regroupées dans le tableau
Type de voiture
Golf Opel Astra Ford Focus Toyota Corolla.
Prix en dinars(0.1 million) 16.2 14.9 14.0 15.2
Objectifs Consommation par Litre/100KM 7.2 7.0 7.5 8.2
puissance(KW) 66.0 62.0 55.0 71.0
Données de l’exemple 1
Notons par S = {V W Golf, OpelAstra, F ord F ocus, T oyota Corolla} l’ensemble

de solutions réalisables où l’ensemble de solutions alternatives où ensemble d’actions .
Cependant, l’ensemble des critères et Y = {Prix,Consommation,puissance}.
On se pose la question suivant : comment choisir une voiture dont le prix est moins chère,
plus puissante et consomme moins ?.
Si on prend uniquement les deux critères consommation (à minimiser) noté par f1 et
le prix (à minimiser) qu’on note par f2 , la figure 1.1 montre que le choix efficace où( le
4
Figure 1.1 – L’espace des critères de l’exemple 1
meilleur choix) est entre Opel and Ford. Notons que, Golf et Toyota sont plus chers et
consomme trop par rapport a Ford et Opel.
En effet, ce problème d’aide à la décision peut ce formulé comme suit :

 ” min ” (f1 (x)

” min ” (f2 (x)

 x∈S
Cette exemple illustre que le concept et la notion d’optimalité dans l’optimisation mul-
tiobjectif que nous allons voir dans la suite de ce chapitre.
1.2.2 Ensemble et fonction convexe

Définition 1. (Ensemble convexe)
Soit l’ensemble S ⊆ Rn . S est convexe si
∀x, y ∈ S : λx + (1 − λ)y ∈ S ∀λ ∈ [0, 1]
La Figure (1.2) illustre cette notion.

r
\
Si S1 , S2 , ..., Sr sont des ensembles convexes, alors l’intersection Ci est convexe
i=1
Définition 2. (Fonction convexe)

Soit un ensemble S ⊆ Rn convexe. Une fonction f : S → Rn est convexe si
∀x, y ∈ S : f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (z) ∀λ ∈ [0, 1]
– f est strictement convexe si cette inégalité est stricte.

– f est concave si (−f ) est convexe.
5
Figure 1.2 – Un ensemble convexe
1.2.3 Optimum local et global

Définition 3. (Optimum local) Soit f une fonction à minimiser sur un ensemble S ⊆ Rn ,
x∗ est un minimum local de f si
∃ε > 0 tel que f (x∗ ) ≤ f (x) ∀x ∈ S avec | x − x∗ |< ε
Définition 4. (Optimum global) Soit f une fonction à minimiser sur un ensemble S ⊆

Rn , x∗ est un minimum globale de f si
∃ε > 0 tel que f (x∗ ) < f (x) ∀x ∈ S avec | x − x∗ |< ε
Les maximums locaux et globaux sont définis de manière similaire.
Remarque 1. Dans le cas d’une fonction objectif convexe, il n’y a pas de distinction
entre minimum local et global : tout minimum local est également global.
Définition 5. Soit la fonction f (x1 , x2 , ..., xn ) continue et admet des dérivés partiels du
premier ordre sur Rn , le gradient de f (x1 , x2 , ..., xn ) est le vecteur suivant :
δf δf δf
∇f (x1 , x2 , ..., xn ) = ( , , ..., , )
x1 x2 xn
Définition 6. Soit la fonction f (x1 , x2 , ..., xn ) continue et admet des dérivés partiels de
deuxième ordre sur Rn , le Hessien de f (x1 , x2 , ..., xn ) est une matrice n × n d’éléments
δ2f
δxi δxj
On note le Hessien de la fonction f (x1 , x2 , ..., xn ) par ∇2 f (x1 , x2 , ..., xn ).
Exemple 2. Calculer le Hessien de la fonction suivante : f (x1 , x2 ) = x31 + 2x1 x2 + x22
6
Le Hessien est donné par la matrice suivante :
! !
δ2 f δ2 f
6x1 2
∇2 f (x1 , x2 ) = δx1 δx1
δ2 f
δx1 δx2
δ2 f =
δx2 δx1 δx2 δx2
2 2
Théorème 1. Soit S ⊂ Rn non vide et convexe et f : S ⊂ Rn → R continue et différen-

tiable sur S, f est convexe si et seulement si
f (y) ≥ f (x) + ∇t f (x)(y − x), ∀x, y ∈ S
de plus f est strictement convexe si et seulement si
f (y) > f (x) + ∇t f (x)(y − x), ∀x, y ∈ S, x 6= y
Théorème 2 (Critère du Sylvestre). .

Si la matrice M est symétrique, alors M est définie positif si et seulement si ses mineurs
principaux sont tous positifs (> 0) et il est semi-définie positif si et seulement si ses
mineurs principaux sont tous non négatifs ≥ 0. et M est définie négatif si et seulement si
ses mineurs principaux sont non nuls et le mineurs d’ordre k a le même signe que (−1)k ,
∀ k = 1, ..., n.
Théorème 3. Soit f (x1 , x2 , ..., xn ) une fonction continue et admet des dérivées partielles
du 2me degré pour tout point x ∈ S alors f (x1 , x2 , ..., xn ) est une fonction convexe sur S
si et seulement si sa matrice Hessien est semi-définie positif, De plus, f est strctement
convexe si et seulemnt si sa matrice Hessien est définie positif .
Théorème 4. Soit f (x1 , x2 , ..., xn ) une fonction continue et admet des dérivées partielles
du 2me degré pour tout point x ∈ S alors f (x1 , x2 , ..., xn ) est une fonction concave sur S
si et seulement si sa matrice Hessien est semi-définie négatif, De plus, f est strictement
concave si et seulement si sa matrice Hessien est définie négatif.
Théorème 5. Soit f (x) une fonction à une seule variable continue et admet des dérivées
partielles du 2me degré pour tout point x ∈ S alors f (x) est une fonction convexe sur S si
et seulement si f 00 (x) ≥ 0. De plus, f est strictement convexe si et seulement si f 00 (x) > 0
1.2.4 Qu’est-ce qu’un problème d’optimisation multiobjectifs

Un problème d’optimisation multiobjectif (multicritères) (M OP ) consiste à optimiser
(minimiser/maximiser) simultanément plusieurs fonctions objectifs f1 , f2 , ..., fp , p ≥ 2 sur
un domaine (ensemble) réalisable S appelé espace de décision définit par des inéquations
gj (x) ≤ 0,j = 1, 2, ..., m.
Mathématiquement, ce problème peut s’écrire comme suit :
(
” min ” (où) ” max ” (f1 (x), f2 (x), ..., fp (x))T , p ≥ 2
(M OP )
gj (x) ≤ 0, j = 1, 2, ..., m
Tel que
7
– x = (x1 , x2 , ..., xn )T est le vecteur de n variables de décision.
– On pose F (x) = (f1 (x), f2 (x), ..., fp (x))T est le vecteur de p fonctions objectifs à
optimiser.
Où
fi : Rn → R, i = 1, 2, ..., p
x → fi (x)
– Notons par S = {x ∈ Rn : gj (x) ≤ 0} l’ensemble de décision

Considérons l’application
F : S → Rp
x → F (x)
L’ensemble Z = F (S) s’appelle espace des critères où espace des objectifs.
La figure (Fig.1.3) montre l’espace de décision S avec 3 variables de décisions et l’espace
des objectif à 2 objectifs.
Figure 1.3 – Espace de décision et l’espace des objectifs
Remarque 2. .
1. Si toutes les fonctions fi , i = 1, 2, ..., p et gj , j = 1, 2, ..., m sont linéaires on parle

d’optimisation multiobjectifs linéaire qu’on note par (M OLP ).
2. Si l’une de ces fonctions n’est pas linéaire, dans ce cas nous parlerons d’optimisation
multiobjectifs non linéaire qu’on note par (M ON LP ).
3. Si une ou plusieurs variables de décision est discrète (entière), on parle d’optimisa-
tion multiobjectifs en nombres entiers et les fonctions fi , i = 1, 2, ..., p et gj , j =
1, 2, ..., m sont linéaires, on parle ainsi d’optimisation multiobjectifs linéaire en
nombres entiers qu’on note (M OILP )
8
1.2.5 Solution efficace et relation de dominance
A la fin du 19ème siècle, l’économiste Vilfredo Pareto formule le concept d’optima-
lité qui porte son nom (optimalité au sens de Pareto) , qui constitue les origines de la
recherche sur l’optimisation multiobjectifs où la notion d’optimalité dans l’optimisation
mono-objectif n’a aucun sens. En effet, elle n’existe aucune solution réalisable x qui fasse
diminuer un objectif sans augmenter dans le même temps au moins un autre objectif.
Cependant, dans la plupart des cas, l’optimum de Pareto n’est pas constitué d’une seule
solution mais d’un ensemble de solutions de ”meilleur compromis” appelées solutions effi-
caces ou solutions non-dominées.
Lorsque nous voulons résoudre un problème d’optimisation multiobjectifs, il s’agit de dé-
terminer un ensemble de solutions efficaces où l’ensemble optimale au sens de Pareto où
l’ensemble de solution non dominées.
Sans perte de généralités, considérons le problème d’optimisation multiobjectifs de type
minimisation qui s’écrit comme suit
(
” min ” F (x) = (f1 (x), f2 (x), ..., fp (x))T , p ≥ 2
(M OP )
gj (x) ≤ 0, j = 1, 2, ..., m
Définition 7 (Solution efficace). .
1. x̂ ∈ S est dite solution efficace ou optimale au sens de Pareto si et seulement

s’il n’existe pas une autre solution x ∈ S tel que fi (x) ≤ fi (x̂) ∀i = 1, 2, ..., p avec au
moins une inégalité stricte. Le vecteur critère ẑ = F x̂ est dit vecteur où solution
non dominé.
2. x̂ ∈ S est dite solution faiblement efficace ou faiblement optimale au sens
de Pareto si et seulement s’il n’existe pas une autre solution x ∈ S tel que fi (x) <
fi (x̂) ∀i = 1, 2, ..., p avec au moins une inégalité stricte. Le vecteur critère ẑ = F (x̂)
est dit vecteur où solution faiblement non dominé.
3. x̂ ∈ S est dite fortement efficace si et seulement s’il n’existe pas une autre solution
x ∈ S tels que x 6= x̂ et fi (x) ≤ fi (x̂) ∀i = 1, 2, ..., p. Le vecteur critère ẑ = F (x̂) est
dit fortement non dominé.
Définition 8 (Relation de dominance). .

Soient z1 , z2 ∈ Rp , on dit que le vecteur z1 domine le vecteur z2 si :
– Dominance faible :∃i, i = 1, 2, ..., p z1 (i) ≤ z2 (i) 2 , et
– Dominance forte ∃i, i = 1, 2, ..., p z1 (i) < z2 (i).
Pour mieux comprendre ce qu’est une relation de dominance, nous considérons l’exemple
suivant
2. Dans le maximisation cette relation devienne ≥
9
Exemple 3. Par exemple, pour le cas de maximisation, considérons les trois vecteurs
suivants :      
5 3 3
z1 = −2 ; z2 = −3 ; z3 = −2
     
1 −2 1
– Nous constatons que z1 domine fortement z2 et z1 domine faiblement z3 .

– Par contre, z3 domine faiblement z2 .
En effet, nous pouvons illustrer graphiquement la notion de dominance, soit l’exemple
suivant avec 5 points
Exemple 4. .
Point objectif f1 objectif f2

z1 8 5
z2 9 2
z3 12 1
z4 11 2
z5 16 2
Données de l’exemple 2
Figure 1.4 – Représentation graphique de l’exemple 2
(a) Si les deux fonctions f1 et f2 à minimiser, alors :
– Les points z1 , z2 et z3 ne sont pas dominés par n’importe quel autres points.
– z5 est dominé par z3 .
– z2 domine faiblement z4 et z5
(b) Si les deux fonctions f1 et f2 à maximiser, alors :
– Les points z1 et z5 ne sont pas dominés par n’importe quel autres points.
10
– z3 est dominé par z5 .
– z5 domine faiblement z4 et z2
Proposition 1. Les solution qui dominent les autres mais ne se dominent pas entre
elles sont appelées solutions non dominées où solutions optimales au sens de Pareto où
l’ensemble de solutions efficaces.
En d’autres termes, une x̂ ∈ S est dite efficace si son image par l’application ẑ = F (x̂)
n’est pas dominée par aucune autre solution.
Dans la suite de ce manuel, notons par XE l’ensemble de solutions efficaces et ZN D
l’ensemble de solutions non dominées ainsi que ZN D = F (XE ).
En effet, les solutions non dominées s’appelle parfois des actions non dominées. En
effet, dans l’exemple 4 le décideur (M D) serait en conflit à choisir entre les deux solutions
(action) z1 et z5 pour le cas de maximisation. Et en conflit à choisir entre les solutions
(actions) z1 , z2 et z3 .
Cependant, le choix d’une solution parmi les solutions non dominées trouvées constitue
une autre véritable problématique qu’on appelle théorie d’aide à la décision multicritère
où le but du décideur va être de modéliser ses choix ou plutôt ses préférences.
Pour modéliser ces choix, on pourra s’appuyer sur deux grandes théories :
1. la théorie de l’utilité multi-attribut ;
2. la théorie de l’aide à la décision.
Notons que ces deux théorie ne feront pas l’objet d’étude de ce présent manuel.
1.2.6 Front de Pareto

Par définition, le front de Pareto est l’ensemble généralement non convexe constitué
par l’image des solutions efficaces dans l’espace des critères . En effet, le front de Pareto
est l’ensemble ZN D = F (XE ) . La figure (Fig.1.5) montre le front de Pareto pour les
différentes situations envisageables pour un problème deux critères. Notons que, le front
de Pareto de chaque cas et la partie en gras de l’ensemble.
Remarque 3. . Considérons un problème multiobjectifs à p fonctions objectif fi , i =

1, 2, ..., p à optimiser sur l’ensemble S = {x ∈ Rn : gj (x) ≤ 0} . Si toutes les fonctions
fi , i = 1, 2, ..., p sont convexes et S est un ensemble convexe alors toutes solutions efficaces
locales et au globales.
1.2.7 Les points caractéristiques

Dans l’optimisation multiobjectif, le plus souvent le décideur raisonne plutôt en termes
d’évaluation où le choix d’une solution potentielle sur chaque critère et se place naturel-
lement dans l’espace des critères.
11
Figure 1.5 – Le front de Pareto
Nous présentons ici quelques points caractéristiques très utilisés dans l’optimisation mul-
tiobjectif notamment le point idéal, le point nadir,la matrice des gains.etc.
Définition 9 (Point idéal). .

Pour le cas de maximisation, le point idéal z ? = (z1? , z2? , ..., zp? ) est le vecteur qui maximise
chacune des fonctions objectifs fi
zi? = max{fi (x), x ∈ S, i = 1, ..., p}
De même manière analogue, le point idéal pour le cas de minimisation est le point
z = (z1? , z2? , ..., zp? ) est le vecteur qui minimise chacune des fonctions objectifs fi
?
zi? = min{fi (x), x ∈ S, i = 1, ..., p}
Le point idéal est généralement une solution utopique, dans le sens où il n’appartient pas
à l’espace objectif réalisable.
Dans certains cas, le décideur peut le définir comme un point de référence exprimant le
but qu’il veut atteindre pour chaque objectif. Le point idéal définit la borne supérieure
(cas de maximisation) où les points non dominés peuvent atteindre. il est souvent employé
comme points de référence dans la programmation du compromis ou dans des méthodes
interactives dont le but est de trouver une solution la plus préférée pour le décideur.
Définition 10 (Point anti-idéal). .

Pour le cas de maximisation, le point anti-idéal z = (z 1 , z 2 , ..., z p ) est le point qui minimise
chacune des fonctions objectifs fi i-e z i = min{fi (x), x ∈ S, i = 1, ..., p}
12
D’une manière similaire, pour le cas de minimisation le point anti-idéal z = (z 1 , z 2 , ..., z p )
est le point qui minimise chacune des fonctions objectifs fi i-e z i = max{fi (x), x ∈ S, i =
1, ..., p}
Définition 11 (Point nadir). . Le coordonnées du point nadir correspondent aux pires

valeurs obtenues par chaque fonction objectif sur l’ensemble de solutions efficaces.
Le point nadir définit la borne inférieure (cas de maximisation) où les points non
dominés peuvent atteindre.
Définition 12. (Matrice des gains) soit x̂j une solution optimale du critère fj . La matrice
des gains p × p est formée des éléments zji = fi (x̂j ) tels que
 
z1? . . . z1j . . . z1j
 .. .. . .. .
. .. . ..

 . 
 
G=
 zi1 . . . zi? . . . zik 

 .. . . . .. . . . .. 
 . . . 
zp1 . . . zkj . . . zp?
Les coordonnées du point idéal apparaissent sur la diagonale principale de cette matrice
et les coordonnées du point Nadir apparaissent sur la diagonale opposée. Lorsqu’un critère
j possède plusieurs solutions optimales, la colonne j de la matrice des gains dépendra de
la solution x̂j choisie (la matrice des gains est univoquement déterminée si, pour tous les
critères j, la solution x̂j est unique).
La figure (Fig. 1.6) illustre ces différents points caractéristiques dans l’espace des objectifs
sur un exemple de problème de maximisation bi-objectifs.
1.2.8 Exemple illustratif

Pour bien illustrer tous ces points, nous introduisons l’exemple suivant pour un cas de
maximisation :
Exemple 5. (Steuer, 1985)



 ” max ” f1 (x) = − 3x1 − x2


 ” max ” f2 (x) =x1 + 2x2



S.c 3x1 − x2 ≤ 6

x2 ≤ 3






 x1 , x2 ≥ 0
La figure (Fig.1.6)) montre l’ensemble réalisable S dans l’espace de décision et son

image Z dans l’espace des critères. Les points extrêmes de S et de Z sont numérotés.
13
Figure 1.6 – L’illustration graphique de l’exemple 5
Tout les points qui se trouvent sur le front de Pareto délimité par les points z 1 ,z 2 et z 3
sont des point non dominés. Tous les points situés à l’intérieur de ce front sont dominés.
Le point idéal est z ? = (0; 8) et la matrice des gains est
!
0 0
G=
−12 8
Le point Nadir est Z N D = (0; −12).
1.3 Caractérisation des solutions efficaces

Dans cette section, nous considérons le problème d’optimisation multiobjectif (M OP )
suivant (
” min ” F (x) = (f1 (x), f2 (x), ..., fp (x))T , p ≥ 2
(M OP ) (1.3.1)
x∈S
Généralement, l’ensemble des solutions efficaces XE d’un problème multiobjectif , qui
est une partie de l’ensemble des solutions réalisable S, soit très vaste et parfois infini,
il est souvent impossible d’énumérer toutes les solutions efficaces. La recherche d’une
solution efficace s’effectue par plusieurs techniques citons brièvement quelques une qui
sont fréquemment utilisées.
1.3.1 Technique de pondération des fonctions objectifs

Cette technique consiste à transformer le problème multiobjectif en un problème mono-
objectif en attribuant des coefficients (paramètres) de pondération notée λi à chaque fonc-
tion objectif fi . On obtient alors une problème d’optimisation à une seul fonction objectif
qu’on appelle problème paramétrique où fonction scalarisante . le vecteur des coefficients
14
de pondération λ = (λ1 , λ2 , ..., λp ) ∈ Rp décrit parfois l’importance où le poids de chaque
fonction objectif.
Fréquemment, les méthodes utilisant cette technique, le vecteur des coefficients de pon-
dération λ = (λ1 , λ2 , ..., λp ) ∈ Rp vérifie les relations suivantes :
1. ∀i = 1, 2, ..., p : λi ≥ 0.
p
X
2. λi = 1.
i=1
Le problème paramétrique (la fonction scalarisante) noté par (Pλ ) en question est
définis comme somme pondérée des p fonctions objectifs tel que :
p

 X
 min λi fi (x)
(Pλ ) i=1
(1.3.2)

x∈S

Comme remarque, si le problème multiobjectif (M OP ) 1.3.1 est linéaire et pour une cer-
taine valeur de vecteur λ le problème paramétrique 1.3.2 est aussi linéaire et sa résolution
peut se faire avec la méthode simplexe est sa solution optimale est toujours un point
extrême de l’ensemble réalisable.
Les théorèmes suivants nous montre les différents aspects théoriques pour caractériser une
solution efficace du problème (M OP ) 1.3.1 en utilisant le problème paramétrique (Pλ ).
Théorème 6. (Geoffrion ,1968) Soit x̂ ∈ S, x̂ est une solution efficace si et seulement si

x̂ ∈ S est une solution optimale du problème paramétrique (Pλ ) pour un certain λ ≥ 0.
Théorème 7. (Iserman ,1974)
(a) x̂ ∈ S une solution optimale du problème paramétrique (Pλ )

1. Si λ ≥ 0 alors x̂ est faiblement efficace.
2. Si λ > 0 alors x̂ est efficace.
3. Si λ ≥ 0 et x̂ est l’unique solution optimale de (Pλ ) alors x̂ est fortement
efficace.
(b) En autre, si S est convexe alors :
1. Si x̂ est efficace alors il existe λ > 0 tel que x̂ est une solution optimale de
(Pλ ).
2. Si x̂ est faiblement efficace alors il existe λ ≥ 0 tel que x̂ est une solution
optimale de (Pλ ).
Théorème 8. (Iserman ,1974) Une solution x̂ ∈ S est efficace si et seulement s’il existe
λ ∈ Rp , λ > 0 tel que
λF (x̂) ≥ λF (x) pour tout x ∈ S
15
1.3.2 Technique de test d’efficacité d’une solution
Cette technique s’applique pour tester l’efficacité d’une solution réalisable donnée. Elle
peut être utiliser pour générer une solution efficace initiale dans certaines méthodes in-
teractives. En effet, elle sert aussi à examiner l’existence de solutions efficaces.
Les premiers résultats spécifiques de cette technique ont été présenté pour la programma-
tion linéaire multiobjectifs (M OLP ) par Ecker and Kouada (1975). Elle a été généralisée
par Wendell and Lee (1977) pour le cas non linéaire.
Etant donnée le problème multiobjectifs

(M OP ) ≡ min F (x)
x∈S
et une solution réalisable x̂, la technique se base sur la résolution du problème mono-
objectif appelé problème auxiliaire suivant :
 p
 X
 min ϕ(x) = fi (x)


(Paux ) i=1 (1.3.3)


 fi (x) ≤ fi (x̂) pour tout i = 1, 2, ..., p
x∈S

ϕ(x) est la valeur de la fonction objectif du problème auxiliaire (Paux ).

Théorème 9. Soit x̂ ∈ S une solution réalisable, x̂ est efficace problème (M OP ) si et
seulement si x̂ est une solution optimale du problème (Paux ) 1.3.3 avec ϕ(x̂) = pi=1 fi (x̂)
P
Remarque 4. Maintenant, si le problème multiobjectif (M OP ) est de type maximisation

c’est-à-dire max F (x), problème auxiliaire suivant :
x∈S
 p
 X
 max ϕ(x) = fi (x)


(Paux ) i=1 (1.3.4)


 fi (x) ≥ fi (x̂) pour tout i = 1, 2, ..., p
x∈S

Ce test d’efficacité d’une solution réalisable donnée qui représente aussi l’examen
d’existence de solutions efficaces a été recombiné par le théorème de Benson (1978).
Théorème 10 (Benson,1978). Etant donné le problème multiobjectifs de type minimisa-
tion (M OP ) ≡ min F (x) tel que F (x) = [f1 (x), f2 (x), · · · fp (x)]T . Soit x̂ ∈ S une solution
x∈S
réalisable donnée, et considérons le problème mono-objectif suivant
 p
X
max γ = εi





 i=1
(Pε ) fi (x) + εi = fi (x̂) pour tout i = 1, 2, ..., p (1.3.5)

εi ≥ 0 pour tout i = 1, 2, ..., p




x∈S

16
Si on résout le problème (Pε ), les résultats suivants sont valides
1. x∗ est une solution efficace du problème (M OP ) si la valeur optimale de la fonction
objectif γ ∗ du problème 1.3.5 est nulle (γ ∗ = 0).
2. Si le problème 1.3.5 a une solution optimale finie et γ ∗ > 0 ou point x∗ alors x∗ est
efficace pour le problème (M OP ).
3. Pour une solution réalisable x∗ , si le problème(M OP ) est convexe et le problème (Pε )
n’a pas de solution finie (Non réalisable, non borné) alors l’ensemble de solutions
efficaces du(M OP ) et vide (XE = ∅).
Remarque 5. Si le problème multiobjectifs est de type maximisation c’est-à-dire (M OP ) ≡
max F (x) tel que F (x) = [f1 (x), f2 (x), · · · fp (x)]T le test d’efficacité de Benson devient
x∈S
comme suit  p
X
max γ = εi





 i=1
(Pε ) fi (x) − εi = fi (x̂) pour tout i = 1, 2, ..., p (1.3.6)

εi ≥ 0 pour tout i = 1, 2, ..., p




x∈S

1.3.3 Techniques utilisant les distances

C’est un ensemble de techniques dont le principe qui cherche à calculer des distance
absolue dr entre un point d’aspiration qui peut être fixé par le décideur, généralement on
prend le point idéal z ∗ .
Cette distance peut se calculer en utilisant des normes comme suit :
" p # r1
X
dr (F (x)) = |zi∗ − fi (x)|r , r ≥ 1
i=1
Pour r=1 la norme devient

p
" #
X
d1 (F (x)) = |zi∗ − fi (x)|
i=1
Pour r=2 # 21
p
"
X
d2 (F (x)) = |zi∗ − fi (x)|2 ,
i=1
Si r → ∞
d∞ (F (x)) = max (zi∗ − fi (x))
i=1,2,...,p
Pour cette dernière forme, la technique se transforme en la méthode dite ”min-max” de

Chebychev très utilisée pour caractériser les solutions efficaces non supportées dans le cas
d’optimisation linéaire multi-objectifs en nombres entiers Voir (Stueur and, Choo, 1983)
et (Ramdani et all, 2012).
17
1.4 Classification des méthodes de résolution
Selon Y.Collette and P. Siarry [5], Il existe un nombre important de méthodes et nous
avons classé celles-ci en cinq groupes :
1. les méthodes scalaires,
2. les méthodes interactives,
3. les méthodes floues,
4. les méthodes exploitant une métaheuristique,
5. les méthodes d’aide à la décision.
Les méthodes de ces cinq groupes peuvent aussi être rangées en trois familles de méthodes
d’optimisation multiobjectifs :
1. Les méthodes à préférence a priori : Dans ces méthodes, l’utilisateur définit le com-
promis qu’il désire réaliser (il fait part de ses préférences) avant de lancer la méthode
d’optimisation. On retrouve dans cette famille la plupart des méthodes par agréga-
tion (où les fonctions objectif sont fusionnées en une seule).
2. Les méthodes à préférence progressive : Dans ces méthodes, l’utilisateur affine son
choix de compromis au fur et à mesure du déroulement de l’optimisation. On re-
trouve dans cette famille les méthodes interactives.
3. Les méthodes à préférence a posteriori : Dans ces méthodes, l’utilisateur choisit une
solution de compromis en examinant toutes les solutions extraites par la méthode
d’optimisation. Les méthodes de cette famille fournissent, à la fin de l’optimisation,
une surface de compromis.
Il existe des méthodes d’optimisation multiobjectifs qui n’entrent pas exclusivement dans
une famille. Par exemple, on peut utiliser une méthode à préférence a priori en lui fournis-
sant des préférences choisies au hasard. Le résultat sera alors un grand nombre de solutions
qui seront présentées à l’utilisateur pour qu’il décide de la solution de compromis. Cette
combinaison forme alors une méthode à préférence a posteriori.
1.5 Série d’exercices

Exercice 1. Considérons le problème multiobjectif linéaire (M OLP )

 ” max ” f1 (x) = −3x1 + x2 ;





 ” max ” f2 (x) = x1 − 2x2
x1 + x2 ≤ 15





 2x + x ≥ 4
1 2
(M OLP )

 x1 − x2 ≤ 5

x1 ≤ 8




x2 ≤ 10





x1 , x2 ≥ 0.

18
1. Représenter graphiquement l’espace de décision S.
2. Représenter graphiquement l’espace des critère Y .
3. Calculer le point idéal, le point Anti-idéal,le point nadir et la matrice des gains.
4. Identifier le front de Pareto (Espace de compromis) ou bien l’ensemble non dominées
YN D et l’ensemble de solutions efficaces XE .
Exercice 2. Considérons le problème multiobjectif (M OP ) défini comme ci-dessus


 ” max ” f1 (x) = x1

(M OP ) ” max ” f2 (x) = x2

 x∈S
Tel que S est l’ensemble de décision défini par la figure (Fig.1.7)
Figure 1.7 – l’ensemble réalisable de l’exercice 2
1. Identifier le point idéal et le point Nadir.

2. Trouver l’ensemble de solution efficace XE et l’ensemble non dominé YN D .
3. Existe-elles des solutions faiblement efficaces/faiblement non dominées ?
4. Refaire toutes ces questions pour les cas suivants
  

 ” max ” f 1 (x) = x 1 
 ” min ” f 1 (x) = x 1  ” min ” f1 (x) = x1

(Cas 2) ” min ” f2 (x) = x2 (Cas 3) ” max ” f2 (x) = x2 (Cas 4) ” min ” f2 (x) = x2

 x∈S 
 x∈S 
 x∈S
19
Exercice 3. Soit le problème multiobjectif non linéaire (M OLP )



 ” max ” f1 (x) = −x1 + 3x2
” max ” f2 (x) = 3(x1 + x2 )





 ” max ” f3 (x) = x1 + 2x2


(M OLP ) x2 ≤ 4




 x1 + 2x2 ≤ 10
2x1 + x2 ≤ 10





 x ,x ≥ 0
1 2
1. Représenter l’espace de décision S.

2. Déterminer le point idéal et la matrice de gains.
3. Réécrire le théorème de Benson 1.3.5 pour le cas de maximisation puis utiliser le
logiciel LINGO pour tester l’efficacité de chaque point extrême de l’ensemble S.
4. Déduire l’ensemble de solutions efficace XE .
Exercice 4. Soit le (M OLP ) suivant




 ” max ” f1 (x) = x1
” max ” f2 (x) = x2





 ” max ” f3 (x) = −2x1 + x2


(M OLP ) x1 + x2 ≤ 8




 x1 − x2 ≤ 2
−7x1 + 3x2 ≤ 14





 x ≤4
1
1. Tracer le domaine de décision S

2. Réécrire le test d’efficacité Ecker and Kouada (1975) 1.3.3 pour ce (M OLP ).
3. Tester l’efficacité des points extrêmes puis déduire l’ensemble efficace XE . Existe-il
des solutions faiblement efficaces ?.
Exercice 5.
20
1.6 Corrigés des exercices
Corrigés de l’exercice 1
Considérons le problème multiobjectif linéaire (M OLP )


 ” max ” f1 (x) = −3x1 + x2 ;




 ” max ” f2 (x) = x1 − 2x2
x1 + x2 ≤ 15





 2x + x ≥ 4
1 2
(M OLP ) (1.6.1)

 x1 − x2 ≤ 5

x1 ≤ 8




x2 ≤ 10





x1 , x2 ≥ 0.

1. Représentation graphique de l’espace de décision S.
Figure 1.8 – L’espace de décision l’exercice 1
La figure (Fig.1.8) montre l’ensemble réalisable S dans l’espace de décision . L’en-

semble S est un polyèdre convexe délimité par les 7 points extrêmes a = (2; 0), b =
(0; 4), c = (0; 10), d = (5; 10), e = (8; 7); f = (8; 3), g = (5; 0).
2. Représentation graphique l’espace des critères Y .
La figure (Fig.1.9) montre l’ensemble réalisable Y dans l’espace des critères . L’en-
semble Y est un polyèdre convexe délimité par les 7 points extrêmes F (a) =
21
Figure 1.9 – L’espace des critères exercice 1
(−6; 2), F (b) = (4; 8), F (c) = (10; −20), F (d) = (−5; −15), F (e) = (−17; −6); F (f ) =
(−21; 2), F (g) = (−15; 5).
3. Calculer le point idéal, le point nadir, le point Anti-ideal et la matrice des gains.
Le point idéal est le point qui maximise les deux critères séparément . Il s’agit de
résoudre les deux programmes suivants :
 

 max f 1 (x) = −3x1 + x2 ; 
 max f2 (x) = x1 − 2x2
 
 x1 + x2 ≤ 15  x1 + x2 ≤ 15

 

 
 
 2x1 + x2 ≥ 4  2x1 + x2 ≥ 4

 

(P 1) x1 − x2 ≤ 5 (P 2) x1 − x2 ≤ 5
 



 x1 ≤ 8 


 x1 ≤ 8
x2 ≤ 10 x2 ≤ 10

 


 


 x , x ≥ 0. 
 x , x ≥ 0.
1 2 1 2
Graphiquement,La figure (Fig.1.8) montre que la solution de (P 1) est le point c =

(0; 10) et son image dans est F (c) = (10; −20). la solution de (P 2) est le point
g = (5; 0) et son image est F (g) = (−15; 5). En effet, le point idéal est le point
z ∗ = (10; 5). On voit clairement sur la figure (Fig.1.9), les coordonnées du point nadir
sont Z nad = (−15; −20. Dans ce cas de maximisation, le point anti-idéal est le point
qui minimise les deux fonctions objectifs, on obtient alors le point z∗ = (−21; −20).
La matrice des gains est
22
!
10 −15
M=
−20 5
4. Le front de Pareto ou (Espace de compromis) est la partie en rouge dans l’espace

des critères voir la la figure (Fig.1.9. Cette partie constitue l’ensemble de solutions
non dominées YN D . L’ensemble de solutions efficaces XE est la partie en rouge dans
l’espace de décision (Fig.1.8) .
Considérons le problème multiobjectif (M OP ) défini comme ci-dessus

 ” max ” f1 (x) = x1

(M OP ) ” max ” f2 (x) = x2

 x∈S
Tel que S est l’ensemble de décision défini par la figure (Fig.1.7)
Figure 1.10 – l’ensemble réalisable de l’exercice 2
1. Sur la figure (Fig.1.10 ), le point idéal et le point z ∗ = (13; 6) et le point Nadir et le

point Znd = (9; 2) et le point anti-idéal z∗ = (0; 1).
23
2. Comme f1 (x) = x1 et f2 (x) = x2 , l’ensemble de solution efficace XE et égale l’en-
semble non dominé YN D qui est donné par la partie en rouge de la figure (Fig.1.10
).
3. On voit sur la figure (Fig.1.10 ) le segment de deux points J = (7; 6) et A = (9; 6)
constitue l’ensemble de solutions faiblement efficaces qui sont aussi des solutions
faiblement non dominées.
4. Refaire toutes ces questions pour les cas suivants ;
(Cas 2)” max ” f1 (x) = x1 et ” min ” f2 (x) = x2 les solutions efficaces, le points idéal
et anti-idéal et le point nadir sont donné par le figure (fig.1.11) .
Figure 1.11 – Cas 2 ” max ” f1 (x) = x1 et ” min ” f2 (x) = x2 de l’exercice 2
(Cas 3)” min ” f1 (x) = x1 et ” max ” f2 (x) = x2

les solutions efficaces, le points idéal et anti-idéal et le point nadir sont donné par
le figure (fig.1.12) .
Cas 4)” min ” f1 (x) = x1 et ” min ” f2 (x) = x2 les solutions efficaces, le points idéal
et anti-idéal et le point nadir sont donné par le figure (fig.1.13) .
24
Figure 1.12 – Cas 3 ” min ” f1 (x) = x1 et ” max ” f2 (x) = x2 de l’exercice 2
Soit le problème multiobjectif linéaire à trois objectifs



 ” max ” f1 (x) = −x1 + 3x2
” max ” f2 (x) = 3(x1 + x2 )





 ” max ” f3 (x) = x1 + 2x2


(M OLP ) x2 ≤ 4




 x1 + 2x2 ≤ 10
2x1 + x2 ≤ 10





 x ,x ≥ 0
1 2
1. L’espace de décision S.
L’espace de décision S est montré dans la figure( Fig.1.14). S est un polyèdre
convexe délimité par les points extrêmes a = (0; 0), b = (0; 4); c = (2; 4); d =
(3.333; 3.333), e = (5; 0).
2. Calcule de point idéal et la matrice de gains.
Soit S = {x ∈ R2 , x2 ≤ 4, x1 + 2x2 ≤ 10, 2x1 + x2 ≤ 10, x1 , x2 ≥ 0}. Pour calculer, le
25
Figure 1.13 – Cas 4 ” min ” f1 (x) = x1 et ” min ” f2 (x) = x2 de l’exercice 2
point idéal il s’agit de résoudre graphiquement les programmes linéaires suivants :
(P 1) ≡ max f1 (x)
x∈S
(P 2) ≡ max f2 (x)
x∈S
(P 3) ≡ max f3 (x).
x∈S
La solution optimale de (P 1) est le point extrême b = (0; 4) et son image par F est le
point F (b) = (12; 12; 8) et celle de (P 2) est le point d = (3.333; 3.333) et son image
est F (d) = (6.666; 19.998; 9.996). La solution optimale de (P 3) n’est pas unique,
touts les points du segment de droite [c, d] sont optimale donc les coordonnées du
point idéal ne sont pas unique. Si on prend le point c = (2; 4) et son image F (c) =
[101810] on obtient alors le point idéal z ∗ = (12; 19.998; 10). En autre, si on prend
le point d = (3.333; 3.333) et son image est F (d) = (6.666; 19.998; 9.996) on obtient
le point idéal devient alorsz ∗ = (12; 19.998; 9.996).
La matrice des gains n’est pas aussi unique, si on prend c = (2; 4) la solution optimale
du (P 3), on obtient la matrice des gains suivante
 
12 12 8
M = 6.666 19.998 9.996
 
10 18 10
3. En utilisant LINGO, vérifier à l’aide du théorème de Benson 1.3.5 l’efficacité des

solutions réalisables suivantes.
xa = (0; 0), xb = (0; 4); xc = (2; 4); xd = (6; 2); xe = (5; 0)
26
Figure 1.14 – L’espace de décision S de l’exercice 3
Soit x∗ ∈ S une solution réalisable donnée, pour le cas de maximisation le test

d’efficacité de Benson 1.3.6 peut s’écrire comme suit
p

 X



 max γ = εi = ε1 + ε2 + ε3
i=1



 f1 (x) − ε1 = f1 (x̂)


(Pε ) f2 (x) − ε2 = f2 (x̂) (1.6.2)

f3 (x) − ε3 = f3 (x̂)




ε1 , ε2 , ε3 ≥ 0





x∈S

Utilisons maintenant le logiciel LINGO, pour tester l’efficacité du point xa = (0.0)

où nous allons résoudre le programme linéaire suivant :


 max γ = ε1 + ε2 + ε3
f1 (x) − ε1 = 0





 f (x) − ε = 0
2 2
(Pε )

 f3 (x) − ε3 = 0

ε1 , ε2 , ε3 ≥ 0




x∈S

Le tableau (Tab.1.1) nous donne les résultats obtenus par l’exécution de LINGO
pour chaque point. Remarquons que les points extrêmes b = (0; 4) , c = (2; 4) et
d = (3.333; 3.333) sont efficaces.
27
Table 1.1 – Test d’efficacité des points de l’exercice 3
le point x Son image F (x) La solution optimale de (Pε ) Efficacité

∗ ∗ ∗
a = (0.0) (0; 0; 0) ε = (10; 8; 10), γ = 38, x = (2; 4) Non
∗ ∗ ∗
b = (0; 4) (12; 12; 8) ε = (0; 0; 0), γ = 0, x = (0; 4) Oui
c = (2; 4) (10; 18; 10) ε∗ = (0; 0; 0), γ ∗ = 0, x∗ = (2; 4) Oui
∗ ∗ ∗
d = (3.333; 3.333) (6.666; 19.998; 9.996) ε = (0; 0; 0), γ = 0, x = (3.333; 3.333) Oui
∗ ∗ ∗
e = (5; 0) (−5; 15; 5) ε = (15; 3; 5), γ = 23, x = (2; 4) Non
En effet, si un point x̄ donné n’est pas efficace, notons par x∗ la solution optimale
donnée par le programme correspondant (Pε ) , d’après le théorème de Benson x∗ est
efficace et son image F (x∗ ) domine effectivement l’image F (x̄).
4. L’ensemble efficace XE de ce problème est la partie rouge de l’ensemble S donnée
dans la figure (Fig.1.14).
Soit le (M OLP ) suivant



 ” max ” f1 (x) = x1
” max ” f2 (x) = x2





 ” max ” f3 (x) = −2x1 + x2


(M OLP ) x1 + x2 ≤ 8




 x1 − x2 ≤ 2
−7x1 + 3x2 ≤ 14





 x ≤4
1
1. Tracer le domaine de décision S Le domaine réalisable dans l’espace de décision est

donné par figure (Fig.1.15). L’ensemble réalisable ici est le polyèdre convexe délimité
par les 4 points extrêmes a = (−5; −7), b = (1; 7), c = (4; 4), d = (4; 2).
2. Etant donné un point réalisable x∗ ,le test d’efficacité Ecker and Kouada (1975) 1.3.3
pour ce (M OLP ) se base sur la résolution du problème mono objectif dit problème
auxiliaire suivant :
p

 X
min ϕ(x) = fi (x) = x1 + x2 − 2x1 + x2 = −x1 + 2x2





 i=1

x1 ≥ f1 (x̂);

(Paux )


 x2 ≥ f2 (x̂);
−2x1 + x2 ≥ f3 (x̂);





 x ∈ S.
28
Figure 1.15 – L’espace de décision S de l’exercice 4
x F (x) Solution de (Paux )

a = (−5; −7) (−5; −7; 3) x∗ = (1; 7)
b = (1; 7) (1; 7; 5) x∗ = (1; 7)
c = (4; 4) (4; 4; −4) (x∗ = (4; 4)
d = (4; 2) (4; 2; −6) (x∗ = (4; 4)
Table 1.2 – Résultats de test de l’exercice (Ex.4)
Par exemple, pour le point a = (−5; −7), ce test d’efficacité s’écrit



 min ϕ(x) = −x1 + 2x2 ;

 x1 ≥ −5;


(Paux ) x2 ≥ −7;




 −2x1 + x2 ≥ 3
x∈S

3. Tester l’efficacité des points extrêmes puis déduire l’ensemble efficace XE Existe-il
des solutions faiblement efficaces.
La résolution graphique des problèmes auxiliaires correspondant aux points extrêmes
nous les résultats de tableau (Tab.1.2). D’après le théorème (Th.1.3.2), x∗ est une so-
lution optimale du problème auxiliaire (Paux ) 1.3.3 alors x∗ est efficace pour (M OP )
c’est à dire fi (x∗ ) ≤ fi (x̂) pour tout i = 1, 2, ..., p. En effet, le point a = (−5; −7)
n’est pas efficace. Les points b = (1; 7) et c = (4; 4) sont efficaces car ils sont opti-
maux pour les problèmes auxiliaires correspondant. Par contre ; le point d = (4; 2)
29
est faiblement efficace. L’ensemble efficace de ce (M OLP ) est la partie rouge de la
figure (fig.1.15). En effet, la segment ]c, d] est faiblement efficace.
30
CHAPITRE 2
Méthodes de scalaires
Dans ce chapitre, nous présenterons quelques méthodes appartenant à la famille de

méthodes scalaires qui permettent essentiellement de trouver une où plusieurs solutions
efficaces d’un problème multiobjctifs.
Sans perte de généralités, nous considérons le problème multiobjectifs de la forme sui-
vantes : 
T
 ” min ” F (x) = (f1 (x), f2 (x), ..., fp (x)) , p ≥ 2

(M OP ) x ∈ S; (2.0.1)
 x ∈ Rn .

Tel que S = {x ∈ Rn : gj (x) ≤ 0, j = 1, 2, ..., m} l’ensemble de décision et Y = F (S) est

l’espace des objectifs.
2.1 Méthode de pondération des fonctions objectif

L’idée principale de cette méthode revient à Gass and Saaty (1955) et Zadeh (1963).
Cette approche de la résolution d’un problème d’optimisation multiobjectif est la plus
évidente, Elle fait parti de la famille des méthodes scalaires ”Weighted Sum Scalarization
Method ” en anglais. D’ailleurs, on appelle aussi cette méthode l’approche naı̈ve de l’opti-
misation multiobjectif .
Le principe de cette méthode est de revenir à un problème d’optimisation mono-objectif
qui consiste à prendre chacune des fonctions objectif fi , i = 1, 2, ..., p, à leur appliquer un
coefficient de pondération λi , i = 1, 2, ..., p λi ≥ 0 pi=1 λi = 1 et à faire la somme des
P
fonctions objectif pondérées.

On obtient alors un nouveau problème d’optimisation à une seule fonction objectif de la
31
forme suivante.  p
 X



 min λi fi (x)

 i=1
(Pλ ) x ∈ S (2.1.1)

 p
 X
 avec λi ≥ 0, i = 1, 2, ..., p et λi = 1



i=1
Généralement, on appelle le vecteur λ ∈ Rp = (λ1 ; λ2 ; ...; λp ) vecteur de poids où vecteur

de paramètres et on appelle le problème mono-objectif (Pλ ) le problème paramétrique où
problème pondéré.
On peut représenter graphiquement le fonctionnement de la méthode sur un problème à
deux objectifs suivant : 
 ” min ” f1 (x)

(M OP ) ” min ” f2 (x)

 x∈S
Le problème paramétrique est le suivant :


 min ϕ = λ1 f1 (x) + λ2 f2 (x)

(Pλ ) x ∈ S (2.1.2)

 avec λ , λ ≥ 0, et λ + λ = 1
1 2 1 2
La fonction objectif du problème paramétrique notée par ϕ aura pour expression
ϕ = λ1 f1 (x) + λ2 f2 (x)
Ceci est l’expression d’une droite dans le plan f1 , f2 .

En effet, si l’on cherche à minimiser la fonction ϕ, on cherche en fait une constante C de
l’équation de droite suivante la plus petite possible :
λ1
f2 = − f1 + C
λ2
Sur la figure (Fig.2.1) l’ensemble Y correspond à l’ensemble réalisable dans l’espace des
objectif . La droite L est le tracé de la droite f2 = − λλ12 f1 + C pour certaine valeur de
λ1 et λ2 . Le point non dominé z ∗ est donné par l’intersection de la droite L et le front
de Pareto. En effet, z ∗ est la solution optimale du problème paramétrique (Pλ . Si l’on
répète ce processus pour plusieurs valeurs des coefficients de pondération λ, les différentes
solutions trouvées forment la surface de compromis.
Cette méthode n’est applicable qu’à des ensembles Y convexes. Dans le cas contraire, elle
ne permet pas de trouver la totalité de la surface de compromis. Par exemple, la portion
en trait gras de la surface de compromis de la figure (Fig.2.2) ne peut être obtenue par
cette méthode.
Théorème 11. Si la solution optimale de problème paramétrique (Pλ ) 2.1.1 est unique
alors elle est efficace pour le problème (M OP ) 2.0.1.
32
Figure 2.1 – Le principe de la méthode de pondération des fonctions objectif
Figure 2.2 – Une difficulté insurmontable pour la méthode de pondération des fonctions
objectif.
Démonstration. Ici on montre
x∗ ∈ S Optimale pour (Pλ )2.1.1 est unique ⇒ x∗ est efficace pour (M OP )2.0.1
Par contradiction, supposons que x∗ ∈ S l’unique solution optimale de (Pλ ) 2.1.1 pour un
certain vecteur de paramètres λ et x∗ n’est pas efficace pour le problème (M OP ) 2.0.1.
En effet, il existe une autre solution réalisable x ∈ S fi (x) ≤ fi (x∗ ) et il existe un certain j
p
X
tel que fj (x) ≤ fj (x∗ ). sachant que le vecteur λ et non négatif alors on aura λi fi (x) ≤
i=1
p p p
X X X
λi fi (x∗ ). Puisque, x∗ est optimale et unique alors λi fi (x∗ ) < λi fi (x) pour tout
i=1 i=1 i=1
x ∈ S. En effet, les deux inégalités sont contradictoires.
33
Théorème 12. La solution optimale de problème paramétrique (Pλ ) 2.1.1 est efficace
pour le problème (M OP ) 2.0.1 si ∀i, λi > 0, i = 1, 2, ..., p
Démonstration. Il s’agit de montrer l’implication suivante :
x∗ ∈ S (Optimale pour(Pλ )2.1.1 ∀i, λi > 0, i = 1, 2, ..., p ⇒ x∗ est efficace pour (M OP )2.0.1
Soit x∗ ∈ S une solution optimale pour (Pλ ) 2.1.1 pour un vecteur de paramètres λ où
∀i, λi > 0, i = 1, 2, ..., p. Supposons que x∗ n’est pas efficace pour le problème (M OP )
2.0.1 donc il existe une autre solution réalisable x ∈ S fi (x) ≤ fi (x∗ ) et il existe un certain
p p
X X
∗
j tel que fj (x) ≤ fj (x ). Puisque ∀i, λi > 0, i = 1, 2, ..., p alors λi fi (x) ≤ λi fi (x∗ )
i=1 i=1
qui est contradiction avec x∗ ∈ S une solution optimale pour (Pλ ).
Les deux théorèmes précédents (Th.11) et (Th.12) montre que la solution de la méthode
de pondération est toujours une solution efficace si le vecteur de poids λ est positifs
ou si la solution optimale (Pλ ) est unique sans imposer d’autres conditions.Cependant,
l’inconvénient de cette méthode ne peut pas en fait si le problème (M OP ) n’est pas
convexe de déterminer certaines solutions efficaces (Voir la figure (Fig.2.2)).
Théorème 13. Si le problème multiobjectif (M OP ) 2.0.1 est convexe et soit x∗ une

solution efficace du (M OP ) alors il existe un vecteur de poids λ = (λ1 ; λ2 ; ...; λp ) λi ≥ 0
p
X
et λi = 1 tel que x∗ est solution optimale du problème paramétrique (Pλ ) .
i=1
Démonstration. Voir livre de [3] page 94
Selon le théorème (Th.13), toute solution efficace d’un problème multiobjectif convexe
peut être déterminer à l’aide de la méthode des sommes pondérées. Notons que la valeur
du vecteur des poids λ n’est pas unique.
Pour deux critères, la figure (Fig.2.3) montre le sens de ce théorème. A gauche de la figure,
toute solution efficace du front en gras peut être obtenue par la résolution du problème
paramétrique par l’alternance du vecteur de poids λ. A droite, il n’est pas possible d’avoir
les solutions dans la partie non convexe du front pour n’importe quelle valeur de λ.
Abordons maintenant la cas de problèmes multiobjectif linéaires (M OLP ), pour deux
critères la fonction objectif du problème paramétrique s’écrit W (x) = λ1 f1 (x) + λ2 f2 (x).
En effet, la solution optimale du Pλ est toujours un point extrême.
Exemple 6. Pour mieux comprendre cette remarque, considérons l’exemple donné dans
l’article [4] 

 ” max ” f1 (x) = x1

 ” max ” f (x) = x
2 2
(M OLP )

 x1 + x2 ≤ 1

x1 , x2 ≥ 0

34
Figure 2.3 – La méthode de sommes pondérées et la convexité
Figure 2.4 – L’esapce de décision et l’esapce de critère de l’exemple 6
L’ensemble réalisable dans l’espace de décision S et son image dans l’espace des critères
Y sont illustrés dans la figure (Fig.2.4).
L’ensemble de solutions efficaces est le segment de droite [a, b] et le front de Pareto où
YN D est le segment de droite [A, B].
Pour λ = (1; 0) la solution efficace donnée par le problème paramétrique et le point b et
si λ = (0; 1) la solution est le point a. Si on prends λ = ( 12 ; 12 ) la solution efficace serait le
point a ou b(Multiplicité de solution).
35
2.1.1 Exemple pour la méthode de pondération
Exemple 7. Considérons l’exemple Binh [5] qui est un problème multiobjectif non linéaire
(M ON LP ) 
 ” min ” f1 (x) = x21 + x22


 ” min ” f (x) = (x − 5)2 + (x − 5)2
2 1 2
(M ON LP )

 −5 ≤ x1 ≤ 10

−5 ≤ x2 ≤ 10

On peut voir facilement que l’exemple de Binh est un problème quadratique convexe
car les deux fonctions objectif f1 et f2 sont des equations de cercles qui peuvent s’écrire se
forme quadratique strictement convexe et l’ensemble de décision S qui est un quadrant.
Utilisons un script qu’on peut écrire dans MATLAB pour tracer l’allure de domaine réa-
lisable dans l’espace des critères.
f1=[] ;
f2=[] ;
for i=-5 :0.2 :10 ;
for j=-5 :0.2 :10 ;
f 1 = [f 1; i.2 + j.2 ] ;
f 2 = [f 2; (i − 5).2 + (j − 5).2 ] ;
end
end
plot(f1,f2,’*’) ;
la fonction objectif du problème paramétrique (Pλ ) peut s’écrire comme suit
min ϕ = λ1 f1 (x) + λ2 f2 (x)

= λ1 x21 + x22 + λ2 (x1 − 5)2 + (x2 − 5)2

Avec λ1 , λ2 ≥ 0 et λ1 + λ2 = 1.
Si on pose λ1 = 1 − λ2 d’où 0 ≤ λ1 ≤ 1 alors la fonction objectif ϕ devient
ϕ = x21 + x22 − 10λ2 (x1 + x2 ) + 50λ2
On cherche maintenant l’optimum de cette nouvelle fonction objectif ϕ : Le gradient de

la fonction ϕ est le vecteur
δϕ δϕ
∇ϕ = ( ; )
δx1 δx2
= (2x1 − 10λ2 ; 2x2 − 10λ2 )
Le Hessien de la fonction ϕ est la matrice

!
2 0
∇2 ϕ =
0 2
36
Figure 2.5 – Espace de critère de l’exemple Binh
Comme on peut le vérifier facilement, le Hessien ϕ est une matrice définie positif alors
le minimum de la fonction ϕ est donné par la résolution du système :
( (
2x1 − 10λ2 = 0; x∗1 = 5λ2 ;
⇒
2x2 − 10λ2 = 0 x∗2 = 5λ2
Cependant, toutes les solutions efficaces de problème multiobjectif peuvent s’écrire
x = 5λ2 (1; 1) avec 0 ≤ λ2 ≤ 1
. Si on remplace x∗1 = 5λ2 , x∗2 = 5λ2 , on obtient alors les fonctions objectif suivantes :
ϕ = 50λ(1 − λ2 )
f1 = 50λ22
f2 = 50(1 − λ2 )2
On peut alors calculer quelques solutions du front de Pareto pour un certain nombre de
valeurs du coefficient λ2 . Ces résultats sont réunis dans le tableau (Tab2.6)
L’allure de front de Pareto est alors celle de la figure (Fig.2.7)
2.2 Méthode -contrainte

La méthode en question s’appelle aussi la méthode du compromis. Elle a été déve-
loppée par Haimes et al. (1971), et autres plusieurs aspects et discussions sont apportés
37
Figure 2.6 – Résultats pour quelques valeur de λ2 de la méthode pondérée
Figure 2.7 – Les points non dominés trouvé pour l’exemple (Ex.7)
par Chankong and Haimes (1983). Cette méthode consiste à transformer le problème
d’optimisation multiobjectif (M OP ) 2.0.1 en un problème d’optimisation mono-objectif
qu’on note par (P ) comportant quelques contraintes supplémentaires. Le principe de cette
méthode est
1. on choisit un objectif à optimiser prioritairement soit fk ;
2. on choisit un vecteur de contraintes initial i , i = 1, 2, ..., p, i 6= k, i ≥ 0 ;
3. on transforme le problème en conservant l’objectif prioritaire et en transformant les
autres objectifs en contraintes d’inégalité de type fi ≤ i , i = 1, 2, ..., p, i 6= k.
38
Mathématiquement, le problème d’optimisation mono-objectif (P ) qu’on appelle parfois
le problème − contraintes peut s’écrire comme suit :

 min fk (x)

(P ) fi (x) ≤ i , i = 1, 2, ..., p, i 6= k (2.2.1)

 x∈S
La résolution du problème d’optimisation mono-objectif − contraintes (P ) 2.2.1 peut

donner des solution efficace où des solutions faiblement efficaces pour le problème mul-
tiobjectif (M OP ) 2.0.1. Citons les théorèmes suivants :
Théorème 14. La solution optimale de problème − contraintes (P ) 2.2.1 est faiblement

efficace (M OP ) 2.0.1
Démonstration. Soit x∗ ∈ S une solution optimale pour le problème − contraintes

(P ) 2.2.1 et supposons que x∗ n’est pas faiblement efficace pour le problème (M OP )
2.0.1. Alors il existe une autre solution x ∈ S tel que fi (x) < fi (x∗ ) pour tout i =
1, 2, ..., p. Puisque x∗ une solution réalisable de problème − contraintes alors elle vérifie
les contraintes fj (x∗ ) ≤ j pour tout j = 1, 2, ..., p; j 6= k d’où fj (x) < fj (x∗ ) ≤ j avec
fk (x) < fk (x∗ ) ce qui contredit le faite x∗ est optimale pour le problème − contraintes
(P ) 2.2.1.
Théorème 15. Une solution réalisable x∗ ∈ S est efficace pour le problème (M OP )

2.0.1 si et seulement si elle est optimale pour le problème mono-objectif (P ) 2.2.1 avec
fi (x∗ ) = i , i = 1, 2, ..., p, i 6= k
Démonstration. Il s’agit de montrer l’équivalence suivante :

x∗ est efficace pour (M OP ) 2.0.1 ⇔ est optimale pour (P ) 2.2.1 avec fi (x∗ ) = i , i =
1, 2, ..., p, i 6= k.
” ⇒ ” Soit x∗ ∈ S une solution efficace pour le problème (M OP ) 2.0.1 et supposons que
x∗ n’est pas optimale pour le problème (P ) 2.2.1 pour un certain k avec fi (x∗ ) =
i , i = 1, 2, ..., p, i 6= k . Alors il existe une autre solution x ∈ S tel que fk (x) < fk (x∗ )
et fi (x) < fi (x∗ ) où i 6= k qui est contradictoire avec l’hypothèse x∗ est efficace pour
(M OP ) 2.0.1.
” ⇐ ” Directement, x∗ ∈ S une solution optimale pour le problème (P ) 2.2.1 pour un tout
k k = 1, 2, ..., p alors il n’existe pas d’autre solution x ∈ S tel que fk (x) < fk (x∗ ) et
fi (x) ≤ fi (x∗ ) avec i 6= k qui est la définition d’une solution efficace.
Notons qu’avec la condition nécessaire du théorème (Th.15) il est possible de trouver

n’importe quelle solution efficace du problème multiobjectif (M OP ) 2.0.1 sans se soucier
le la convexité du problème.
39
Théorème 16. Une solution réalisable x∗ ∈ S est efficace pour le problème (M OP ) 2.0.1
si elle est optimale et unique pour le problème mono-objectif (P ) 2.2.1 avec fi (x∗ ) = i , i =
1, 2, ..., p, i 6= k
Démonstration. Ici, il s’agit de montrer l’implication suivante :

x∗ solution optimale et unique pour (P ) 2.2.1 avec fi (x∗ ) = i , i = 1, 2, ..., p, i 6= k ⇒ x∗
est efficace pour le problème (M OP ) 2.0.1.
Soit x∗ ∈ S est l’unique solution optimale pour le problème (P ) 2.2.1 pour un certain k.
Supposons que x∗ n’est pas efficace pour le problème (M OP ) 2.0.1. En d’autres termes,
il existe une solution x0 dont f (x0 ) domine f (x∗ ) c’est-à-dire fi (x0 ) ≤ fi (x∗ ) pour tout
i = 1, 2, ..., p avec au moins une inégalité stricte fj (x0 ) < fj (x∗ ) . L’unicité de la solution
x∗ entraine ∀x ∈ S, fi (x) ≤ fi (x∗ ), i 6= k et fk (x) < fk (x∗ ) alors c’est contradictoire avec
les précédentes inégalités et l’hypothèse x∗ est efficace pour (M OP ) 2.0.1.
Théorème 17. L’unique solution optimale du problème mono-objectif (P ) 2.2.1 et efficace

pour problème (M OP ) 2.0.1 pour tout vecteur donné = (1 ; 2 ; ...; i−1 ; i+1 ; ...; p )
Démonstration. Par définition, soit x∗ solution optimale et unique pour le problème (P )

2.2.1 ceci implique fk (x∗ ) < fk (x) pour toute solution x ∈ S où fi (x∗ ) ≤ i pour tout
i = 1, 2, ..., p, i 6= k. Supposons maintenant, x∗ n’est pas efficace pour le problème (M OP )
2.0.1 alors il existe une autre solution x0 dont f (x0 ) domine f (x∗ ) c’est-à-dire fi (x0 ) ≤
fi (x∗ ) pour tout i = 1, 2, ..., p avec au moins une inégalité stricte j tel que fj (x0 ) < fj (x∗ ).
Deux cas sont possibles :
Cas 1 Si j = k alors fk (x0 ) < fk (x∗ ) et fi (x0 ) ≤ fi (x∗ ) ≤ i pour tout i 6= k qui est une
contradiction avec x∗ une solution optimale pour (P ) 2.2.1 .
Cas 2 Si j 6= k alors fj (x0 ) < fj (x∗ ) ≤ j et fi (x0 ) ≤ fi (x∗ ) ≤ i et fk (x0 ) < fk (x∗ ) pour
tout i 6= j i 6= ket qui est une contradiction avec x∗ une solution optimale unique
pour (P ) 2.2.1 .
Pour plus détailles sur ces démonstrations, nous référons le lecteur à voir le livre
K.Miettinen [3].
Pour des problèmes simples, le choix des valeurs de i peut donner une bonne répartition
des solutions sur le front de Pareto. En revanche, dans la plupart des cas concrets, le choix
(arbitraire) des valeurs de i ne permet pas d’obtenir une bonne répartition des solutions
sur le front de Pareto. Alors, on peut ne pas avoir assez de points et rencontrer de grandes
difficultés pour extrapoler l’allure de front de Pareto.
40
2.2.1 Exemple pour la méthode -contrainte
Exemple 8. Reprenons l’exemple Binh [5] qui est un problème multiobjectif non linéaire
(M ON LP ) 
 ” min ” f1 (x) = x21 + x22


 ” min ” f (x) = (x − 5)2 + (x − 5)2
2 1 2
(M ON LP )

 −5 ≤ x1 ≤ 10

−5 ≤ x2 ≤ 10

L’ensemble réalisable dans l’espace de décision est donné par la figure (Fig.2.8) Prenons
Figure 2.8 – Espace de décision de l’exemple 8
k = 2, le problème mono-objectif -contrainte devient



 min f2 (x) = (x1 − 5)2 + (x2 − 5)2

 x2 + x2 ≤
1 2
(P )

 −5 ≤ x1 ≤ 10

−5 ≤ x2 ≤ 10

On décide maintenant de résoudre ce problème en choisissons quelques valeurs de .

Pour une certaine valeur fixe de , ce problème appartient à une classe de problème
d’optimisation qu’on appelle problèmes quadratiques avec contraintes quadratiques ”qua-
dratically constrained linear/quadratic programming problems”, qui représente parfois des
énormes difficultés pour sa résolution.
Il n’est pas en question d’aborder les méthodes spécifiques de résolution de ce type de
problèmes.
41
En effet, on peut utiliser l’approche graphique pour trouver sa solution.
Figure 2.9 – Résolution graphique l’exemple 8
Comme on peut le constater, l’expression des fonction objectifs f1 et f2 sont respecti-

√ √
vement des équations de cercle de centre (0; 0) et (5; 5) et de rayon f1 et f2 .
Dans l’espace de décision, la figure (Fig.2.9) montre les solutions efficaces du problème
pour deux cas = 1 et = 16.
x∗ f1 (x∗ ) f2 (x∗ )
0 (0; 0) 0 50
1 (0.70; 0.70) 1 36.857
4 (1.414; 1.414) 4 25.715
5 (1.581; 1.581) 5 23.377
9 (2.1213; 2.1213) 9 16.573
16 (2.828; 2.828) 16 9.431
25 (3.535; 3.535) 25 4.289
36 (4.242; 4.242) 36 1.147
50 (5; 5) 50 0
60 5; 5) 50 0
Résultats avec la méthode -contrainte de l’exemple (Ex.8)
Le tableau (Tab.2.2.1) nous donne les résultats trouvés pour quelques valeurs de . D’après
les résultats trouvés, nous remarquons que l’allure du front de Pareto donné par la figure
(Fig.2.10) est presque la même trouvée par la méthode des sommes pondérées (Voir figure
42
Figure 2.10 – Les solutions non dominées de l’exemple (Ex.8)
(Fig.2.7)).
En effet, l’énoncé des théorèmes en particulier (Th.15) et (Th.17) sont évidement valable
dans toutes les valeurs de considérées c’est-à-dire dans le tableau (Tab.2.2.1) on voit que
f1 (x∗ ) = et la solution optimale du problème −contrainte est unique alors elle efficace
pour le problème de Binh.
Constatons que la valeur = 50 représente une borne supérieure pour l’objectif f1 =
x21 + x22 . Si on augmente d’avantage la solution efficace reste la même x∗ = (5; 5) et son
image le point non dominé est y ∗ = (0; 50).
2.3 Méthode hybride

Comme nous allons le voir, il est possible d’exploiter plusieurs méthodes pour en former
une nouvelle. Dans ce cas, nous obtenons une ”méthode hybride”.
La méthode hybride la plus connue qu’on va aborder ici est la méthode de Corley (1980)
et Wendell and Lee (1977). Cette méthode utilise la méthode de sommes pondérées des
fonctions objectif et la méthode de -contrainte.
Considérons le problème multiobjectif (MOP) 2.0.1, le problème mono-objectif hybride
qu’on note par (P ) peut s’écrire comme suit
 p
 X
 min λi fi (x)


(P ) i=1 (2.3.1)


 f i (x) ≤ i , i = 1, 2, ..., p.
x ∈ S.

Avec λ = (λ1 ; λ2 ; ...; λp ) le vecteur de poids et ∀i, λi ≥ 0, pi=1 λi = 1.

P
Un sous-ensemble de solution efficace XE du problème multiobjectif (MOP) 2.0.1 peut
43
être déterminer par la résolution du problème mono-objectif (P ) 2.3.1 pour différentes
valeurs de . Notons que les valeurs de peuvent être des bornes supérieures des objectifs
fi .
Théorème 18. La solution optimale x∗ de problème hybride (P ) 2.3.1 est une solution
efficace de problème multiobjectif (MOP) 2.0.1.En d’autre termes, si x∗ ∈ S est efficace
pour (MOP) 2.0.1 alors elle est optimale pour le problème hybride (P ) 2.3.1 pour i =
fi (x∗ ), i = 1, 2, ..., p.
Démonstration. Voir Corley (1980) ou Wendell and Lee (1977).
La figure (Fig.2.11) représente le fonctionnement de cette méthode pour un problème

à deux objectifs. On peut voir que l’ajout des deux contraintes (f1 (x) ≤ 1 ) et f2 (x) ≤
Figure 2.11 – Le fonctionnement de la méthode hybride
2 ) a permis de restreindre l’espace de recherche. Ensuite, on applique la méthode de

pondération des fonctions objectif sur cet espace restreint de recherche. Pour un vecteur
des poids λ = (λ1 , λ2 ) auquel on fait correspondre la droite L, chercher une valeur optimale
revient à faire tangenter la droite L avec l’espace restreint de recherche.
Cette méthode permet de combiner les avantages des deux méthodes citées précédemment
(la méthode de pondération des fonctions objectif et la méthode -contrainte). Elle est
ainsi efficace sur différents types de problèmes, qu’ils soient convexes ou non convexes.
Cependant, une difficulté survient : le nombre de paramètres à déterminer a été multiplié
par deux. Il sera beaucoup plus difficile à l’utilisateur d’exprimer sa préférence en jouant
sur l’ensemble des paramètres. Pour plus d’informations, voir le livre Miettinen [3].
44
2.4 Série d’exercices
Exercice 1
Considérons le problème multiobjectifs linéaire (M OLP )


 ” max ” f1 (x) = x1 ;




 ” max ” f2 (x) = x2
x1 + x2 ≤ 15





 2x + x ≥ 4
1 2
(M OLP )

 x1 − x2 ≤ 5

x1 ≤ 8




x2 ≤ 10





x1 , x2 ≥ 0.

1. Représenter graphiquement l’espace de décision S et l’espace des critères Y .

2. Soit le problème pondéré (Pλ ) ≡ max λf1 (x) + (1 − λ)f2 (x). En utilisons la méthode
x∈S
de pondération, trouver et discuter graphiquement les solutions efficaces selon les
valeurs de λ.
λ = 1 ;λ = 0 ;λ = 0.5 ; λ = 0.2 ;λ = 0.3 ;λ = 0.8
Exercice 2
Soit le problème multiobjectif non linéaire (M ON LP )


 ” min ” f1 (x) = x1 + x2 ;

 ” min ” f (x) = (x − 3)2 + (x − 3)2
2 1 2
(M ON LP )

 0 ≤ x 1 ≤ 3

0 ≤ x2 ≤ 3

1. En utilisant la méthode -Contraintes, trouver les solutions efficaces/non dominées

pour les différentes valeurs de 1 . 1 = 2; 1; 0.
2. Refaire la même question pour 2 =; 16; 9; 4; 2; 1.
3. Tracer l’allure du front de Pareto dans les deux cas.
45
2.5 Corrigés des exercices
Corrigé de l’exercice 1
Soit le problème multiobjectifs linéaire (M OLP )


 ” max ” f1 (x) = x1 ;




 ” max ” f2 (x) = x2
 x1 + x2 ≤ 15




 2x + x ≥ 4
1 2
(M OLP )
 x1 − x2 ≤ 5


x1 ≤ 8




x2 ≤ 10





x1 , x2 ≥ 0.

1. Représentation graphique de l’espace de décision S.
Figure 2.12 – L’espace de décision l’exercice 1 chapitre 2
La figure (Fig.2.12) montre l’ensemble réalisable S dans l’espace de décision est

lui même qui représente l’ensemble réalisable dans l’espace des critères Y S = Y
. L’ensemble S est un polyèdre convexe délimité par les 7 points extrêmes a =
(2; 0), b = (0; 4), c = (0; 10), d = (5; 10), e = (8; 7); f = (8; 3), g = (5; 0).
2. Soit le problème pondéré (Pλ ) ≡ max λf1 (x) + (1 − λ)f2 (x). Discutons les solutions
x∈S
efficaces selon les valeurs de λ. Le problème paramétrique (Pλ ) est linéaire et le
46
domaine de décision S est un polyèdre convexe alors sa solution optimale si elle
unique elle est en un point extrême de S.
(a) λ = 1 : le problème paramétrique correspondant est (Pλ ) ≡ max x1 . la solution
x∈S
optimale de problème paramétrique (Pλ ) n’est pas unique, tous les points qui se
trouve sur le segment ]e, f ] sont optimales. L’ensemble des solutions faiblement
efficaces est les segment ]e, f ], le point extrêmes e = (8; 7) est la seule solution
efficace du problème multiobjectifs (M OLP ).
(b) λ = 0 : la solution optimale de problème paramétrique (Pλ ) n’est pas unique,
tous les points qui se trouve sur le segment ]c, d] sont optimales. L’ensemble des
solutions faiblement efficaces est les segment [c, d[, le point extrêmes d = (5; 10)
est la seule solution efficace du problème multiobjectifs (M OLP ).
(c) λ = 0.5 : la solution optimale de problème paramétrique (Pλ ) n’est pas unique,
tous les points qui se trouve sur le segment [d, e] sont optimales. L’ensemble des
solutions efficaces du problème multiobjectifs (M OLP ) est les segment [d, e].
(d) λ = 0.2 : Le point extrême d = (5; 10) est la seule solution optimale du problème
paramétrique (Pλ ) d’après le théorème (Th. 11) cette solution est efficace pour
le problème multiobjectifs (M OLP ).
(e) λ = 0.3 : Le point extrême d = (5; 10) est la seule solution optimale du problème
(f) λ = 0.8 : Le point extrême e = (8; 7) est la seule solution optimale du problème
En résumé, sur la figure (Fig.2.12) les segments en couleur jaune représente les
solutions faiblement efficaces et celui en rouge nous donne les solution efficace du
problème multiobjectifs (M OLP ).
Corrigé de l’exercice 2
Soit le problème multiobjectif non linéaire (M ON LP )


 ” min ” f1 (x) = x1 + x2 ;

 ” min ” f (x) = (x − 3)2 + (x − 3)2
2 1 2
(M ON LP )

 0 ≤ x1 ≤ 3

0 ≤ x2 ≤ 3

1. En utilisant la méthode -Contraintes, trouver les solutions efficaces/non dominées

pour les différentes valeurs de 1 .
47
Le problème mono-objectif (P1 ) correspondant est


 min f2 (x) = (x1 − 3)2 + (x2 − 3)2

 x +x ≤
1 2
(P1 )

 0 ≤ x 1 ≤ 3

0 ≤ x2 ≤ 3

Le problème (P1 ) est un PNL quadratique qu’on peut résoudre facilement d’une
manière graphique. On peut le résoudre par une manière algébrique en utilisant las
conditions d’optimalités K.K.T.
(a) Cas 1 = 2 : Graphiquement, on peut voir facilement sur la figure (Fig.2.13) que
la solution optimale de (P1 ) est le point x∗ = (1; 1) et f1 (x∗ ) = 1 = 2, d’après
le théorème (Th. 15) cette solution est efficace pour le problème multiobjectifs
considéré, le point non dominé correspondant y = (2; 8).
Figure 2.13 – Résolution exercice 2 chapitre 2 cas = 2
(b) Cas 1 = 1 : De la même manière, la solution optimale de (P1 ) est le point

x∗ = (0.5; 0.5) et f1 (x∗ ) = 1 = 1, d’après le théorème (Th. 15) cette solution
est efficace pour le problème multiobjectifs considéré, le point non dominé
correspondant y = (1; 12.53).
(c) Cas 1 = 0 : Dans ce cas S = 0, la solution optimale de (P1 ) est le point
x∗ = (0; 0) et f1 (x∗ ) = 1 = 1, d’après le théorème (Th. 15) cette solution
est efficace pour le problème multiobjectifs considéré, le point non dominé
correspondant y = (0; 18).
2. Refaire la même question pour 2 =; 16; 9; 4; 2; 1.
3. Tracer l’allure du front de Pareto dans les cas.
48
Bibliographie
[1] M.J. Alves C.H.Antunes and J. Climaco. Multiobjective Linear and Integer Program-
ming. Springer International Publishing Switzerland, 2016.
[2] M. Ehrgott. Multicriteria Optimzation. Springer Berlin-Heidelberg, second edition,
2005.
[3] K.Miettinen. Nonlinear multiobjective optimzation. Kluwer acaddemic publisher, 1999.
[4] V.Morovati and L.Pourkarimi. Extension of zoutendijk method for solving constrained
multiobjective optimization problems. European Journal of Operational Research,
(2018).
[5] Y.Collette and P. Siarry. Optimsation multiobjectif. Editions Eyrolles, 2005.
49

Cours MOP 2019

Transféré par

Droits d'auteur :

Formats disponibles

Cours MOP 2019

Transféré par

Informations du document

Description originale:

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours MOP 2019

Transféré par

Droits d'auteur :

Formats disponibles

Université Mohamed Elbachir Elibrahimi de B.B.

Par : RAMDANI Zoubir

1 Introduction et concepts de base 2

Introduction et concepts de base

Contrairement en optimisation classique mono-objectif, où il s’agit de chercher une

1.2 Notions fondamentales

Notons par S = {V W Golf, OpelAstra, F ord F ocus, T oyota Corolla} l’ensemble

1.2.2 Ensemble et fonction convexe

∀x, y ∈ S : λx + (1 − λ)y ∈ S ∀λ ∈ [0, 1]

La Figure (1.2) illustre cette notion.

Définition 2. (Fonction convexe)

∀x, y ∈ S : f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (z) ∀λ ∈ [0, 1]

– f est strictement convexe si cette inégalité est stricte.

1.2.3 Optimum local et global

∃ε > 0 tel que f (x∗ ) ≤ f (x) ∀x ∈ S avec | x − x∗ |< ε

Définition 4. (Optimum global) Soit f une fonction à minimiser sur un ensemble S ⊆

∃ε > 0 tel que f (x∗ ) < f (x) ∀x ∈ S avec | x − x∗ |< ε

Les maximums locaux et globaux sont définis de manière similaire.

On note le Hessien de la fonction f (x1 , x2 , ..., xn ) par ∇2 f (x1 , x2 , ..., xn ).

Exemple 2. Calculer le Hessien de la fonction suivante : f (x1 , x2 ) = x31 + 2x1 x2 + x22

Théorème 1. Soit S ⊂ Rn non vide et convexe et f : S ⊂ Rn → R continue et différen-

f (y) ≥ f (x) + ∇t f (x)(y − x), ∀x, y ∈ S

de plus f est strictement convexe si et seulement si

f (y) > f (x) + ∇t f (x)(y − x), ∀x, y ∈ S, x 6= y

Théorème 2 (Critère du Sylvestre). .

1.2.4 Qu’est-ce qu’un problème d’optimisation multiobjectifs

– Notons par S = {x ∈ Rn : gj (x) ≤ 0} l’ensemble de décision

Figure 1.3 – Espace de décision et l’espace des objectifs

1. Si toutes les fonctions fi , i = 1, 2, ..., p et gj , j = 1, 2, ..., m sont linéaires on parle

Définition 7 (Solution efficace). .

1. x̂ ∈ S est dite solution efficace ou optimale au sens de Pareto si et seulement

Définition 8 (Relation de dominance). .

– Nous constatons que z1 domine fortement z2 et z1 domine faiblement z3 .

Point objectif f1 objectif f2

Figure 1.4 – Représentation graphique de l’exemple 2

(a) Si les deux fonctions f1 et f2 à minimiser, alors :

1.2.6 Front de Pareto

Remarque 3. . Considérons un problème multiobjectifs à p fonctions objectif fi , i =

1.2.7 Les points caractéristiques

Définition 9 (Point idéal). .

zi? = max{fi (x), x ∈ S, i = 1, ..., p}

zi? = min{fi (x), x ∈ S, i = 1, ..., p}

Définition 10 (Point anti-idéal). .

Définition 11 (Point nadir). . Le coordonnées du point nadir correspondent aux pires

1.2.8 Exemple illustratif

Exemple 5. (Steuer, 1985)

La figure (Fig.1.6)) montre l’ensemble réalisable S dans l’espace de décision et son

Le point Nadir est Z N D = (0; −12).

1.3 Caractérisation des solutions efficaces

1.3.1 Technique de pondération des fonctions objectifs

Théorème 6. (Geoffrion ,1968) Soit x̂ ∈ S, x̂ est une solution efficace si et seulement si

Théorème 7. (Iserman ,1974)

(a) x̂ ∈ S une solution optimale du problème paramétrique (Pλ )

Etant donnée le problème multiobjectifs

ϕ(x) est la valeur de la fonction objectif du problème auxiliaire (Paux ).

Remarque 4. Maintenant, si le problème multiobjectif (M OP ) est de type maximisation

1.3.3 Techniques utilisant les distances

Pour r=1 la norme devient

2.2 Méthode -contrainte

La résolution du problème d’optimisation mono-objectif − contraintes (P ) 2.2.1 peut

Théorème 14. La solution optimale de problème − contraintes (P ) 2.2.1 est faiblement

Démonstration. Soit x∗ ∈ S une solution optimale pour le problème − contraintes

k = 2, le problème mono-objectif -contrainte devient

On décide maintenant de résoudre ce problème en choisissons quelques valeurs de .