EXPOSE DE RECHERCHE OPERATIONNELLE
Nom de l’enseignant :
MOUKANGALA Alex Gautier
PRESENTES PAR :
TOMINA BLANCHINA ESTHER
ANNEE ACADEMIQUE 2024-2025
1
SOMMAIRE
I-Introduction
1. Définition de la programmation dynamique
2. Importance et applications modernes
II Historique et origine
1. Richard Bellman (années 1950)
2. Pourquoi il a créé cette technique
III. Principes fondamentaux de la P.D
1. Le principe d’optimalité de Bellman
2. La décomposition en sous-problèmes
3. La récursivité (relation entre les états)
IV. Les deux méthodes de P.D.
A. Approche Top-Down (mémorisation)
1. Fonction récursive
2. Cache des résultats
3. Avantages / Inconvénients
B. Approche Bottom-Up (tabulation)
1. Construction d’un tableau
2. Résolution en P.D.
V. Étapes et généralités
1. Identifier les sous-problèmes
2. Définir les états
3. Trouver la relation de récurrence
[Link] top-lown ou botton-up
[Link] le tableau / mémoriser
[Link] la solution optimale
VI. Exemples classiques
1. Suite de Fibonacci
2. Problème du sac à dos (Knapsack)
2
3. Plus court chemin
4. Algorithme de Bellman-Ford
5. Multiplication de chaînes de matrices
VII. Application en recherche opérationnelle
[Link] et ordonnancement
2. Gestion des stocks
3. Chaînes logistiques
4. Allocation de ressources
5. Décision séquentielle
VIII. Avantages et limites
Avantages :
a. Évite les recalculs
b. Accélère fortement les algorithmes
c. Applicable à de nombreux problèmes réels
Limites :
a. Peut consommer beaucoup de mémoire
b. Nécessite une structure optimale
c. Complexité parfois difficile à réduire
IX. Conclusion
3
INTRODUCTION
Depuis plusieurs décennies, les chercheurs et ingénieurs en informatique se heurtent
à des problèmes dont la résolution exige non seulement de la rigueur, mais aussi
une stratégie efficace pour réduire la complexité. Face à des calculs répétitifs et des
structures de données de plus en plus vastes, une approche méthodique s’est
imposée : la programmation dynamique.
Cette technique est née dans un contexte où l’optimisation des ressources était
cruciale, notamment dans les domaines militaires et scientifiques des années 1950.
Elle s’est ensuite diffusée dans de nombreux secteurs, allant des mathématiques
appliquées à l’intelligence artificielle. Aujourd’hui, elle constitue un outil
incontournable pour traiter des problèmes où la recherche d’une solution optimale
repose sur la décomposition en étapes successives.
L’intérêt de la programmation dynamique réside dans sa capacité à transformer un
problème apparemment insurmontable en une suite de décisions simples et
cohérentes. Elle illustre parfaitement comment une approche structurée peut rendre
accessible des solutions élégantes à des défis complexes.
1. Définition
La programmation dynamique est une méthode qui repose sur le principe
de diviser pour régner et sur la mémoïsation (stockage des résultats
intermédiaires).
c’est une méthode qui consiste à résoudre un problème en le décomposant en
sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus
grands, en mémorisant les résultats intermédiaires.
2. Importance et Applications modernes
La programmation dynamique est essentielle car elle permet de résoudre
efficacement des problèmes complexes d’optimisation, et ses applications
modernes couvrent des domaines allant de l’intelligence artificielle à la bio-
informatique.
Importance
● Optimisation des calculs : elle évite la répétition inutile de sous-problèmes
en mémorisant les résultats intermédiaires.
● Gain de temps et de ressources : les algorithmes deviennent plus rapides et
plus économes, ce qui est crucial pour les systèmes modernes où la
performance est déterminante.
● Principe d’optimalité : elle repose sur l’idée que la solution optimale d’un
problème global peut être construite à partir des solutions optimales de ses
sous-problèmes.
● Flexibilité : elle s’adapte à une grande variété de problèmes, qu’ils soient
mathématiques, informatiques ou liés à la gestion de ressources.
4
● Applications modernes
Domaines Exemple d’application Impact
Intelligence artificielle Planification de tâches, Améliore la prise de
recherche de chemins décision des agents
optimaux intelligents
Bio-informatique Alignement de séquences Permet de comparer
ADN (algorithme de efficacement des
Needleman-Wunsch) génomes et d’étudier
l’évolution des espèces
Économie et finance Gestion de stocks, Réduit les coûts et
optimisation de maximise les profits
portefeuilles
Recherche opérationnelle Problème du sac à dos, Résout des problèmes
allocation de ressources logistiques complexes
Traitement du langage Reconnaissance vocale, Améliore la précision des
naturel traduction automatique systèmes linguistiques
Vision par ordinateur Reconnaissance d’images Rend possible des
et d’objets applications comme la
conduite autonome
5
6
7
8
B. Approche du Bottom-Up (Tabulation)
1. Construction d’un tableau
Principe général
• En programmation dynamique, l’approche bottom-up consiste à résoudre un
problème en partant des sous-problèmes les plus simples et en remontant
progressivement vers le problème global.
• On utilise un tableau (ou une matrice) pour mémoriser les résultats
intermédiaires afin d’éviter les calculs répétés.
• Contrairement à l’approche top-down (mémoïsation) qui repose sur la
récursivité, le bottom-up est itératif.
Étapes de construction d’un tableau
a.Définir la taille du tableau
o Le tableau doit couvrir toutes les sous-étapes nécessaires pour
atteindre la solution finale.
o Exemple : pour calculer la suite de Fibonacci jusqu’à 𝑛, on crée un
tableau de taille 𝑛 + 1.
[Link] les cas de base
o On remplit les premières cases avec les valeurs connues.
o Exemple : 𝐹(0) = 0, 𝐹(1) = 1.
[Link] le tableau de manière itérative
o Chaque case est calculée à partir des cases déjà remplies.
o Exemple : 𝐹(𝑖) = 𝐹(𝑖 − 1) + 𝐹(𝑖 − 2).
[Link] la solution finale
La dernière case du tableau contient la réponse au problème.
EXEMPLE :
i Dp[i] Explication
0 0 Cas de base : F(0)=0
1 1 Cas de base : F(1)=1
2 1 F(2)=F(1)+F(0)=1+0
3 2 F(3)=F(2)+F(1)=1+1
4 3 F(4)=F(3)+F(2)=2+1
9
5 5 F(5)=F(4)+F(3)=3+2
6 8 F(6)=F(5)+F(4)=5+3
7 13 F(7)=F(6)+F(5)=8+5
8 21 F(8)=F(7)+F(6)=13+8
9 34 F(9)=F(8)+F(7)=21+13
10 55 F(10)=F(9)+F(8)=34+21
Avantages de la tabulation
• ✅ Évite la récursivité → pas de risque de dépassement de pile.
• ✅ Complexité en temps et en mémoire bien maîtrisée.
• ✅ Permet de visualiser clairement la progression vers la solution.
2) Résolution en programmation dynamique (exécution bottom-up)
Objectif
Résoudre un problème complexe en le découpant en sous-problèmes plus
simples, puis en stockant leurs solutions dans une structure (souvent un tableau)
pour éviter les recalculs.
Déroulement Étape par Étape
a. Identifier la structure du problème
• Le problème doit avoir une structure optimale : la solution globale peut être
construite à partir de solutions de sous-problèmes.
• Il doit aussi présenter des chevauchements de sous-problèmes (les mêmes
sous-problèmes apparaissent plusieurs fois).
b. Définir les sous-problèmes
• On exprime le problème global comme une combinaison de sous-problèmes
plus petits.
• On définit une relation de récurrence (formule) qui permet de passer d’un
sous-problème à un autre.
c. Choisir une structure de stockage
• Typiquement un tableau dp[] ou dp[][].
• Chaque case représente la solution d’un sous-problème.
d. Initialiser les cas de base
10
• On remplit les premières cases du tableau avec les valeurs triviales
connues (ex. : dp[0], dp[1]).
e. Remplir le tableau de bas en haut
• On utilise des boucles itératives pour remplir le tableau selon la relation de
récurrence.
• Chaque cellule est remplie en fonction des cellules déjà calculées.
f. Lire la solution finale
• La solution du problème initial se trouve dans la dernière cellule du tableau
(ex. : dp[n] ou dp[n][W]).
Exemple : Problème du rendu de monnaie
Problème
On dispose de pièces de différentes valeurs et on veut rendre une somme S avec le
minimum de pièces. Chaque pièce peut être utilisée un nombre illimité de fois.
Données
• coins = [1, 3, 4]
• S=6
Étapes de résolution
1. Définir le tableau
a. dp[i] = nombre minimal de pièces pour rendre la somme i
b. Taille : dp[0...S]
2. Initialisation
o dp[0] = 0 (zéro pièce pour rendre 0)
o Les autres cases sont initialisées à l’infini (∞) pour représenter une
solution inconnue
3. Remplissage
for i in range(1, S + 1):
for coin in coins:
if i - coin >= 0:
dp[i] = min(dp[i], dp[i - coin] + 1)
11
Résultat
• dp[S] contient le nombre minimal de pièces pour rendre S.
Code complet
def rendu_monnaie(coins, S):
dp = [float('inf')] * (S + 1)
dp[0] = 0
for i in range(1, S + 1):
for coin in coins:
if i - coin >= 0:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[S] if dp[S] != float('inf') else -1
# Exemple
print(rendu_monnaie([1, 3, 4], 6)) # Résultat : 2 (2 pièces de 3)
12
13
14
6-la solution optimale
Pour donner la solution optimale d'un programme dynamique il faut d'abord :
1) Définir le problème : Définir clairement le problème que l'on veut résoudre et
identifier les variables et les contraintes.
2)Décomposer le problème : Décomposer le problème en sous-problèmes plus petits
et plus faciles à résoudre.
3)Identifier les états : Identifier les différentes étapes du problème, c'est à dire pour
prendre une décision.
4)Définir la fonction de transition : Définir la fonction de transition qui permet de
passer d'une étape à un autre.
5)Définir la fonction de cout : Définir la fonction cout qui évalue la qualité de la
solution.
6)Résoudre les sous problèmes : Résoudre les sous problèmes de manière
récursive ou itérative en utilisant la fonction de transition ou de cout.
7)Construire la solution optimale : Construire la solution optimale en combinant les
solutions des sous problèmes.
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
5-MULTIPLICATION DE CHAÎNES DE MATRICES
On veut calculer le produit A1A2 ...An de n matrices données.
Pour n = 4, il existe 5 produits complètement parenthésés
(A1(A2(A3A4))) (A1((A2A3)A4)) (((A1A2)A3)A4)
((A1A2)(A3A4)) ((A1(A2A3))A4)
Le parenthésage choisi peut avoir une grande importance pour l’efficacité du calcul.
Problème de la multiplication d’une suite de matrices
Etant données A1,...,An avec pi−1 × pi la dimension de la matrice Ai, trouver un
parenthésage qui minimise le nombre de multiplications scalaires à effectuer.
Remarque : Le nombre de parenthésages est exponentiel en n (on ne peut pas
énumérer).
Exemple : Mais le parenthésage du produit peut avoir un impact crucial sur le cout
de l’´évaluation du produit.
Rappel : Le produit d’une matrice A de taille p×q par une matrice B de taille q×r
produit une matrice C de taille p×r en pqr multiplications scalaires.
Considérons trois matrices A1, A2 et A3 de dimensions respectives 10×100, 100×5
et 5×50. • Si on effectue la multiplication de ces trois matrices selon le
parenthésage((A1A2)A3), on effectue 10 × 100 × 5 = 5000 multiplications dans un
premier temps, puis 10×5×50=2500 dans un deuxième temps, soit 7500 au total.
• Si, au contraire, on effectue la multiplication selon le parenthésage (A1(A2A3)), on
effectue 100×5×50 = 25000 multiplications dans un premier temps, puis
10×100×50=50000 dans un deuxième temps, soit 75000 au total et 10 fois plus
qu’avec le premier parenthésage.
32
1. Structure d’un parenthésage optimal
Soit m[i,j] = le nb. minimal de multiplications scalaires pour le calcul de Ai..j =
AiAi+1...Aj.
Un parenthésage optimal est le produit de 2 parenthésages optimaux
((Ai..k).(Ak+1..j))
pour une certaine valeur de k.
Les dimensions des matrices produits Ai..k et Ak+1..j sont respectivement pi−1 × pk
et pk ×pj.
Donc on obtient m[i,j] = m[i][k] + m[k + 1][j] + pi−1pkpj.
2. Définition récursive de la valeur optimale
3. Calcul “ascendant” de la valeur optimale
Avec une procédure récursive basée sur la forme précédente on obtient la même
complexité qu’avec l’´énumération !
33
On utilise un calcul “ascendant” de la solution optimale.
Nb. de sous-problèmes = |{(i,j) : 1 ≤ i ≤ j ≤ n}|
= n(n−1) /2+n
→Recouvrement des sous-problèmes
Exemple :
Supposons 3 matrices :
• A : 10 × 30
• B : 30 × 5
• C : 5 × 60
Deux façons possibles :
1) (A × B) × C
Coût = (10 ×30 × 5) + (10 × 5 × 60)
= 1500 + 3000
= 4500
2) A × (B × C)
Coût = (30× 5 × 60) + (10 × 30 × 60)
= 9000 + 18000
= 27000
34
35
36
37
2- GESTION DES STOCKS
La gestion des stocks vise à déterminer combien commander et à quel moment le
faire tout en minimisant les coûts.
a) Qu’est-ce que le stock ?
Le stock est un état du système, elle représente la quantité disponible au
début d’une période.
38