Multicritere Sup Aero

0
0-0
Décision multicritères
Hélène Fargier, Michel Lemaître

d’après beaucoup d’autres ...
fargier@irit.fr
Cours Optimisation, Partie "Décision Multicritère", 3ième Année Sup Aéro (SID)
1
2
1. Introduction
SupAéro Décision Multi critères 1. I NTRODUCTION

3
Quelques problèmes de décision et

d’évaluation
• Choisir le site d’implantation d’une usine, d’un magasin ...
• Engager du personnel.
• Acheter du matériel.
• Évaluer la qualité des fournisseurs.
• Évaluer des projets.
• Choisir une stratégie d’investissement.

4
Modèle unicritère
• Modèle unicritère : Optimiser {g(a), a ∈ A} où g : A 7→ R
• Mathématiquement bien posé :

– Notion de solution optimale;
– Classement complet des actions;
• Économiquement mal posé :

– Un seul critère ?
– seuils de perception, ...
– Exigence de critères numériques

5
Choix d’une automobile

alternatives
Citroen Peugeot Renault Ford
prix (×1000 ∈) 22 20 21 16
critères consommation 7.1 7.0 7.2 7.8
puissance (kW) 55 65 58 55
type essence gpl gpl diesel
• le nombre fini critères

• le nombre fini d’alternatives
• aucune ne s’impose a priori (n’est meilleure sur tous les
critères)
6
Exemple : choix d’un candidat
alternatives
Durant Dupont Dubois Dubosc
prétentions 53 50 53 45
critères âge 31 25 32 38
expérience 7 2 7 15
compétences moyennes top top forte

7
Modèle multicritère
• Modèle multicritère : Optimiser

{g1 (a), g2 (a) . . . gn (a), a ∈ A} où gi : A 7→ R
Comment optimiser sur **plusieurs** fonctions ?
Les critères sont
• Souvent contradictoires (puissance et prix)
• Exprimés dans des unités différentes ((puissance et prix)
• Difficiles à mesurer quantitativement (type moteur): les

critères qualitatifs ordonnent plutôt que n’évaluent

8
Démarche générale en
décision/optimisation multicritère
• définir l’ensemble des alternatives possibles (les objets sur

lesquels portent la décision : candidats, ordonnancements,
plans), et leurs attributs
• définir les différents points de vue sur lesquels on jugera les

alternatives, établir des préférences sur ces points de vue, les
traduire en critères (de manière ordinale ou cardinale)

9
Attributs et critères
• Attribut: Caractéristique décrivant chaque objet
(âge, diplôme, résultats aux tests d’aptitude, prétentions)
• Critère : exprime les préférences du décideur relativement

à un point de vue (ex: compétence);
Intègre la structure de préférence du décideur sur ce critère
(minimiser les prétentions, maximiser la compétence)
Tableau des attributs 7→ Tableau des performances
• Généralement (et pour la suite) : attribut critère

10
Démarche générale en
décision/optimisation multicritère - cont
• définir l’ensemble des alternatives possibles (les objets sur

lesquels portent la décision : candidats, ordonnancements,
plans), et leurs attributs
• définir les différents points de vue sur lesquels on jugera les
alternatives, établir des préférences sur ces points de vue, les
traduire en critères (de manière ordinale ou cardinale)
• synthétiser une structure de préférence globale sur les alt.
• exploiter cette structure de préférence globale pour décider
(algorithmes, calculs)
11
Problématiques d’aide à la décision MCDM

Données: un ensemble d’alternatives, évaluées ou classées par
des critères
Problèmes:
• Sélection : Choix d’une solution (la meilleure) ou d’un

ensemble de (meilleures) solutions
• Affectation : Tri résultant de l’affectation de chaque

alternative à une catégorie parmi n (préféfinies)
• Classement : ordonner l’ensemble des alternatives

12
Plan
• Introduction
• Principes de base pour la modélisation des préférences
• Agréger puis comparer : les principales approches par

fonction d’agrégation
• Comparer puis agréger : les méthodes de surclassement
• Conclusion

13
Exercice 1
alternatives
prix (×1000 ∈) 22 20 21 16
Avec gpl > essence, diesel; minimiser prix et consommation,
maximiser performance
Quelles sont les meilleures solutions ? Que dire si on ne tient compte
que des critères prix et consommation ?
Représenter les alternatives dans l’espace de ces deux critères.

14
Exercice 2

15
2. Principes de base
SupAéro Décision Multi critères 2.P RINCIPES BE BASE

16
2.1 Modélisation des préférences
Dans un problème multicritère, on distingue:

1. Les préférences locales, exprimées par les critères
2. La préférence globale du décideur sur l’ensemble des
alternatives
En général, les préférence locales forment la donnée du
problème,
et on cherche à synthétiser la préférence globale.
Les deux niveaux utilisent les mêmes modèles pour exprimer
les préférences. Attention à ne pas les confondre.
17
Le modèle relationnel
Ce modèle décrit explicitement toutes les comparaisons deux à
deux entre alternatives.
On représente les préférences par une relation sur A: a b
signifiant que a est préféré au sens large à b.
Hypothèse minimale : est doit être réflexive (a est toujours
au moins aussi bon que a).
Le problème de classement: synthétiser un g global à partir

des critères, cad de préférences locales i , i = 1, n.

18
Préférence stricte, indifférence et incomparabilité
définit 3 relations exclusives sur A :
la préférence stricte, notée : ab ⇔ a b ∧ ¬(b a)

l’indifférence, notée ∼ : a∼b ⇔ ab∧ba
l’incomparabilité, notée : a b< ⇔ ¬(a b) ∧ ¬(b a)

19
Préférence stricte, indifférence et incomparabilité

(cont.)
Pour tout a et b ∈ A
• est asymétrique : a b implique non b a
• est irréflexive : non a a
• ∼ est réflexive : a ∼ a
• ∼ est symétrique : a ∼ b implique b ∼ a
• est symétrique : a b implique b a

20
Transitivité
Définition [(Quasi) Transitivité] Une relation R est transitive

⇐⇒def aRb et bRc implique aRc.
Une relation est quasi-transitive ⇐⇒def sa partie stricte est
transitive.
• Les relations d’indifférence ∼ (et donc les relations ) ne

sont pas toujours transitives
• Les relations de préférence stricte sont généralement
transitives
Exercice 3 Par exemple dans la vie courante ?

21
Critères à seuil ou "quasi critères"
Un quasi critère se défini partir d’un attribut g numérique
A maximiser : a b ⇐⇒ g(a) + q ≥ g(b) avec q > 0
i.e. a b ⇐⇒ g(a) > g(b) + q,

a ∼ b ⇐⇒ |g(a) − g(b)| ≤ q
Attribut à minimiser: a b ⇐⇒ g(a) − q ≤ g(b)

(i.e. a b quand g(b) − q > g(a))
Ex: pour l’achat voiture, le critère consommation ne fait une
différence qu’à plus de 0.1 litre aux 100.

22
Quasi critères (cont.)
La relation d’indifférence n’est pas transitive en général

Peugeot (7 l) ∼conso Citroen (7.1 l) car 7.1 − 7 ≤ 0.1
Citroen (7.1 l) ∼conso Renault (7.2 l ) car 7.2 − 7.1 ≤ 0.1
Mais Peugeot conso Renault (car 7.2 − 7.0 > 0.1)
La relation de préférence stricte obtenue par un critère à seuil
est toujours transitive.

23
Vote à la majorité
C’est une règle pour synthétiser la préférence globale à partir
des préférences locales ("règle de décision")
a M aj b ⇐⇒ |{i, a i b}| ≥ |{i, b i a}|
Votant 1: a 1 b 1 c
Exemple: Votant 2: c 2 a 2 b
Votant 3: b 3 c 3 a
|{1, 2}| > |{3}| : a M aj b,
|{1, 3}| > |{2}| : b M aj c,
mais |{2, 3}| > |{1}| : c M aj a

24
Complétude
Définition [relation complète)] Une relation est complète

⇐⇒def a b ou b a pour tout a et b.
est complète ⇐⇒ est vide.
Un critère à seuil définit une préférence locale complète
Le vote à la majorité définit une préférence globale complète

25
La règle d’unanimité
Une règle de décision a minima : a U na b ⇐⇒ ∀i, a i b

prix (×1000 ∈) 22 20 21 16
Peugeot U na Citroen; Peugeot U na Renault.
Ford et Peugeot sont incomparables; Citroen et Renault le sont
aussi.
26
Le modèle ordinal : le préordre complet
Définition [préordre] Un préordre est une relation binaire

réflexive et transitive.
Exercice 4 Montrer que la relation de préférence à l’unanimité est

un préordre (partiel)
Exercice 5 Montrer que si est un préordre, ∼ est une relation

d’équivalence (réflexive, symétrique, transitive) et une relation
d’ordre (antisymétrique, transitive)

27
Le modèle ordinal : le préordre complet (cont.)
Un préordre défini donc un ordre sur les classes d’équivalence

des ex-æquo possibles.
Un préordre complet définit un ordre total sur les classes
d’équivalence (on peut ranger).
Modèle ordinal ←→ préordre complet sur les alternatives
Un critère ordinal peut être représenté par une fonction
g:A→ N

28
Le modèle cardinal
Définition [critère numérique cardinal] Un critère cardinal est

une fonction g : A → R
Par rapport au modèle ordinal (qui peut aussi être représenté
numériquement), le modèle cardinal permet d’exploiter des
«différences d’intensités» entre préférences. On suppose une
information riche.
Un critère cardinal induit une relation de préférence ordinale:
a b ⇐⇒ g(a) ≥ g(b) (si maximisation)
Exercice 6 Le prouver.

29
Représentation des préférences: en bref

Trois principaux modèles pour exprimer des préférences :
• le modèle relationnel
– modèles acceptant l’incomparabilité : Pareto
dominance, surclassement
– modèles acceptant l’intransitivité: quasicritères,
décision à la majorité
• le modèle ordinal = modèle relationnel + complétude +

transitivité
• le modèle cardinal = information ordinale + intensités

cardinales

30
Représentation des préférences: en bref (cont.)
Autres modèles:
• modèles incluant l’incertitude, l’imprécision, le risque
• modèles logiques, logique pondérée, distances ...
• ...
Dans la suite: les critères seront supposés au moins ordinaux

31
On fait l’hypothèse simplificatrice que les préférences sont locales

représentées par des critères numériques, ordinaux ou
cardinaux, (à maximiser, par convention)
gi : A 7→ R, i = 1, n
Problème de classement: synthétiser la préférence globale du

décideur (g ) qui en découle.
Problème de sélection: sélectionner une alternative préférée au
sens de g .

32
Hypothèse simplificatrice (cont)

Puisque les préférences locales sont des critères numériques
gi : A 7→ Ri ⊆ R, i = 1, n ...
... à tout a correspond un vecteur hg1 (a), g2 (a), . . . gn (a)i des

valeurs de a sur les critères, qu’on appelle profil de a.
On le note par convention a = ha1 , a2 , . . . , an i, avec ai = gi (a)
... on peut passer de l’espace des alternatives à l’espace des

profils: on travaille maintenant sur A = R1 × · · · × Rn

33
2.2 Quelques principes de base pour une règle de

décision
Le principe d’universalité: pour toute paire a, b ∈ A, on doit
pouvoir décider si a g b ou non.
Le principe d’unanimité: si a est au moins aussi bon que b sur
tous les critères, alors il faut que a g b
Le principe d’efficacité: a est au moins aussi bon que b sur tous
les critères et meilleur sur certaines (a "domine" b), alors il faut
que a g b
Le principe d’indépendance préférentielle (ou "séparabilité"): la
préférence entre a et b ne dépend pas des critères sur lesquels
a et b reçoivent la même évaluation.

34
Pareto-unanimité
Pareto : économiste, première référence historique à la décision
multicritère (1896).
Définition [dominance faible]
a domine faiblement b ⇐⇒def ∀i, ai ≥ bi
Définition [Principe d’unanimité] g satisfait le principe

d’unanimité si et seulement si, si a domine faiblement b alors
a g b.

35
Pareto-optimalité et efficacité
Définition [dominance (forte)]
a domine b ⇐⇒def ∀i, ai ≥ bi et ∃i, a >i b
Définition [Principe d’efficacité] : g satisfait le principe
d’efficacité si et seulement si, si a domine b alors a g b.
Définition [Pareto-optimalité] Une alternative a est dite

Pareto-optimale si elle n’est dominée par aucune autre.
Une alternative Pareto-optimale ne peut être améliorée au regard d’un
critère sans la détériorer pour un autre.
Sélection: rechercher uniquement des Pareto optimales

36
g1
g (a)
alternatives dominées
par g(a)
(y compris la frontière, sauf le coin)
g2

37
g1
Pareto optimale
dominées
g2
38
Principe d’indépendance préférentielle mutuelle

(ou "séparabilité")
Assure que les décisions sont cohérentes "toutes choses égales
par ailleurs"
Définition [] g satisfait le principe de séparabilité ssi, quel que

soit I ⊆ X, quels que soient a, b, c, d ∈ Rn :
aIc g bIc ⇐⇒ aId g bId
où xIy désigne le profil t tel que ti = xi si i ∈ I, ti = yi sinon.
Informellement, la préférence globale entre deux alternatives

ne dépend pas des critères qui ne les départagent pas.

39
Exemple du téléviseur [Vincke]
a b c d
- prix -1000 -800 -1000 -800
critères image 5 4 5 4
son 5 5 3 3
SAV 4 4 5 5
Le principe de séparabilité dit que, si le décideur préfère a à b,

alors il préfère c à d (et réciproquement)
Si le décideur peut toujours se décider entre 2 alternatives qui ne diffèrent
que sur prix et image, on dit que {prix, image} est (préférentiellement)
indépendant dans {prix, image, SAV, son}

40
Autres propriétés
(Quasi) Transitivité de g
Capacité à prendre en compte l’importance des critères
Robustesse à des variations (ordinalement neutres) des
évaluations
Mise en évidence des conflits = Classement complet des
alternatives

41
Exercices
Exercice 7 Montrer que :
• est asymétrique : a b implique non b a
• ∼ est réflexive : a ∼ a
• ∼ est symétrique : a ∼ b implique b ∼ a
• est symétrique : a b implique b a

42
Exercice 8 On définit généralement , ∼, depuis :

a b ⇐⇒ a b et non b a
a ∼ b ⇐⇒ a b et b a
a b ⇐⇒ non a b et non b a
On pourrait inversement partir de deux relations exclusives

(asymétrique) et ∼ (réflexive, symétrique) et poser:
a b ⇐⇒def a b ou a ∼ b
Montrer que définie à partir de et ∼ est réflexive.

43
Exercice 9 Montrer que toute relation de préférence globale qui est

transitive, séparable et satisfait le principe de projection des échelles:
∀a, b, c, ∀h, ∀i : ai i bi ⇐⇒ ai {i}h bi {i}h
satisfait aussi le principe d’efficacité

44
3. Agrégation multi critère
SupAéro Décision Multi critères 3. A GRÉGATION MULTI CRITÈRE

45
3.1 Introduction
Types d’approches
• Agréger puis comparer: calculer une note globale pour

chaque alternative, puis préférer celle qui obtient la
meilleure (ce chapitre)
• Comparaison par paires: établir la préférence entre deux

alternatives en fonction des degrés de surclassement
obtenus sur chaque critère (chapitre suivant)

46
Principe de base
La relation de préférence globale est donnée par un critère

cardinal global h : A → R obtenu par agrégation des critères
numériques par une fonction d’agrégation f : Rn → R.
Le critère cardinal global est défini par
h(a) = f (a1 , . . . , an ).
"Agréger puis comparer" : a g b ⇐⇒ h(a) ≥ h(b)

47
Propriétés des approches par fonction d’agrégation
a g b ⇐⇒ f (a1 , . . . , an ) ≥ f (b1 , . . . , bn )
La relation de préférence globale est forcément un préordre

total.
Le principe d’unanimité exige que f soit monotone croissante.
Le principe d’efficacité exige que f soit monotone strictement
croissante.
Selon les fonctions d’agrégation, les principes d’efficacité et de

séparabilité peuvent être ou non satisfaits

48
Revue des principales fonctions d’agrégation
• additives
• la fonction min et le préordre leximin
• les moyennes pondérées ordonnées (OWA)
• l’intégrale de Choquet
• autres familles

49
3.2 Fonctions d’agrégation additives
n
X
h(a) = fi (ai )
i=1
avec fi monotones strictement croissantes (fi : fcts. d’utilité)
Cas particulier de la combinaison linéaire des critères

(ou «somme pondérée»): fi (ai ) = λi . ai
X
h(a) = λi . ai , λi > 0
i
Exercice 10 Montrer que le maximum d’une fonction d’agrégation

additive correspond à des alternatives Pareto-optimales.
50
Séparabilité
= cohérence des décisions toutes choses égales par ailleurs.
Propriété Les fonctions d’agrégation additives satisfont le

principe de séparabilité.
Exercice 11 Le démontrer
Théorème (Debreu 1960) Si A est connexe, séparable et

ordonné w.r.t. g , alors il existe une fonction d’agrégation
additive représentant la relation g .
Inversement, si g n’est pas séparable, aucune fonction
d’agrégation additive ne peut la représenter.

51
Le cas particulier de la somme pondérée
X
u(a) = wi · ai , wi > 0
i=1,n
Interprétation des poids wi ? un point délicat :
• les poids wi représentent des taux de substitution

entre critères (wi = bwj signifie (0, b, ....) ∼ (1, 0, ......)))
plutôt qu’une importance
• véhicule l’idée de compensations possibles entre critères
• suppose implicitement que tous les critères peuvent

s’exprimer indirectement dans la même unité (euros,
secondes, ...) : pb. de normalisation des échelles

52
Somme pondérée : critique 1)
• Gomme le caractère conflictuel possible des critères
wi a b c d
u1 0.5 100 80 200 0
u2 0.5 100 80 0 160
u(a) = 100 > u(b) = 80

u(c) = 100 > u(d) = 80
(a, b) et (c, d) sont comparés de la même façon
alors que a domine b (pas de conflit)
mais que gros conflit entre les critères sur c et d
53
• Élimine des alternatives Pareto-optimales

qui peuvent être intéressantes car équilibrées et peut donc
favoriser des alternatives extrêmes.
wi a b c
g1 0.5 20 5 12
g2 0.5 5 20 12
Les deux alternatives extrêmes a et b sont considérées

équivalentes, et meilleures que l’alternative équilibrée c.

54
• Une faible variation des poids peut entraîner de grandes

conséquences sur la préférence globale.
wi a b c
g1 0.499 20 5 12
g2 0.501 5 20 12
Le jeu de poids h0.499, 0.501i entraîne b a, mais le jeu

h0.501, 0.499i entraîne a b.

55
3.3 La fonction min
h(a) = min fi (ai )

i
On cherche à maximiser le critère le moins satisfait.

Contrairement aux agrégations additives, elle est adaptée aux
critères ordinaux comme aux critères cardinaux.
Utilisé plutôt en décision coopérative (ex: des allocations
monétaires aux agents) :maximiser la satisfaction de l’agent le
moins satisfait

56
Séparabilité
L’opérateur min ne distingue pas entre les profils dont les
minimaux sont égaux. Exemple : h4, 2, 3, 2i et h2, 4, 2, 2i sont
indistingués.
Le min ne satisfait pas le principe de séparabilité: h5, 4i h5, 3i
mais h2, 4i ∼ h2, 3i
Le principe d’efficacité n’est pas respecté non plus : h2, 4i ∼ h2, 3i

57
Un raffinement du min : le leximin
Rattraper le faible pouvoir de décision du min en raffinant

l’ordre qu’il propose.
L’idée est donc d’ôter les paires d’utilités minimum égales
avant de prendre le min, jusqu’à ce qu’ils soient différents.
Ici : h4, 2, 3, 2i : h2, 4, 2, 2i → h4, 3, 2i : h4, 2, 2i → h4, 3i : h4, 2i.

58
Le leximin (2)
Ordre leximin = tris non décroissant des vecteurs,
puis ordre lexicographique (inverse)
Exemples :
h1, 2, 3, 4i =leximin h4, 2, 1, 3i, car h1, 2, 3, 4i ⇐⇒ h1, 2, 3, 4i
h4, 2, 3, 2i leximin h9, 2, 2, 2i, car h2, 2, 3, 4i précède h2, 2, 2, 9i
dans l’ordre lexicographique inverse
L’ordre leximin raffine l’ordre induit par le min :

v min u ⇒ v leximin u

59
Le leximin (3)
Étant donné un vecteur u, on dénote par u? le vecteur obtenu
par réarrangement des éléments du vecteur u en ordre non
décroissant.
Exemple si u = h5, 3, 2, 4, 3i, alors u? = h2, 3, 3, 4, 5i.
Définition [Ordre leximin] Soient u et v deux vecteurs de Rn .

• les vecteurs u et v sont indifférents pour l’ordre leximin
(noté u =leximin v) si u? = v ?
• u est préférée à v pour l’ordre leximin (noté u >leximin v)
s’il existe j ≤ n tel que
u?i = vi? pour i < j, et u?j > vj?

60
Théorème L’ordre leximin est un préordre complet et

respecte les principes d’efficacité et de séparabilité.
En toute généralité l’ordre leximin ne peut pas être représenté
par une fonction d’agrégation additive. Mais cette restriction
est théorique:
• elle ne tient plus dans le cas fini.
• Il peut être approché "aussi près que l’on veut" par une
fonction d’agrégation additive

61
3.4 Les moyennes pondérées ordonnées

(OWA)
en anglais : Ordered Weighted Averaging operators

Un n-OWA (OWA opérant sur des vecteurs de taille n) est
P
défini par un vecteur w = hw1 , . . . , wn i, wi ∈ [0, 1] et i wi = 1.
Une fois w fixé, l’OWA est défini par
n
X
déf
Ow (a) = wi · a?i
i=1
(rappel : on note ha?1 , a?2 , · · · , a?n i le vecteur ha1 , a2 , . . . , an i une

fois ses composantes réordonnées de façon non décroissante).
62
Les moyennes pondérées ordonnées (cont.)

En général, ne satisfait pas les principe de séparabilité et
d’efficacité
Par exemple, le min, la médiane....
Alternatives
a b c d
f1 1 3 1 3
Critères f2 6 4 6 4
f3 2 2 5 5

63
Exercice 12 Exprimer par un OWA les fonctions d’agrégation

suivantes :
1. le min
2. la moyenne
3. le leximin (dans le cas fini)
4. donnant un "compromis paramétrable" entre les deux précédents

64
3.5 L’intégrale de Choquet
Le principe de séparabilité est loin être respecté lorsque l’on

observe des décideurs en situation
Il est battu en brèche lorsqu’il y a des interactions entre critères

(redondances, oppositions)

65
Un contre exemple à la séparabilité

alternatives = clubs de tennis
critères = équipements: tennis,sauna, hammam, tir à l’arc
Critères
sauna hammam arc tennis
Cat non non OUI oui
Alternatives Cht non OUI non oui
Cats oui non OUI oui
Chts oui OUI non oui
La plupart des gens préfèrent Cht à Cat , mais Cats à Chts . La

séparabilité n’est pas respectée

66
Mesure floue
Il faut exprimer explicitement l’importance des combinaisons
de critères.
Définition [Mesure floue] Une mesure floue sur X est une
fonction µ : 2X → [0, 1], avec
• µ(X) = 1,
• µ(∅) = 0,
• S ⊆ T =⇒ µ(S) ≤ µ(T )(monotonie)
(étend la notion de poids à un sous-ensemble de critères)

67
Mesure floue (cont.)

Sur l’exemple:
µ({ten.}) = 0.6, µ({ten.} ∪ A) = 0.6 + µ(A) (A t.q. ten. ∈

/ A)
µ({arc}) = 0.1, µ({arc} ∪ A) = 0.1 + µ(A) (A t.q. arc ∈
/ A)
µ({sauna}) = 0.25, µ({sauna, ham.}) = 0.3
µ({ham.}) = 0.25
Donc, µ({sauna, arc}) = 0.35 alors que µ({sauna, ham.}) = 0.3,
et ce bien que "arc" soit un critère bien moins prioritaire que
"hammam"

68
L’intégrale de Choquet
Scruter la décision par niveau de satisfaction λi , du plus bas au
plus haut.
Soutien au niveau au moins λi : Ai = {gi , gi (a) ≥ λi }, i = 0, m,
Am+1 = ∅
Force du soutien propre au niveau λi : µ(Aj ) − µ(Aj+1 )
(µ(Aj+1 ) est reporté au niveau supérieur)
Utilité pondérée au niveau λi : u(λj ) · (µ(Aj ) − µ(Aj+1 ))
A sommer sur tous les niveaux de satisfaction.

69
L’intégrale de Choquet (cont.)

Définition [Intégrale de Choquet] Étant donnée une mesure
floue µ définie sur un ensemble de critères cardinaux
X = {g1 , g2 , . . . gn } à valeur dans λ = {λ1 , . . . , λm } l’intégrale de
Choquet sur a est définie par
déf Pm
Cµ (a) = j=1 u(λj ) · (µ(Aj ) − µ(Aj+1 ))
où Ai = {gi , gi (a) ≥ λi }, i = 0, m, Am+1 = ∅
Pour retrouver les moyenne pondérées, poser

P
µ(A) = gi ∈A µ({gi })

70

Avec λ1 = non (u(non) = 0) et λ2 = oui (u(oui) = 1)
Cµ (Cat ) = 0 × 1 + 1 × (µ({arc, ten.}) − 0) = 0.7

Cµ (Cht ) = 0 × 1 + 1 × (µ({hamman, ten.}) − 0) = 0.85
Cµ (Cats ) = 0 × 1 + 1 × (µ({arc, ten., sauna}) − 0) = 0.95
Cµ (Chts ) = 0 × 1 + 1 × (µ({hamman, ten., sauna}) − 0) = 0.9

71
Le min est une intégrale de Choquet particulière
Exercice 13 Le montrer
Plus généralement, on peut montrer que les moyennes

pondérées ordonnées sont des intégrales de Choquet
particulières.
En fait, les intégrales de Choquet recouvrent toute une gamme
de compromis entre le min et le max, en passant par les
moyennes pondérées et la médiane.

72
3.6 Utilisation des approches agregatives –

théorie de l’utilité multi attribut
On ne connait pas au départ les critères du décideur, mais

simplement l’espace des vecteurs d’attributs A = A1 × · · · × An .
Le décideur ne peut pas exprimer toute sa relation de
préférence sur A.
Le problème: Essayer, en fonction des propriétés souhaitées de
la règle de décision et d’exemples de deviner et calibrer la règle
de décision ("Théorie du Mesurage Conjoint"). Puis l’utiliser en
situation de décision.

73
L’utilité multiattribut
C’est LE modèle standard, traditionnel, appelé aussi modèle dit

de « l’école américaine ». Ref: R. L. Keeney and H. Raiffa, 1976:
Decisions with Multiple Objectives: Preferences and Value Tradeoffs.
Hypothèse fondamentale : La relation de préférence globale
g est un préordre total, donc
il existe un critère global u : A → R, («fonction d’utilité globale»)
avec
a b ⇐⇒ u(a) ≥ u(b)
Cette relation est pré-existante mais cachée. Le rôle d’une

méthode d’aide à la décision est de révéler cette relation.
74
L’utilité multiattribut (cont.)

Autres hypothèses :
• les préférences sur les points de vue s’expriment par des

attributs numériques («utilités») g1 , g2 , . . . , gn
• l’utilité globale ne dépend que des critères, est donnée par

une fonction d’agrégation :
u(a) = f (a1 , a2 , . . . , an ) avec ai = gi (a).

75
L’utilité multiattribut – cas séparable

Lorsqu’on admet la séparabilité des critères, on se tourne
(quasi) forcément vers un modèle additif (Debreu)
P
u(a) = i=1,n fi (ai ) avec fi monotones strictement croissantes
La question essentielle reste donc de trouver les fi .

Principales voies :
1. «apprentissage» des fi par points à partir d’une base
d’alternatives évaluées sur tous les critères et classées
globalement. Dans cette voie : méthode UTA, logiciel
UTA+
2. recherche de courbes iso-préférence.
76
Cas non séparable

Lorsque
• la propriété de séparabilité n’est pas vérifiée
• on cherche à exprimer des synergies entre critères
Se tourner plutôt vers des fonction d’agrégation non additives :
• des fonctions simples comme u(a) = [f1 (a1 ) + f2 (a2 )] · f3 (a3 )
• les moyennes pondérées ordonnées (OWA)
• les intégrales de Choquet
A paramétrer correctement (éliciter les poids ou plus

généralement la mesure floue .....)

77
Exercice 14 Montrer que l’ordre leximin est un préordre complet et

respecte le principe d’efficacité.
Exercice 15 Imaginez un exemple réaliste d’une situation de

décision multicritère pour laquelle la propriété de séparabilité des
critères n’est pas vérifiée.
1. Donnez pour votre exemple (1) le tableau alternatives / critères

habituel, (2) les préférences globales du décideur sur les
alternatives, et montrez pourquoi la propriété n’est pas vérifiée.
2. Quelle conséquence majeure cela a-t-il sur l’expression de

relation de préférence globale du décideur ?
3. Sur votre exemple, imaginez une fonction d’utilité globale,

agrégeant les critères, capable d’exprimer les préférences globales.

78
Exercice 16 (préférence globale lexicographique) On se donne

un ordre total (un classement sans ex-aequos) sur les critères,
représentant leur importance.
Soit deux alternatives a et b. Si on peut décider laquelle est la
meilleure au regard du premier critère seul (le plus important), alors
on ne tient pas compte des autres. Sinon, c’est que ces alternatives
sont indiscernables au regard du premier critère. On cherche alors à
trancher entre celles-ci à l’aide du second critère, ... et ainsi de suite.
Questions :
1) exprimer formellement la relation de préférence globale.
2) est-ce bien un préordre complet ? est t il séparable ? efficace ?
3) On supposera que les domaines des critères sont finis. Élaborer un
critère cardinal global représentant la relation de préférence globale.
79
4. Méthodes de
surclassement
SupAéro Décision Multi critères 4. M ÉTHODES DE SURCLASSEMENT

80
4.1 Introduction
L’approche par fonctions d’agrégation “procède par réduction

d’une logique multicritère au cas monocritère, au prix d’hypothèses
extrêmement restrictives”
Dans le monde réel
• les critères ne sont pas séparables
• les échelles des différents critères ne sont pas
commensurables (unité commune ?)
• l’indifférence n’est pas transitive
• l’indifférence (on peut choisir au hasard) est différente de
l’incomparabilité (incapacité à choisir si critères en conflit)
81
Résumé de la démarche
Contrairement au modèle traditionnel, on ne présuppose pas

qu’une relation de préférence sur les décisions soit totale, ni
transitive, ni même qu’elle pré-existe.
L’aide à la décision multicritère est plutôt considérée comme
un processus d’élaboration d’une structure de préférences.
Recherche d’un compromis entre
• la relation de dominance au sens de Pareto, jugée trop
pauvre,
• et une relation d’ordre total découlant d’une agrégation
jugée trop arbitraire et réductrice (finalement, c’est du
monocritère).
82
Exemple: la méthode interactive "STEM"

Aider l’utilisateur à se déplacer dans l’espace des alternatives.
Par exemple, optimiser sur deux critères =
• 1. Optimiser sur le premier, puis sur le second (ex:

maximiser h(a) = γg1 (a) + g2(a) avec γ grand)
• 2. Demander à l’utilisateur de combien il peut en rabattre

sur C1 : poser une contrainte g1 (a) ≥ α sur C1 et optimiser
sur C2
• 3,4,5,... : On recommence : Demander à l’utilisateur de

combien il peut en rabattre sur C2 et optimiser sur C1, etc.

83
Méthodes de surclassement (outranking)

Une méthode de surclassement cherche à établir et explorer
une relation de surclassement.
aSb ⇐⇒def il existe suffisamment d’arguments pour admettre
que a est au moins aussi bonne que b, sans qu’il y ait de raison
importante de refuser cette affirmation.
Deux étapes :
• la construction de la relation de surclassement (pas

forcement transitive ni quasi transitive)
• son exploitation: en extraire un "noyau" de bonnes

alternatives

84
4.2 Construction d’une relation de

surclassement
La démarche : on compare (phase 1) puis on agrège (phase 2)
Phase 1 : les alternatives sont comparées par paires (a, b),

Pour chaque critère i, une fonction φi : R × R → R, établit le
degré de surclassement de a sur b:
→ On obtient n indices φi (ai , bi )

85
Construction d’une relation de surclassement

(cont.)
Phase 1 → n indices φi (ai , bi )
Phase 2 : on agrège les résultats des comparaisons

par une fonction ψ : Rn → R
ce qui décide de la préférence globale :

aSb ⇐⇒ ψ φ1 a1 , b1 , . . . , φn an , bn ≥0
En général cela donne une relation de préférence globale qui

n’est pas un préordre complet, donc pouvant être difficile à
exploiter.
86
Exemple: surclassement à la majorité

Exemple très simple (majorité relative, méthode de Condorcet)
φi (x, y) = 1 si x >i y,
φi (x, y) = 0 si x =i y,
φi (x, y) = −1 si x <i y.
P
ψ= .
Autrement dit : aSb (i.e. Σi φ(ai , bi ) ≥ 0) si une majorité de

critères (votants) préfèrent a à b.
Exercice 17 Construire, selon cette méthode, un exemple pour lequel

la relation de préférence n’est pas transitive (paradoxe de Condorcet).

87
4.3 Exploitation de la relation de

surclassement
On fait correspondre à S un graphe sur A.

On cherche un sous-ensemble N d’alternatives incomparables
entre elles et tel que toute alternative qui n’est pas dans N est
surclassée par au moins une alternative de N ; formellement :
∀b ∈ A − N , ∃a ∈ N : aSb
∀a, b ∈ N : ¬aSb
L’ensemble N s’appelle le noyau du graphe. Il représente un
ensemble d’alternatives «intéressantes» parmi lesquelles le ou
les décideurs devraient faire leur choix.
88
Détermination du noyau
Tout graphe sans circuit admet un noyau unique.
Un graphe avec circuits admet 0, 1 ou plusieurs noyaux.
Le problème général de décider si un graphe possède un noyau

de moins de k nœuds est NP-complet (dc on ne connaît pas
d’autres algorithmes que croissant exponentiellelement avec la
taille des données).
Ce problème n’admet pas d’algorithme d’approximation
polynômial.

89
4.4 Un exemple historique :

la méthode ELECTRE I
(Roy, 1968), la plus ancienne mais bien représentative.

90
ELECTRE I : définition de la relation de

surclassement
• on attribue à chaque critère gi un seuil d’indifférence βi et
P
un poids pi reflétant son importance (avec i pi = 1)
• matrice de concordance : on calcule pour chaque paire

d’alternatives (a, b) le nombre
X
c(a, b) = pi
i:ai +βi ≥bi
Le nombre c(a, b) est un réel entre 0 et 1 ; il résume « la

force des arguments qui ne s’opposent pas à aSb », par une
sorte de vote pondéré.

91
ELECTRE I : définition de la relation de veto
• on attribue à chaque critère gi un seuil de veto vi
• matrice de veto : on calcule pour chaque paire d’alternatives

(a, b) le nombre
d(a, b) = 1 si ∃i, bi > ai + vi , d(a, b) = 0 sinon
d(a, b) = 1 ⇐⇒ veto sur la préférence aSb car b est bien

meilleur que a sur un critère au moins i

92
ELECTRE I : définition de la relation de

surclassement
Finalement:
• on se fixe un seuil de concordance µ avec 0 < µ ≤ 1
• on définit
aSµ b ⇐⇒def c(a, b) ≥ µ et d(a, b) 6= 1
Exercice 18 Exprimer la relation de surclassement de la méthode

ELECTRE I dans le modèle général des relations de surclassement.

93
ELECTRE Is : définition du Noyau et +

Tout graphe sans circuit admet un noyau unique.
Idée : supprimer les cycles dans S en condensant les classes
d’équivalence et supprimant des arêtes (selon une matrice de
robustesse)
→ En général on revient ensuite à la phase 1 et on essaie

d’autres seuils de concordance, voire d’autres poids (analyse de
sensibilité), afin de conforter les opinions.
Logiciels associés → bureau d’étude.

94
Autres méthodes ELECTRE
• ELECTRE-1, ELECTRE-1S → choix d’une ou de quelques

alternatives
• ELECTRE-TRI → tri (dans des classes prédéfinies)
• ELECTRE III et IV → rangement (préordre)

95
Exercices
Exercice 19 Soit la propriété de monotonie suivante :

∀a, b :

∃j : gj (a) ≥ gj (b) et ∀i 6= j : gi (a) = gi (b) =⇒ aSb
Quelles exigences sur les ψ et φi peuvent traduire cette hypothèse ?

96
Exercice 20 Un cabinet de recrutement fait subir 3 tests aux 6 candidats à un

poste. Ces tests concernent les points de vue suivants: l’évaluation des compétences
(critère g1 ), la culture générale (critère g2 ) et la motivation (critère g3 ). Chaque test
est noté sur une échelle de 0 à 20. Les résultats sont les suivants
candidats
A B C D E F
g1 16 10 18 18 16 6
critères g2 14 18 12 4 10 14
g3 16 12 6 20 12 18
On considère que le critère de compétence est primordial (poids relatif 0.6), le critère
de motivation deux fois moins important (poids relatif 0.3) et le critère de culture
générale secondaire (poids relatif 0.1).
• Quels sont les alternatives pareto efficaces
• Quelles seraient les meilleurs candidats au sens de la somme pondérée

97
candidats
A B C D E F
g1 16 10 18 18 16 6
critères g2 14 18 12 4 10 14
g3 16 12 6 20 12 18
Compétence: 0.6; motivation : 0.3) ; culture générale : 0.1.
• Etablir la matrice de concordance (pour chacun des critères, on prend un seuil
d’indifférence egal à 3) et la matrice de véto (seuil de véto égal à 9). On
rappelle que c(a, b) = Σj:aj +qj ≥bj pj et d(a, b) = 1 si ∃j, aj + vj < bj ,
d(a, b) = 0 sinon.
• Etablir la relation de surclassement pour un seuil µ1 correspondant aux
conditions les plus sévères. Extraire le noyau.
• Déterminer un ou deux autres seuil(s) offrant une relation plus riche sans
pour autant introduire de cycle. Quel serait d’après cette analyse le meilleur
candidat ?
98
• Comparer les resultats obtenus par les deux méthodes (somme pondérée et
surclassement)

99
5. Conclusion: l’optimisation
multicritère en pratique
SupAéro Décision Multi critères 5. C ONCLUSION : L’ OPTIMISATION MULTICRITÈRE EN PRATIQUE

100
L’optimisation multicritère en pratique
Problématiques essentielles:
• Quelles sont les propriétés souhaitables/intéressantes de la

relation de préférence globale ?
→ monotonie, séparabilité des critères, complétude,
transitivité, compensation possibles entre critères
• Lorsque c’est possible (hypothèses fortes) se tourner vers

un approche agrégative:
→ Quelle est la «bonne» fonction d’agrégation ?
→ comment la paramétrer (ex: utilité multi attribut) ?

101
Le modèle additif ou non ?

Le modèle additif fait des hypothèses fortes : complétude,
commensurabilité donc compensations possibles entre points de
vue, séparabilité, transitivité
Il convient bien pour les applications de type
• technique (critères quantitatifs mesurables objectivement)
• répétitif dans le temps
Les modèles non additifs : pour prendre en compte des

interactions entre critères (synergies, non-séparabilité), la non
commensurabilité, l’ordinalité des évaluations

102
Approches constructives
Approches constructives: "fonder progressivement une conviction
plutôt que de révéler un optimum ou une préférence pré-existante”
On ne présuppose pas qu’une relation de préférence sur les
décisions soit totale, ni transitive, ni même qu’elle pré-existe.
L’aide à la décision multicritère est plutôt considérée comme
un processus d’élaboration d’une structure de préférences.

103
Optimiser sur un espace combinatoire
• Approches agregatives simples (critères indépendants)

→ Programmation par contraintes, contraintes valuées
• Critères dépendants: Choquet en programmation par

contraintes (ça commence)
• Méthodes de surclassement: plus dur, il faut comparer un

nombre exponentiel de paires
→ Mais on peut toutefois garder l’aspect interactif (ex:
STEM)

104
BIBLIOGRAPHIE
• R. L. Keeney and H. Raiffa.
Decisions with Multiple Objectives: Preferences and Value
Tradeoffs.
John Wiley and Sons, 1976.
• Philippe Vincke.
L’aide multicritère à la décision.
Ellipses, Bruxelles, 1989.
• Bernard Roy et Denis Bouyssou.

Aide multicritère à la décision : méthodes et cas.
Economica 1993.
SupAéro Décision Multi critères B IBLIOGRAPHIE
105
• Matthias Ehrgott.
Multicriteria Optimization.
Lecture Notes in Economics and Mathematical Systems
491, Springer 2000.
• Hervé Moulin.
Axioms of Cooperative Decision Making.
Cambridge University Press, 1988.
• Robert Kast.
Théorie de la décision.
Éditions La Découverte, 1993.
SupAéro Décision Multi critères B IBLIOGRAPHIE

105-1
Décision multi critères:

corrigé des exercices
SupAéro Décision Multi critères C ORRIGÉ DES EXERCICES ( COURS "O PTIMISATION "
105-2
Exercice 1 (choix d’une automobile)

Si l’on compare les alternatives sur les 4 critères: Peugeot domine
Renault (consomption plus faible, plus puissante et moins cher
pour le même type de moteur). Elle domine également Citroen.
En revanche, elle ne domine pas Ford. Ford ne domine ni n’est
dominée par aucune autre alternative. Peugeot et Ford sont ap-
pelées décisions efficaces ou Pareto-optimales. Ce sont les deux
meilleures solutions
Même résultat si l’on ne prend en compte que les critères consom-
mation et prix:
105-3
− consommation
−22 −21 −20 −19
− prix
P
−7.0
C
−7.2
R
−7.5
F
−7.8
C et R sont dominées par P (moins bonnes sur les deux critères.

Elles peuvent donc être rejetées a priori.
105-4
Exercice 2 (choix d’un site)

Exercice 3 (Exemples de et ∼ non transitifs)
∼ non transitif : on peu aimer son café peu sucré, un grain de
sucre en plus ou en moins ne change rien. Mais in fine, on le
préfère peu sucré à trop sucré ou à pas sucré du tout !
non transitif : le jeu ciseau/papier/puits : ciseau est plus fort
que papier, lui même plus fort que puits, qui est plus fort que
ciseaux
105-5
Exercice 4 On montre facilement à partir de sa définition que

la relation de préférence globale à l’unanimité que la réflexivité
des préférences locales ( ∀i, ai i ai ) entraîne celle de la relation
globale.
Pour la transitivité, on suppose que a U na b et b U na c, i.e.
par définition, ∀i, ai U na bi et ∀i, bi U na ci . Donc ∀i, ai U na
bi et bi U na ci . Par transitivité des i , cela donne ∀i, ai i ci .
Donc ∀i, a U na c. a U na est transitive.
Reflexive et transitive, U na est un préordre.
Il est partiel (pas complet): on peut exhiber un cas d’incomparabilité,
e.g. sur l’exemple du choix d’automobiles.
105-6
Exercice 5 (décompositions du préordre)

• ∼ est réflexive parce que l’est.
• ∼ est symétrique : supposons a ∼ b. Par définition on a
a b et b a ce qui est aussi la définition de b ∼ a.
• ∼ est transitive : a ∼ b et b ∼ c s’écrit a b et b c et b a
et c b. Par transitivité de , cela donne a c et c a
donc a ∼ c.
• est irréflexive : a a est par définition a a et non a a
ce qui est impossible. Donc non(a a).
• est transitive : supposons a b et b c. On a donc les
assertions suivantes : a b, non(b a), b c, non(c b).
De là nous tirons que a c par transitivité de .
Pour montrer maintenant que non(c a), supposons que
cela soit : c a. Par transitivité de , avec a b, nous
105-7
tirons c b, ce qui est en contradiction avec non(c b).

Donc on a non(c a). Mais nous avions montré a c, ce
qui, avec non(c a), s’écrit a c et termine la démonstra-
tion.
• Supposons a b. On doit montrer que est asymétrique,

c’est-à-dire non(b a). Supposons que cela soit, c’est-à-
dire b a. Par la transitivité on tire a a, en contradic-
tion avec l’irréflexibilité démontrée plus haut. G est donc
asymétrique.
105-8
Exercice 6 On pose a b ⇐⇒ g(a) ≥ g(b)

et on montre les propriétés de ainsi définie:
• est vide :
Évident : on a soit g(a) > g(b) soit g(b) > g(a), soit g(a) =
g(b), et jamais impossibilité de comparer.
• est complete (ou complète) : a b ou b a pour tout
a et b ∈ A
parce que est vide
• ∼ et sont transitives :
Évident : par transitivité de > et =
et donc
• = ∪ ∼ est réflexive et transitive (c’est un préordre)
est reflexive parce que ∼ l’est.
est transitive parce que ∼ et le sont.
105-9
Exercice 7 Trivial a partir des définitions

Exercice 8 ( est réflexive)
Évident : a ∼ a donc a a
105-10
Exercice 9 Montrer que toute relation de préférence globale qui

est transitive, séparable et satisfait le principe de projection des
échelles:
∀a, b, c, ∀i : ai i bi ⇐⇒ ai {i}h bi {i}h
satisfait aussi le principe d’efficacité.
Se démontre par récurrence sur le nombre de critères où ai i bi .
Si pour tous les critères sauf un, aj = bj (sur ces critères, les
deux vecteurs sont identiques), et que sur le dernier critère, dis-
ons i, ai i bi . Le principe de projection des échelles assure que
ai {i}h bi {i}h, en posant h = a = b, cela donne ai {i}a bi {i}b,
i.e. a b.
Supposons que , quels que soient a et b, si sur tous critères sauf
m, aj = bj et que sur les m autres critères ai i bi , alors a b.
On choisit maintenant a et b tels que, sur tous critères sauf m + 1,
aj = bj et que sur les m + 1 autres critères ai i bi . On note j
l’un des critères où ai i bi . Par récurrence, a{j}a a{j}b et à
105-11
cause du principe de projection a{j}b b{j}b. Par transitivité,

a{j}a b{j}b, i.e. a b
105-12
Exercice 10 Montrer que le maximum d’une fonction d’agrégation

additive correspond à des alternatives Pareto-optimales.
Rappel
Pn : une fonction d’agrégation additive est de la forme h(a) =
i=1 fi (ai ) où les fi sont des fonctions monotones strictement
croissantes.
Soit â une alternative maximisant sur A la fonction h(a), et sup-
posons que cette alternative ne soit pas Pareto optimale. Il existe
donc une alternative a0 qui la domine, et donc :
∀i : a0i ≥ âi , et ∃i : a0i > âi
Utilisons maintenant le fait que les fonctions fi sont monotones
strictement croissantes par définition :
∀i : a0i ≥ fi (âi ), et ∃i : a0i > fi (âi )
et donc
n
X n
X
fi (a0i ) > fi (âi ),
i=1 i=1
105-13
d’où une contradiction puisque â ne maximiserait pas h(a).
105-14
Exercice 11 Montrer que les fonctions d’agrégation additives con-

struisent une préférence globale qui satisfait le principe de sé-
parabilité.
Soient a, b, c trois alternatives et V un ensemble de critères tels
que aV c bV c au sens d’une agrégation additive, i.e. Σi∈V f i(ai )+
/ f i(ci ) ≥ Σi∈V f i(bi )+Σi∈V
Σi∈V / f i(ci ). Ceci est logiquement équiv-
alent à Σi∈V f i(ai ) ≥ Σi∈V f i(bi ), cette dernière inégalité étant
elle même équivalente à Σi∈V f i(ai ) + Σi∈V / f i(di ) ≥ Σi∈V f i(bi ) +
/ f i(di ), quel que soit l’alternative d. Donc aV c bV c est
Σi∈V
logiquement équivalent à aV d bV d.
105-15
Exercice 12 Exprimer par un OWA les fonctions d’agrégation

suivantes :
1. la moyenne : wi = 1/n, ∀i
2. le min : w1 = 1, wi = 0 ∀i > 1
3. donnant un compromis paramétrable entre les deux précé-
dents : wi = αi , 0 < α < 1, avec la normalisation qui va
bien
4. représentant, dans le cas fini, le préordre leximin: en sup-
posant que le notes données par les critères soient des en-
tiers entre α0 = 0 et αN = N (on rappelle que l’on est dans
le cas fini, cette hypothèse peut donc être faire dans perte
de géneralité ), on peut prendre wi = n1i . v , où n est le nom-
bre de critères et v un facteur de normalisation permettant
que la somme des poids soit égale à 1.
105-16
Idée du raisonnement permettant de trouver les poids pour l’encodage

du leximin. Supposons que a leximin b, et que a et b ne soient
différents qu’à la ième plus faible note; soit αk la note reçue à ce
niveau par a (i.e. ai = αk ). L’un des cas les plus défavorables pour
a leximin b survient quand a est de la forme (h1 , .., hi−1 , αk , αk , ..., αk )
et b de la forme (h1 , .., hi−1 , αk−1 , 1, ..., 1).
L’owa s’écrit:
Σj=1,i−1 hj .wj +αk Σj=i,n wj > Σj=1,i−1 hj .wj +αk−1 .wi +1.Σj=i+1,n wj .
En faisant l’hypothèse que les wi decroissent quand i augmente,
une condition suffisante pour que cette inéquation soit satisfaite
est: αk .wi > αk−1 .wi + (n − 1).wi+1 , i.e., puisque αk − αk−1 = 1,
wi > (n − 1).wi+1 . On peut donc choisir wi = n1i (i.e. la suite
1 1
n , n2 , .... ), que l’on normalise ensuite de manière à avoir une
somme des wi égale à 1.
En toute rigueur, il faut ensuite montrer l’équivalence entre l’ordre
du leximin et l’ordre donné par cet OWA. Si il y a équivalence sur
105-17
le leximin, il y a donc identité des vecteurs classés et donc égal-

ité des valeurs rendues par l’OWA. Si il y a préférence stricte de a
sur b, avec par exemple une différence au niveau i, il faut montrer
que :
Σj=1,i−1 hj .wj + αk .wi + Σj=i,n aj .wj > Σj=1,i−1 hj .wj + αk−1 .wi +
.Σj=i+1,n bj .wj , ce qui est équivalent à
αk . n1i + Σj=i+1,n aj . n1j > αk−1 . n1i + .Σj=i+1,n bj . n1j .
1
Notons que (n − 1). ni+1 est un majorant de Σj=i+1,n bj . n1j et 0 est
un minorant de Σj=i+1,n aj . n1j . Il suffit donc de montrer que
αk . n1i > αk−1 . n1i + (n − 1). ni+1
1
, cad que n1i > (n − 1). ni+1
1
- ce qui
(n−1)
est trivial puisque 1 > n
105-18
Exercice 13
Pour exprimer le min par une intégrale de Choquet, on pose µ(S) =
1, µ(A) = 0∀A 6= S.
Pour exprimer un OWA quelconque par une intégrale de Cho-
quet, poser µ(A) = Σi=n−Card(A)+1,n wi
Voir: M. Grabisch, On equivalence classes of fuzzy connectives:
The case of fuzzy integrals. IEEE Transactions on Fuzzy Systems
3 1 (1995), pages 96 à 109.
105-19
Exercice 14
L’ordre leximin est complet car on peut toujours comparer lex-
icographiquement (ordre du dictionnaire) deux vecteurs. Il est
réflexif car l’ordre lexicographique sur les vecteurs est réflexif.
Supposons que a leximin b et b leximin c.
Si on a deux indifférences, c’est que les trois vecteurs sont iden-
tiques à une permutation près; une fois rangés ils sont donc équiv-
alent pour l’ordre lexicographique. Donc ils sont équivalents pour
le leximin.
Si a leximin b et b leximin c, cela signifie que, jusqu’à une com-
posante i∗ les vecteurs classes correspondant à a et à b, notés a0 et
b0 sont identiques, et qu’en i∗ , a0i∗ > b0i∗ . De la même façon, jusqu’à
une composante j ∗ les vecteurs classes correspondant à b et à c,
sont identiques, et qu’en j ∗ , b0j ∗ > b0j ∗ .
105-20
Soit k ∗ = min(i∗ , j ∗ ). Jusqu’en k ∗ , les trois vecteurs classés sont

identiques; en k ∗ , soit a0k∗ > b0k∗ et b0k∗ = ck∗ , soit a0k∗ = b0k∗ et
b0k∗ > ck∗ . Donc en k ∗ a0k∗ > ck∗ . Les vecteurs classes a0 et c0 étant
identiques jusqu’en k ∗ , avec de plus a0k∗ > ck∗ , on a par définition
a leximin c.
Pour prouver le principe d’efficacité, prenons a et b tels que a
domine b au sens de Pareto (sens fort). a ∼leximin b est impossible
car les deux vecteurs classes sont différent du fait de la domi-
nance. Considérons les deux vecteurs classés, et supposons que
b leximin a. Cela signifie qu’il existe une composante des vecteurs
classés tels que a0i < b0i et ∀j < i, a0j = b0j .
Soit k le critère qui fournit a0i ; sur ce critère, ak ≥ bk , par domi-
nance. Ce critère, dans b0 , ne peut pas apparaître après le rang i
car toutes les notes a partir du rang i sont supérieurs ou égales à
b0i et b0i > a0i = ak .
105-21
On fait le même raisonnement pour tous les critères qui four-

nissent les a0j , j < i. Soient donc i + 1 notes a apparaître avant
le rang i, ce qui est impossible.
105-22
Exercice 15
On compare 4 types d’automobiles selon 3 critères : prix (en kE),
consommation (en l/100 km), confort (noté sur 20).
alternatives
a b c d
g1 consommation -10 -9 -10 -9
critères g2 confort 15 13 15 13
g3 prix -10 -10 -30 -30
g -35 -34 -40 -43
On suppose que les préférences globales du décideur sont d ≺

c ≺ a ≺ b. Le décideur préfère b à a (lorsque le prix est faible,
il privilégie la consommation au confort), mais il préfère c à d
(lorsque le prix est élevé, il privilégie le confort à la consomma-
tion).
105-23
La conséquence importante de la non-séparabilité est que la préférence

globale ne peut pas être représentée par une fonction d’utilité qui
soit une fonction d’agrégation additive sur les critères.
Pour aller au plus simple, on va utiliser un critère global h le
critère global défini par test sur le critère coût (on aurait pu alter-
nativement construire une intégrale de Choquet) :
• si g3 < −20 : h = g1 + 2g2 + 2g3
• si g3 ≥ −20 : h = 3g1 + g2 + 2g3 .
Les valeurs de g sont représentées dans le tableau ci-dessus. Elles

permettent de représenter les préférences globales : (x ≺ y) ⇐⇒
(h(x) < h(y))
105-24
Exercice 16 Ordre lexicographique

On classe les critères du moins important (petit indices) au plus impor-
tant (gros indices).
1) exprimer formellement la relation de préférence globale.
• a b ssi existe un critère j tel que aj > bj et si ak = bk pour tous

les critères k plus importants que j, i.e. pour tout k > j.
• a ∼ b ssi ak = bk pour tout k.
• comme = ∪ ∼.
2) est-ce bien un préordre complet ?
• complete, forcément : si deux alternatives ont les même éval-

uations sur tous les critères, elle sont jugées indifférente. Sinon,
on considère le plus important des critères où les notes diffèrent,
et là ce critère impose sa préférence stricte.
105-25
• réflexif évident aussi car a ∼ a pour tout a, par définition
• transitif : ∼ est transitif, elle correspond à l’identité des vecteurs.

Soient a, b, c tel que a b et b c. Soit k le plus important des
critères sur lesquels soient a diffère de b, soit b diffère de a. Sur
tous les critères plus importants, ai = bi = ci . En k, on a soit
ak >k bk et bk ≥k ck , soit ak ≥k bk et bk >k ck ; dans les deux
cas, par transitivité des préférences locale, ak > ck . Puisque
ai = ci ∀i > k et ak > ck la definition induit a c. Donc
est transitive. Puisque la relation est complète et que ses deux
composantes ∼ et sont transitives, elle est transitive.
3) élaborer un critère numérique global représentant la relation de préférence

globale
On va chercher à encoder la relation de préférence globale par une
somme pondérée.
h(a) = Σi ai . pi
105-26
Pour y parvenir, il faut que les niveaux de préférence sur chaque critère
soient en nombre fini. Supposons qu’on s’y ramène, avec par exemple
N + 1 niveaux par critère, par exemple entre 0 et N (ceci se fait sans
perte de généralité). Soit n le nombre de critères.
Le cas le moins favorable pour une préférence lexicographique a b
est quand, sur le critère décisif k, ak − bk = 1 et que sur tous les critères
moins important que k, b est excellent (note N ) et a mauvais (note 0).
La traduction de a b par une somme pondérée exige que:
Σi>k ai . pi + ak . pk + 0 > Σi>k bi . pi + bk . pk + Σi<k N.pi

ce qui est équivalent à
ak . pk + 0 > +bk . pk + Σi<k N.pi

Une condition suffisante pour que cette in équation soit vérifiée est
ak . pk + 0 > +bk . pk + (n − 1)N.pk−1 ∀k
Soit (ak − bk ) . pk > (n − 1)N.pk−1 ∀k, i.e. pk > (n − 1)N.pk−1
105-27
Il suffit alors que choisir les poids pk de manière à respecter cette in-
équation. Par exemple pk = nk .N k . En effet nk N k > (n−1).N.nk−1 .N k−1 ,
puisque n ≥ 1.
La somme pondérée choisie est donc celle où pour tout critère i, pi =
ni N i (ou pi = M 2i avec M = max(n, N )), les indices de critères devant
être d’autant plus forts que le critère est important.
En toute rigueur, il faut maintenant prouver que a est meilleur que b
au sens lexicographique ssi a est meilleur que b au sens de cette somme
pondérée. Il est évident que si a est indifferent à b au sens lexicographique,
c’est qu’il a les même évaluations sur tous les critères et que donc il
reçoit la même note au sens de la somme pondérée. Maintenant, si
a est strictement préféré à b par la règle lexicographique, on utilise la
condition élaborée plus haut pour montrer que c’est également vrai en
utilisant la somme pondérée.
La relation étant complète, on en déduit que a lexicographique b au sens
lexicographique ssi a sommepondre b.
105-28
Exercice 17 Construire, selon la méthode de Condorcet, un exemple

pour lequel la relation de préférence n’est pas transitive (paradoxe de
Condorcet).
Trois alternatives a, b, c.
g1 (a) = 3, g1 (b) = 2, g1 (c) = 1
g2 (a) = 2, g2 (b) = 1, g2 (c) = 3
g3 (a) = 1, g3 (b) = 3, g3 (c) = 2
105-29
Exercice 18 Exprimer la relation de surclassement de la méthode ELEC-

TRE I dans le modèle général des relations de surclassement.
On suppose P = 1 (somme des pj ).


 (1 − µ) · pj si aj ≥ bj (j est d’accord pour a b)
φi (aj , bj ) = −M si (aj , bj ) ∈ Dj (veto de j pour a b) (1)
−µ · pj sinon

avec M un nombre suffisamment grand. Et pour ψ on fait la somme.

Vérification : s’il y a veto d’un critère, alors
s(a, b) = ψ(φ1 (g1 (a), g1 (b)), . . . , φn (gn (a), gn (b)) < 0,
et on ne peut avoir a µ b.
S’il n’y a pas veto, alors
X X X
ψ(a, b) = (1 − µ) · pj − µ · pj = ( pj ) − µ (2)
j:aj ≥bj j:aj <bj j:aj ≥bj
et s(a, b) ≥ 0 est équivalent à c(a, b) ≥ µ, cqfd.
105-30
Exercice 19 Soit la propriété de monotonie suivante :

∀a, b :
∃j : aj ≥ bj et ∀i 6= j : ai = bi =⇒ a b
Quelles exigences sur les ψ et φi permettent d’assurer cette propriété ?
On suppose φi (v, v) = 0∀v, i, φi croissantes sur le premier argument et

décroissante sur le second ( φi (u, v) croit quand u croit et décroît quand
v croit, et ce pour tout i ).
Sur ψ, on suppose ψ(0, ....., 0) = 0 et que ψ est croissante avec ses argu-
ments.
Dans ce cas en effet, pour tous les i 6= j, φi (ai , bi ) = φi (ai , ai ) = 0.
Comme les φi sont croissante dans leur premier argument, φj (aj , bj ) ≥
φj (bj , bj ) = 0.
Comme φj (aj , bj ) ≥ 0, que φi (ai , bi ) = 0 pour tout i 6= j, et que ψ est
croissante ψ(φj (aj , bj ), 0, ..., 0) ≥ ψ(0, ....., 0). Puisque psi(0, ....., 0) = 0,
on obtient ψ(a, b) ≥ 0 donc a b
105-31
Exercice 20
candidats
A B C D E F
g1 16 10 18 18 16 6
critères g2 14 18 12 4 10 14
g3 16 12 6 20 12 18
Compétence: 0.6; motivation : 0.3 ; culture générale : 0.1.
• Alternatives pareto optimales: toutes, sauf E qui est dominé par

A
• D, qui a une note globale pondérée de 17.2 (suivi de A : 15.8)
• Matrice de concordance:
105-32
A B C D E F
A 1 0.9 1 0.7 1 1
B 0.1 1 0.4 0.1 0.4 0.7
C 0.7 0.6 1 0.7 0.7 0.7
D 0.9 0.9 1 0.9 0.9 0.9
E 0.6 0.9 1 0.7 1 0.6
F 0.4 0.3 0.4 0.4 0.4 1
• Matrice de discordance: veto sur (C, A), (C, D), (C, F ), (D, A),
(D, B), (D, F ), (F, A),(F, C), (F, D), donc des 1 sur ces cases, 0
sur les autres.
• Avec µ = 1, la relation de surclassement est la relation de domi-

nance stricte au seuils d’indifférence près. C’est une relation très
pauvre (peu de couples la satisfont): A surclasse C, E et F ; E
surclasse C; Noyau {A, B, D}
• On obtient des relations plus riches pour µ = 0.9 et µ = 0.7. Le

noyau est {A, D} dans le premier cas, {A} dans le second.
105-33
• On recommande A, qui est dans tous les noyaux lorsque l’on fait
varier le seuil µ (en dessous de 0.7, le consensus devient vraiment
mou; en dessous de 0.5, µ n’a pas de sens).
• avec la somme pondérée, D se détache très nettement, bien qu’il

ne soit pas équilibré (sa culture générale est catastrophique). A
se detache avec l’approche par surclassement : cette approche
limite les effets de compensation et degage des candidats plus
équilibrés.

Multicritere Sup Aero

Transféré par

Droits d'auteur :

Formats disponibles

Multicritere Sup Aero

Transféré par

Informations du document

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

Multicritere Sup Aero

Transféré par

Droits d'auteur :

Formats disponibles

0

Hélène Fargier, Michel Lemaître

SupAéro Décision Multi critères 1. I NTRODUCTION

Quelques problèmes de décision et

• Choisir le site d’implantation d’une usine, d’un magasin ...

• Évaluer la qualité des fournisseurs.

• Évaluer des projets.

• Choisir une stratégie d’investissement.

SupAéro Décision Multi critères 1. I NTRODUCTION

• Modèle unicritère : Optimiser {g(a), a ∈ A} où g : A 7→ R

• Mathématiquement bien posé :

• Économiquement mal posé :

SupAéro Décision Multi critères 1. I NTRODUCTION

Choix d’une automobile

• le nombre fini critères

Exemple : choix d’un candidat

SupAéro Décision Multi critères 1. I NTRODUCTION

• Modèle multicritère : Optimiser

Les critères sont

• Souvent contradictoires (puissance et prix)

• Exprimés dans des unités différentes ((puissance et prix)

• Difficiles à mesurer quantitativement (type moteur): les

SupAéro Décision Multi critères 1. I NTRODUCTION

• définir l’ensemble des alternatives possibles (les objets sur

• définir les différents points de vue sur lesquels on jugera les

SupAéro Décision Multi critères 1. I NTRODUCTION

• Critère : exprime les préférences du décideur relativement

• Généralement (et pour la suite) : attribut  critère

SupAéro Décision Multi critères 1. I NTRODUCTION

• définir l’ensemble des alternatives possibles (les objets sur

Problématiques d’aide à la décision MCDM

• Sélection : Choix d’une solution (la meilleure) ou d’un

• Affectation : Tri résultant de l’affectation de chaque

• Classement : ordonner l’ensemble des alternatives

SupAéro Décision Multi critères 1. I NTRODUCTION

• Principes de base pour la modélisation des préférences

• Agréger puis comparer : les principales approches par

• Comparer puis agréger : les méthodes de surclassement

SupAéro Décision Multi critères 1. I NTRODUCTION

SupAéro Décision Multi critères 1. I NTRODUCTION

SupAéro Décision Multi critères 1. I NTRODUCTION

SupAéro Décision Multi critères 2.P RINCIPES BE BASE

2.1 Modélisation des préférences

Dans un problème multicritère, on distingue:

Le problème de classement: synthétiser un g global à partir

SupAéro Décision Multi critères 2.P RINCIPES BE BASE

Préférence stricte, indifférence et incomparabilité

 définit 3 relations exclusives sur A :

la préférence stricte, notée  : ab ⇔ a  b ∧ ¬(b  a)

SupAéro Décision Multi critères 2.P RINCIPES BE BASE

Préférence stricte, indifférence et incomparabilité

•  est asymétrique : a  b implique non b  a

•  est irréflexive : non a  a

• ∼ est symétrique : a ∼ b implique b ∼ a

•  est irréflexive : non a  a

•  est symétrique : a  b implique b  a

SupAéro Décision Multi critères 2.P RINCIPES BE BASE

Définition [(Quasi) Transitivité] Une relation R est transitive

• Les relations d’indifférence ∼ (et donc les relations ) ne

• Généralement (et pour la suite) : attribut critère

Le problème de classement: synthétiser un g global à partir

définit 3 relations exclusives sur A :

la préférence stricte, notée : ab ⇔ a b ∧ ¬(b a)

• est asymétrique : a b implique non b a

• est irréflexive : non a a

• est irréflexive : non a a

• est symétrique : a b implique b a

• Les relations d’indifférence ∼ (et donc les relations ) ne

A maximiser : a b ⇐⇒ g(a) + q ≥ g(b) avec q > 0

i.e. a b ⇐⇒ g(a) > g(b) + q,

Attribut à minimiser: a b ⇐⇒ g(a) − q ≤ g(b)

a M aj b ⇐⇒ |{i, a i b}| ≥ |{i, b i a}|

Définition [relation complète)] Une relation est complète

est complète ⇐⇒ est vide.

Une règle de décision a minima : a U na b ⇐⇒ ∀i, a i b

Exercice 5 Montrer que si est un préordre, ∼ est une relation

Définition [Principe d’unanimité] g satisfait le principe

Définition [] g satisfait le principe de séparabilité ssi, quel que

aIc g bIc ⇐⇒ aId g bId

• est asymétrique : a b implique non b a

• est irréflexive : non a a

• est irréflexive : non a a

• est symétrique : a b implique b a