Chapitre 5 • Pro ces sus sto chas tiques et pro gram ma tion…
218
Bien entendu, l’exemple n’est rela tif qu’à deux phases, mais on peut ima gi ner
un nombre élevé de phases suc ces sives. Il arrive par fois que les diverses phases se
déroulent exac te ment selon le même schéma, contrai re ment à ce qui se passe dans
l’exemple choisi cidessus ; il est alors indi qué de faire appel éga le ment à la théo rie
des chaînes de Markov (méthode de Howard).
Le théo rème d’optimalité, rela tif à un phé no mène s’éten dant sur N périodes,
s’énonce alors : une sous- stratégie opti male de Ν à N 2 n ne peut être for mée que
par une sous- stratégie opti male de Ν à N 2 n 1 1.
On peut évi dem ment consi dé rer, en ave nir aléa toire, des choix dis crets ou conti
nus, un hori zon (nombre de phases) limité ou un hori zon illi mité.
Essayons de for mu ler les équa tions de récur rence dans le cas aléa toire, comme
nous l’avons fait pour le cas cer tain, avec des choix dis crets et un hori zon limité.
Nous choi si rons un pro ces sus où, à chaque phase, le hasard inter vient pour faire
évo luer la situa tion, après que l’on ait pris une déci sion ; pour cette rai son, on qua li
fie un tel pro ces sus de pro ces sus D.H. (décision hasard) ; il existe, bien entendu, le
pro ces sus inverse, H.D., un peu plus dif fi cile cepen dant à manier.
Soient donc :
• E
t 2 1
1 , E
t 2 1
2 , c , E
t 2 1
i , c , E
t 2 1
p(t) , les états dans les quels peut se trou ver le sys tème
au début de la phase t ; p(t) désigne le nombre d’états pos sibles lors de ce début de
phase.
• D
t
1 , D
t
2 , c , D
t
j , c , D
t
q(t) , les états vers lesquels le déci deur peut trans fé rer le sys
tème par la déci sion qu’il prend à la phase t ;
• c
t
ij , le coût de la déci sion de trans fé rer le sys tème de l’état E
t 2 1
i
à l’état D
t
j (dans
l’exemple ci dessus ce coût était nul).
Obser vons tou te fois qu’à par tir de l’état E
t 2 1
i , seule une par tie des D
t
j , soit G
1
1 E
t 2 1
i
2 ,
est acces sible ;
• p
t
jk , la pro ba bi lité de pas ser de l’état D
t
j à l’état E
t
k à la fin de la phase t, et r
t
jk le
revenu résul tant de ce pas sage (cf les arcs en poin tillés de la Fig 5.3).
Rap pe lons qu’on appelle « stra té gie » la col lec tion des déci sions qui doivent être
prises, pour chaque phase, quand le sys tème est dans un état déter miné.
Sup po sons que nous connais sions la sous stratégie opti male du début de la phase
t 1 1 jus qu’à la fin de la phase N, donc les z
*
t 1 E
t
k 2 , c’est àdire les p(t) valeurs opti
males de l’espé rance mathéma tique du revenu en cha cun des états pos sibles E
t
k à la
fin de la phase t (ou début de la phase t 1 1).
Nous écri rons z
*
t 1 E
t
k 2 sous la forme plus simple z
*t
k . Nous vou lons éva luer les
z
*t 2 1
i
, c’est àdire espé rances mathéma tiques opti males lorsque, au début de la phase
t, le sys tème se trouve dans l’état E
t 2 1
i . On a :
z
*t 2 1
t
5 max
jPG
1 (E t 2 1
t
)
e 2c
t
ij 1 a
p(t)
k51
p
t
jk
# (r
t
jk 1 z
*t
k ) f .
218
Bien entendu, l’exemple n’est rela tif qu’à deux phases, mais on peut ima gi ner
un nombre élevé de phases suc ces sives. Il arrive par fois que les diverses phases se
déroulent exac te ment selon le même schéma, contrai re ment à ce qui se passe dans
l’exemple choisi cidessus ; il est alors indi qué de faire appel éga le ment à la théo rie
des chaînes de Markov (méthode de Howard).
Le théo rème d’optimalité, rela tif à un phé no mène s’éten dant sur N périodes,
s’énonce alors : une sous- stratégie opti male de Ν à N 2 n ne peut être for mée que
par une sous- stratégie opti male de Ν à N 2 n 1 1.
On peut évi dem ment consi dé rer, en ave nir aléa toire, des choix dis crets ou conti
nus, un hori zon (nombre de phases) limité ou un hori zon illi mité.
Essayons de for mu ler les équa tions de récur rence dans le cas aléa toire, comme
nous l’avons fait pour le cas cer tain, avec des choix dis crets et un hori zon limité.
Nous choi si rons un pro ces sus où, à chaque phase, le hasard inter vient pour faire
évo luer la situa tion, après que l’on ait pris une déci sion ; pour cette rai son, on qua li
fie un tel pro ces sus de pro ces sus D.H. (décision hasard) ; il existe, bien entendu, le
pro ces sus inverse, H.D., un peu plus dif fi cile cepen dant à manier.
Soient donc :
• E
t 2 1
1 , E
t 2 1
2 , c , E
t 2 1
i , c , E
t 2 1
p(t) , les états dans les quels peut se trou ver le sys tème
au début de la phase t ; p(t) désigne le nombre d’états pos sibles lors de ce début de
phase.
• D
t
1 , D
t
2 , c , D
t
j , c , D
t
q(t) , les états vers lesquels le déci deur peut trans fé rer le sys
tème par la déci sion qu’il prend à la phase t ;
• c
t
ij , le coût de la déci sion de trans fé rer le sys tème de l’état E
t 2 1
i
à l’état D
t
j (dans
l’exemple ci dessus ce coût était nul).
Obser vons tou te fois qu’à par tir de l’état E
t 2 1
i , seule une par tie des D
t
j , soit G
1
1 E
t 2 1
i
2 ,
est acces sible ;
• p
t
jk , la pro ba bi lité de pas ser de l’état D
t
j à l’état E
t
k à la fin de la phase t, et r
t
jk le
revenu résul tant de ce pas sage (cf les arcs en poin tillés de la Fig 5.3).
Rap pe lons qu’on appelle « stra té gie » la col lec tion des déci sions qui doivent être
prises, pour chaque phase, quand le sys tème est dans un état déter miné.
Sup po sons que nous connais sions la sous stratégie opti male du début de la phase
t 1 1 jus qu’à la fin de la phase N, donc les z
*
t 1 E
t
k 2 , c’est àdire les p(t) valeurs opti
males de l’espé rance mathéma tique du revenu en cha cun des états pos sibles E
t
k à la
fin de la phase t (ou début de la phase t 1 1).
Nous écri rons z
*
t 1 E
t
k 2 sous la forme plus simple z
*t
k . Nous vou lons éva luer les
z
*t 2 1
i
, c’est àdire espé rances mathéma tiques opti males lorsque, au début de la phase
t, le sys tème se trouve dans l’état E
t 2 1
i . On a :
z
*t 2 1
t
5 max
jPG
1 (E t 2 1
t
)
e 2c
t
ij 1 a
p(t)
k51
p
t
jk
# (r
t
jk 1 z
*t
k ) f .