Calcul d'une politique optimale avec actualisation
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:
|
On choisit *d tel que
|
Les vrais nouveaux coûts sont donnés par:
|
Donc:
|
Considérons le i qui donne le minimum de vid - *vi *d: on a
|
|
|
Finalement on ne peut pas avoir =0 pour tout j; et donc on a une amélioration pour tout j...
Le cas sans actualisation
|
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
|
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
|
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
Calcul de la politique optimale
|
|
Donc, une troisième politique:
et v=[1299,1465,1833,2341]
v1
=
100 + 0.9(.8v1+.2v2)
v2
=
200 + 0.9(.8v1+.2v3)
v3
=
475 + 0.9(.95v2+.05v4)
v4
=
600 + 0.9(.8v3+.2v4)
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).
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)
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)
(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)
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.
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).
Dans l'exemple, au lieu de 12 trajets avec 4 possibilités chacun, on a: