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 1
Programmation Dynamique
1
Master I SIAD 2020/2021
Problèmes d’optimisation auxquels on s’intéresse
Sont associés à des situations où des décisions doivent être
prises de manière séquentielle:
On cherche une suite de décisions optimales.
Impliquent un système dynamique à temps discret.
Sur horizon fini:
Le système évolue sur un nombre fini d’ étapes.
Impliquent une fonction coût (à la base) additive:
c’est-à-dire que le coût s'accumule avec le temps. 2
Modèle de base
Un problème de Programmation Dynamique Déterministe
implique un système dynamique en temps discret de la forme:
𝑥𝑘+1 = 𝑓𝑘 (𝑥𝑘 , 𝑢𝑘 ) 𝑘 = 1,2, … , 𝑁
𝑘 : numérote les périodes ou les étapes et N est l’horizon ou le
nombre de fois que doit prendre une décision
𝑥𝑘 : état du système au début de la période k , 𝑥𝑘 ∈ 𝑆𝑘 . 𝑆𝑘 est
l’ensemble de tous les états possibles.
𝑢𝑘 : décision (ou contrôle) devant être prise à la période k, 𝑢𝑘
∈ 𝐶𝑘 . 𝐶𝑘 est l’ensemble de toutes les décisions possibles.
𝒇𝒌 : fonction de transfert ou de transition qui décrit le
mécanisme par lequel l'état est mis à jour de l’ étape k à l’ 3
étape k + 1.
Modèle de base (suite)
Une fonction coût est associée à chaque période du système dynamique
(coût intermédiaire) et qu’on dénote :
𝑔𝑘 (𝑥𝑘 , 𝑢𝑘 )
Il est possible de définir un coût terminal dépendant uniquement de
l’état atteint à la fin du processus et qu’on dénote:
𝑔𝑁+1 (𝑥𝑁+1 ).
Pour un état initial x1 , le coût total associé à une suite de décision
u1 , u2 ,…. uN est:
𝐽 𝑥1 ; 𝑢1 …. 𝑢𝑁 = 𝑔𝑁+1 𝑥𝑁+1 + 𝑔𝑘 (𝑥𝑘 , 𝜇𝑘 (𝑥𝑘 )) 4
𝑘=1
Modélisation des problèmes d’optimisation en tant que
des problèmes de PD
1. Identifier les décisions (𝑢𝑘 ) à prendre et quand (k) ?
2. Choisir l’état (𝑥𝑘 ) qui doit inclure toute information
connu à l’étape k par le décideur et qu’il peut exploiter
dans la prise de décision.
3. (…le reste se découle )
5
Exemple de Modélisation: problème de sac à dos
On veut charger un sac de volume b par des
objets de différents types numérotés de 1 à
N.
Chaque objet de type k est caractérisé par
une valeur 𝑐𝑘 > 0 entière et un volume
𝑎𝑘 > 0 également entier.
on considère que l'on a plusieurs
exemplaires de chaque objet.
6
Exemple de Modélisation: problème de sac à dos
On veut charger un sac de volume b par des
objets de différents types numérotés de 1 à
N.
Chaque objet de type k est caractérisé par
une valeur 𝑐𝑘 > 0 entière et un volume
𝑎𝑘 > 0 également entier.
on considère que l'on a plusieurs
exemplaires de chaque objet.
Objectif:
Trouver le nombre (entier) d'exemplaires à prendre pour chaque type
d’objet. La sélection doit être de valeur maximale ne dépassant pas le 7
volume du sac
Exemple de Modélisation: problème de sac à dos
𝒖𝒌 : nombre d’objets de type k à inclure dans la sélection.
Le nombre des étapes étant égal au nombre de décisions à
prendre. Alors, les étapes seront numérotées de 1 à N (N :
nombre des types des objets).
Au début de l’étape k , afin de décider combien d’objets
mettre, on dois savoir l’espace disponible après insertion des
objets 𝟏 … 𝒌 − 𝟏 = L’état 𝑥𝑘 du système
𝑥𝑘
Chaque décision doit vérifier: 0 ≤ 𝑢𝑘 ≤ . 8
𝑎𝑘
Exemple de Modélisation: problème de sac à dos
Si 𝑢𝑘 objets de type k sont sélectionnés, l’espace disponible à l’étape
k+1 est :
𝑥𝑘+1 = 𝑓𝑘 (𝑥𝑘 , 𝑢𝑘 )= 𝑥𝑘 - 𝑎𝑘 𝑢𝑘 , k=1,2,…,N
La valeur des objets sélectionnés à l’étape k est définie comme suit:
𝑔𝑘 𝑥𝑘 , 𝑢𝑘 = 𝑐𝑘 𝑢𝑘
Le profit total sera alors :
𝑁 𝑁
𝑘=1 𝑔𝑘 𝑥𝑘 , 𝑢𝑘 = 𝑘=1 𝑐𝑘 𝑢𝑘
Aucun bénéfice terminal n’est défini :
9
𝑔𝑁+1 (𝑥𝑁+1 ) = 0
Modèle stochastique sur horizon fini
A chaque étape k, on observe l‘état 𝑥𝑘 et on prend une décision 𝑢𝑘
Puis, une variable aléatoire 𝝎𝒌 est générée selon une loi de
probabilité ∶
𝑷𝒌 (𝝎𝒌 |𝒙𝒌 , 𝒖𝒌 )
On observe 𝜔𝑘 et on paye un coût:
𝒈𝒌 (𝒙𝒌 , 𝒖𝒌 , 𝝎𝒌 )
L‘état à la prochaine étape est :
𝒙𝒌+𝟏 = 𝒇𝒌 (𝒙𝒌 , 𝒖𝒌 , 𝝎𝒌 )
On parlera alors d’espérance du coût total:
𝑁
10
𝐽 𝑥1 ; 𝑢1 …. 𝑢𝑁 = 𝑬𝝎𝒌 𝑔𝑁+1 𝑥𝑁+1 + 𝑔𝑘 (𝑥𝑘 , 𝑢𝑘 , 𝝎𝒌 )
𝑘=1
Espérance Mathématique: Rappel
Considérons une variable aléatoire Y discrète prenant les
valeurs yi avec les probabilités pi . L’espérance est définie
comme-suit :
E Y = pi yi
i
Exemple
On lance un dé équilibré à six faces, numérotées de 1 à 6. On
gagne 6 u.m, si on obtient 1 ou 6 et on perd 2 u.m sinon.
𝟐
P(𝐘 = 𝟔) =
𝟔
𝟒
P(𝐘 = −𝟐) =
𝟔
𝟐 𝟏 𝟐 11
𝐄 𝐘 = ∗ −𝟐 + ∗ 𝟔 =
𝟑 𝟑 𝟑
Exemple: Gestion de Stock
𝑥𝑘 : niveau du stock au début de l’étape k (i.e avant de
commander).
𝑢𝑘 : nombre de biens commandés (et reçus).
𝜔𝑘 : nombre de bien demandés par les clients durant l’étape k.
(on ne peut pas savoir quelle sera la demande clientèle avant de
prendre notre décision)
Fonction de transition:
𝒙𝒌+𝟏 = 𝒙𝒌 + 𝒖𝒌 − 𝝎𝒌
𝒙𝒌+𝟏 = 𝑴𝒂𝒙 {𝒙𝒌 + 𝒖𝒌 − 𝝎𝒌 ,0}
12
Algorithme de la PD déterministe
Fonction Coût
Additive
13
Résolution du problème de sac à dos
par l’algorithme de la PD
On cherche le chargement optimal d’un sac de volume 6.
Les caractéristiques des objets susceptibles d’être inclus
dans ce sac sont données par le tableau suivant :
14
