3.2.4 Programmation
dynamique :
La programmation dynamique est l'une des grandes paradigmes de
l'algorithmique, elle s'applique généralement à des
problèmes d'optimisation pour les quels le calcul de la solution
optimale fait appel à la résolution de sous-problème
similaire au problème initial.
Ces sous - problèmes naissent souvent des
différentes choix que l'on peut effectuer pour construire une
solution.
Une approche de programmation dynamique sera efficace si un
même sous-problème apparait à plusieurs reprises lors de
l'analyse.
Cette méthode consiste à éliminer les
recalcules dans un programme récursif en stock, on envisage la
programmation dynamique lorsque :
ü La subdivision n'est pas facile à
déterminer de façon optimale.
ü Les sous-problèmes ne sont pas
indépendants.
La programmation dynamique est une méthode dont les
calculs se fait de bas en haut : on commence par résoudre les plus
petits sous -problèmes, en combinant leur solution, on obtient les
solutions des sous-problèmes de plus en plus grand.
La conception d'un algorithme de programmation dynamique peut
être planifiée dans une séquence de quatre
étapes :
ü Décomposer le problème de décision
global en phases. chaque phase est relative à, la prise d'une
décision, on donne à chaque phase un numéro k qui est un
nombre indiquant le nombre de phase (ou décision) qui restent à
faire (à prendre).
ü Au début de chaque phase il doit être
possible d'énumérer tous les états possibles du
système, c'est-à-dire de décrire toutes les situations
où pourrait être le système.
ü A chaque phase il ya n décisions
possibles : les décisions ou politiques sont
désignées par xj (j= 1, ..., n).
ü Associer à chaque décision pour une phase
k un résultat qui mesure la « valeur » de la
décision. Les politiques possibles ne sont pas nécessairement les
mêmes à chaque phase. d'autre part les politiques possibles
à une phase dépendent de l'état initial du système,
et donc ne sont pas possibles pour chaque état.
L'ensemble des notations qui sont utilisées dans la
formulation et la résolution des problèmes de programmation
dynamique sont :
K : numéro de phase indiquant le nombre de
phases restant jusqu'à la fin de l'horizon (ou fin de solution du
problème)
S : état du système (de la nature) au
début d'une phase
xj : la jème politique ou
décision à prendre
dk (s, xj) : effet total
(résultat) de la politique xj prise à la phase k étant
donné l'état s du système
fk(s, xj) effet total (direct et indirect) pour les k
dernières phases étant donné que :
§ L'état au début de la phase k est s.
§ La politique xj est adoptée pour la phase k.
§ Une fois cette politique xi choisie et qu'il en
résulte un état pour le début de la phase k-1, des
politiques optimales sont choisies pour les k-1 phases suivantes.
| 
