Exercice TD (Stratégie Optimale de Jeu)
𝑘 ∈ 1,2 : Associé aux deux premières parties du jeu.
𝑥𝑘 : Score avant le début de la partie k. De ce fait :
𝑥1 ∈ {0 − 0}
𝑥2 ∈ {0 − 1, 0.5 − 0.5,1 − 0}
𝑥3 ∈ {0 − 2,0.5 − 1.5,1 − 1,1.5 − 0.5,2 − 0} (Etat terminal)
𝐴 𝑠𝑖 𝑙𝑒 𝑗𝑜𝑢𝑒𝑢𝑟 𝑐ℎ𝑜𝑖𝑠𝑖𝑡 𝑢𝑛 𝑠𝑡𝑦𝑙𝑒 𝑎𝑔𝑟𝑒𝑠𝑠𝑖𝑓
𝑢𝑘 = 𝑃 𝑠𝑖 𝑙𝑒 𝑗𝑜𝑢𝑒𝑢𝑟 𝑐ℎ𝑜𝑖𝑠𝑖𝑡 𝑢𝑛 𝑠𝑡𝑦𝑙𝑒 𝑝𝑎𝑠𝑠𝑖𝑓
𝜔𝑘 : variable aléatoire qui représente le résultat de la partie k.
𝜔𝑘 ∈ {0 − 1, 0.5 − 0.5,1 − 0} 1
𝑓𝑘 𝑥𝑘 , 𝑢𝑘 , 𝜔𝑘 = 𝑥𝑘 + 𝜔𝑘 .
Récapitulons l’évolution du score :
𝐱𝐤 𝐮𝐤 𝛚𝐤 𝐏(𝛚𝐤 = . |𝐱 𝐤 , 𝐮𝐤 ) 𝐱 𝐤+𝟏 = 𝐱 𝐤 + 𝛚𝐤
k=1 0–0 P 0.5 – 0.5 0.9 0.5 – 0.5
0–1 0.1 0–1
A 1–0 0.45 1–0
0–1 0.55 0–1
k=2 0–1 P 0.5 – 0.5 0.9 0.5 – 1.5
0–1 0.1 0– 2
A 1–0 0.45 1–1
0–1 0.55 0–2
0.5 – 0.5 P 0.5 – 0.5 0.9 1–1
0–1 0.1 0.5– 1.5
A 1–0 0.45 1.5 – 0.5
0–1 0.55 0.5 – 1.5
1–0 P 0.5 – 0.5 0.9 1.5 – 0.5
0–1 0.1 1– 1
A 1–0 0.45 2–0
2
0–1 0.55 1– 1
République Algérienne Démocratique et Populaire
Ministère de l’Enseignement Supérieur et de la Recherche Scientifique
Université de Jijel
Faculté des Sciences Exactes et Informatique
Département d’Informatique
Optimisation Stochastique
Cours 2
Programmation Stochastique
3
Master I SIAD 2020/2021
Introduction
Plusieurs problèmes de décisions se décrivent sous forme de
programmes linéaires:
Min F = cj x j
s. c aij xj = bj i = 1, m
𝑥𝑗 ≥ 0 𝑗 = 1, 𝑛
Dans plusieurs situations pratiques, les coefficients 𝑎𝑖𝑗 , 𝑏𝑖 , 𝑐𝑗
ne sont pas connus avec certitude: un Programme Linéaire
Stochastique (PLS) se découle dans ce cas. 4
Comment le résoudre?
Méthode de la valeur estimée (EXPECTED VALUE Method)
Min −x2 1,0.75 avec p = 0.5
s. c x1 + x2 + x3 = 2 a21 , a22 =
𝒂𝟐𝟏 𝒙𝟏 + 𝒂𝟐𝟐 𝒙𝟐 + 𝒙𝟒 = 𝟐 −3,1.25 avec p = 0.5
−1 ≤ x1 ≤ 1
xj ≥ 0, j = 2,3,4
E[a21 ]= -1 𝒙𝟏 +𝟎. 𝟕𝟓𝒙𝟐 + 𝒙𝟒 ? = 𝟐
E[a22 ]=1 −𝟑𝒙𝟏 + 𝟏. 𝟐𝟓 𝒙𝟐 + 𝒙𝟒 ? = 𝟐.
EVS = (x1 , x2 , x3 , x4 ) = (0,2,0,0)
Non faisable sous incertitude !!
5
Méthode d’analyse de scénarios
Résoudre le problème pour toutes les réalisations possibles
des variables aléatoires (Elle suppose que les évènements
aléatoires se présentent suivant des distributions discrètes).
Min −x2
1,0.75 avec p = 0.5 s. c x1 + x2 + x3 = 2
a21 , a22 = 𝒙𝟏 + 𝟎. 𝟕𝟓 + 𝒙𝟒 = 𝟐
−3,1.25 avec p = 0.5 −1 ≤ x1 ≤ 1
xj ≥ 0, j = 2,3,4
(-1, 3, 0, 0.75).
Min −x2
Chaque solution a une chance s. c x1 + x2 + x3 = 2
−𝟑 𝒙𝟏 + 𝟏. 𝟐𝟓 𝒙𝟐 + 𝒙𝟒 = 𝟐
de 50% d’échouer à satisfaire la −1 ≤ x1 ≤ 1
contrainte !! xj ≥ 0, j = 2,3,4 6
(0.12, 1.88, 0, 0)
Exercice
La demande d’une ville en eau est 10 unités. La ville reçoit de
l’eau à partir d’une rivière. Cette source fournit une quantité
d’eau b. En cas de manque, les autorités peuvent acheter de l’eau
d’une autre ville voisine avec c$ l’unité.
Considérons que la variable aléatoire dans ce problème possède 5
réalisations possibles équiprobables qui sont : 0,3,6,9,12.
1. Appliquer l’approche de la valeur estimée.
2. Appliquer l’approche d’analyse de scénarios.
3. Considérer maintenant que la variable aléatoire suit la loi
uniforme sur l’intervalle [2,8]. Appliquer l’approche de la 7
valeur estimée.
Problèmes avec Recours
Optimiser les décisions que l’on doit prendre au moment T=1
tout en tenant compte de leurs conséquences futures pour
toute réalisation possible des aléas.
Le mot “Recours” révèle la possibilité dont on dispose de
remédier à une décision de la première étape éventuellement
trop optimiste en mettant en œuvre des actions correctives,
évidemment plus chères, qui satisfont pourtant les contraintes
posées aux instants ultérieurs (T > 1).
8
Dans ce qui suit, nous considérerons le cas de deux étapes
seulement (T=2).
Problèmes avec Recours à deux Etapes
• Décisions de première étape (structurantes, stratégiques)
sont prises avant que l’incertitude soit levée. Elles ne peuvent
plus changer à la seconde étape.
• Décisions de seconde étape (actions correctives ou de
recours) sont prises en réagissant à la situation qui se
présente après que les variables aléatoires réalisent leurs
valeurs.
9
Exemple 1: Planification de production
Un usine peut traiter deux matières premières 𝑚𝑎𝑡1 et 𝑚𝑎𝑡2
afin de produire deux produits 𝑝𝑟𝑜𝑑1 et 𝑝𝑟𝑜𝑑2. La demande sur
les produits est aléatoire ainsi que les productivités des
matières premières. Afin de satisfaire ses clients, les quantités
manquantes peuvent être achetées directement du marché
Décisions 1ere étape: quantités traités des matières premières.
Décisions 2eme étape: quantités achetées des produits en cas de
10
manque.
Exemple 2: Newsboy vendor problem
Chaque matin, un vendeur de journaux doit décider combien
de journaux à acheter afin de maximiser son profit. Il ne sait
pas au début de la journée combien de journaux il pourra
vendre. À la fin de la journée, le vendeur peut retourner
chaque journal invendu . La demande quotidienne en
journaux est décrite par une variable aléatoire 𝛚 .
Décisions 1ere étape: nombre de journaux achetées le matin
Décisions 2eme étape: nombre de journaux vendu et revendu
11
Formulation d’un PLS en deux étapes avec recours
Dans ce problème, les décisions de la première étape sont prises en
tenant compte de leurs conséquences futures. Ces dernières sont
mesurées par ce qu’on appelle fonction de recours . On dénote les
variables aléatoires (discrètes ou continues) par un vecteur 𝜉.
𝒎𝒊𝒏 𝒄𝑻 𝒙 + 𝝍(𝒙)
s.c 𝑨𝒙 = 𝒃 , 𝒙 ≥ 𝟎
avec 𝝍 𝒙 = 𝑬𝝃 𝑸 𝒙, 𝝃
et 𝑸 𝒙, 𝝃 = 𝐦𝐢𝐧 𝒒 𝝃 𝑻 𝒚 | 𝑾 𝝃 𝒚 = 𝒉 𝝃 − 𝑻 𝝃 𝒙, 𝒚 ≥ 𝟎
12
𝒎𝒊𝒏 𝒄𝑻 𝒙 + 𝝍(𝒙)
s.c 𝑨𝒙 = 𝒃 , 𝒙 ≥ 𝟎
𝝍 𝒙 = 𝑬𝝃 𝑸 𝒙, 𝝃
𝑸 𝒙, 𝝃 = 𝐦𝐢𝐧 𝒒 𝝃 𝑻 𝒚 | 𝑾 𝝃 𝒚 = 𝒉 𝝃 − 𝑻 𝝃 𝒙, 𝒚≥𝟎
𝑥 : décisions de la première étape
𝐴, 𝑏, 𝑐: Matrice et vecteurs déterministes.
𝜓 𝑥 : Espérance de la fonction de recours.
𝑄 𝑥, 𝜉 : fonction de recours.
𝑦 : décisions de la deuxième étape
𝑞 𝜉 : Vecteur stochastique des coûts unitaires de pénalités
W(𝜉) : Matrice de recours stochastique 13
ℎ 𝜉 − 𝑇 𝜉 𝑥 : mesure le manque
Modélisation du problème de Planification de production
Un usine peut traiter deux matières premières 𝑚𝑎𝑡1 et 𝑚𝑎𝑡2
afin de produire deux produits 𝑝𝑟𝑜𝑑1 et 𝑝𝑟𝑜𝑑2. Les coûts de
production sont c 𝑇 = (2,3) 𝑇 . La capacité de production ne
peut dépasser 100. La demande sur les produits est aléatoire
ainsi que les productivités des matières premières. Afin de
satisfaire ses clients, les quantités manquantes peuvent être
achetées directement du marché avec les coûts unitaires
suivants : q 𝑇 = (7,12) 𝑇 .
On cherche à trouver le plan de production optimale. 14