1
Master MIMSE - Année 2
Optimisation Stochastique
Contraintes de hasard
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT --
2
Exemple : PL stochastique
• On veut résoudre
min cT x
s.c. Ax = b
T (ω)x ≥ h
x ∈ ℜn.
• Il est quelquefois impossible de résoudre pour tous les ω : “fat
solution”.
• “fat solution” : vérifier les contraintes avec 100% de probabil-
ité.
• On admet une certaine probabilité de ne pas vérifier des con-
traintes.
• Par exemple, vérifier les contraintes avec une proba de 90%,
95 %, 99 % ...
• “Le risque zéro n’existe pas” mais alors “risque maîtrisé”
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT --
3
Contrainte de hasard - Deux approches
• On remplace T x ≥ h par Pr(T x ≥ h) ≥ α avec α = 0.9,
0.95, 0.99 ...
• Pour être précis on a Pr({ω|T (ω)x ≥ h(ω)}) ≥ α.
• C’est le modèle des contraintes de hasard jointes.
• Si on partage les contraintes de hasard on a le modèle des
contraintes de hasard séparées :
Pr({ω|Tk (ω)T x ≥ hk (ω)}) ≥ αk ∀k.
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT --
4
Analogie avec la gestion des stocks
• En gestion des stocks stochastique, on parle de niveau de ser-
vice lorsqu’on estime ne pas pouvoir répondre toujours à toutes
les demandes et qu’on se fixe une probabilité de satisfaction à
atteindre.
• Niveau de stock st et demande Dt pour la période t.
• Contraintes : ∀t st ≥ Dt.
• Niveau de type 1 : On veut que pour α % des périodes, les
demandes soient satisfaites.
• → contrainte séparée
• Niveau de type 2 : On veut que globalement, on satisfasse α
% des demandes :
• → contrainte jointe.
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT --
5
Exemple : une contrainte linéaire
• On considère la contrainte linéaire suivante :
ax + by ≥ c.
• On suppose que seul c est aléatoire.
• Vérifier la contrainte avec la probabilité α c’est vérifier
P (c ≤ ax + by) = F (ax + by) ≥ α,
avec F (x) = P (c ≤ x)
• Si v.a. discrète, F discontinue, donc F −1 mal définie,
• Sinon, en général, F −1 n’a pas d’expression analytique utile
• Utiliser des tables de valeurs (ex. loi normale centrée réduite)
• On remplace par ax + by ≥ F −1(α).
• Contraintes de hasard séparées devient un PL déterministe !
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT --
6
Exemple avec des demandes discrètes
• On considère le PL suivant, où seules les demandes sont aléa-
toires :
min x + y
s.c. 2x + y ≥ h1(ω)
x + 3y ≥ h2(ω)
x, y ≥ 0.
• On considère que seules trois réalisations sont possibles (“scé-
narios”) :
– h = (15, 10) avec une proba de 0.75
– h = (12, 18) avec une proba de 0.15
– h = (20, 15) avec une proba de 0.10
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT --
7
Exemple - α > 0.9
• Il faut vérifier les contraintes dans les trois scénarios.
• On a à résoudre :
min x + y
s.c. 2x + y ≥ 15
2x + y ≥ 12
2x + y ≥ 20
x + 3y ≥ 10
x + 3y ≥ 18
x + 3y ≥ 15
x, y ≥ 0.
• On simplifie en :
min x + y
s.c. 2x + y ≥ 20
x + 3y ≥ 18
x, y ≥ 0.
• Solution optimale (8.4; 3.2) de coût 11.6.
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT --
8
Exemple - α ∈]0.85; 0.9]
• Vérifier les contraintes dans le scénario 1 et 2 (éventuellement
3, mais pas obligé → pas dans les contraintes).
• On a un PL à résoudre :
min x + y
s.c. 2x + y ≥ 15 (∗)
2x + y ≥ 12
x + 3y ≥ 10
x + 3y ≥ 18 (∗)
x, y ≥ 0.
• On a pour optimum : (5.4; 4.2) pour un coût de 9.6,
• L’ensemble des solutions contient l’ensemble des solutions
précédent.
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT --
9
Exemple - α ∈]0.75; 0.85]
• Vérifier les contraintes dans le scénario 1, et 2 ou 3.
• On a deux PL à résoudre :
min x + y
s.c. 2x + y ≥ 15 (∗)
2x + y ≥ 12
x + 3y ≥ 10
x + 3y ≥ 18 (∗)
x, y ≥ 0.
et
min x + y
s.c. 2x + y ≥ 15
2x + y ≥ 20 (∗)
x + 3y ≥ 10
x + 3y ≥ 15 (∗)
x, y ≥ 0.
• On a deux optimums (un pour chaque PL) :
1. (5.4; 4.2) pour un coût de 9.6,
2. (9; 2) pour un coût de 11.
• L’espace des solutions n’est pas convexe !!
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT --
10
Exemple - α ∈]0.25; 0.75]
• Vérifier les contraintes dans le scénario 1 est nécessaire et
suffisant.
• On a un PL à résoudre :
min x + y
s.c. 2x + y ≥ 15
x + 3y ≥ 10
x, y ≥ 0.
• On a l’optimum suivant : (7; 1) pour un coût de 8.
• L’espace des solutions est redevenu convexe !!
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT --
11
Non convexité - Convexité
• De façon générale, soit Gα la famille des ensembles G d’évé-
nements tels que Pr(G) ≥ α (ensembles de scénarios dont
la proba globale est ≥ α),
• L’ensemble des x admissibles B(α) est tel que
[ \
B(α) = {x|g(x, ω) ≤ 0}
G∈Gα ω∈G
• Si g est convexe, les {x|g(x, ω)} sont convexes,
• leur intersection est convexe,
• mais l’union peut ne pas être convexe.
• Non convexité : optimums multiples, difficultés calculatoires
• Mais B(1) est convexe (fortes valeurs de α),
• et sous certaines hypothèses (fortes !)sur g et la distribution
des ω, on peut avoir B(α) convexe pour tout α.
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT --
12
Exemple : une contrainte linéaire - 2
• On reconsidère la contrainte linéaire suivante :
ax + by ≥ c.
• On suppose maintenant a, b, c sont aléatoires.
• Vérifier la contrainte avec la probabilité α c’est vérifier
P (c ≤ ax+by) = P (c−ax−by ≤ 0) = FZ (0) ≥ α,
avec FZ (x) = P (Z ≤ x) et Z = c − ax − by.
• Il faut donc déterminer (à x, y fixés) la loi de Z.
• Ex. a, b, c de lois normales, indépendantes
• Z de loi normale de moyenne somme des moyennes, de vari-
ance σc2 + x2σa2 + y 2σb2 ,
• Utiliser des tables de valeurs (loi normale centrée réduite)
pour déterminer F −1(α) = zα
• On trouve zα(σc2 +x2σa2 +y 2σb2 ) = E[c]−E[a]x−E[b]y
• Contraintes de hasard séparées devient un P Non Linéaire,
déterministe.
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT --
13
Conclusion
• Modèle assez naturel : maîtrise du risque
• Des cas assez simples se transforment en modèles détermin-
istes,
• mais calculs parfois importants pour reformuler (loi de sommes...)
• et après calculs parfois ardus (P Non Linéaires)
• non-convexité inhérente à certains modèles
• Optimums locaux possibles.
DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT --