11

Optimisation de lOptimisation de l’’Evolution des Evolution des SystèmesSystèmes

(Décisions dans l’incertain)(Décisions dans l’incertain)

Eric SanlavilleProfesseur université du Havre

Eric.sanlaville@isima.frWwwmaths.univ-bpclermont.fr/sanlavil~

ISIMA 3 F3 et Master 2 SIAD Novembre 2008

22

OrganisationOrganisation

3 x 4 heures de Cours / TD3 x 4 heures de Cours / TD 4 heures de TP4 heures de TP PlanPlan

DDéécisions sous incertitudescisions sous incertitudes Programmation stochastiqueProgrammation stochastique ModModèèles markoviens pour lles markoviens pour l’é’évolution de volution de

systsystèèmesmes Processus de dProcessus de déécision markoviens finis et infinis cision markoviens finis et infinis

Evaluation : Evaluation : compte rendu de TPcompte rendu de TP

33

RRééfféérencesrences

1.1. Hillier Lieberman Hillier Lieberman Introduction to ORIntroduction to OR2.2. MartelMartel techniques et applications de la ROtechniques et applications de la RO3.3. Heche, Liebling, De WerraHeche, Liebling, De Werra (PUR)(PUR)4.4. RoseauxRoseaux Exercices et problExercices et problèèmes rmes réésolus de solus de

RO, T3RO, T35.5. AllenAllenStatistics and queueing theoryStatistics and queueing theory6.6. Bouyssou Roy (multicritBouyssou Roy (multicritèères)res)7.7. Fuderberg TiroleFuderberg Tirole (game theory)(game theory)8.8. Ehrgott Ehrgott GandibleuxGandibleux (multicrit(multicritèères)res)9.9. Kouvelis YuKouvelis Yu (robust optimisation)(robust optimisation)10.10. WhiteWhite (markov decision processes)(markov decision processes)

Partie 1Partie 1

Décisions sous incertitudes : Décisions sous incertitudes : modèles, méthodes, modèles, méthodes,

évaluations des décisionsévaluations des décisions

55

Prise en compte des Prise en compte des incertitudes : pourquoiincertitudes : pourquoi??

Logistique : des trains toujours Logistique : des trains toujours àà l l’’heure heure Production : des machines jamais en Production : des machines jamais en

panne, des oppanne, des opéérateurs toujours disponiblesrateurs toujours disponibles Marketing : des clients toujours prMarketing : des clients toujours préévisiblesvisibles ChaChaîîne logistique : des fournisseurs ne logistique : des fournisseurs

toujours fiablestoujours fiables Equipements publics : des politiques Equipements publics : des politiques

stables, des populations stables stables, des populations stables Nos décisions s’appliquent-elles à un monde parfait?

66

Importance de la Importance de la dimension temporelledimension temporelle

Une dUne déécision scision s’’applique :applique : ImmImméédiatement. Mais il nous manque des diatement. Mais il nous manque des

donndonnéées.es. Dans le futur. Nos donnDans le futur. Nos donnéées resteront-elles es resteront-elles

pertinentes?pertinentes? On pilote un systOn pilote un systèème qui me qui éévolue : volue :

suite de dsuite de déécisionscisions ÉÉtaltaléées dans le temps (notion des dans le temps (notion d’’horizon de horizon de

ddéécision)cision)En général la connaissance des données utiles( les paramètres du système )augmente avec le temps

Mais on ne peut pas toujours reporter la prise de décision!

77

DiffDifféérents types rents types dd’’incertitudesincertitudes

Nos dNos déécisions visent au pilotage dcisions visent au pilotage d’’un un systsystèèmeme. . Elles dElles déépendent des valeurs des parampendent des valeurs des paramèètres de tres de ce systce systèème (qui peuvent me (qui peuvent àà leur tour d leur tour déépendre de pendre de ces dces déécisions : variables!).cisions : variables!).

Logistique : nombre et type de camions, produits Logistique : nombre et type de camions, produits àà transporter, lieux dtransporter, lieux d’’approvisionnement et de dapprovisionnement et de déépôts,pôts,……

Production : machines, robots de transport, quantitProduction : machines, robots de transport, quantitéés s àà produire,produire,……

Marketing : nombre de clients potentiels, coMarketing : nombre de clients potentiels, coûût dt d’’une une campagne de pub,..campagne de pub,..

88

DiffDifféérents types rents types dd’’incertitudes (2)incertitudes (2)

Incertitudes sur les donnIncertitudes sur les donnéées discres discrèètes : nombre de camions tes : nombre de camions disponibles, nombre de machines en pannes, nombre de disponibles, nombre de machines en pannes, nombre de commandescommandes

Incertitudes sur les donnIncertitudes sur les donnéées continues : dures continues : duréée de d’’un trajet, un trajet, durduréée de d’’une opune opéération sur un poste de travail, quantitration sur un poste de travail, quantitéé àà produire,produire,……

Incertitude structurelle : certaines donnIncertitude structurelle : certaines donnéées ne sont pas es ne sont pas disponibles !disponibles !

Appel dAppel d’’offre doffre d’’un concurrent (secret)un concurrent (secret) DDéécisions cisions àà un niveau sup un niveau supéérieur (secret aussi ?)rieur (secret aussi ?) Taille dTaille d’’un marchun marchéé ( (éétude de marchtude de marchéé incompl incomplèète)te) Marge dMarge d’’erreur derreur d’’une une éétudetude

99

Comment juger en Comment juger en prpréésence dsence d’’incertitudesincertitudes? ?

Intuition : il nous faut être capables de classer Intuition : il nous faut être capables de classer diffdifféérentes alternatives (ou drentes alternatives (ou déécisions, ou cisions, ou solutions).solutions).

ProblProblèème : suivant les conditions rme : suivant les conditions rééelles, lelles, l’’ordre ordre relatif des alternatives peut changer!relatif des alternatives peut changer! Exemple : le produit X ne fera des bExemple : le produit X ne fera des béénnééfices que si le fices que si le

nombre de clients dnombre de clients déépasse un certain seuil, qui dpasse un certain seuil, qui déépend pend du prix de vente (la ddu prix de vente (la déécision cision àà prendre) mais ne peut prendre) mais ne peut être entiêtre entièèrement drement dééterminterminéé àà l l’’avanceavance

La meilleure alternative est donc dLa meilleure alternative est donc dééterminterminéée a e a postpostéériori? riori? Inacceptable!!Inacceptable!!

Il faut être capable de choisir entre deux alternativesIl faut être capable de choisir entre deux alternatives,,Même si aucune nMême si aucune n’’est toujours meilleure que lest toujours meilleure que l’’autreautre

1010

Comment juger en Comment juger en présence d’incertitudes présence d’incertitudes

(2)(2) HypothHypothèèse : se : il existe un critèreil existe un critère « « objectifobjectif » » permettant de permettant de choisir entre deux alternatives A et B pour des donnchoisir entre deux alternatives A et B pour des donnéées es fixfixéées D.es D.

Ce critCe critèère peut être absolu : Zre peut être absolu : ZDD(A).(A). Exemple : bExemple : béénnééfice obtenu si le prix de vente est de A, et le fice obtenu si le prix de vente est de A, et le

nombre de clients est de D.nombre de clients est de D.

Ce critCe critèère peut être relatif : A <re peut être relatif : A <DD B B exemple : un expert dexemple : un expert déécide entre 2 alternatives, sans cide entre 2 alternatives, sans

pouvoir quantifier son choix.pouvoir quantifier son choix.

Il nous faut donc pouvoir « agréger les préférencesIl nous faut donc pouvoir « agréger les préférences : «  : « Etant donné l’ensemble de tous les scénarios Etant donné l’ensemble de tous les scénarios

possiblespossibles,,quelle alternative/décision/solution choisirquelle alternative/décision/solution choisir ? ?

1111

Les différents modèles pour laprise de décision en présence d’incertitudes se

distinguent donc suivant la façon dont ils réalisent cette agrégation des préférences

pour ne retenir qu’une alternativeAVANT la levée des incertitudes

1212

ApprochesApproches1.1. ModModèèles Dles Dééterministes (analyse de la terministes (analyse de la

valeur moyenne, valeur moyenne, ééchantillonnage)chantillonnage)2.2. ThThééorie des jeuxorie des jeux3.3. DDéécisions multi-critcisions multi-critèèresres4.4. Optimisation robuste (min max regret) Optimisation robuste (min max regret) 5.5. Optimisation robuste (espOptimisation robuste (espéérance)rance)6.6. Optimisation stochastiqueOptimisation stochastique7.7. Processus de dProcessus de déécision markovienscision markoviens

Etc, etc,Etc, etc,……

Et la simulation là dedans?

1313

ModModèèle dle dééterministe 1 :terministe 1 :Analyse de la valeur Analyse de la valeur

moyennemoyenne

Domaine dDomaine d’’application : application : incertitude sur les durincertitude sur les duréées et les quantites et les quantitéés.s. Horizon de temps : quelconque Horizon de temps : quelconque

Chaque paramChaque paramèètre variable est remplactre variable est remplacéé par par sa valeur moyenne (estimation)sa valeur moyenne (estimation)

Recherche dRecherche d’’une bonne solution pour ces une bonne solution pour ces valeurs de paramvaleurs de paramèètres.tres.

1414

Analyse de la valeur Analyse de la valeur moyenne :moyenne :

inconvinconvéénientsnients

La solution nLa solution n’’est pas toujours rest pas toujours rééalisablealisable

Elle est Elle est « « bonnebonne » » (optimale) sur un domaine (optimale) sur un domaine éétroit troit : analyse de sensibilit: analyse de sensibilitéé..

Elle peut être trElle peut être trèès mauvaise sur un grand nombre s mauvaise sur un grand nombre de scde scéénarios du problnarios du problèèmeme

1515

ModModèèle dle dééterministe 2 :terministe 2 :ééchantillonnage et chantillonnage et

optimisationoptimisation Domaine dDomaine d’’application : incertitude sur les durapplication : incertitude sur les duréées es

et les quantitet les quantitéés s

N scN scéénarios sont snarios sont séélectionnlectionnéés par s par ééchantillonnagechantillonnage Une meilleure solution est calculUne meilleure solution est calculéée pour chacune. e pour chacune. LL’’ensemble de ces solutions est considensemble de ces solutions est considéérréé : celle : celle

qui est globalement qui est globalement « « la meilleurela meilleure » » est choisie. est choisie.

1616

Echantillonnage et Echantillonnage et optimisation :optimisation :inconvinconvéénientsnients

MMééthode cothode coûûteuse : N optimisationsteuse : N optimisations On a rOn a rééduit le nombre dduit le nombre d’’instance et le nombre instance et le nombre

de solutions considde solutions considéérréées. Mais le choix de la es. Mais le choix de la solution finale ? Voir les autres msolution finale ? Voir les autres mééthodesthodes

A tA t’’on conservon conservéé toutes les solutions toutes les solutions intintééressantes?ressantes?

La solution retenue estLa solution retenue est’’elle toujours relle toujours rééalisable ?alisable ?

1717

Exemple (Wallace 00) : Exemple (Wallace 00) : production sans production sans

stockagestockage3 produits A, B, C. production =1

demandes pour A et B : a et b inconnues ,mais leur somme vaut 1

C : substitutionInterdit : produire plus que la demande

Max Z = 3A + 2B + CA aB 1-aA+B+C 1

a connue après la décision

Solution optimale pour a fixée : (a,1-

a,0)Infaisable!

Les solutions optimales ont une structure indésirable : A,B >0, C =0

Solution robuste : (0,0,1)

1818

ThThééorie des Jeuxorie des Jeux

Plusieurs acteurs en concurrence (joueurs)Plusieurs acteurs en concurrence (joueurs) Chaque joueur a le choix entre plusieurs Chaque joueur a le choix entre plusieurs

ddéécisions (stratcisions (stratéégies)gies) Une fois que chaque joueur a choisi sa Une fois que chaque joueur a choisi sa

stratstratéégie, le gain de chacun est connugie, le gain de chacun est connu Horizon de temps : quelconqueHorizon de temps : quelconque

Incertitudes ? La stratégie des autres joueurs!

1919

ThThééorie des Jeuxorie des Jeux

Cadre : Cadre : ééconomie conomie

Tarification : telecom, aTarification : telecom, aéérienrien Fonctionnement dFonctionnement d’’un marchun marchéé libre libre

Situations de conflitSituations de conflit Hypothèse : comportement rationnel et

individualiste des joueurs (??)

2020

ThThééorie des jeux : orie des jeux : exemple 1exemple 1

stratstratéégiesgies

11 22 33

11 --33 --22 66

22 22 00 22

33 55 --22 --44Joueur 1

Joueur 2

-3

0

-4

5 0 6

Chaque joueur tente de maximiser son gain ,mais doit tenir compte de la stratégie de l’autre

Existence d’un point d’équilibre :

Aucun joueur n’a intérêt à changer

de stratégie

2121

ThThééorie des jeux : orie des jeux : exemple 2exemple 2

stratstratéégiesgies

11 22 33

11 00 --22 22

22 55 44 --33

33 22 33 --44Joueur 1

Joueur 2

-2

-3

-4

5 4 2

Chaque joueur tente de maximiser son gain ,mais doit tenir compte de la stratégie de l’autre

L’équilibre est instable:

Alternatives ?Stratégies mixtes

probabilistes

2222

ThThééorie des Jeux, orie des Jeux, extensionsextensions

Plus de 2 joueursPlus de 2 joueurs Jeux simples, jeux rJeux simples, jeux rééppééttééss Objectif : recherche des Objectif : recherche des ééquilibresquilibres RRéésolution : programmation linsolution : programmation linééaire, aire,

programmation mathprogrammation mathéématique,matique,……

2323

DDéécisions multicritcisions multicritèères :res :approche qualitativeapproche qualitative

N critères, P alternativesChaque critère (votant) trie l’ensemble des alternatives (fixées)

Exemple : 100 votants, 5 alternatives

AA BB CC DD EE

AA5544

4488

7755

8899

BB4466

5588

7722

5599

CC5522

4422

4477

6633

DD2255

2288

5533

5577

EE1111

4411

3377

4433

CONDORCET: A > B > C >A

Méthode Electre: Prudence!!

Seuil à 55 %: restent A et B

2424

DDéécisions multicritcisions multicritèères :res :approche quantitativeapproche quantitative

N critN critèères (N petit). res (N petit). Un grand nombre Un grand nombre de solutions.de solutions.

Conserver les Conserver les solutions non solutions non domindominéées :es :

X solution de Pareto X solution de Pareto (min) : pour tout Y, (min) : pour tout Y,

Yi < Xi implique : il Yi < Xi implique : il existe j, Yj > Xiexiste j, Yj > Xi

+

+

+

+

+

-

--

-

---

X

C1

C2

-

2525

DDéécisions multicritcisions multicritèères :res :approche quantitative (2)approche quantitative (2)

ProblProblèème : les optima de Pareto me : les optima de Pareto peuvent être nombreux (courbe de peuvent être nombreux (courbe de Pareto)Pareto)

Trouver un optimum de Pareto peut Trouver un optimum de Pareto peut être bien plus dur que optimiser un être bien plus dur que optimiser un seul critseul critèère!re!

2626

Optimisation robuste 1 :Optimisation robuste 1 :min max regretmin max regret

Constat : on ne peut pas trouver une Constat : on ne peut pas trouver une solution optimale pour tous les solution optimale pour tous les scscéénarios.narios.

HypothHypothèèse : Ce qui compte, cse : Ce qui compte, c’’est lest l’é’écart cart àà la meilleure solution pour chaque la meilleure solution pour chaque scscéénario. nario.

le regretle regret : ce que l : ce que l’’on aurait don aurait dûû faire si on faire si on avait su!avait su!

La meilleure solution : celle pour laquelle La meilleure solution : celle pour laquelle le plus grand regret est minimum le plus grand regret est minimum

2727

Optimisation robuste 1 :Optimisation robuste 1 :min max regretmin max regret

Trouver X / Trouver X / maxmaxss ( f ( fss (X) (X) –– f* f*ss ) ) est est minimumminimum

ffss (X) : valeur de la solution X pour le sc (X) : valeur de la solution X pour le scéénario snario sf*f*s s : valeur optimale pour le sc: valeur optimale pour le scéénario snario s

C’est une approche « pire cas «Résoudre le problème d’optimisation est en général

Très difficile.

2828

Exemple (Mahjoub 04)Exemple (Mahjoub 04) Ligne de production (petite série, flow shop). Une des machines (la dernière) est en panne.

( Il en manque une partie, qui arrivera le lendemain ) 7 pièces doivent passer par la ligne, il faut

déterminer tout de suite leur ordre de passage pour qu’elles soient disponibles à l’arrivée de la machine : ordre figé.

A chaque pièce est associée une durée d’exécution sur la machine en panne, et une date de livraison impérative

Le service commercial souhaite minimiser le nombre de retards de livraisons (une pénalité est prévue)

PB : la date d’arrivée de la partie manquante n’est pas connue

2929

Exemple Exemple (indisponibilit(indisponibilitéé,suite),suite)

1 / /Uj : Ordonnancement sur une machine, minimiser le nombre de pièces en retard. Indisponibilité possible de la machine au démarrage

Cas de deux scénarios. La pièce est livrée par camion :soit à 8h, soit à11 h ( indispo sur [0,3])

jj 11 22 33 44 55 66 77

pjpj 11 11 11 33 11 11 11

djdj 33 33 33 66 99 99 99

Ordre initial:1 2 3 4 5 6 7

3030

Exemple Exemple (indisponibilit(indisponibilitéé,suite),suite)

1 2 3 4 5 6 7

d3 = 3 d4 =6 d7=9

4

1 2 3 5 6 7

5 6 7

S1

S2

S3

OK [0,3] Max (f - f*)

0 7 4

3 3 3

1 4 1

3131

Optimisation robuste 2Optimisation robuste 2

Objectif : minimiser le critObjectif : minimiser le critèère f sur re f sur ll’’ensemble des scensemble des scéénariosnarios

HypothHypothèèses :ses : On a une modOn a une modéélisation du probllisation du problèème me

ddééterministe initial (PL, PLNE, quadratique)terministe initial (PL, PLNE, quadratique) On fait On fait «« bouger bouger »» une contrainte ou plusieurs une contrainte ou plusieurs La fonction objectif ne change pasLa fonction objectif ne change pas

On transforme le problOn transforme le problèème en un nouveau me en un nouveau problproblèème dme d’’optimisation (en goptimisation (en géénnééral plus ral plus complexe). La solution cherchcomplexe). La solution cherchéée est e est rrééalisable pour tous les scalisable pour tous les scéénarios narios retenus.retenus.

3232

Exemple 1: les coefts de la contrainte Exemple 1: les coefts de la contrainte varient sur un intervalle : [ai-a,ai+a] varient sur un intervalle : [ai-a,ai+a]

Exemple 2 : lExemple 2 : l’’ensemble de la contrainte ensemble de la contrainte devient une ellipsodevient une ellipsoïïdede

Dans le 2Dans le 2èème cas, on est ramenme cas, on est ramenéé àà un un programme quadratique particulier, programme quadratique particulier, polynômial!polynômial!

Remarque : ces modRemarque : ces modèèles reviennent souvent les reviennent souvent àà ééliminer les scliminer les scéénarios extrnarios extrèèmes, trmes, trèès s improbablesimprobables

Optimisation robuste 2 Optimisation robuste 2 exemples Programmation linéaireexemples Programmation linéaire

3333

Exemple dExemple d’’application :application :incertitudes sur la incertitudes sur la

qualitqualitéé des mati des matièères res premipremièèresres

3434

Approches Approches stochasssstiquesstochasssstiques

JusquJusqu’’ici : aucune hypothici : aucune hypothèèse se probabiliste explicite sur les donnprobabiliste explicite sur les donnéées es incertainesincertaines

Quel est lQuel est l’’apport des modapport des modèèles les stochastiques?stochastiques?

3535

ModModéélisation lisation stochastiquestochastique

Chaque donnChaque donnéée incertaine est e incertaine est modmodéélisliséée par une variable ale par une variable alééatoire.atoire.

LL’’objectif devient lui-même une objectif devient lui-même une variable alvariable alééatoire.atoire.

On cherche On cherche àà minimiser son minimiser son espespéérance, plus rarement : minimiser rance, plus rarement : minimiser la probabilitla probabilitéé qu qu’’il dil déépasse un certain passe un certain seuil : rseuil : réésultat trsultat trèès utile, mais difficile s utile, mais difficile àà obtenir !! obtenir !!

3636

Exemple indisponibilitExemple indisponibilitéé de de la machine revisitla machine revisitéé

On suppose maintenant que la durOn suppose maintenant que la duréée e dd’’indisponibilitindisponibilitéé de la machine est de la machine est une variable alune variable alééatoire discratoire discrèète. Elle te. Elle est de 3 heures avec proba p, et de est de 3 heures avec proba p, et de zero sinon. zero sinon.

3737

Exemple indisponibilité de la Exemple indisponibilité de la machine : exercicemachine : exercice

Quelle est alors lQuelle est alors l’’espespéérance du rance du nombre de retards pour chacune des nombre de retards pour chacune des 3 solutions suivant p ?3 solutions suivant p ?

Tracez les courbes associTracez les courbes associééeses ConcluezConcluez

Vous êtes le chef dVous êtes le chef d’’atelier. Que faites atelier. Que faites vous?vous?

3838

1 2 3 4 5 6 7

d3 = 3 d4 =6 d7=9

4

1 2 3 5 6 7

5 6 7

S1

S2

S3

OK [0,3] Max (f - f*)

0 7 4

3 3 3

1 4 1

3939

Programmation Programmation stochastiquestochastique

HypothHypothèèses : lses : l’’incertitude influence la incertitude influence la valeur des solutions plus que leur valeur des solutions plus que leur structure. Chaque scstructure. Chaque scéénario induit donc une nario induit donc une fonction difffonction difféérente rente àà optimiser. Il est optimiser. Il est possible dpossible d’’associer une probabilitassocier une probabilitéé àà chaque scchaque scéénario.nario.

mmééthode : considthode : considéérer lrer l’’espespéérance de la rance de la valeur des solutions comme une fonction valeur des solutions comme une fonction unique, pour se ramener unique, pour se ramener àà un seul un seul problproblèème dme d’’optimisationoptimisation

4040

Programmation Programmation stochastique : exemple stochastique : exemple classique du vendeur de classique du vendeur de

journauxjournaux Un vendeur de journaux achUn vendeur de journaux achèète un te un

journal au prix unitaire a. Il le vend journal au prix unitaire a. Il le vend au prix p. Il peut ramener les au prix p. Il peut ramener les invendus, dans ce cas il obtient r < a invendus, dans ce cas il obtient r < a par journal.par journal.

La demande est modLa demande est modéélisliséée par une e par une variable alvariable alééatoire d.atoire d.

Quelle quantité de journaux doit-il acheter??

4141

Processus de dProcessus de déécision cision markoviensmarkoviens

On travaille sur un horizon de temps long. On travaille sur un horizon de temps long. Les dLes déécisions influent sur lcisions influent sur l’é’évolution du volution du

systsystèème considme considéérréé. Cette . Cette éévolution est volution est probabiliste.probabiliste.

Le coLe coûût total dt total déépend des dpend des déécisions et des cisions et des éétats successifstats successifs

HypothHypothèèse markovienne : se markovienne : éévolution sans volution sans mméémoire du systmoire du systèèmeme

Objectif : minimiser lObjectif : minimiser l’’espespéérance du corance du coûût t total sur N ptotal sur N péériodes (ou le coriodes (ou le coûût par pt par péériode riode en horizon infini)en horizon infini)

4242

Processus de dProcessus de déécision cision markoviensmarkoviens

MarketingMarketing SystSystèèmes de productionmes de production Gestion de stocks Gestion de stocks ……

Tout systTout systèème qui se laisse me qui se laisse «« conduire conduire »»

4343

La SimulationLa Simulation Simulation monte carlo : tirage alSimulation monte carlo : tirage alééatoire atoire

rrééppééttéé pour obtenir un pour obtenir un ééchantillon dchantillon d’’une une variable alvariable alééatoire.atoire. Exemple : Exemple : ééchantillonner une donnchantillonner une donnéée incertainee incertaine

Simulation de lSimulation de l’é’évolution dvolution d’’un systun systèème :me : Simu Simu àà éévvéénements discrnements discrèèts :un tirage alts :un tirage alééatoire atoire

permet de calculer la date dpermet de calculer la date d’’un un éévvéénement.nement. Exemple : systExemple : systèème de production, fin dme de production, fin d’’une une

opopéération.ration. Cas particulier : simulation dCas particulier : simulation d’’un run rééseau de seau de

files dfiles d’’attente quand les mattente quand les mééthodes thodes analytiques sont inapplicablesanalytiques sont inapplicables

4444

Simulation versus Simulation versus OptimisationOptimisation? ?

La simulation : un outil pour analyser La simulation : un outil pour analyser le comportement dle comportement d’’un systun systèème me complexecomplexe

Pour nous : permet dPour nous : permet d’é’évaluer la valuer la performance dperformance d’’une solution dune solution d’’un un problproblèème de dme de déécisioncision

Ne permet pas de calculer une Ne permet pas de calculer une « « bonnebonne » » solution !! solution !!

4545

Couplage Couplage Simulation/OptimisationSimulation/Optimisation! !

!! Quand calculer la valeur dQuand calculer la valeur d’’une solution est une solution est trop cotrop coûûteux par une mteux par une mééthode analytique, la thode analytique, la simulation permet dsimulation permet d’é’évaluer cette valeurvaluer cette valeur

En rEn rééppéétant une simulation, on tant une simulation, on éévalue la value la performance moyenne dperformance moyenne d’’une solution S, et on une solution S, et on approche E(f(S))approche E(f(S))

Exemple : systExemple : systèème de production, modme de production, modèèle le RFARFA

Utilisation : on peut incorporer la simulation Utilisation : on peut incorporer la simulation dans les mdans les mééthodes classiques dthodes classiques d’’optimisation : optimisation : heuristiques de voisinage, algos heuristiques de voisinage, algos éévolutionnaires, Branch and Bound, volutionnaires, Branch and Bound, ……

4646

ConclusionsConclusions Prise en compte des incertitudes : de Prise en compte des incertitudes : de

nombreux modnombreux modèèles.les. Ils ne sIls ne s’’appliquent pas aux mêmes appliquent pas aux mêmes

problproblèèmes, ils nmes, ils n’’ont pas les même outils ont pas les même outils pour le pour le choixchoix..

Seul le contexte permet de choisir.Seul le contexte permet de choisir. En dernier ressort, ces outils restent des En dernier ressort, ces outils restent des

AIDES AIDES àà la DECISION la DECISION