OPTIMISATION
STOCHASTIQUE
I - Introduction
Rappels d’optimisation
• Optimiser : trouver le (un des) meilleur(s)
choix, en respectant certaines contraintes
• min/max f(x)
• s.c. (« sous les contraintes »)
• gk(x) ≥, ≤, = bk
• x ∈X⊆Rn
Différents types d’optimisation
• Pas de gk : optimisation sans contraintes
• f, gk linéaires (= polynômes de degré 1):
Programmation Linéaire
• Sinon, programmation non linéaire
(Optimisation 2)
• + X discret (⊆Zn) : PL Nombres Entiers
(Programmation Entière)
Optimisation
déterministe/stochastique
• Jusqu’ici, on suppose que les fonctions et
les seconds membres sont parfaitement
connus.
• Dans beaucoup de cas réels, on optimise
sur des données non connues
exactement
• Une part de hasard : « stochastique »
Eléments aléatoires
• Prévoir le futur (forcément…) :
demandes des clients, pannes,
défauts,…
liés à la météo (retards de projets,
mode),…
réactions des concurrents
cours de la Bourse, du marché,…
• Evaluer le présent
Exemple 1 : marchand de
journaux
• Un marchand de journaux achète à un
fournisseur des journaux qu’il revend à
des clients.
• Il ne sait pas le matin combien de journaux
seront vendus dans la journée.
• Acheter beaucoup ⇒ satisfaire plus
sûrement les demandes, trop d’invendus
• Acheter peu ⇒ peu d’invendus, manque à
gagner (clients non satisfaits)
Exemple 1 : modèle
• a,v,i nombres de journaux achetés,
vendus, invendus (éventuellement repris
au prix du papier)
• Max E[bénef] = E[(cV v + cI i - cA a)]
s.c. a = v+i (cohérence des variables)
v ≤D (demande, aléatoire)
v,i ≥ 0
• a,v,i aléatoires ?
Exemple 2 : Stock
• Etat du stock à la période t st
• Arrivées de commandes à la période t Lt
• Demandes à la période t Dt
• Coûts de stockage par période h
• Coûts fixes de commande K
• Min E [Σt (v Dt - Kxt - h st - a Lt)]
• st+1 = st + Lt – Dt ≥ 0 ∀t
• Lt ≤ Lmax xt , xt ∈{0,1} (Modèle mixte entier)
Exemple 2 (suite)
st+1 = st + Lt – Dt ≥ 0 ∀t
• Contraintes
très difficiles à satisfaire (à moins qu’il
existe un Dmax )
• Soit prévoir des pénuries (demandes
à satisfaire en période t+1), quitte à
payer des pénalités
• Soit pouvoir varier les quantités
commandées au fur et à mesure =
« recours »
Exemple 3 : processus de
production
• Au lieu d’avoir des commandes qui arrivent
toutes faites, on a des produits que l’on fabrique
• Nouvelle difficulté : les quantités fabriquées sont
incertaines (défauts, pannes de machines,
manque ponctuel de personnel…)
• Partie aléatoire dans le membre de gauche des
contraintes
• Aléas aussi dans les coûts des matières
premières ou les prix de revente
(négociations…) donc dans la fonction objectif
Influence des aléas
• Soit un problème déterministe (P) avec
une solution optimale (x*), de coût f(x*).
• Rajouter des aléas (P ⇒ P’) peut :
laisser (x*) optimale pour (P’), de coût
modifié f’(x*)
modifier la solution optimale, mais
conserver ses caractéristiques
changer complètement l’optimum
Décision/aléas
• En général les décisions sont à prendre au
temps t=0,
• Les aléas se réalisent à des t>0.
• Solutions wait-and-see : optimums si on
connaissait les réalisations des v.a.
• Modèle à 2 étapes : décisions seulement à t=0;
• Modèle à plusieurs étapes : on prend des
décisions à des temps tk, connaissant les
décisions prises à t<tk, et les réalisations des
v.a. à t<tk.
Variables aléatoires
• Variables ω pouvant prendre des valeurs
sur un espace Ω ⊆ ℜ.
• Support : plus petit espace contenant
toutes les valeurs possibles de ω.
• Fonction de densité f.d. : f : Ω → ℜ+
• Proba P(x<ω<x+dx) = f(x) dx
• Proba P(a<ω<b) = ∫a→b f(x) dx
• Espérance (moyenne):E[ω] = ∫a→b x f(x) dx
Distributions usuelles
• Distribution discrète : ensemble fini X de
doublets X={(xi, pi)} avec P(ω=xi) = pi.
• Distribution uniforme discrète : idem, avec ∀i, pi
= cte = 1/|X|.
• Distribution uniforme (continue) sur [a,b]
U(a,b) : support = [a,b], f.d. f(x)=1/(b-a).
• Distribution normale de moyenne μ et d’écart-
type σ
N(μ,σ) : support = ℜ, f.d. f(x) = 1/ σ√(2π) exp
(-½[(x-μ)/σ]²) (fonction en cloche)
Idées simplistes
• Vérifier toutes les contraintes quelque soit
la valeur des variables aléatoires ⇒
solution tous cas, ou pire cas (« fat
solution ») :
en général, très coûteuse
et même parfois de coût infini (ex.
distribution de support non borné :
distribution normale)
Solution pire cas
• Exemple : marchand de journaux
• Pas d’invendus repris, il veut satisfaire les
demandes.
• Demandes : distribuées uniformément sur un
intervalle [0,b], 0<b<∞
• Il doit commander toujours b journaux
• Il dépense b cA euros par jour
• Il récupère en moyenne (b/2) cV euros par jour
• Si cV / cA< 2, il perd de l’argent !!
Solution pire cas
• Coûts bien trop élevés dans certains cas
• Variables aléatoires à support non borné (ex. loi
normale) : solutions parfois infinies
• Parfois à peu près justifiée : construction de
centrales nucléaires, d’immeubles en zone
sismique…
• Plus réaliste : admettre un risque de probabilité
très faible : niveau de service en stocks,
modèles de la contrainte de hasard (« chance
constraint »).
Valeurs moyennes
• Idée : remplacer les variables aléatoires par
leurs espérances.
• Résoudre le problème comme un problème
déterministe.
• ☺: Modèle facile (déterministe)
• ☹ : Les risques sont bien trop importants :
si on identifie “moyenne” et “médiane”,
contraintes violées dans la moitié des cas.
Valeurs moyennes avec
marges de sécurité
• Idée : On remplace les données aléatoires
par des valeurs plus “sûres” que les
moyennes.
• Analogie gestion des stocks : niveaux de
sécurité.
• Problème déterministe, donc facile.
Valeurs moyennes avec
marges de sécurité -2-
• Très empirique, pas forcément un bon
modèle de décision.
• Qu'est-ce qu'une valeur “plus sure” ?
• De combien faut-il prendre une marge de
sécurité ? ☞Modèle de la contrainte de
hasard.
• A compléter par une analyse de sensibilité :
– Comment évolue la solution quand on fait
T←T+δT et h←h+δh ?
Exemple du marchand de
journaux – idées simplistes
• Prix d'achat CA , de vente CV, de reprise
des invendus CI.
• Demande inconnue D.
• Cas 1 : D uniforme sur [0;100].
• Cas 2 : D normale N(50;29).
• CA=0.7€ , CV= 1€, CI=0.1€.
Exemple du marchand de
journaux – valeur max
• Cas 1 : Pire cas = demande de 100
journaux. Il commande donc Q=100.
• Il paye [Link]=70€ par jour.
• En moyenne il vend 50 journaux par jour
donc 50 invendus, ce qui lui rapporte
E[D].CV+(Q-E[D]).CI=55€ par jour.
• Il perd 15€ par jour !
• Cas 2 : Pire cas = demande infinie !!
Exemple du marchand de
journaux – valeur moyenne
• On remplace D par E[D]=50.
• Donc Q = 50.
• Il paye 35€ par jour.
• Cas 1 : En moyenne un jour sur deux il
vend tout donc il gagne 50€ par jour
• En moyenne un jour sur deux il ne vend
pas tout. Il vend alors en moyenne
E[D|D<50]=25 journaux donc gagne 27.5€
• Bilan : -35 + (50+27.5)/2=3.75€
Exemple du marchand de
journaux – valeur moyenne
• Cas 2 : Il paye 35€ par jour.
• Un jour sur deux il vend ses 50 journaux
donc gagne 50€.
• Un jour sur deux il ne vend pas tout. Il vend
en moyenne E[D|D<50]= 38.4 journaux et
garde en moyenne 50-E[D|D<50]= 11.6
journaux invendus (dans les tables).
• Gain moyen : 9.78€ par jour.
Exemple du marchand de
journaux – marge de sécurité
• Le marchand choisit Q = E[D]+∆ . Par
exemple ∆ =29 (écart-type).
• Il commande 79 journaux qu'il paye 55.3€.
• Cas 1: 21 % des jours il vend tout donc
gagne 79€. 79% des jours il ne vend pas
tout. Il vend alors en moyenne E[D|D<79]
=39.5 journaux, avec 39.5 journaux
invendus. Il gagne alors 43.45€.
• Il perd 55.3-(0.79*43.45+0.21*79)=4.38€ !!
Exemple du marchand de
journaux – marge de sécurité
• Qu'est-ce qu'une marge de sécurité ici ?
• Satisfaire les demandes ou “minimiser” les
risques d'invendus ?
• Les invendus coûtent cher, le mieux serait
peut-être de diminuer Q.
Le marchand de journaux –
analyse de sensibilité
• Analyse de sensibilité autour de Q=50 (cas
1): on paye 0.7(50+d)€,
• On vend tout dans (50-d)% des jours donc
on gagne (50+d)€,
• dans (50+d)% des jours on a en moyenne
(50+d)/2 journaux vendus et (50+d)/2
invendus. Gain (50+d)/2+(50+d)/2*0.1 €
• Bilan : 3.75 – 0.0045 d² – 0.15 d
Le marchand de journaux –
la solution
• CO cout par journal invendu = CA-CI
• CU cout par demande insatisfaite = CV-CA
• G(Q) = CO∫0Q(Q-D)f(D)dD+CU∫Q∞(D-
Q)f(D)dD
• G'=COF(Q)–CU(1-F(Q)) avec F(Q)=P[D≤Q]
• Trouver Q* tel que F(Q*)=CU/(CO+CU)
• Cas 1 : Q*=33, cas 2 : Q*=38.