INDEX

III. Caractéristiques d’un problème de programmation dynamique

Nous allons maintenant sur la base de l’exemple précédant analyser les propriétés communes aux problèmes de programmation dynamique.

(i) Le problème peut être décomposé en étapes et une décision doit être prise à chaque étape.

Le dernier exemple est devisé en 4 étapes où à chaque étape, la décision à prendre est celle de la destination à choisir. Ces décisions sont interdépendantes et séquentielles.

(ii) A chaque étape correspond un certain nombre d’états. Dans l’exemple du voyageur, les états à chaque étapes sont représentés par les villes que le voyageur visité. Le nombre de ces états dans l’exemple est fini. Dans ce qui suit en étudiera des problèmes où le nombre d’états est infinie (xnÎ IN) ou continue (xnÎ IR)

(iii) A chaque étape, la décision prise transforme l’état actuel en un état associé à l’étape suivante (dans certains cas avec une distribution de probabilité).

Dans notre exemple, se trouvant à une ville donnée, le voyageur décide de se rendre à une autre ville qui est un état de l’étape suivante.

(iv) Etant donné un état, une stratégie optimale pour les étapes restantes est indépendante des décisions prises au étapes précédentes.

Si le voyageur est dans un état quelconque de l’étape i, le chemin optimal entre cet état et l’état 10 sera indépendant de la façon dont il y est arrivé. En d’autres termes, l’état actuel contient toute l’information nécessaire aux décisions futures. Cette propriété est dite principe d’optimalité.

(v) L’algorithme de recherche de la solution optimale commence par trouver la stratégie optimale pour tous les états de la dernière étape.

(vi) Une relation de récurrence identifie la stratégie optimale dans chaque état de l’étape n à partir de la stratégie optimale dans chaque état de l’étape n+1.

Dans notre exemple la relation est (S)= {Csxn + (xn)}

La stratégie optimale étant donné que nous sommes à l’état S de l’étape n, nécessite de retrouver la valeur de xn qui minimise l’expression ci-dessus.

La relation de récurrence à toujours cette forme (S)= ou {fn(S,xn)},

avec fn(S,xn) est une expression en fonction de S, xn et (-)

(vii) Utilisant cette relation de récurrence, l’algorithme procède à reculons étape par étape. Il détermine la stratégie optimale pour chaque état de chaque étape.

Dans tout problème de programmation dynamique, on peut construire à chaque étape un tableau analogue au suivant.

Etape n

 

fn(S, x1)

 

 

x1

S

états n+1

(s)

états n

le coût ou la distance

La longueur du chemin optimal à partir de S jusqu’à l’état final

Le meilleur état de l’étape n+1 le long du chemin optimal final

  

Cliquer ici pour enregistrer le chapitre 7 en format Word sur votre disque dur (436 Ko)


Pour tout commentaire envoyer un mail à hatem_masri@yahoo.com