Programmation dynamique
Les problèmes propices
Le type de problèmes concerné
La programmation dynamique impose un cadre assez spécifique et donc des contraintes sur les problèmes que l’on peut résoudre grâce à cette méthode. En règle générale, il s’agit d’un problème dont le but est d’optimiser une suite de prises de décisions par rapport au coût qu’elles engendrent. Cette suite doit être finie et sa longueur (qu'on nommera N) connue par avance. Le système mis en jeu dans ce problème est par conséquent qualifié de système dynamique à temps discret.
De plus, la suite de prises de décisions correspond à un découpage du problème P en sous-problèmes Pn (avec n allant de 1 à N) : à la nème étape, il s’agit de résoudre le problème Pn. On espère que, plus n est grand, plus Pn est facile à résoudre. On cherchera enfin une relation de récurrence entre les sous-problèmes Pn de sorte à résoudre P.
Remarques complémentaires
Il convient de remarquer que l’on prendra des décisions au sens large : il s’agit d’assigner une valeur à une variable — par opposition au sens strict qui concerne les réponses de type oui/non.
Ensuite, les conséquences des décisions prises ne sont pas nécessairement déterministes. Il s'agit sans doute là d'un avantage incontestable de la programmation dynamique : nous pourrons nous contenter de lois de probabilités.
Enfin, le but du problème à résoudre peut s’énoncer de manière plus précise : nous pourrions déterminer que les problèmes propices à la résolution par l'approche type programmation dynamique ont pour objectif l'optimisation d'une fonction de coût (ou de profit) associée à la suite de décisions retenues et à leurs conséquences sur le système.
Le cadre industriel
La corrélation du type de problèmes concernés par une résolution favorable à l'application des méthodes de programmation dynamique nous amène à constater que cette technique d'optimisation est très souvent applicable dans un cadre industriel pour deux raisons :
- la nature additive (variable extensive) de la monnaie
- la loi des rendements décroissants sur la plupart des postes de production
En voici deux exemples concrets qui reviennent régulièrement dans la littérature :
- Optimiser la production d'un bassin minier en fonction des ressources sur chaque puits.
- Optimiser le nombre de consommateurs touchés par une campagne publicitaire en répartissant le budget sur différents médias, ou au contraire en le concentrant (on parle alors de media-planning).
En conclusion
La programmation dynamique est séduisante car son formalisme est assez générique, ce qui laisse libre cours à de multiples variantes et à la résolution de problèmes assez divers, qu’ils soient déterministes ou non. Cependant, seule la catégorie des problèmes d’optimisations séquentielles est concernée et la vérification de l’applicabilité du principe d’optimalité est indispensable avant toute utilisation de cette méthode.