Une méthode d’évaluation multicritère basée sur une interprétation probabiliste

François Glineur Faculté Polytechnique de Mons Groupe de Contact du F.N.R.S. Méthodes quantitatives de gestion.

20 mars 1998.

Contents

1 Introduction 2 1.1 Chaînes de Markov . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Relations de préférence . . . . . . . . . . . . . . . . . . . . . . 3

2 Méthode probabiliste 5 2.1 Exploitation d’une relation de préférence . . . . . . . . . . . . 5 2.2 Passage au cas multicritère . . . . . . . . . . . . . . . . . . . . 7 2.3 Extension : introduction de l’incomparabilité . . . . . . . . . . 8

3 Illustrations 10 3.1 Relations de préférence . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Choix d’un supermarché . . . . . . . . . . . . . . . . . . . . . 10 3.3 Implantation d’une usine . . . . . . . . . . . . . . . . . . . . . 10

4 Conclusion 11 4.1 Exploitation de relation de préférence . . . . . . . . . . . . . . 11 4.2 Analyse multicritère . . . . . . . . . . . . . . . . . . . . . . . 11 4.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1 Introduction

1.1 Chaînes de Markov

Soit un ensemble fini composé de n états E = {E_{i}, i = 1, 2, …, n}. Soit un ensemble de variables aléatoires X = {X_{t}, t = 0, 1, 2, …} indexé par le temps, où chaque X_{t} prend ses valeurs dans X.

Si

• X_{t} dépend uniquement de X_{t−1} (processus markovien)

• Cette dépendance est invariante dans le temps (processus homogène)

on dit que X est une chaîne de Markov (finie, à temps discret).

Elle est caractérisée complètement par la matrice M = (p_{ij}) où

p_{ij} = ℙ(X_{t} = E_{j}|X_{t−1} = E_{i})

On peut la représenter par un graphe orienté valué (sommets ≡ états, arcs ≡ transitions).

Par exemple, à la matrice M = ( \begin{matrix}1/2 & 1/2 & 0 & 0 \\ 1/3 & 0 & 1/3 & 1/3 \\ 0 & 0 & 1/4 & 3/4 \\ 0 & 0 & 1/2 & 1/2 \end{matrix} ) correspond le

graphe [figure: E_{1}; 1/2; 1/2; E_{2}; 1/3; 1/3; 1/3; E_{3}; 1/4; 3/4; E_{4}; 1/2; 1/2]

M est une matrice stochastique (somme des éléments sur une ligne égale à un).

Soit une distribution initiale a_{0} (correspondant à X_{0}).

• Il est possible de calculer a_{i}, la distribution de X_{i}, pour tout i (récursivement à partir de a_{i−1}

• Dans certaines conditions (chaîne régulière), la suite des a_{i} tend vers une limite a indépendamment de la distribution initiale a_{0}.

• Cette limite est appelée distribution stationnaire.

• Il existe un moyen efficace de la calculer (système linéaire ou vecteur propre à gauche).

Dans notre exemple, a = (0, 0, \frac{2}{5}, \frac{3}{5}).

1.2 Relations de préférence

Définitions Soit A = {A_{i}, i = 1, 2, …, n} un ensemble de n alternatives et R une relation sur A (R ⊆ A^{2}).

R est dite

• réflexive si a R a pour tout a ∈ A

• complète si a R b ou b R a pour tout a, b ∈ A

• symétrique si a R b ⇒ b R a pour tout a, b ∈ A

• asymétrique si a R b ⇒ b ¬R a pour tout a, b ∈ A

• transitive si a R b et b R c ⇒ a R c pour tout a, b, c ∈ A

On donne à R la signification ≤, c’est-à-dire a R b ≡ a n’est pas préféré strictement à b. A partir de R, on définit les relations I et S selon a I b ⇔ a R b et b R a et a S b ⇔ a R b et b ¬R a.

I représente l’indifférence de R (I est symétrique et réflexive). S représente la préférence stricte de R (S est asymétrique et non-réflexive). Si a R b, on a soit a I b, soit a S b.

Représentations R peut se représenter sous forme matricielle (r_{ij}), avec r_{ij} égal à 1 si A_{i} R A_{j}, à 0 dans le cas contraire.

R peut aussi se représenter graphiquement par un graphe orienté (sommets ≡ alternatives, arcs ≡ relation R).

Par exemple, si A = {a, b, c} et a R c, c R a, a R b, b R c, a R a, b R b et c R c, R est réflexive et complète.

R = ( \begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix} ) et le graphe est [figure: a; b; c]

Quelques relations de préférence Soit R réflexive et complète.

• Si S est transitive et I est transitive, R est un préordre complet (ordre avec ex-aequo). On peut associer à chaque alternative une valeur v_{i} telle que A_{i} R A_{j} ⇔ v_{i} ≤ v_{j}.

• Si S est transitive et I = {(a, a)}, R est un ordre complet. On peut associer à chaque alternative une valeur v_{i} distincte telle que A_{i} R A_{j} ⇔ v_{i} ≤ v_{j}.

• Si on peut associer à chaque alternative A_{i} un intervalle de la droite réelle U_{i} = [v_{i}v′_{i}] tel que A_{i} I A_{j} ⇔ U_{i} ∩ U_{j} ≠ ∅ et A_{i} S A_{j} ⇔ v′_{i} < v_{j}, R est un ordre d’intervalle. Dans ce cas, S est transitive mais I ne l’est pas.

• Si on peut associer à chaque alternative A_{i} un intervalle de la droite réelle U_{i} = [v_{i}v′_{i}] tel que A_{i} I A_{j} ⇔ U_{i} ∩ U_{j} ≠ ∅ et A_{i} S A_{j} ⇔ v′_{i} < v_{j}, et si aucun des intervalles n’est inclus strictement dans un autre, R est un semiordre. Dans ce cas, S est transitive mais I ne l’est pas.

Exemples de relations

• Ordre complet. ( \begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} ) [figure: a; b; c]

• Préordre complet ( \begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix} ) [figure: a; b, c]

• Ordre d’intervalle ( \begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix} ) [figure: \{; [; a; ]; [; b; ]; [; c; ]; \}; d]

• Semiordre ( \begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{matrix} ) [figure: [; a; ]; [; b; \{; ]; [; \}; d; c; ]]

Théorèmes Soit R une relation sans alternatives équivalentes (a et b sont équivalentes si a R x ⇔ b R x et x R a ⇔ x R b pour tout x ∈ A.

• Si R est un semiordre, il existe un unique ordre complet sous-jacent à R. Il s’agit de l’ordre des extrémités v_{i} (ou v′_{i}) des intervalles U_{i}. De plus, si on ordonne les lignes et les colonnes de la matrice représentative de R selon cet ordre, on obtient une matrice échelonnée.

• Si R est un ordre d’intervalle, il existe deux ordres complets sousjacents à R. Il s’agit de l’ordre des extrémités v_{i} (ou v′_{i}) des intervalles U_{i}. De plus, si on ordonne les lignes (les colonnes) de la matrice représentative de R selon le premier (le second) ordre, on obtient une matrice échelonnée.

Exemples : ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{matrix} ) et ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} )

2 Méthode probabiliste

2.1 Exploitation d’une relation de préférence

Soit une relation de préférence R complète et réflexive.

On crée une chaîne de Markov en associant à l’alternative A_{i} un état E_{i}. On choisit les probabilités de transition p_{ij} de façon à avoir

• p_{ij} > 0 lorsque A_{i} R A_{j}

• p_{ij} = 0 lorsque A_{i} ¬R A_{j}

• la matrice (p_{ij}) est stochastique

On calcule alors la distribution stationnaire de la chaîne ainsi définie et on classe les alternatives selon cette distribution.

Justification Intuitivement, le processus passe toujours d’une alternative à une alternative meilleure ou équivalente. Il est donc raisonnable de penser que les meilleures alternatives auront une forte probabilité dans la distribution stationnaire.

Choix des p_{ij} Il semble raisonnable de ne pas faire dépendre le choix des p_{ij} d’autres alternatives que A_{i} et A_{j} (une certaine forme d’indépendance).

Une première possibilité est Si A_{i} R A_{j}, on pose p_{ij} = 1/n ; sinon on pose p_{ij} = 0. Cependant, la matrice obtenue n’est pas stochastique. On modifie alors

p_{ii} de façon à rendre la matrice stochastique, c’est-à-dire

p_{ii} = 1 − ∑_{j≠i} p_{ij}

On interprète alors le processus comme suit :

• Je suis à l’état i.

• Je choisis au hasard un état j (équitablement).

• Si A_{i} R A_{j}, je passe à l’état j, sinon je reste en i.

Exemples : R = ( \begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix} ) donne M = ( \begin{matrix}1/3 & 1/3 & 1/3 \\ 0 & 2/3 & 1/3 \\ 1/3 & 0 & 2/3 \end{matrix} ).

[figure: a; b; c]

La distribution stationnaire vaut (\frac{1}{4}, \frac{1}{4}, \frac{1}{2}) : c est meilleur, a et b suivent.

R = ( \begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} ) donne M = ( \begin{matrix}1/3 & 1/3 & 1/3 \\ 0 & 2/3 & 1/3 \\ 0 & 0 & 1 \end{matrix} ).

[figure: a; b; c]

La distribution stationnaire vaut (0, 0, 1) : c est meilleur, a et b suivent. Inconvénient : information perdue pour b et a. Méthode trop agressive (c est un état absorbant).

Autre choix des p_{ij} Ajoutons à la chaîne de Markov un état fictif neutre E_{0}, ne représentant aucune alternative, tel que p_{00} = 0 et p_{0i} = 1/n ∀i > 0. Les transitions depuis cet état ne favorisent aucune alternative.

Reprenons la règle Si A_{i} R A_{j}, on pose p_{ij} = 1/n ; sinon on pose p_{ij} = 0. Cette fois, pour rendre la matrice stochastique, on choisit les p_{i0}, c’est-à-

dire

p_{i0} = 1 − ∑_{j≠0} p_{ij}

On interprète alors le processus comme suit :

• Je suis à l’état i.

• Je choisis au hasard un état j (équitablement).

• Si A_{i} R A_{j}, je passe à l’état j, sinon je vais en 0.

Exemples : R = ( \begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix} ) donne M = ( \begin{matrix}1/3 & 1/3 & 1/30 \\ 0 & 1/3 & 1/3 & 1/3 \\ 1/3 & 0 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 & 0 \end{matrix} ).

La distribution stationnaire vaut (\frac{7}{27}, \frac{6}{27}, \frac{9}{27}, \frac{5}{27}) : c est meilleur, suivi de a puis de b.

R = ( \begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} ) donne M = ( \begin{matrix}1/3 & 1/3 & 1/30 \\ 0 & 1/3 & 1/3 & 1/3 \\ 0 & 0 & 1/3 & 2/3 \\ 1/3 & 1/3 & 1/3 & 0 \end{matrix} ). Distribution

stationnaire : (\frac{4}{27}, \frac{6}{27}, \frac{9}{27}, \frac{8}{27}) : c est meilleur, suivi de b puis de a.

Propriété Si R est un préordre complet, la distribution stationnaire reflète ce préordre complet.

2.2 Passage au cas multicritère

Considérons à présent plusieurs relations de préférence (critères) à agréger. Soit R_{i}, i = 1, 2, …, r r critères avec R_{i} complète et réflexive ∀i.

Supposons que ces critères sont pondérés par des poids w_{i}, i = 1, 2, …, r dont la somme vaut 1.

Calculons la matrice stochastique M_{i} pour chaque relation R_{i} de la manière décrite plus haut. Soit M la sommet de ces M_{i} pondérée par les poids w_{i}.

M est également stochastique, elle définit une chaîne de Markov. On classe alors les alternatives selon la distribution stationnaire de cette chaîne.

Cette méthode admet l’interprétation suivante :

• Je suis à l’état i.

• Je choisis au hasard un critère R_{p} (selon les w_{i})

• Je choisis au hasard un état j (équitablement).

• Si A_{i} R_{p} A_{j}, je passe à l’état j, sinon je vais en 0.

Exemple : r = 2, w_{1} = 1/3 et w_{2} = 2/3. M_{1} = ( \begin{matrix}1/3 & 1/3 & 1/30 \\ 0 & 1/3 & 1/3 & 1/3 \\ 0 & 0 & 1/3 & 2/3 \\ 1/3 & 1/3 & 1/3 & 0 \end{matrix} ),

M_{2} = ( \begin{matrix}1/3 & 1/3 & 1/30 \\ 0 & 1/3 & 0 & 2/3 \\ 1/3 & 1/3 & 1/3 & 0 \\ 1/3 & 1/3 & 1/3 & 0 \end{matrix} ), M = ( \begin{matrix}1/3 & 1/3 & 1/30 \\ 0 & 1/3 & 1/9 & 5/9 \\ 2/9 & 2/9 & 1/3 & 2/9 \\ 1/3 & 1/3 & 1/3 & 0 \end{matrix} ). La dis-

tribution stationnaire est (\frac{16}{79}, \frac{24}{79}, \frac{21}{79}, \frac{18}{79}), ce qui suggère b en tête, suivi de c puis de a.

R_{1} : [figure: b; a; c]R_{2} : [figure: b; a; c]

2.3 Extension : introduction de l’incomparabilité

Même si les R_{i} sont des préordres complets, le théorème d’Arrow interdit l’existence d’une bonne méthode d’agrégation, à savoir une méthode fournissant un préordre complet vérifiant

• La règle de l’unanimité

• L’absence de dictateur

• La règle d’indépendance vis-à-vis de tierces altenatives

dès que l’on agrège plus de 2 critères.

Notre procédure d’agrégation fournit un rangement. Pour échapper au thèorème d’Arrow, on va affaiblir la structure de la relation résultante.

Lors du choix des probabilités de transition, on n’a pas fait la différence entre les cas A_{i} S A_{j} et A_{i} I A_{j} (indifférence ou préférence stricte).

S’il est raisonnable de maintenir la règle p_{ij} = 1/n dans le premier cas, on peut envisager un choix moins radical si A_{i} I A_{j}. Nous proposons dans ce as le choix p_{ij} = α/n, où α est un paramètre à choisir dans l’intervalle [0, 1].

La matrice est toujours rendue stochastique à l’aide des p_{i0}. Cela nous donne l’interprétation suivante :

• Je suis à l’état i.

• Je choisis au hasard un état j (équitablement).

• Si A_{i} S A_{j}, je passe à l’état j.

• Si A_{i} I A_{j}, je passe à l’état j avec une probabilité α et à l’état 0 avec une probabilité 1 − α.

• Sinon, je vais en 0. La méthode précédente est un cas particulier (α = 1). On peut également

adapter de façon semblable le cas multicritère.

On va mainteanant considérer la famille des rangements obtenus pour toutes les valeurs de α comprises entre 0 et 1. Nous l’exploitons de la façon suivante :

• Si A_{i} est classé avant A_{j} pour toutes les valeurs de α, on considére A_{i} supérieur à A_{j}.

• Si A_{i} est classé après A_{j} pour toutes les valeurs de α, on considére A_{i} inférieur à A_{j}.

• Sinon, on déclare A_{i} et A_{j} incomparables. Exemples :

• Ordre complet. ( \begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} )

• Préordre complet ( \begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix} )

• Ordre d’intervalle ( \begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix} )

• Semiordre ( \begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{matrix} )

Propriétés Si R est un préordre complet, le rangement obtenu ∀α ∈ [0, 1] est conforme à R.

Si R est un semiordre, le rangement obtenu ∀α ∈]0, 1[ est l’ordre strict associé à R.

Si R est un ordre d’intervalle, les rangements obtenus pour α tendant vers 0 et 1 sont les deux ordres stricts associés à R, ce qui implique au moins deux alternatives incomparables.

Utilisation Si l’on doit sélectionner la meilleur alternative, choisir parmi toutes celles se trouvant en tête pour une valeur de α (celles-ci étant incomparables entre-elles).

Plus un croisement est proche des extrémités 0 et 1, moins l’incomparabilité qu’il représente est forte.

Intérêt

• Méthode simple et intuitive.

• Pas de paramètre à fixer.

• Implémentation aisée.

• Visualisation d’une relation de préférence.

• Détecter les alternatives qui posent problème.

3 Illustrations

3.1 Relations de préférence

3.2 Choix d’un supermarché

4 critères : Prix, Accueil, Qualité et Situation.

3.3 Implantation d’une usine

5 critères : Prix, Transport, Environnement, Résidents, Compétition : notes. Calcul d’un semiordre pour chaque critère.

4 Conclusion

4.1 Exploitation de relation de préférence

• Principe intuitif

• Visualisation du résultat

• Pas de paramètre à fixer

• Implémentation aisée

4.2 Analyse multicritère

• Généralisation naturelle

• Analyse de sensibilité facile à réaliser

• Exploitation d’information cardinale possible

4.3 Perspectives

• Propriétés théoriques

• Utilisation sur relations valuées