Calcul d'une politique optimale avec actualisation

On considère (enfin) le cas où on peut choisir entre plusieurs décisions en chaque état et on veut minimiser le coût total avec actualisation.
C'est évident que la décision optimale en chaque état ne dépend ni de l'histoire ni du temps.

On peut utiliser l'algorithme d'amélioration d'une politique initiale: calculer le coût total (avec actualisation) vj à partir de chaque état j; choisir à chaque état i la décision *d qui minimise a *di + råj=1N P *di,j vj; répéter tant qu'il y a une réduction;
(Ca équivaut à minimiser le coût qu'on aurait si on choisissait une nouvelle politique pour la première étape et gardait l'ancienne politique après, ce qui explique pourquoi il y a amélioration)

Terminaison de l'algorithme

Démonstration plus ``mathématique'' que l'algorithme réduit les coûts à chaque étape, sauf si on est déjà à une politique optimale:

D'abord avec les décisions d on a:
vdi  =  adi + r N
å
j=1 
Pdi,j vdj

On choisit *d tel que
a *di + r N
å
j=1 
P *di,j vdj £ vdi
(et on continue si on a < pour au moins un i)

Les vrais nouveaux coûts sont donnés par:
*v *di = a *di + r N
å
j=1 
P *di,j *v *dj

Donc:
vdi - *vi *d ³ r N
å
j=1 
P *di,j(vdj - *vj *d)
(et on a > pour au moins un i)

Considérons le i qui donne le minimum de vid - *vi *d: on a


vdi - *vi *d ³ r N
å
j=1 
P *di,j(vdi - *vi *d)


vdi - *vi *d ³ r(vdi - *vi *d)


vdi - *vi *d ³ 0

et, donc, vdj - *vj *d ³ 0 pour tout j

Finalement on ne peut pas avoir =0 pour tout j; et donc on a une amélioration pour tout j...

Le cas sans actualisation

Ce cas est plus compliqué parce que les équations:
vi  =  ai + r N
å
j=1 
Pi,j vj
ne sont pas utilisables si r = 1; (soit aucune solution, soit plusieurs)

On peut définir v(n)i le coût moyen d'une suite de n transitions à partir de l'état i. On trouve que
v(n)i  ®   n g + vi
où, maintenant, vi est le coût d'avoir commencé en l'état i.

On a
vi = ai - g + åj=1N Pi,jvj

mais ces équations ne suffisent pas (ajout de la même constante k à chaque vi donne une nouvelle solution) Il faut ajouter

N
å
i=1 
Pi vi = 0

On essaie d'optimiser la politique en utilisant la même idée que dans le cas avec actualisation:

Un exemple: assurance d'un véhicule

Le coût de l'assurance d'un véhicule est 100, 200, 400 ou 600.
Après un an sans aucun accident déclaré, le prix est réduit au niveau inférieur
Après un an avec un accident déclaré, le prix est augmenté au niveau supérieur
La probabilité d'un accident grave est 5% par an
La probabilité d'un accident mineur est 15% par an et le coût de sa réparation est 500
Devrait-on déclarer un accident mineur ou payer la réparation?
(nous prenons r = 0.9 et supposons les coûts actualisés au début de l'année)

Calcul de la politique optimale

Je commence avec la politique de déclarer tout incident
v1
=
100 + 0.9(.8v1+.2v2)
v2
=
200 + 0.9(.8v1+.2v3)
v3
=
400 + 0.9(.8v2+.2v4)
v4
=
600 + 0.9(.8v3+.2v4)
et je calcule v=[1315,1489,1905,2405]
Donc une meilleur politique pour les niveau 200 et 400 est de payer les réparations (par exemple pour v2, 200 + 0.9(.8v1+.2v3) > 275 + 0.9(.95v1+.05v3)):
v1
=
100 + 0.9(.8v1+.2v2)
v2
=
275 + 0.9(.95v1+.05v3)
v3
=
475 + 0.9(.95v2+.05v4)
v4
=
600 + 0.9(.8v3+.2v4)
et v=[1304,1472,1839,2347] Maintenant on voit qu'une meilleur politique à v2 est de déclarer l'accident
(parce que maintenant
200 + 0.9(.8v1+.2v3)
   <   275 + 0.9(.95v1+.05v3))

Donc, une troisième politique:
v1
=
100 + 0.9(.8v1+.2v2)
v2
=
200 + 0.9(.8v1+.2v3)
v3
=
475 + 0.9(.95v2+.05v4)
v4
=
600 + 0.9(.8v3+.2v4)
et v=[1299,1465,1833,2341]
la solution optimale!
Le modèle n'est pas très réaliste (tous les accidents mineurs n'ont pas le même coût) mais ce calcul peut aider à prendre de bonnes décisions, par exemple en l'état 2 déclarer un sinistre si le coût est supérieur à r×(1833-1299).

Application à l'exemple de la compagnie de livraison
(sans actualisation)

Exemple plus sérieux parce que 286 états
Comment stocker une politique?
Une politique consiste en le choix à prendre pour chaque combinaison de demandes possibles;
nombre de demandes possibles pour chaque trajet=4
nombre de combinaisons =412  »  16.000.000
MAIS si on stocke les vi, on peut facilement décider le choix pour une combinaison de demandes donnée.
(le choix sera celui pour la prochaine politique à être trouvée par l'algorithme d'optimisation, donc meilleure sauf si les vi sont déjà ceux de la politique optimale)

La distribution stationnaire

175: proba 0.000199; (P,B,L,N) (3,1,1,5)
176: proba 0.002807; (P,B,L,N) (3,1,2,4)
177: proba 0.009328; (P,B,L,N) (3,1,3,3)
178: proba 0.003979; (P,B,L,N) (3,1,4,2)
179: proba 0.000461; (P,B,L,N) (3,1,5,1)
182: proba 0.003891; (P,B,L,N) (3,2,1,4)
183: proba 0.077652; (P,B,L,N) (3,2,2,3)
184: proba 0.084612; (P,B,L,N) (3,2,3,2)
185: proba 0.010439; (P,B,L,N) (3,2,4,1)
188: proba 0.021063; (P,B,L,N) (3,3,1,3)
189: proba 0.238848; (P,B,L,N) (3,3,2,2)
190: proba 0.082526; (P,B,L,N) (3,3,3,1)
193: proba 0.022501; (P,B,L,N) (3,4,1,2)
194: proba 0.064240; (P,B,L,N) (3,4,2,1)
197: proba 0.003536; (P,B,L,N) (3,5,1,1)
210: proba 0.001801; (P,B,L,N) (4,1,1,4)
211: proba 0.018411; (P,B,L,N) (4,1,2,3)
212: proba 0.015182; (P,B,L,N) (4,1,3,2)
213: proba 0.002270; (P,B,L,N) (4,1,4,1)
216: proba 0.024650; (P,B,L,N) (4,2,1,3)
217: proba 0.108160; (P,B,L,N) (4,2,2,2)
218: proba 0.034831; (P,B,L,N) (4,2,3,1)
221: proba 0.045585; (P,B,L,N) (4,3,1,2)
222: proba 0.064734; (P,B,L,N) (4,3,2,1)
225: proba 0.009697; (P,B,L,N) (4,4,1,1)
237: proba 0.002730; (P,B,L,N) (5,1,1,3)
238: proba 0.007733; (P,B,L,N) (5,1,2,2)
239: proba 0.002520; (P,B,L,N) (5,1,3,1)
242: proba 0.010885; (P,B,L,N) (5,2,1,2)
243: proba 0.013463; (P,B,L,N) (5,2,2,1)
246: proba 0.008298; (P,B,L,N) (5,3,1,1)
257: proba 0.000820; (P,B,L,N) (6,1,1,2)
258: proba 0.000792; (P,B,L,N) (6,1,2,1)
261: proba 0.001280; (P,B,L,N) (6,2,1,1)
271: proba 0.000072; (P,B,L,N) (7,1,1,1)

Calcul du meilleur choix

(Etat et demandes connus)
Pour chaque ville il y a un nombre pas trop élevé de plans possibles;
la direction de la compagnie interdit de garder un camion dans une ville où il y a de la demande non satisfaite;
donc, ce n'est que dans le cas que la demande dépasse le nombre de camions que le choix doit être calculé;
et, par exemple, si on a 3 camions à Bordeaux, le nombre de plans possibles est au maximum 10 et moins si quelques demandes sont inférieures à 3:
(0,0,3), (0,1,2), (0,2,1), (0,3,0)
(1,0,2), (1,1,1), (1,2,0)
(2,0,1), (2,1,0)
(3,0,0)

5!/2!

Chaque plan a une valeur (l'argent gagné par les trajets partants);
pour chaque combinaison de quatre plans (quelques milliers dans le pire des cas), on peut calculer la somme des quatre coûts (valeurs multipliées par -1) et le v de l'état résultant;
et on choisit la meilleure somme.

Optimisation

Pour chaque état
pour chaque combinaison de demandes
décider le choix et donc le nouveau v (moyen)
pondérer par la probabilité de cette combinaison
ajouter pour trouver le nouveau v de cet état
pour les »  16.000.000 combinaisons c'est possible mais peut-être lent
On peut faire mieux:
Dans un état (par exemple (3,3,2,2)) pour chaque trajet (par exemple Paris-Nantes) toutes les demandes supérieures ou égales au nombre de camions disponibles peuvent être traitées ensemble
dans l'exemple, au lieu de probabilités 0.2, 0.3,0.4,0.1 pour demandes (1,2,3,4) on aura probabilités 0.2, 0.3,0.5 pour demandes (1,2, ³ 3).

Réduction importante?

Dans l'exemple, au lieu de 12 trajets avec 4 possibilités chacun, on a:

nombre de combinaisons à considérer:
38 ×42 ×22 = 419904
Pareil dans les autres cas bien équilibrés et beaucoup mieux dans les (nombreux) autres.
Réduction en moyenne très importante.




File translated from TEX by TTH, version 3.05.
On 30 Sep 2003, 11:14.