--- title: "Programmation dynamique" source: "https://systems-analysis.info/int/Programmation_dynamique" wiki: "systems-analysis.info/int" article: "Programmation_dynamique" language: "fr" categories: - "Category:French" - "Category:Operations research" - "Category:Optimization" revision_id: 5889 wiki_created_at: 2026-09-06T23:55:28Z wiki_modified_at: 2026-09-06T23:55:28Z downloaded_at: 2026-09-07T23:10:53Z --- # Programmation dynamique **La programmation dynamique** (**PD** ; en anglais *dynamic programming, DP*) est une méthode de résolution de problèmes d'optimisation complexes, basée sur la décomposition du problème initial en une séquence de sous-problèmes plus simples^{[\[1\]](https://systems-analysis.info/int/Programmation_dynamique#cite_note-bigenc-dp-1)[\[2\]](https://systems-analysis.info/int/Programmation_dynamique#cite_note-ru-wiki-dp-2)}. La méthode s'applique aux processus de décision séquentiels, où la solution optimale du problème global peut être construite à partir des solutions optimales de ses sous-problèmes. Le terme a été introduit par le mathématicien américain Richard Bellman dans les années 1950^{[\[3\]](https://systems-analysis.info/int/Programmation_dynamique#cite_note-rechetnikov-dp-3)}. Dans ce contexte, le mot « programmation » est utilisé dans le sens de « planification » ou d'« élaboration d'un plan d'action optimal », et non dans celui de l'écriture de code informatique^{[\[4\]](https://systems-analysis.info/int/Programmation_dynamique#cite_note-en-wiki-dp-4)}. ## Principes et propriétés clés L'applicabilité de la programmation dynamique à un problème est déterminée par la présence de deux propriétés fondamentales. ### Principe d'optimalité de Bellman Le concept central de la méthode est le **principe d'optimalité de Bellman** (en anglais *Bellman's principle of optimality*). Il stipule que, quels que soient l'état initial et la décision initiale, les décisions suivantes doivent constituer une stratégie optimale par rapport à l'état résultant de la première décision^{[\[3\]](https://systems-analysis.info/int/Programmation_dynamique#cite_note-rechetnikov-dp-3)}. En d'autres termes, toute partie d'une trajectoire optimale est elle-même optimale. Cette propriété permet de décomposer le problème global en une séquence de sous-problèmes plus simples et de les résoudre de manière récursive. ### Sous-problèmes chevauchants Un problème possède la propriété de **sous-problèmes chevauchants** (en anglais *overlapping subproblems*) si, lors de sa résolution récursive, les mêmes sous-problèmes apparaissent de manière répétée. La programmation dynamique permet d'éviter les calculs redondants en sauvegardant les solutions des sous-problèmes déjà rencontrés (cette technique est appelée mémoïsation ou tabulation), ce qui augmente considérablement l'efficacité par rapport à une exploration récursive naïve. ## Équation de Bellman Du principe d'optimalité découle la relation de récurrence fondamentale de la méthode : l'**équation de Bellman**^{[\[1\]](https://systems-analysis.info/int/Programmation_dynamique#cite_note-bigenc-dp-1)}. Elle relie la « valeur » (gain ou coût optimal) de l'état actuel aux valeurs des états suivants. Sous sa forme générale pour un processus déterministe en plusieurs étapes avec une fonction objectif additive, elle s'écrit : $$ V_{k - 1}(x) = \max\limits_{y \in U(x)}\{\varphi_{k}(x,y) + V_{k}(f_{k}(x,y))\} $$ où : - $k$ — le numéro de l'étape (de $m$ à 1) ; - $x$ — l'état du système à l'étape $k - 1$ ; - $y$ — la décision (ou le contrôle) prise à l'étape $k$ ; - $\varphi_{k}(x,y)$ — le gain (ou le coût) à l'étape k ; - $f_{k}(x,y)$ — la fonction définissant le nouvel état du système (fonction de transition) ; - $V_{k}(s)$ — la valeur optimale de la fonction objectif pour le sous-problème commençant à l'étape $k$ dans l'état $s$. L'équation est résolue séquentiellement, généralement « à rebours », en partant de la dernière étape pour remonter jusqu'à la première. ## Exemples d'application - **Problème du plus court chemin dans un graphe** : Ce problème possède la propriété de sous-structure optimale, car toute section d'un plus court chemin est elle-même un plus court chemin. Les algorithmes de Bellman-Ford et de Floyd-Warshall sont des exemples classiques de l'application de la programmation dynamique pour résoudre ce problème^{[\[5\]](https://systems-analysis.info/int/Programmation_dynamique#cite_note-mit-amp-5)}. - **Problème du sac à dos** : Problème consistant à remplir de manière optimale un sac à dos de capacité limitée avec des objets de valeurs et de poids différents. La programmation dynamique permet de résoudre ce problème en considérant les objets séquentiellement et en calculant à chaque étape la valeur maximale pour toutes les capacités restantes possibles. - **Problème d'allocation de ressources** : Allocation d'une ressource limitée (par exemple, des investissements) entre plusieurs projets afin de maximiser le gain total. ## Limites La principale limite de la méthode est le **fléau de la dimensionnalité** (en anglais *curse of dimensionality*) — un terme introduit par Bellman pour décrire la croissance exponentielle du nombre d'états et, par conséquent, de la complexité de calcul, à mesure que le nombre de variables décrivant l'état du système augmente^{[\[6\]](https://systems-analysis.info/int/Programmation_dynamique#cite_note-ru-wiki-curse-6)[\[7\]](https://systems-analysis.info/int/Programmation_dynamique#cite_note-utexas-ormm-7)}. Cela limite l'application pratique de la programmation dynamique exacte aux problèmes de très grande dimension. ## Concepts liés - [Recherche opérationnelle](https://systems-analysis.info/int/Recherche_op%C3%A9rationnelle "Recherche opérationnelle") - Théorie de la commande optimale - Processus de décision markovien (généralisation stochastique) - Équation de Hamilton-Jacobi-Bellman (analogue pour le temps continu) ## Références 1. ↑ ^{[1.0](https://systems-analysis.info/int/Programmation_dynamique#cite_ref-bigenc-dp_1-0)} ^{[1.1](https://systems-analysis.info/int/Programmation_dynamique#cite_ref-bigenc-dp_1-1)} "Programmation dynamique". *Grande Encyclopédie Russe*. [1] 2. [↑](https://systems-analysis.info/int/Programmation_dynamique#cite_ref-ru-wiki-dp_2-0) "Programmation dynamique". *Wikipédia*. [2] 3. ↑ ^{[3.0](https://systems-analysis.info/int/Programmation_dynamique#cite_ref-rechetnikov-dp_3-0)} ^{[3.1](https://systems-analysis.info/int/Programmation_dynamique#cite_ref-rechetnikov-dp_3-1)} Reshetnikov A. N., Kochenkov A. V., Pirov D. M., Ryabokon D. A. (2011). *Programmation dynamique. Exemples d'application*. Manuel, Université d'État de Nijni Novgorod Lobatchevski (Faculté de mathématiques computationnelles et de cybernétique). [3] 4. [↑](https://systems-analysis.info/int/Programmation_dynamique#cite_ref-en-wiki-dp_4-0) "Dynamic programming". *Wikipedia*. [4] 5. [↑](https://systems-analysis.info/int/Programmation_dynamique#cite_ref-mit-amp_5-0) Bradley S. P., Hax A. C., Magnanti T. L. (1977). *Applied Mathematical Programming*. Addison-Wesley. [5] 6. [↑](https://systems-analysis.info/int/Programmation_dynamique#cite_ref-ru-wiki-curse_6-0) "Fléau de la dimensionnalité". *Wikipédia*. [6] 7. [↑](https://systems-analysis.info/int/Programmation_dynamique#cite_ref-utexas-ormm_7-0) Jensen P. A. (2004). *Dynamic Programming – Models*. Operations Research Models and Methods, Univ. of Texas. [7]