Optimisation multicritère pour la gestion d'un réseau d'AEP

CHAPITRE III

Méthodes d'optimisation multicritère

III.1 Introduction :

Dans de très nombreux cas impliquant une décision, on entend fréquemment les principaux responsables parler de solution optimale. L'optimisation multicritère a pour but de résoudre des problèmes de décision en présence de critères d'optimalité multiples.

Du fait que ces critères se trouvent souvent en conflit, il n'existe pas de solution unique qui s'impose d'elle-même. L'aide multicritère à la décision et son formalisme jouent un rôle structurant, qui permet de mieux appréhender le problème et faciliter le processus de décision.

III. 2 Les méthodes d'optimisation multicritère [21]

On distingue trois grandes familles de méthodes d'optimisation multicritère :

III.2.1 La théorie de l'utilité multi-attribut

Cette théorie repose sur le principe suivant : le scientifique pose des questions parfois difficiles et pertinentes au décideur. Les réponses de ce dernier lui permettent de maximiser ou minimiser une fonction U = U(g1, g2, ...g_n) en posant des hypothèses mathématiques trop fortes. (g1, g2, ...g_n sont les points de vue pris en compte par le décideur).

III.2.2 Les méthodes de surclassement

Contrairement à la théorie précédente, les méthodes de surclassement permettent à l'homme d'étude d'éviter l'introduction des hypothèses mathématiques trop fortes et les questions difficiles pour le décideur. Dans ces méthodes, l'homme d'étude essaye d'enrichir la relation de surclassement (dominance) par des éléments peu discutables, c'est-à-dire par les préférences solidement établies du décideur.

III.2.3 Les méthodes interactives

Elles consistent en une alternance d'étapes de calculs et de dialogue avec le décideur. La première étape de calcul fournit une première solution. Le décideur réagit à cette solution en apportant des informations supplémentaires sur ses préférences (étape de dialogue). Ces informations sont injectées dans le modèle utilisé par l'homme d'étude et permettent de fournir une nouvelle solution (nouvelle étape de calcul). Cette alternance d'étapes se poursuit jusqu'à atteindre la solution optimale.

Le schéma suivant présente les différentes approches opérationnelles et méthodes d'optimisation multicritère :

Notes scolaires

Théorie de l'utilité multi- attribut

Approche opérationnelle du critère unique de synthèse. Agrégation complète

		Approche opérationnelle de surclassement de synthèse.
		Agrégation partielle.

	ELECTRE

QUALIFEX

PROMETHEE

Approche opérationnelle du jugement local et interactif.

Agrégation local et itérative.

UTA interactive

PREFCALC

Fig.(III.1) : Approches opérationnelles et méthodes [15]

III.3 Concepts de base d'un problème multicritère III.3.1 Action et ensemble des actions potentielles [15, 21]

Les éléments de réponse qu'un décideur attend de l'aide à la décision ont trait aux diverses actions qu'il peut envisager. Selon la nature des problèmes, ces actions peuvent se présenter de diverses manières :

- Sites pour une localisation,

- Réponses à un appel d'offre,

- Plan d'aménagement,

- Gestion des divers réseaux (eaux, télécommunications, gaz et électricité) - Etc.

Pour la clarté du travail d'aide à la décision, il est utile d'introduire les distinctions suivantes :

Action potentielle : c'est une action provisoirement jugée possible par un des intervenants au moins ou présumée telle par l'homme d'étude en vue de l'aide à la décision.

Action globale : c'est une action dont la mise à exécution est exclusive de toute autre action. Dans le cas contraire, on parle d'action fragmentaire.

Action de référence : c'est une action servant de référence par rapport à laquelle les actions potentielles sont examinées. Les actions de référence servent de limites à des catégories auxquelles les actions potentielles sont affectées.

L'ensemble des actions potentielles : c'est l'ensemble des objets, décisions, candidats, ... que l'on va explorer dans le processus de décision. Il est désigné par A = (a1, a2, ..., ai, ... a_n) où les ai sont les actions potentielles. Cet ensemble peut être défini:

· En extension (par énumération de ses éléments) lorsqu'il est fini et suffisamment petit pour que l'énumération soit possible.

· En compréhension (par une propriété caractéristique ou par des contraintes mathématiques) lorsqu'il est infini ou fini mais trop grand pour que l'énumération soit possible.

L'ensemble A peut aussi être :

· Stable : s'il est défini à priori et n'est pas susceptible d'être changé au cours de la procédure.

· Évolutif : s'il peut être modifié en cours de procédure, soir à cause des résultats intermédiaires que cette procédure fait apparaître, soit parce que le problème de décision pose un environnement changeant.

III.3.2 Critères et famille cohérente de critères

Un critère peut être défini comme un outil qui permet la comparaison des actions selon un point de vue. Lorsque le problème repose sur la considération de plusieurs critères, nous les notons g1, g2, ... gj, ... g_m. L'évaluation d'une action ai suivant le critère j est notée gj(ai).

On appelle famille cohérente de critères F = (gj : j = 1 .. m), l'ensemble de tous les critères pris en considération.

III.3.3 Poids des critères

L'importance donnée par le décideur à chacun des critères n'est pas toujours la même. Les méthodes d'aide à la décision traduisent cette importance relative par des nombres, souvent appelés « poids ». L'ensemble des poids est noté : P = (Pj ; j = 1. .m). Si par exemple Pj = 2Ph, cela signifie qu'il attribue deux fois plus d'importance au critère j qu'au critère h.

III.3.4 La problématique d'aide à la décision [18]

La problématique est la façon dont le problème de décision est posé. En matière d'aide à la décision, il est préférable, dans bien des cas, de chercher, au moins au départ, à formuler le problème en termes moins restrictifs. Dans cette optique, quatre problématiques de référence doivent être considérées, à savoir :

> Déterminer un sous-ensemble d'actions considérées comme les meilleures actions vis-à-vis de F (problème de choix),

> Partitionner A en sous-ensembles suivant des normes préétablies (problème de tri),

> Ranger les actions de A de la meilleure à la moins bonne (problème de rangement).

Dans cette optique, quatre problématiques de référence sont considérées :

Problématique	Objectif	Résultat		Procédure	·
Choix d'un sous-ensemble contenant les actions	Choix	Sélection
« les meilleures » ou à défaut, « satisfaisantes »				·
Tri par affectation des actions à des catégories prédéfinies	Tri	Affectation
Rangement de classes d'équivalence, composées d'actions, ces classes étant données de façon complète ou partielle	Rangement	Classement		·
Éclairer la décision par une description, dans un langage approprié, des actions et de leurs conséquences	Description	Cognition

Tableau (III-1) : Problématiques de référence[15]

III.3.5 Les résultats

L'appréciation de chacune des actions ai sur chacun des critères gj donne lieu à un résultat gj(ai). L'évaluation des résultats peut être quantitative, qualitative ou ordinale. Le tableau suivant résume tous les éléments constitutifs d'un problème multicritère déjà cités :

		Critères						Actions
Critère 1		Critère 2	...	Critère j	...	Critère m	a1
g1(a1)		g2(a1)	...	gj(a1)	...	gm(a1)	a2
g1(a2)		g2(a2)	...	gj(a2)	...	gm(a2)	...
...		...	...	...	...	...	ai
g1(ai)		g2(ai)	...	gj(ai)	...	gm(ai)	...
...		...	...	...	...	...	an
g1(an)		g2(an)	...	gj(an)	...	gm(an)	Poids
P1		P2	...	Pj	...	Pm

Tableau (III-2) : Éléments constitutifs d'un problème multicritère [16]

III.4 Formulation mathématique d'un problème de décision multicritère On appelle problème multicritère le couple (A, F), où :

- A est un sous-ensemble de Rⁿ appelé ensemble des actions potentielles ;

n

- F une fonction vectorielle g : AR R

? n ? , qui a toute action ai A associe un

vecteur g(ai) = (g1(ai), g2(ai), ..., g_m(ai)).

Les fonctions gj : A ? R, j = {1, 2,.. .m} sont appelés critères ou fonctions

objectifs.

Le décideur a pour objectif d'obtenir des valeurs optimales (maximales ou minimales pour chaque fonction objectif ; autrement dit, trouver la meilleure solution

j=1,...m a* i telle que g ( a ) = opt ( g j ( a i ) ) * A j i , a i A

donc une meilleure action.

III.5 Les méthodes ELECTRE [15]

Les méthodes d'analyse multicritère ont été développées suites aux besoins qui se sont fait sentir dans le domaine de l'aide à la décision. Les projets de grande envergure, en effet, nécessitent des choix qui font bien souvent intervenir des critères peu compatibles. Pour résoudre ce genre de problème, il faut donc faire appel à des méthodes de formalisation qui permettent d'effectuer des classements entre les diverses décisions. C'est le but des méthodes ELECTRE (Élimination Et Choix Traduisant Réalité) qui ont été mises au point par B. ROY. Ces méthodes se servent :

- D'une hypothèse de surclassement,

- D'une notion de concordance et de non-discordance.

Relation de surclassement

Une action ai surclasse une action ak, s'il est possible d'affirmer : ai est au moins aussi bonne que ak.

Concordance

Si l'hypothèse ai surclasse ak est émise, il est dit du critère j qu'il concorde avec l'hypothèse si : gj(ai)=gj(ak).

Non-discordance

La condition de non-discordance permet de refuser une hypothèse de surclassement, obtenue après application de la condition de concordance, lorsqu'il existe une opposition trop forte sur un critère au moins.

III.5.1 ELECTRE I

La méthode ELECTRE I relève de la problématique á (procédure de sélection) : il s'agit de choisir la meilleure action parmi plusieurs.

Au moyen de la relation de surclassement S, il est nécessaire d'effectuer une partition de l'ensemble A des actions potentielles en deux sous-ensembles N et A\N complémentaires tel que :

· Toute action appartenant à A\N est surclassée par au moins aune action appartenant à N ; les actions de A\N sont éliminées.

· Les actions appartenant à N sont incomparables entre elles ; ce sont les actions sélectionnées.

Pour tout couple d'actions (ai, ak), on définit un indice de concordance et un indice de discordance. Il est d'abord utile de définir les paramètres suivants :

· ( ) { ( ) ( ak ) }

J + ai, a_k = j F/ g_j ai > g_j : l'ensemble des critères pour lesquels l'actions ai

est préférée à l'action ak.

· ( ) { ( ) ( a k ) }

J = a _i , a k = j F / g j a i = g _j: l'ensemble des critères pour lesquels l'actions ai est équivalente à l'action ak.

· ( ) { ( ) ( ak ) }

J a _i , a k = j F /g j j

ai < g : l'ensemble des critères pour lesquels l'actions ak

est préférée à l'action ai.

· p ( a , a ) = ‡» p , j

+ +

J ( a , a )

i k j : la somme des poids des critères appartenant à

i k

l'ensemble j ⁺(ai, ak).

· p ( a , a ) = ‡» p , j
= J ( a _i , a k )

=

i k j : la somme des poids des critères appartenant à

l'ensemble j⁼(ai, ak).

· p (ai, ak)= ‡»pj, j J (ai, ak) : la somme des poids des critères appartenant à

l'ensemble j^-(ai, ak).

· P = P⁺(ai, ak) + P⁼(ai, ak) + P^-(ai, ak)

L'indice de concordance :

p ( a , a ) + p ( a , a )

+ =

C = i k

p

i k

ik

0 sij (a,a)=0

i k

L'indice de discordance :

D =

^{ik 1}max { g (a ) g (a ) ; j

j k j i i k

j (a ,a )

ä

ä : amplitude de l'échelle associée au critère j pour lequel il existe le maximum de désaccord.

S est acceptée si _Cik ^et _Dik sont respectivement supérieur ou égal et inférieur à des seuils qu'il ne faut pas dépasser, notés respectivement c et d.

III.5.2 ELECTRE II

La méthode ELECTRE II relève de la problématique ã (procédure de classement) ; sont but est de classer les actions potentielles depuis les meilleures jusqu'aux moins bonnes, en tolérant les ex æquo.

ELECTRE II utilise deux sortes de classements :

· surclassement fort : ai SF ak, concerne les surclassements avancés avec une grande certitude.

· surclassement faible : ai Sf ak, concerne les surclassements qui sont sujets à caution.

Condition de concordance : Trois seuils de concordance (au lieu d'un seul dans ELECTRE I) sont définis ; ils sont noté : c⁺, c0, c^- et suivent toujours l'ordre : c⁺= c⁰= c^-.

Le test de concordance est satisfait si :

+

c c ou

=

ik

0

c c ou

=

ik

c ik = c -

+

et 1

p a a

- ( , ) >

i k

p a a

( , )

i k

?

?

?

?

??

Test de non-discordance

Deux seuils de discordance sont définis : D1 et D2 tel que D1<D2.

Le test de discordance peut se résumer, pour j ? j^-(ai, ak), comme suit :

· Si gj(ak) - gj(ai) = D2, alors il y a une certitude forte que le critère j ne présente pas une opposition majeure à l'hypothèse de surclassement.

· Si gj(ak) - gj(ai) = D1, alors il y a une certitude faible que le critère j ne présente pas une opposition majeure à l'hypothèse de surclassement.

Établissement de la relation de surclassement

Deux classements différents des actions sont opérés :

- Classement direct : les actions sommets du graphe sont classées en fonction de la longueur des chemins incidents qui y aboutissent, dans l'ordre croissant de ces longueurs.

- Classement inverse : les sommets sont classés en fonction de la longueur des chemins qui sont issus, dans l'ordre décroissant des longueurs.

III.5.3 ELECTRE III

La méthode ELECTRE III relève aussi de la problématique ã (procédure de classement). Dans l'hypothèse de surclassement, une nouvelle notion est introduite, celle de préférence faible qui marque l'hésitation entre l'indifférence et la préférence stricte. Pour chacun des critères, ces trois relations sont séparées par deux seuils dits d'indifférence (q) et de préférence stricte (p). Un troisième seuil, le seuil de veto, est utilisé dans la concrétisation de la notion de discordance. La méthode ELECTRE III utilise aussi la notion de pseudo-critère.

Pseudo-critère

Un pseudo-critère est une fonction g dont le pouvoir discriminant est caractérisé par les deux seuils q(g) et p(g) tels que :

q g a q g a et 1

( ( )) ( ( )) = -

k i

- p g a p g a

( ( )) ( ( )) = -

k i

-

1

g a g a

( ) ( )

k i

- g a g a

( ) ( )

k i

-

Indice de concordance

ELECTRE III utilise deux indices pour la concordance : indice de concordance par critère et indice de concordance globale.

· Indice de concordance par critère : noté Cj(ai, ak), affirme dans quelle mesure l'action ai est au moins aussi bonne que l'action ak. Il est définit comme suit :

( ) ( ) ( )

g a g a +p

j i j k j

c a , a = Min 1 , Max 0,

j i kpq

j j

· Indice de concordance globale : noté _Cik, affirme dans quelle mesure il y a concordance avec l'hypothèse l'action ai surclasse l'action ak. Il est défini par la

m

j=1 j j

‡» p x c

c= ik

( )

a , a

i k

^m ‡»p

j=1 j

formule suivante :

· Indice de discordance ( ) d a , a = Min 1 , Max 0, j i k		g a g a p ( ) ( ) j i j k j

Degré de crédibilité :

Il existe des couples d'actions où la relation de surclassement paraît très peu convaincante. On définit alors un degré de crédibilité de surclassement :

1 d a ,a

j i k

( )

ä ik ik Ð avec : F= { j/j

=c ik F, dj(ai,ak) > c ik} et F 1/2 F

j F

1 c

III.5.4 ELECTRE TRI

III.5.4.1 Principe de la méthode

La méthode ELECTRE tri relève de la problématique â (procédure

d'affectation) : le problème est posé en terme d'attribution de chaque action à une catégorie prédéfinie.

Des actions de référence sont utilisées pour segmenter l'espace des critères en catégories : chaque catégorie est bornée inférieurement et supérieurement par deux actions de référence.

Cette méthode suit la procédure d'ELECTRE III jusqu'aux degrés de crédibilité. Pour déceler l'incomparabilité, deux procédures d'affectations distinctes, appelées optimiste et pessimiste, sont nécessaires : elles consistent à comparer chaque action potentielle avec les actions de référence en commençant par la plus contraignante, respectivement la moins contraignante. Si les deux procédures affectent l'action potentielle à la même catégorie, elle est alors parfaitement comparable avec les actions de référence ; sinon en fonction de la différence entre les deux catégories auxquelles elle est attribuée, elle est plus ou moins incomparable.

III.5.4.2 Développement de la méthode

Définition des actions de référence

Deux manières de définir les actions de référence sont envisageables :

· La première consiste à les définir en dehors de toute considération sur les actions potentielle. On peut parler alors de problématique â stricte.

· La seconde consiste à vouloir classer les actions potentielles non plus les une par rapport aux autres, mais par groupe. Si un classement est souhaité, rien n'empêche d'appliquer une méthode relevant de la problématique ã aux actions appartenant à une même catégorie. Deux actions de référence b⁰ et b^k sont définies de manière à borner inférieurement la catégorie la plus basse, et supérieurement la catégorie la plus haute respectivement.

Indice de concordance par critère : ( ) ( ) ( )

k

k j i j

g _a ^g _b +p _j

c a , b = Min 1 , Max 0,

j ipq

j j

Indice de concordance globale :

m ‡» p x c j j j=1

( )

a , b ^k

i

c= ik

^m ‡»p

j=1 j

Indice de discordance par critère: ( ) ( ) ( )

g a g b p

k

j

j i j

d a , a = Min 1 , Max 0,

j j

j i kv p

1 d a , b

( )

k

j i

Degrés de crédibilité : ä =c Ð

ik ik avec :

1 c ik

j F

F={j/j F, dj(ai,ak)>cik} et F 1/2 F

Établissement de la relation de surclassement floue :

La relation de surclassement entre une action potentielle a et une action de référence b est établie à partir des degrés de crédibilité et d'un seuil de coupe ë constant comme le montre le schéma suivant :

ó s ( a , b ) = ë

ós(b,a) =ë

ós(b,a)=ë

non oui

non

oui non oui

aRb b > a a>b aIb

Fig.(III.2) : Etablissement de la relation de surclassement pour ELECTRE TRI [15]

Procédure d'affectation

Avant d'aborder les procédures d'affectation optimiste et pessimiste, sept exigences doivent être respectées :

· Aucune action potentielle ne peut être indifférente à plus d'une action de référence.

· Toute action potentielle doit être attribuée à une et une seule catégorie (unicité).

· L'affectation d'une action potentielle ne dépend pas de l'affectation d'autres actions (indépendance).

· L'affectation des actions potentielles aux catégories doit être conforme à la conception des actions de référence (conformité).

· Lorsque deux actions se comparent de manière identique avec les actions de référence, elles doivent être affectées à la même catégorie (homogénéité).

· Si ai domine l'action ak, alors ak doit être affectée à une catégorie supérieure ou égale à celle de ai (monotonicité).

· Le regroupement de deux catégories voisines ne doit pas modifier l'affectation des actions aux catégories non concernées (stabilité).

Les caractéristiques des deux procédures d'affectation sont détaillées dans le tableau suivant :

Procédure d'affectation	pessimiste		Optimiste	Objectif
Pousser les actions dans les catégories les plus basses possibles.	Pousser les actions dans les catégories les plus hautes possibles		Procédure
Affecter l'action à une catégorie de façon telle que cette action surclasse l'action de référence basse de cette catégorie : aSb^h· a Ch+1	Affecter l'action à une catégorie de façon telle que l'action de référence haute de cette catégorie soit préférée à l'action : bh Sa · a Ch		Sens
De haut en bas	De bas en haut

Tableau III-3 : caractéristiques des procédures d'affectation[15]

Le cheminement d'ELECTRE TRI est représenté est représenté par l'organigramme suivant :

Problèmes objectifs

Ensemble des actions
de référence et des
catégories

Ensemble des actions
potentielles

Matrice des évaluations

Famille cohérente
de pseudo-critères

Degrés de crédibilité

Indices de
concordance par
critère

Coefficients
d'importance
(poids)

Hypothèse de
surclassement

Indice de
concordance
globale

Indices de
discordance par
critère

Seuils de veto

Recommandations

Fig.(III.3) : Algorithme de la méthode EECTRE TRI [15]

III.6 Conclusion

L'approche de surclassement de synthèse (méthodes ELECTRE) constitue une famille de méthodes d'aide multicritère à la décision très efficaces pour la comparaison d'actions potentielles.

Pour notre étude, nous avons choisi d'appliquer le méthode ELECTRE TRI. Cette méthode est très intéressante car elle permet de considérer un nombre d'actions

potentielles très important que les autres méthodes ELECTRE. Elle permet aussi de classer les actions en catégories et de comparer les actions non plus entre-elles, mais par rapport à une référence stable, ce qui n'est pas le cas pour les autres méthodes ELECTRE.

L'étape suivante de notre étude sera consacrée à la définition des actions potentielles et à la modélisation des critères de décision, en se basant sur les principes de la méthode ELECTRE TRI. Ce sera l'objet du chapitre suivant.