next up previous
Next: About this document ...

Chaînes de Markov avec coûts associés
(tous les états persistants et apériodiques)

Coût d'une transition: Ai,j pour la transition de i à j (ne dépend pas du temps ni de l'histoire)

Coût moyen d'une transition: de l'état i:

\begin{displaymath}a_i ~=~ \sum_{j=1}^N P_{i,j}A_{i,j}\end{displaymath}

Coût moyen d'une suite de transitions de longueur n à partir de l'état i:

\begin{displaymath}v^{(n)}_i ~=~ a_i + \sum_{j=1}^N P_{i,j}v^{(n-1)}_j\end{displaymath}


v(n)  =  a + Pv(n-1)


v(n)  =  v(n-1) + Pn-1a

Tendance vers la moyenne

\begin{displaymath}v^{(n)}_i ~\rightarrow ~ n g + v_i \end{displaymath}

g est le coût moyen d'une transition dans la distribution limite $\Pi$ et vi est le coût d'avoir commencé en état i.
On peut calculer g:

\begin{displaymath}\sum_{i=1}^N \Pi _i a_i =g\end{displaymath}

et ensuite les vi:

\begin{displaymath}v_i = a_i - g + \sum_{j=1}^N P_{i,j}v_j \end{displaymath}


\begin{displaymath}\sum_{i=1}^N \Pi _i v_i = 0\end{displaymath}

Les seules différences entre les états sont leurs valeurs de vi. En effet vi-vj est le prix raisonnable à payer pour changer de i à j.

Décisions qui peuvent changer
les probabilités de transition

La possibilité de choix: supposons que dans l'état i on peut choisir entre plusieurs décisions et que pour la décision d, la probabilité d'aller en état j est Pdi,j avec un coût adi,j

on peut calculer l'espérance du coût d'une transition:

\begin{displaymath}a^d_i ~=~ \sum_{j=1}^N P^d_{i,j} a^d_{i,j}\end{displaymath}

mais minimiser ca n'est pas forcément la bonne politique

Une politique Markovienne est une règle qui détermine pour chaque état i, la probabilité de choisir chaque décision possible en cet état. Il existe une infinité (même non dénombrable) de politiques; il faut en choisir l'optimale!

Politiques ``stationnaires''

Les politiques ``mixtes'' sont celles où dans un état i au moins deux décisions ont une probabilité non nulle. C'est bien connu dans la théorie des jeux qu'une politique mixte peut être supérieure à toute politique non mixte (stationnaire).

Ici, ça n'est pas le cas; il existe toujours une politique stationnaire optimale.
C'est pareil à la programmation linéaire où il y a toujours une solution de base qui est optimale. Mais le nombre de politiques stationnaires peut être trop grand pour calculer le coût de chacune.

Optimisation d'un système non-linéaire!
Le coût n'est pas une fonction linéaire des probabilités des choix.

Calcul d'une politique optimale

Commencer à une politique stationnaire
(aucune difficulté pour la trouver)

Chercher des améliorations locales qui donnent une meilleure politique stationnaire:

Répéter tant qu'il y a des améliorations possibles

Pourquoi amélioration?
un changement de politique réduit le coût pour cet état;
cette réduction peut réduire les coûts d'autres états (mais pas les augmenter)

Pourquoi terminaison?
parce que amélioration à chaque étape et un nombre fini de politiques stationnaires

Pourquoi optimal?? Supposons que d est calculée et d' est optimale:
(a) vid-vid' ne dépend pas de i
(b) on peut changer d à d' pour un état i, en gardant les mêmes coûts
(c) ... et donc d et d' ont les mêmes coûts; d est aussi optimale.

Un exemple: remplacement et/ou entretien de machines
(Sakarovitch)
Une machine peut être dans l'état 1 (neuve), 2 (usagée) ou 3 (en panne);

Les choix possibles sont:
machine neuve: entretien normal:
entretien préventif:

machine usagée: entretien normal:
entretien minutieux:entretien super

machine en panne: remplacement;
révision générale. Les probabilités de transition (et coûts associés) sont:

machine neuve:
entretien normal: 0 (-), 0.9 (100), 0.1 (300)
entretien préventif: 0.1 (500), 0.9 (500), 0 (-)

machine usagée:
entretien normal: 0 (-), 0.7 (150), 0.3 (350)
entretien minutieux: 0 (-), 0.8 (400), 0.2 (600)
entretien super: 0 (-), 0.9 (750), 0.1 (950)

machine en panne:
remplacement: 1 (5000), 0 (-), 0 (-)
révision générale: 0.1 (7500), 0.9 (2500), 0 (-).

Les coûts moyens en 1 étape sont 120, 500, 210, 440, 770, 5000 et 3000.

Calcul de la politique optimale

On part de la politique (1,1,1)


\begin{displaymath}P ~=~ \begin{array}{rrr}
0 & 0.9 & 0.1 \\ 0 & 0.7 & 0.3\\ 1 & 0 & 0\end{array}\end{displaymath}

donc $ \Pi = (0.2,0.6,0.2) $

a = (120,210,5000) et donc g=1150.

v = ( -1200, - 483.33, 2650)

On décide une nouvelle politique de (2,2,2).
Par exemple, en l'état 1, le calcul v1=120+0.9 x -483.33+0.1 x 2650 donne -50;
par contre la politique 2 donne 500+0.1 x -1200 + 0.9 x -483.33 = -55 et la politique 2 est meilleure.


\begin{displaymath}P ~=~ \begin{array}{rrr}
0.1&0.9&0\\ 0&0.8&0.2\\ 0.1&0.9&0\end{array}\end{displaymath}

donc $ \Pi = (1/55,45/55,9/55)$

a = (500,440,3000) et donc g=860.

v = (-8100/11,-3700/11,19400/11)

On décide une nouvelle politique de (1,1,2).


\begin{displaymath}P ~=~ \begin{array}{rrr}
0&0.9&0.1\\ 0&0.7&0.3\\ 0.1&0.9&0\end{array}\end{displaymath}

donc $ \Pi = (1/44,3/4,10/44)$

a = (120,210,3000) et donc g=37050/44

v = (-473625,-226125,793575)/484
calculé par
solve(v1=120+(9/10)*v2+v3/10-g,
v2=210+(7/10)*v2+(3/10)*v3-g,
v1/44+3*v2/4+10*v3/44=0);

$\approx (-978,-467,1640)$

Aucune amélioration possible.




next up previous
Next: About this document ...
Mike ROBSON
2000-11-27