Ba 3 Ba 3 [PDF]

Zitiervorschau

Université Sultan Moulay Slimane Ecole Nationale Supérieure de khouribga Cycle d’ingénieur en réseaux et télécommunication

Rapport de Mini Projet

Programmation Multicritères

Présenté par : Mr. EL MOUHTADI Walid

Encadrant :

Mr Pr. K. ISKAFI

1

Table des matières

Rapport de Mini Projet ............................................................................................................. 1 1.

Introduction générale : ..................................................................................................... 3

2.

Les méthodes d’analyse multicritère : ............................................................................... 4

3.

Les Principales Méthodes : ................................................................................................ 4

4.

Pourquoi plusieurs types de méthodes ? ........................................................................... 6

5.

Les étapes des résolutions d’une analyse Multicritère :..................................................... 6

6.

Illustration des méthodes multicritère : ............................................................................ 6

7.

La Réalisation pratique : .................................................................................................... 7

7.1.

Introduction : ....................................................................................... 7

7.2.

Problématique : ................................................................................... 7

7.3. Développement et réalisation de projet : .................................................. 9 7.4.

Partie code : ......................................................................................... 9

7.5.

Partie teste : ....................................................................................... 11

2

1. Introduction générale : L'aide à la décision multicritère constitue une branche d'étude majeure de la recherche opérationnelle impliquant plusieurs écoles de pensée, principalement américaine avec les travaux de Thomas L. Saaty et européenne avec ceux de Bernard Roy et du LAMSADE (Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision). Il s'agit de méthodes et de calculs permettant de choisir la meilleure solution ou la solution optimale parmi tout un ensemble de solutions, l'alternative de type OUINON n'étant qu'un cas particulier du cas général. Un abus de langage courant consiste à la confondre avec l'informatique décisionnelle (en anglais "business intelligence") et l'aide à la décision multicritère. L'informatique décisionnelle est dédiée à l'exploitation de données (query/reporting et data mining, principalement) destinée à l'élaboration de synthèses multi-niveaux. S’intéresse au choix parmi un nombre fini d'actions possibles (projet, investissement, décision, solution, plan, variante, candidat...) pour atteindre un objectif.

3

2. Les méthodes d’analyse multicritère :

Les méthodes d'analyse multicritère ont pour but la résolution des problèmes d'Aide à la décision multicritère. Elles constituent une étape importante du processus de décision, qui suit celle d'identification et de définition du problème, et aboutissent au choix d'une ou plusieurs solutions optimales (s), parmi un ensemble discret de solutions, via une procédure de sélection. Elles permettent également de répondre aux problématiques de tri et de rangement, par l'intermédiaire d'une procédure d'affectation et de classement respectivement. Ces méthodes sont issues principalement des travaux de Thomas L. Saaty et du chercheur Bernard Roy, créateur du LAMSADE (Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision). Elles sont confrontées à deux limites : l'une liée au manque de données fiables sur une durée suffisante, ce qui peut empêcher la construction ou la validation de la méthode ; l'autre liée à la technicité inhérente à de telles méthodes puisque ces dernières nécessitent l'usage de concepts délicats qui peuvent déboucher sur des résultats erronés ou une analyse confuse. Ces méthodes héritent également des problèmes informatiques, notamment celui de l'explosion combinatoire.

3. Les Principales Méthodes : WSM (Weight Sum Method) On utilise ici une échelle de 0 à 6 (excellent=6, très bon=5, bon=4, moyen=3, passable=2, pas bon=1, médiocre=0) Voici les résultats : Action 1 : 1 5 4 4 4 La somme est 18 Action 2 : 4 3 4 3 3 La somme est 17 Selon la somme des évaluations des critères, l’action 1 serait la meilleure, pourtant elle est loin de satisfaire le critère 1.

4

WPM (Weight Product Method) Cette méthode pénalise fortement les actions très mauvaises pour un critère Voici par exemple 3 actions potentielles et 3 critères Action 1: 1 5 4 4 4 e1=(1/5)*(5/8)*(4/8)*(4/7)*(4/7)=0,0204 Action 2: 4 3 4 3 3 e2=(4/5)*(3/8)*(4/8)*(3/7)*(3/7)=0,0276. AHP (Analytic Hierarchy Process) • Décomposer le problème complexe en une structure hiérarchique (niveaux) • Effectuer les combinaisons binaires • Déterminer les priorités • Synthétiser les priorités • Cohérence des jugements. ELECTRE (Outranking method) • Famille de méthodes dites de surclassement conçues par Bernard Roy et basées sur la comparaison d’actions • Première méthode de la famille, Electre I, publiée en 1968 • Cette méthode repose sur le principe de Condorat (1785): – Une action en surclasse une autre si elle est au moins aussi bonne que l’autre relativement à une majorité de critères, sans être nettement plus mauvaise que cette autre relativement aux autres critères • On s’intéresse donc à chaque action de l’ensemble et on la compare à toutes les autres • La comparaison se fait par paire ordonnée (a p/r b ≠ b p/r a) et on se demande alors si l’action a surclasse ou non l’action b.

5

4. Pourquoi plusieurs types de méthodes ? On a déjà listé les solutions probables, on a fixé les critères de jugements et comment noter ces solutions, alors quoi de plus ? Si vous devez choisir la couleur de votre mur, probablement vous aurez un choix à faire du type : bleu, un peu plus bleu, un peu moins bleu, plus clair, moins clair …… pas simple, car vous n’avez pas une solution en réalité vous en avez une infinité. Autre situation, vous devez choisir un nouveau tracé pour la route d’évitement de votre village, impossible de mettre les participant à la décision d’accord sur les critères, leurs poids respectifs, et la façon de moduler les notes des solutions. Dernier cas, vous êtes jurés à un examen vous devez rendre une note sur les travaux selon des critères de savoir. Pour chacun des exemples présentés, vous comprenez que l’approche, le type de méthode de recherche ne sera pas pareil.

5. Les étapes des résolutions d’une analyse

Multicritère :  La détermination des alternatives et des critères de décision pertinents  La fixation des mesures numériques d’importance relative (poids) et des performances des alternatives vs les critères définis  Le traitement des valeurs numériques pour classer les alternatives.

6. Illustration des méthodes multicritère : Nous présentons dans ce qui suit trois méthodes multicritères, en fonction de la problématique considérée. La première méthode Electre I, est préconisée pour répondre à une problématique de choix. La méthode Electre-Tri est préconisée pour les problématiques de tri ou d’affectation. La méthode Electre III est utilisée pour répondre à des problématiques de rangement ou de classement.

6

7. La Réalisation pratique :

7.1.

Introduction :

Electre-tri est une méthode qui permet de résoudre des problèmes d’affectation, le principe de la méthode est d’assigner un ensemble de m d’alternatives ou d’actions noté A= {a1, a2, a3,…,am} sur lesquelles se base la décision à des catégories ou classes bien définies. On note l’ensemble F= {1,2,…, n} l’ensemble des indices des critères. Chaque action de l’ensemble A sera évaluée par une fonction réelle, exprimant l’évaluation de l’action pour un critère donné, on note G= {g1, g2,…, gn} l’évaluation de l’action pour les critères considérés. L’importance des critères dans la prise de décision est évaluée par un ensemble de poids K= {k1, k2,…, kn}. Par opposition aux autres approches, les alternatives qui constituent l’objet de la décision ne sont pas comparées entre elles, mais à des seuils traduisant la frontière entre les h classes prédéfinies, noté C= {C1, C2,…, Ch}. Chaque alternative sera comparée aux frontières de chaque catégorie, formant un profil B= {b1, b2, b3,…, bh}. La Figure 2 illustre la problématique de tri ou d’affectation.

7.2.

Problématique :

L’exemple traite de la mise en place d’une démarche de gestion patrimoniale des réseaux d’assainissement. A partir d’inspections caméra des tronçons d’assainissement, on définit un ensemble de critères pour décrire l’état des tronçons, 5 critères1 sont considérés comme suit : o Cr1 : Bouchage du tronçon

7

o Cr2 : Effondrement de la paroi du tronçon o Cr3 : Ensablement du tronçon o Cr4 : Détérioration de la capacité hydraulique o Cr5 : Présence d’infiltrations L’analyse multicritère vise à définir des classes homogènes de tronçons en fonction de leur état. En concertation avec le gestionnaire du réseau, trois classes sont définies état : « Bon », « Moyen » et « Mauvais ». La problématique posée étant une problématique d’affectation, on utilise Electre-tri pour affecter les tronçons aux catégories définies. On considère un ensemble de tronçon à classer, les performances de chaque tronçon sont contenues dans le Tableau 9. Tableau 9. Evaluation des critères, tableau de performances. Tronçons T1 T2 T3 T4 T5

Cr1 2.63 0 0 0 0

Cr2 5.26 0 10.13 0 210.53

Cr3 52.63 492.31 20.25 0 280.7

Cr4 84.21 492.31 20.25 0 280.7

Cr5 26.32 0 405.06 0 1171.93

Comme l’affectation se fait dans 3 catégories distinctes, deux profils b1 et b2 sont définis, où b1 représente la frontière entre la classe état « Bon » et état « Moyen », et b2 la frontière entre la catégorie état « Moyen » et état « Mauvais ». La valeur des seuils et poids des critères sont définis dans le Tableau 10.

Tableau 10. Définition des seuils et poids des critères. G (b1) Qj (b1) Pj (b1) G (b2) Qj (b2) Pj (b2) kj

Cr1 0.5 0.5 1 7 0.5 1 0.1

Cr2 2.23 0.5 1 29 0.5 1 0.35

Cr3 37.53 0.5 1 126.7 0.5 1 0.1

8

Cr4 37.96 0.5 1 128 0.5 1 0.1

Cr5 40.67 0.5 1 300 0.5 1 0.35

L’implémentation du cas d’étude sur le Logiciel ELECTRE-TRI® permet d’obtenir une affectation des tronçons selon deux procédures : pessimiste et optimiste, le résultat de l’affectation est présenté dans le Tableau 11.

Tableau 11. Résultat de l’affectation. Procédure d’affectation

7.3.

Tronçons

Procédure pessimiste

Procédure optimiste

T1

Moyen

Bon

T2

Bon

Bon

T3

Mauvais

Moyene

T4

Bon

Bon

T5

Mauvais

Mauvais

Développement et réalisation de projet :

Pour faire une réalisation pratique on a besoin d’une programmation multicritère par une méthode parmi les méthodes de programmation multicritère j’ai utilisé Electre-Tri à l’aide de logiciel de programmation «python» dans ce cas-là par ce que nous sommes dans un problématique d’affectation.

7.4.

Partie code :

#!/usr/bin/python # -*- coding: utf-8 -*from __future__ import division # biblio https://engees.unistra.fr/fileadmin/user_upload/pdf/gsp/Cours_MCDA_AN.pdf Criteres = [ 'Cr1', 'Cr2', 'Cr3', 'Cr4', 'Cr5' ] #//liste = tableau une deminsiion Poids = { 'Cr1':0.1, 'Cr2':0.35, 'Cr3':0.1, 'Cr4':0.1, 'Cr5':0.35 } #//dictionnaire qui contient "cle , valeur"

9

Actions = [ 'T1', 'T2', 'T3', 'T4', 'T5' ] Performances = { 'T1': { 'Cr1':2.63, valeurs 'T2': { 'Cr1':0.00, 'T3': { 'Cr1':0.00, 'T4': { 'Cr1':0.00, 'T6': { 'Cr1':0.00,

'Cr2':

5.26, 'Cr3': 52.63, 'Cr4': 84.21, 'Cr5':

'Cr2': 0.00, 'Cr2': 10.13, 'Cr2': 0.00, 'Cr2':210.53,

'Cr3':492.31, 'Cr3': 20.25, 'Cr3': 0.00, 'Cr3':280.70,

'Cr4':492.31, 'Cr4': 20.25, 'Cr4': 0.00, 'Cr4':280.70,

26.30 }, #//T1 se forme de 5

'Cr5': 0.00 'Cr5': 405.06 'Cr5': 0.00 'Cr5':1171.93

}, }, }, } }

Classes = ['Bon', 'Moyen', 'Mauvais' ] Seuils = { # seuils (g,q,p) de Bon - Moyen 'Bon': { #//élement de dictionnaire de seuils 'Cr1': ( 0.50, 0.5, 1.0), #//clé de 3 valeurs 'Cr2': ( 2.23, 0.5, 1.0), 'Cr3': (37.53, 0.5, 1.0), 'Cr4': (37.96, 0.5, 1.0), 'Cr5': (40.67, 0.5, 1.0) }, # seuils (g,q,p) de Moyen - Mauvais 'Moyen': { 'Cr1': ( 7.0, 0.5, 1.0), 'Cr2': ( 29.0, 0.5, 1.0), 'Cr3': (126.7, 0.5, 1.0), 'Cr4': (128.0, 0.5, 1.0), 'Cr5': (300.0, 0.5, 1.0) } } Lambda = 0.76 def Concordance(a, bh): 2 argement a et bh #//la boucle pour determiner Bon et moyenne for critere in Criteres: poids = Poids[critere] ga = Performances[a][critere] gbh,qbh,pbh = Seuils[bh][critere] if gbh - ga >= pbh: conc = conc + 1.0 * poids elif gbh - ga