Les chaînes de Markov
261
une condition nécessaire est en particulier
)
(1
2
1
3
C
C
C
Par la considération des coûts (ou gains) moyens par phase, on peut ainsi comparer entre
elles plusieurs politiques, correspondant à plusieurs chaînes de Markov. Le problème se
complique lorsque le hasard n'est pas seul à intervenir, c'est-à-dire lorsque, à chaque
étape du processus, on peut essayer d'infléchir l'avenir par des décisions. On tombe alors
dans le domaine de la programmation dynamique.
10.6. PROGRAMMATION DYNAMIQUE DISCRETE
Nous allons étudier le processus suivant, évoluant par phases, mais enrichi par rapport
au précédent schéma (chaîne de Markov avec valeurs de transition) par le fait qu'une
phase quelconque se décompose en deux étapes : une étape décision et une étape hasard.
On a alors la configuration suivante :
En début de phase , on peut se trouver en états
On prend une décision
(étape décision) amenant en un état parmi
possibles
; le coût (ou le
revenu) de cette décision est
si l'état de départ est
et l'état « décidé »
À partir de cet état le système évolue de façon aléatoire (étape hasard) pour se trouver
en fin de phase en un état . On connaît
, probabilité de passer de en
et
,
coût où revenu correspondant.
Le processus continue alors de cette façon jusqu'à la phase terminale
D
D
D
H
H
H
Phase t-1
Phase t
Phase t+1
D 1
D 1
D 1
D m
D m
D m
E 1
E 1
E 1
E n
E n
E n
E k
E j
D i
(t)
ki
p (t)
ij r (t)
ij
E k