29
L’Aide à la Décision Multicritère Enjeux, Méthodes et Exemples Vincent T’KINDT Laboratoire d’Informatique (EA 2101) Dépt. Informatique - Polytech’Tours Université François-Rabelais de Tours – France [email protected]

Vincent T'KINDT - Aide à la décision multicritère

Embed Size (px)

DESCRIPTION

Enjeux, Méthodes et Exemples

Citation preview

  • 1. LAide la Dcision Multicritre Enjeux, Mthodes et Exemples Vincent TKINDT Laboratoire dInformatique (EA 2101) Dpt. Informatique - PolytechTours Universit Franois-Rabelais de Tours France [email_address]

2. Prambule

    • Aide quunHomme dEtudespeut apporter pour permettre unDcideurde prendre une dcision en fonction de plusieurs critres dvaluation

Vincent Tkindt Modlisation Rsolution Quentend-on par Aide la Dcision Multicritre ?

    • Recherche Oprationnelle et Aide la Dcision sont deux faces indissociables dune mme mdaille [Roy, 2006]

Techniques mathmatiques et informatiques permettant de rsoudredes problmes doptimisation Techniques permettant de formaliser un problme, les prfrences du Dcideur et les dcisions quil peut tre amen prendre Aide la Dcision Multicritre Aide la Dcision Multicritre Recherche Oprationnelle 3. Prambule Vincent Tkindt Anna est proche de son argent Bob aime le bon vin Problme : Comment choisir le vin ? Quest-ce qui compte pour vous? Anna => le prix, Bob => la qualit. Quel est le prix maximum que vous souhaitez y mettre? Anna => au plus 10 euros, Bob => plutt 30 euros, Anna => ok pour 20 euros. Le Dcideur LHomme dEtudes Le problme de dcision Modlisation des prfrences 4. Prambule Vincent Tkindt Voici ce que propose notre carte (vins blancs): Carbonnieux (Graves), 1993 Haut-Brion (Graves), 1992 Meurseault Drouhin, 1992 Gaston Huet (Vouvray), 1990 Z 1 =15 euros et Z 2 =3 Z 1 =20 euros et Z 2 =3 Z 1 =18 euros et Z 2 =5 Z 1 =12 euros et Z 2 =4 5. Prambule Vincent Tkindt

  • Un processus dAide la Dcision implique forcment un Dcideur et un Homme dEtude,
  • Il nexiste pas forcment une solution optimale unique voir pas de solution optimale,
  • Limportant est de pouvoir obtenir les prfrences du Dcideur.

6. Contenu Vincent Tkindt

  • Les concepts fondamentaux de lAide la Dcision Multicritre,
  • LOptimisation Multicritre,
  • Exemples.

7. Concepts fondamentaux Vincent Tkindt

  • LAide la Dcision Multicritre propose un cadre gnral pour conduire lHomme dEtude dans son travail de conseil,
  • L Homme dEtude peut tre un acteur humain ou un logiciel dAide la Dcision,

8. Concepts fondamentaux Vincent Tkindt

  • Les problmatiques dAide la Dcision peuvent tre spares en quatre catgories,

Le choix dune meilleure dcision Trac 1 Trac 2 Trac 3 Trac 4 Choix dun tracdautoroute Trac 2 9. Concepts fondamentaux Vincent Tkindt

  • Les problmatiques dAide la Dcision peuvent tre spares en quatre catgories,

Le tri de dcisions Trac 1 Trac 2 Trac 3 Trac 4 Tri des tracsdautoroute Tracs faible cot Tracscologiques Trac 1 Trac 4 Trac 2 Trac 3 10. Concepts fondamentaux Vincent Tkindt

  • Les problmatiques dAide la Dcision peuvent tre spares en quatre catgories,

Le rangement de dcisions Trac 1 Trac 2 Trac 3 Trac 4 Rangement des tracsdautoroute Tracsconsensuels Trac 1 Trac 4 Trac 2 Trac 3 Plus Moins 11. Concepts fondamentaux Vincent Tkindt

  • Les problmatiques dAide la Dcision peuvent tre spares en quatre catgories,

La description des dcisions

  • Quest-ce quun trac dautoroute ? Quels sont les impacts dun trac ?
    • Impact conomique,
    • Impact socital,
    • Impact cologique,

12. Concepts fondamentaux

  • Dfinition des prfrences du Dcideur
  • Dfinition des consquences puis des critres dvaluation,

Vincent Tkindt

  • Pour une problmatique donne,
  • Dfinition de lensemble des dcisions possibles,

Le problme est pos et on sait comment prendre en compte les prfrences du Dcideur

  • Quels sont les impacts dun trac ?
    • Impact conomique,
    • Impact socital,
    • Impact cologique,

Trac 1 Trac 2 Trac 3 Trac 4 Critre environnemental Le systme relationnel de prfrences Trac 1 Trac 2 Trac 3 Trac 4 13. Concepts fondamentaux

  • Dduction partir du systme relationnel de prfrence de solutionsde meilleurs compromis.

Vincent Tkindt

  • Pour une problmatique donne,
  • Mise au point dun algorithmede rsolution,
  • OU

Dpend du nombre de dcisions Si ce nombre est trop grand alors on se dirigera plus vers lutilisation de techniques de Recherches OprationnellesDans tous les cas, cest le Dcideur qui choisit au final, pas lalgorithme de rsolution. 14. Concepts fondamentaux Vincent Tkindt

  • Quelques mthodes dAide la Dcision Multicritre,
    • MAUT ([Von Neumann et Morgenstern, 1954])
      • UTA ([Jacquet-Lagrze et Siskos, 1982]),
      • Analytic Hierarchy Process ([Saaty, 1986]),
    • Les mthodes Electre,
    • Promethee,
    • Mthodes de loptimisation multicritre,
    • [Figueira et al., 2005] J. Figueira, S. Greco et M. Erghott. Multiple Criteria Decision Analysis: State-of-the-art surveys, International Series on Operations Research and Management Sciences, Springer.

15. LOptimisation Multicritre Vincent Tkindt

  • Un Problme dOptimisation Multicritre (POM) peut tre dfini comme suit :

Minimiser Z 1 (x) Minimiser Z 2 (x) Minimiser Z K (x) Sous contrainte xS Trouver une solution (dcision) qui minimise K critres dvaluation Z i . Cette solution existe-t-elle ? [Tkindt et Billaut, 2006] V. Tkindt et JC Billaut. Multicriteria Scheduling: Theory, Models and Algorithms, 2 ndedition, Springer. 16. LOptimisation Multicritre Vincent Tkindt

  • Un Problme dOptimisation Multicritre (POM) peut tre dfini comme suit :

Carbonnieux (Graves), 1993 Haut-Brion (Graves), 1992 Meurseault Drouhin, 1992 Gaston Huet (Vouvray), 1990 Z 1 =15 euros et Z 2 =3 Z 1 =20 euros et Z 2 =3 Z 1 =18 euros et Z 2 =5 Z 1 =12 euros et Z 2 =4 17. LOptimisation Multicritre Vincent Tkindt

  • Notion doptimalit : les optima de Pareto,

Z 2 Une solution x est un optimum dePareto strictssi il nexiste pas une autre solution y telle que Z i (y) Z i (x), i=1, ,K, avec au moins une ingalit stricte. Z 1 18. LOptimisation Multicritre Vincent Tkindt

  • Deux questions fondamentales :
    • Comment calculer un optimum de Pareto (de prfrence strict) ?
    • Quel est le meilleur optimum de Pareto pour le Dcideur ?

Cela dpend des prfrences du Dcideur !

    • Comment sexpriment ses prfrences ?
    • Avec quelle fiabilit peut-il les exprimer ?

Nous sommes en plein dans la problmatique dAide la Dcision Multicritre 19. LOptimisation Multicritre Vincent Tkindt

  • Les prfrences peuvent sexprimer pour chaque critre Z i ,
    • sous forme de poids i ,
    • sous forme dobjectif atteindre (ex: Z i [A;B]),
    • sous forme de bornes ne pas dpasser,
    • ou sous forme dun ordre absolu entre les critres.
  • Exemples :
  • Si les prfrences sexpriment uniquement par des poids :
  • Minimiser i i Z i
  • Si les prfrences sexpriment par des poids et des bornes :
  • Minimiser i i Z i
  • sous contrainte Z i b i

Les solutions optimales sont desoptima de Pareto 20. LOptimisation Multicritre Vincent Tkindt

  • La fiabilit des prfrences influence le type dalgorithme mettre en place,

21. LOptimisation Multicritre Vincent Tkindt

  • La fiabilit des prfrences influence le type dalgorithme mettre en place,

Minimiser Z 1 (s)+ Z 2 (s) Sous contrainte Z 1 (s) b 1 Z 2 (s) b 2 sS Dcideur Optimum de Pareto Prfrences(poids, bornes) Homme dEtudes Module dAD Module Optim 22. LOptimisation Multicritre Vincent Tkindt

  • Comment rsoudre le problme doptimisation construit partir des prfrences du Dcideur ?

Minimiser Z 1 (s)+ Z 2 (s) Sous contrainte Z 1 (s) b 1 Z 2 (s) b 2 sS Dcideur Optimum de Pareto Prfrences(poids, bornes) Homme dEtudes

  • En utilisant la Recherche Oprationnelle :
    • Etude de la complexit du problme,
    • Mise au point dalgorithmes exacts (mthodes ddies, procdures par sparation et valuation, modles mathmatiques, ),
    • Mise au point dalgorithmes heuristiques (mthodes par construction progressive, algorithmes volutionnaires, mthodes par voisinage, )

Module dAD Module Optim 23. Exemple : Cartographie statistique Vincent Tkindt

  • Exemple prospectif : Sectorisation dune zone gographique,
  • Formulation du problme,

Une zone gographique

  • Une zone gographique est compose de parties,
  • Une partie j est dfinie par des caractristiques C i j
  • Problme :trouver la meilleure sectorisation pour le Dcideur.
  • Sectorisation :ensemble degroupes de parties.

Avec laimable autorisation dArticques pour lutilisation des cartes. 24. Exemple : Cartographie statistique Vincent Tkindt

  • Modlisation du problme :
  • Une partie j est dfinie par K caractristiques C j i ,
  • Un secteur s est dfini par un vecteur dvaluation v(s),
  • Une sectorisation est value par K critres Z i ,
  • Une partie est un pays, K=2, C j 1 = superficie et C j 2 =densit de population,
  • Pour chaque secteur s, on peut poser : v(s)=[ j C j 1; j C j 2 /P]
  • Z 1: cart de superficie maximum,
  • Z 1 =max p,q (v 1 (p)-v 1 (q)),
  • Z 2: cart de densit maximum,
  • Z 2 =max p,q (v 2 (p)-v 2 (q)),

Illustration : v(s 1 )=[10;30] v(s 2 )=[100;20] v(s 3 )=[2;25] Z 1 =max(100-10;100-2;10-2)=98 Z 2 =max(30-20;30-25;25-20)=5 Minimiser Z 1et Z 2 . 25. Exemple : Cartographie statistique Vincent Tkindt

  • Modlisation des prfrences :
  • Minimiser Z 1 + Z 2 ,
  • => peu pertinent en thorie.
  • Minimiser Z 1
  • sous contrainte Z 2
  • Sous forme de poids uniquement ?
  • Sous forme dune borne ?
  • (problme -contraint)

Illustration : Sectorisation Z 1 Z 2 s 1 98 5 s 2 96 7 s 3 90 10 Z 1 Z 2 90 98 96 5 10 7 26. Exemple : Cartographie statistique Vincent Tkindt

  • Modlisation des prfrences :
  • Le Dcideur est peu certain de ce quil veut : approche interactive,
  • Interactions sur la borne(quit considrer des pourcentages),
  • Quelle fiabilit pour les prfrences ?

Illustration : Z 1 Z 2

  • Augmenterpour diminuer lcart maximum sur la superficie,
  • Diminuerpour diminuer lcart sur la densit,

27. Exemple : Cartographie statistique Vincent Tkindt

  • Rsolution du problme :
  • Comment calculer une sectorisation pour le problme -contraint ?
  • => nombre de secteurs et constitution des secteurs.
  • Utilisation de mthodes de la Recherche Oprationnelle (heuristiques, algorithmes exacts).
  • Note :ce problme peut-il galement tre vu comme un problme de classification non supervise ?

28. Conclusions Vincent Tkindt

  • Ce quil faut retenir :
    • Une dmarche dADM fait ncessairement intervenir le Dcideur,
    • Il nexiste pas de solution optimale unique, mais plutt un ensemble de solutions optimales,
    • La prise en compte des prfrences est une tape cruciale,
    • La mise au point dalgorithmes efficaces ncessite une bonne connaissance des outils de la Recherche Oprationnelle et de lAide la Dcision.

29. Bibliographie Vincent Tkindt [Figueira et al., 2005] J. Figueira, S. Greco et M. Erghott. Multiple Criteria Decision Analysis: State-of-the-art surveys, International Series on Operations Research and Management Sciences, Springer. [Jacquet-Lagrze et Siskos, 1982] E. Jacquet-Lagrze et Y. Siskos. Assessing a set of additive utility functions for multicriteria decision making: the UTA method. European Journal of Operational Research, 10(2):151-164, 1982. [Roy, 2006] B. Roy. Regard historique sur la place de la RO-AD en France, Cahier du Lamsade, num. 237, Universit Paris-Dauphine, mai 2006. [Saaty, 1986] T. Saaty. Axiomatic foundation of the Analytic Hierarchy Process, Management Science, 32(7):841-855, 1986. [Von Neumann et Morgenstern, 1954] J. Von Neumann et O. Morgenstern. Theory of games and economic behaviour, Wiley Edition, 1954.