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

II- Historique et Origine

5
1-Richard Bellman

Richard Bellman (1920–1984) est le fondateur de la programmation dynamique.

Dans les années 1950, alors qu’il travaillait à la RAND Corporation, il cherchait une
méthode pour résoudre des problèmes d’optimisation complexes impliquant des
décisions successives.

• Introduit la programmation dynamique, basée sur le principe d’optimalité de Bell man:

une solution optimale globale peut être obtenue à partir de solutions optimales de
sous problèmes.

En termes simples :

➡ Un problème complexe peut être découpé en sous-problèmes plus simples,

➡ et la solution optimale globale dépend des solutions optimales locales.

C’est le cœur même de la programmation dynamique.
Contributions majeures
Formalisation de la programmation dynamique
Équation de Bellman (très utilisée en : intelligence artificielle, apprentissage par
renforcement, économie)
Applications en :
• gestion des stocks,
• contrôle optimal,
• théorie des décisions,
• télécommunications
Cette idée permet de décomposer un problème en étapes plus simples et est
aujourd’hui utilisée en gestion de stock, en informatique, en économie et en
intelligence artificielle.
Œuvre marquante
. Dynamic Programming (1957) → Livre fondateur qui structure la méthode et ses
applications.
Source: Wikipédia, Princeton University Press, 1957

2- Pourquoi il a créé cette technique

Richard Bellman a créé la programmation dynamique dans les années 1950 afin de
résoudre des problèmes d’optimisation complexes, souvent séquentiels. À cette

6
époque, de nombreux problèmes de planification nécessitaient de prendre une série
de décisions successives, où chaque choix influençait les suivants. Les méthodes
classiques étaient alors trop lentes et entraînaient une explosion combinatoire, rendant
les calculs impraticables même pour les ordinateurs de l’époque.
Pour répondre à cette difficulté, Bellman a proposé de décomposer ces problèmes en
sous-problèmes plus simples et de mémoriser leurs solutions afin d’éviter les calculs
redondants. Cette approche repose sur son principe d’optimalité, selon lequel une
solution globale optimale est construite à partir de solutions optimales à chaque étape
intermédiaire. Il cherchait ainsi une méthode efficace pour la planification et
l’ordonnancement dans des domaines comme l’économie, l’ingénierie et le contrôle
optimal.
Raisons principales de sa création
• Résolution de problèmes d’optimisation séquentiels : Trouver la meilleure succession
de décisions possibles, par exemple en minimisant un coût, une trajectoire ou un
temps.
• Gestion de la complexité : Plutôt que de recalculer plusieurs fois les mêmes sous-
problèmes (comme dans le calcul naïf de la suite de Fibonacci), Bellman a introduit la
mémorisation, aussi appelée tabulation ou memoization, permettant d’échanger du
temps de calcul contre de l’espace mémoire.
• Formalisation du principe d’optimalité : L’idée qu’une solution optimale d’un
problème global contient nécessairement les solutions optimales de ses sous-
problèmes.
• Applications pratiques concrètes : Initialement développée pour des problèmes réels
tels que la gestion des stocks, l’allocation de ressources et le contrôle optimal,
notamment dans le cadre du guidage de systèmes complexes comme les fusées.
La programmation dynamique a été créée par Richard Bellman pour rendre
abordables et efficaces des problèmes d’optimisation séquentiels trop complexes pour
les méthodes classiques, en évitant les recalculs inutiles grâce à une résolution
structurée et mémorisée des sous-problèmes.

III- Principes fondamentaux de la P.D

1-Le principe optimalité de Bellman

Composer une solution optimale du problème en combinant les solutions (optimales)
de ses sous-problèmes
▪ En pratique : Décomposer le problème en des sous-problèmes plus petits, Calculer
les solutions optimales de tous ces sous-problèmes et les garder en mémoire.
Calculer la solution optimale à partir des solutions optimales des sous-problèmes
2-La décomposition en sous-problèmes

7
La programmation dynamique repose sur un principe fondamental : résoudre un
problème complexe en le décomposant en une série de sous-problèmes plus simples
et plus faciles à gérer. Cette méthode permet d’éviter les calculs redondants en
réutilisant les solutions des sous-problèmes déjà résolus.
Dans le contexte de la recherche opérationnelle, cette décomposition est essentielle
pour traiter des problèmes d’optimisation, comme la gestion des ressources, la
planification ou encore la logistique. Le problème initial est divisé en étapes
successives, où chaque étape dépend des décisions prises aux étapes précédentes.
Prenons un exemple simple : le problème du plus court chemin dans un graphe. Au
lieu de recalculer tous les chemins possibles, on peut calculer le plus court chemin
vers chaque sommet à partir du point de départ, en s’appuyant uniquement sur les
résultats déjà obtenus pour les sommets précédents. Chaque sous-problème
correspond ici à la recherche du chemin optimal jusqu’à un certain sommet.
Ainsi, la décomposition en sous-problèmes permet non seulement de simplifier la
résolution, mais aussi d’améliorer considérablement l’efficacité de l’algorithme,
surtout pour les problèmes à grande échelle.

3-La récursivité (relation entre les états)

En programmation dynamique, la récursivité désigne le processus par lequel un
problème est défini en fonction de versions plus simples de lui-même. Cette
approche repose sur une relation de récurrence ou relation entre les états, qui
permet de passer d’un sous-problème à un autre.
L’idée est que l’état actuel du système dépend uniquement d’un ou plusieurs états
précédents. En d’autres termes, pour résoudre le problème à une étape donnée, il
suffit de connaître la solution optimale des étapes précédentes. Cette relation
récursive est au cœur de la programmation dynamique : elle permet de construire
progressivement la solution globale à partir des solutions partielles.
Par exemple, dans le problème du sac à dos (knapsack problem), la valeur maximale
qu’on peut obtenir pour une certaine capacité dépend du choix d’inclure ou non un
objet, et donc de la solution du problème pour une capacité réduite. Cette
dépendance directe entre états est exprimée par une formule récursive. La
récursivité permet ainsi de modéliser le lien logique entre les différentes étapes d’un
processus, ce qui est essentiel dans la recherche opérationnelle pour optimiser les
prises de décision séquentielles.

IV- Les deux méthodes de P.D.

A- Approche Top-Down (mémorisation)

1- Fonction récursive

8
L’approche Top-Down en programmation dynamique consiste à partir du problème
principal pour le résoudre en le divisant progressivement en sous-problèmes plus
petits. Cette méthode utilise une fonction récursive pour exprimer la solution du
problème global à partir des solutions des sous-problèmes.
La fonction récursive est une fonction qui s’appelle elle-même tant qu’elle n’a pas
atteint un cas de base (ou condition d’arrêt). Elle permet de parcourir l’espace des
solutions de manière descendante, en décomposant le problème étape par étape.
Cependant, une fonction récursive classique peut recalculer plusieurs fois les mêmes
résultats, ce qui est inefficace. C’est pourquoi l’approche Top-Down utilise la
mémorisation (memoization) : chaque fois qu’un sous-problème est résolu, son
résultat est stocké (en mémoire ou dans une structure comme un tableau ou un
dictionnaire). Si le même sous-problème se présente à nouveau, le résultat déjà
calculé est réutilisé.
Cette technique permet d’améliorer considérablement les performances des
algorithmes récursifs en évitant les redondances de calcul, tout en conservant une
structure simple et intuitive.

2-Cache des résultats

Le cache des résultats consiste à stocker les résultats des sous-problèmes déjà
résolus afin d’éviter de recalculer plusieurs fois les mêmes informations.
Le programme vérifie si le résultat existe dans le cache.
S’il existe, il l’utilise directement. Sinon, il le calcule, le stocke dans le cache et le
retourne.
3-Avantages / Inconvénients
a. Avantages
Accélère l’exécution des programmes
Évite les calculs répétitifs
Améliore les performances des algorithmes
Réduit la charge du processeur
b. Inconvénients
Consommation élevée de mémoire RAM
Gestion du cache parfois complexe
Risque de saturation mémoire
Peu utile pour les problèmes simples

9
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.
b. Initialiser 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
5 5 F(5)=F(4)+F(3)=3+2
6 8 F(6)=F(5)+F(4)=5+3

10
 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

• On remplit les premières cases du tableau avec les valeurs triviales connues
(ex. : dp[0], dp[1]).

11
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)

Résultat

12
 • 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)

V- Etapes et généralités

1- Identifier les sous-problèmes

La programmation dynamique est une méthode algorithmique utilisée pour résoudre

des problèmes complexes en exploitant leur sous-structure optimale et la présence
de sous-problèmes recouvrants. Le principe fondamental consiste à décomposer le
problème initial en plusieurs sous-problèmes de même nature mais de taille plus
réduite, puis à combiner leurs solutions pour obtenir la solution globale.
L’identification des sous-problèmes est une étape essentielle de cette approche. Elle
permet de déterminer quelles sont les différentes instances réduites du problème qui
doivent être résolues de manière systématique.
La première étape consiste à analyser les décisions répétitives imposées par le
problème. Dans de nombreux cas, résoudre le problème revient à effectuer une série
de choix successifs. Chaque choix réduit la taille du problème initial et génère un
sous-problème plus petit. Ces sous-problèmes conservent la même structure logique
que le problème d’origine, ce qui permet leur réutilisation.
La seconde étape consiste à identifier les paramètres nécessaires pour décrire un
état du problème. Un état représente l’ensemble minimal d’informations permettant
de caractériser une situation donnée sans ambiguïté. Le choix correct de ces
paramètres est crucial, car chaque état correspond à un sous-problème distinct qui
sera résolu une seule fois.
Une fois les états définis, les sous-problèmes peuvent être formulés de manière
formelle.

13
Exemple 1 : La suite de Fibonacci ; Le problème consiste à calculer. Les sous-
problèmes sont les valeurs pour tout. L’état est défini par un seul paramètre : la
valeur de Chaque est une solution réutilisable.

Exemple 2 : Le rendu de monnaie ; Pour rendre une somme, le sous-problème

consiste à calculer le nombre minimal de pièces pour chaque montant intermédiaire.
L'état est simplement le montant restant à rendre.
Ainsi, identifier les sous-problèmes revient à définir clairement les états du problème
et à associer à chacun d’eux une solution optimale. Cette étape structure la
résolution en programmation dynamique et conditionne directement l’efficacité de
l’algorithme, tant en temps de calcul qu’en consommation mémoire.
Les notions abordées reposent sur des références classiques en algorithmique, en
particulier les travaux de Cormen et de Kleinberg, qui présentent de manière
rigoureuse les principes de la programmation dynamique, l’identification des sous-
problèmes et la définition des états.

2-Définir les états

-Illustration via le problème du sac à dos :

On suppose qu’il existe n objets et que chaque objet noté i possède un poids
w[i] et une valeur v[i] ; à coté nous avons un sac de capacité W.
L’objectif est de maximiser la valeur totale sans dépasser la capacité W
-Définition de l’état
dp[i] [w]= la valeur maximale possible en utilisant les i premiers objets avec une
capacité de sac w
3-Trouver la relation de récurrence
Il existe 2 possibilités pour chaque objet i
Cas 1 : ne pas prendre l’objet i
On conserve la valeur obtenue avec les précédents objets
Cas 2 : prendre l’objet i
Si son poids est ≤ w dp[i] [w] =dp [i-1][w-poids[i]] + valeur [i]
- Relation finale
dp[i] [w] = {dp[i-1] [w] si poids[i] ≥w ; max(dp[i-1][i-1][w-poids[i]+valeur[i])}

4-Choisir top-lown ou botton-up

14
En programmation dynamique, deux approches principales permettent de résoudre
un problème : Top-Down (avec mémorisation) et Bottom-Up (avec tabulation). Le
choix entre ces deux dépend de plusieurs critères :
- Top-Down (mémorisation) :
Cette approche est plus intuitive, car elle commence par le problème global et le
décompose en sous-problèmes plus petits. Elle est basée sur la récursivité et
convient lorsque l'on ne connaît pas d’avance l’ordre d'exécution des sous-
problèmes. Elle est plus facile à écrire mais peut entraîner un dépassement de pile si
la profondeur de récursion est trop grande.
- Bottom-Up (tabulation) :
Elle consiste à résoudre d’abord les plus petits sous-problèmes pour construire
progressivement la solution du problème global. Elle n’utilise pas la récursivité, mais
des boucles, ce qui la rend plus efficace en termes de mémoire et de temps dans
certains cas. Elle est préférable lorsque tous les sous-problèmes doivent être
calculés.
Conclusion :
- On privilégiera Top-Down pour sa simplicité de mise en œuvre et sa clarté.
- On optera pour Bottom-Up lorsqu'on a besoin d'une meilleure performance,
notamment en temps et en espace.

5-Remplir le tableau / mémoriser

En programmation dynamique, une étape essentielle consiste à stocker les résultats
des sous-problèmes déjà résolus pour éviter les calculs répétitifs. Cette technique
s’appelle la mémorisation (en Top-Down) ou le remplissage de tableau (en Bottom-
Up).
- Dans l’approche Top-Down, on utilise une structure de données (comme un tableau
ou un dictionnaire) pour enregistrer les solutions déjà trouvées. Ainsi, si un sous-
problème se répète, sa solution est directement réutilisée, ce qui réduit le temps
d’exécution.
- Dans l’approche Bottom-Up, on remplit un tableau de manière progressive, en
partant des cas de base jusqu’au problème complet. Chaque case du tableau
représente un sous-problème, et sa valeur est calculée à partir des résultats
précédents. Cela garantit une résolution systématique et optimisée.
Avantages :
- Réduction de la complexité temporelle (évite la redondance).
- Économie de ressources grâce à la réutilisation des solutions.
Conclusion :

15
La mémorisation ou le remplissage du tableau est la clé de l’efficacité de la
programmation dynamique, permettant de résoudre des problèmes complexes en
temps raisonnable.

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.

VI- Exemples classiques

1-Suite de Fibonacci

La suite de Fibonacci est un exemple classique pour illustrer la programmation

dynamique. Elle est définie comme suit :
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) pour n ≥ 2
a) Approche naïve (récursive simple)
Cette approche consiste à appeler récursivement F(n-1) et F(n-2). Cependant, elle
entraîne de nombreuses répétitions de calculs pour les mêmes valeurs, ce qui rend
le processus très lent pour les grandes valeurs de n.
b) Approche avec programmation dynamique

16
Deux méthodes permettent d'optimiser :

- Top-Down avec mémorisation : on stocke les résultats des appels récursifs dans un
tableau (ou dictionnaire), et on les réutilise si nécessaire.
- Bottom-Up : on commence par calculer les valeurs de F(0) et F(1), puis on remplit
progressivement un tableau jusqu’à F(n).
Exemple en Bottom-Up :
c
int fibonacci(int n) {
int fib[n+1];
fib[0] = 0;
fib[1] = 1;
for(int i = 2; i <= n; i++) {
fib[i] = fib[i-1] + fib[i-2];
}
return fib[n];
}

Cette méthode a une complexité en temps linéaire O(n), bien plus efficace que
l’approche récursive simple.

2- Problème du sac à dos (Knapsack)

Le problème du sac à dos consiste à choisir des objets à placer dans un sac ayant
une capacité limitée, de manière à maximiser la valeur totale sans dépasser la
capacité du sac.
Énoncé de l’exemple
On dispose d’un sac ayant une capacité maximale de 5 kg. Trois objets sont
disponibles. Chaque objet possède un poids et une valeur.
Objet Poids (kg) Valeur
A 2 3
B 3 4
C 4 5

Analyse des choix possibles

17
• A + B : poids total = 2 + 3 = 5 kg, valeur totale = 7 (solution acceptable).
• A + C : poids total = 6 kg, dépasse la capacité du sac.
• B + C : poids total = 7 kg, dépasse la capacité du sac.
• C seul : poids total = 4 kg, valeur = 5.
Solution optimale
La meilleure solution est de choisir les objets A et B, car ils respectent la capacité du
sac tout en donnant la valeur totale maximale de 7

3-Plus court chemin

Exercice: fais tourner l'algorithme de bellman-Ford
En appliquant l'algorithme de bellman-Ford, calculer les plus courts chemins d'origine
(S) sur le graphe.

4-Algorithme de Bellman-Ford

A- Énoncé

18
L'algorithme de Bellman-Ford est une méthode utilisée pour trouver le plus court
chemin d'un sommet source unique vers tous les autres sommets d'un graphe
pondéré, même si certaines arêtes ont des poids négatifs. Contrairement à
l'algorithme de Dijkstra, il est capable de gérer ces poids négatifs et de détecter la
présence de circuits de poids négatifs.
B- Principes
-Objectif : Déterminer les distances minimales depuis un point de départ unique vers
toutes les destinations possibles dans un graphe dirigé pondéré.
-Capacité Unique : Il est l'un des rares algorithmes capables de fonctionner avec
des poids d'arêtes négatives.
-Détection de Cycles Négatifs : L'algorithme permet de détecter si le graphe contient
un circuit (cycle) dont la somme totale des poids est négative, auquel cas aucun plus
court chemin n'existe, car la distance pourrait être réduite indéfiniment.
C- Fonctionnement
L'algorithme utilise une approche itérative appelée relaxation, qui réduit
progressivement l'estimation de la distance entre les sommets.
a- Initialisation
-La distance du sommet de départ à lui-même est initialisée à 0.
-Les distances à tous les autres sommets sont initialisées à l'infini.
b- Itérations de Relaxation
-L'algorithme parcourt toutes les arêtes du graphe un nombre fixe de fois : V - 1 fois
(où V est le nombre de sommets).
-À chaque passage, pour chaque arête (u, v), il vérifie si le chemin passant par 'u'
est plus court que le chemin actuellement connu pour atteindre 'v'. Si oui, la distance
de 'v' est mise à jour (relâchée).
-Ce processus garantit qu'après V-1 itérations, le plus court chemin est trouvé pour
tous les sommets accessibles, à condition qu'il n'y ait pas de cycle négatif.
c- Vérification des Cycles Négatifs
- Une V-ième itération est effectuée sur toutes les arêtes.
- Si, lors de cette dernière itération, une distance est encore réduite, cela signifie
qu'un cycle de poids négatif est présent dans le graphe, rendant impossible la
détermination d'un plus court chemin absolu. L'algorithme signale alors cette
condition.
NB:
L'algorithme de Bellman-Ford a une complexité temporelle de O(V × E), où V est le
nombre de sommets et E le nombre d'arêtes, ce qui le rend plus lent que l'algorithme
de Dijkstra (qui est plus efficace pour les graphes sans poids négatifs).

19
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.

1. Structure d’un parenthésage optimal

20
Soit m[i,j] = le [Link] 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 !
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 :

21
• 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

Vll: Application en recherche opérationnelle

1- Planification et ordonnancement
I-Définition de quelques concepts utilisés dans le domaine
En production industrielle, les termes ordonnancement, planification et
contraintes ont des significations spécifiques liées à l'organisation et à la
gestion des tâches. Voici la définition de chaque terme :
I-1. Ordonnancement :
L’ordonnancement désigne la méthode de gestion du temps et des
ressources pour réaliser les différentes tâches ou opérations de production. Il
s'agit de déterminer l'ordre dans lequel les différentes tâches doivent être
réalisées pour atteindre les objectifs de production dans les délais impartis.
L'ordonnancement peut concerner :
• L'assignation de tâches aux machines, opérateurs, ou lignes de production.
• La gestion des priorités des tâches en fonction de l'urgence ou de l'importance.
• L'optimisation de la production pour minimiser les coûts et les délais.
• L'ordonnancement peut être statique (fixe, avec peu de changements) ou
dynamique (adaptatif, avec des ajustements en temps réel).
L’ordonnancement est un processus essentiel dans le domaine de la
gestion de la production et de la chaine d’approvisionnement
I-2. Planification:

22
. I-2-1 Définitions
La planification industrielle est un processus anticipatif et stratégique qui
consiste à définir les objectifs de production à long terme, à moyen, à court
terme et à établir un programme de travail pour les atteindre. Ce programme
de travail vise à élaborer et à réviser un ensemble de plans interdépendants de
(ventes, fabrication, achats, trésorerie) en vue de garantir le meilleur équilibre
possible entre l’offre et la demande en tout point de la chaîne logistique à tout
moment. Voire figure 1.
Sa réalisation exige l’implication de plusieurs fonctions de l’entreprise afin de
déterminer les délais et les priorités de la production. De la direction générale
qui a une vision à plus long terme jusqu’au responsable de production qui gère
le planning journalier.

. I-2-2 Rôle de la planification la production

Le rôle essentiel de la planification de la production est de garantir le meilleur
équilibre entre les systèmes d’offre et de demande de l’entreprise en tout point de la
chaîne logistique et à tout moment. Tout en assurant une Synchronisation entre la
fabrication des produits, l’arrivée des matières, l’arrivée des outillages et l’utilisation
des ressources, l’optimisation des dates de livraison, les stocks et l’utilisation des
ressources et une réaction rapide quant à la gestion des aléas (mode perturbé).

Demande Offre
( Besoins du marché ) ( Ressources entreprise )

Stocks : produits finis, semi-finis, matières

Commandes fermes
Prévisions de vente (marketing) Premières, composants
Promesses de vente (vente) Main d’œuvre
Moyens de production
Nouveaux produits (responsables de projet)
Fournisseurs
Objectifs d’inventaire commerciaux
Finances (BFR, trésorerie)

Figure 1. Équilibre entre l’offre et la demande

I-2-3 Les différents types de planification

Il existe trois types de planification, présentés dans le tableau suivant :
La planification La planification
La planification stratégique
tactique à moyen terme opérationnel à court terme

23
 • Elle s’étale sur plus de • Elle s’étale sur une
• Elle couvre une
cinq ans. période pas plus qu’un an.
période de cinq ans au
• Il s’agit : • Les cadres inférieurs
maximum.
− d’analyser certains aspects de définissent :
• Les chefs de
l’environnement externe. − les tâches à accomplir
départements et les
− de repérer les forces et les − les programmes, les
directeurs élaborent :
faiblesses. projets, les opérations et les
des plans détaillés,
• Le dirigeant détermine : activités propres à leurs
coordonnés, qui
− la mission de l’entreprise. − les unités organisationnelles.
concerne la
objectifs généraux de l’entreprise • Elle consiste aussi à
production, la
(objectifs annuels, prévisions de mettre en œuvre et
commercialisation et
besoins, investissements). contrôler les réalisations.
les ressources
humaines...
− les politiques et les stratégies.
Elle se déploie en trois étapes :
• Une analyse préalable,
• La définition d'objectifs spécifiques (conception du plan)
• La répartition des tâches (l'exécution.).

2. LA METHODE PERT

Principe de la méthode : Réduire la durée totale d'un projet par une analyse
détaillée des tâches ou activités élémentaires et de leur enchaînement. On
étudie les délais sans prendre en compte les charges.

Notions de base :

La méthode s'appuie en grande partie sur une représentation graphique qui

permet de bâtir un « réseau PERT ».

Un réseau PERT est constitué par des tâches et des étapes

Étape : commencement ou fin d'une tâche. Une étape n'a pas de durée. On
symbolise une étape (ou « nœud ») sur le réseau par un
cercle.

Tâche : déroulement dans le temps d'une opération. Contrairement à l'étape,

la tâche est pénalisante car elle demande toujours une certaine durée, des
moyens (ou ressources) et coûte de l'argent. Elle est symbolisée par un
vecteur (ou arc orienté, ou liaison orientée) sur lequel seront indiqués l'action à
effectuer et le temps estimé de réalisation de cette tâche.

24
 B (6 )
1 2 3

A
(12) Exemple de réseau :

A (12 )

Remarques : - La longueur des arcs n'est pas proportionnelle au

temps d'exécution. - Pour alléger la représentation, on
ne note pas le nom complet de la tâche, mais une lettre
ou code la représentant.

Représentation graphique des étapes et des tâches dans un réseau.

Tâches successives :

Exemple :

A (12 ) B (6) C (3)

1 2 3 4

B ne peut commencer que si A est terminée (A précède B , ou A est

antériorité de B) . C ne peut commencer que si A et B sont terminées
(A et B précèdent C, ou A et B sont antériorité de C, ou A et B
enclenchent C).

Remarque : en fait B terminée suffit, sinon il y a redondance. La

contrainte d'antériorité qui lie A à C n'a pas besoin d'être représentée.

Tâches simultanées : Elles peuvent commencer en même temps en

partant d'une même étape.

25
Exemple :

D (4 )
3 5
B (6)
A (12)
1 2

C (3)
4

D ne peut commencer que si B est terminée.

Si l'on souhaite que D ne commence que si B et C sont terminées :

D (4 )
3 4
B (6)
A (12)
1 2 X (0)
C (3)
3'

Du fait de la règle de construction qui interdit de faire se dérouler

les deux tâches B et C simultanément, nous utilisons une tâche x (0) dite
« tâche fictive » qui sert à représenter ce type de contraintes de liaison
(contraintes d'antériorité). Il s'agit d'une tâche dont la durée et le coût
sont nuls. On la représente en pointillés.

Tâches convergentes : Plusieurs tâches peuvent se terminer sur une

même étape.

Exemple :

1
A (12)

C (3 )
3 4
B (6)

Ici, la tâche A (12) a une durée de 12 unités de temps, B(6) a une durée
de 6 unités de temps. On constate que la tâche A dure plus
longtemps que B. A est dite « Pénalisante ».

26
 Nous pouvons calculer la durée du projet (ici : 12+3 = 15 unités de
temps) en prenant le chemin le plus long dit « chemin critique ».
Ce « chemin critique » pourra être repéré en rouge. Les tâches de ce
chemin seront à surveiller prioritairement.

Normalisation du graphe.
Si le graphe doit débuter par plusieurs tâches simultanées, il ne doit y
avoir qu'une seule étape d'entrée (ou étape de début, ou étape de
départ). Les étapes seront donc regroupées en une seule.

Exemple :

A (12)
1 4 2
A (12)

B (6) B (6)
2 5 1 3

C (3)
B (6) 6
3 4
NON OUI

Si le graphe se termine par plusieurs tâches (plusieurs étapes de sortie

(ou de fin), il ne doit y avoir qu'une seule étape de sortie.

Exemple :

T (2)
11 14 11 T (2)

U (4) 15 12 U (4)
12 14

V (6)
V (6) 16
13 13

NON
OUI
Problèmes de dépendances : A enclenche B, A enclenche D, C
enclenche D.

Nous pouvons être tentés de dessiner le graphe suivant :

27
 1 4
A (12)
B (6)

3
C (3)
D (4)
2 FAUX 5

Le graphe précédent est faux car cette construction signifie : A enclenche

B, A enclenche D, C enclenche B, et C enclenche D.

Pour respecter les contraintes d'antériorités du projet, on introduit une

tâche fictive comme suit :

A (12) C (3)
1 3 4

X (0)

B (6) D (4)
2 3' 5

Représentation des étapes :

Les étapes ou « noeuds » peuvent être représentés de différentes façons

selon les informations que l'on souhaite mettre en évidence.
Date de fin au
plus tôt de la
4 22 tâche précédente.
Étape : 4 ou ou 4 1 Battement ou
22 23 marge.
23
Date de fin au Date de débutau
plus tôt de la plus tard de la Date de début au
tâche précédente. plus tard de la
tâche suivante.
tâche suivante.

Méthodologie de construction d'un réseau PERT.

- Établir la liste des tâches (faire le partitionnement des tâches en fonction

des ressources).

28
- Déterminer des antériorités : tâches immédiatement antérieures, et tâches
antérieures. - Déterminer les niveaux d'exécution ou rang des tâches
(optionnel). - Construire le réseau PERT.
Calculer la durée du projet, les dates début et de fin des tâches.
Déterminer le chemin critique. Mettre en évidence les marges.

Application.

Soit les tâches suivantes qui constituent un projet : A (3), B (4), C (2), D (3), E
(4).

Les antériorités sont les suivantes :

A enclenche C,
A
en
cle
nc
he
D,
B
en
cle
nc
he
E,
C enclenche E.

Afin de construire le réseau, nous allons déterminer le rang (ou niveau)

d'exécution de chaque tâche, c'est à dire la position chronologique qu'elle
occupe au début de son exécution dans le projet.

Nous pouvons utiliser une matrice (ou grille) de dépouillement des données
(dite : « matrice de dépouillement par les sommets ») : On met une croix
lorsqu'il y a une antériorité entre une tâche et une autre. On cherche s'il existe
des croix dans l'une des colonnes. Si nous ne trouvons pas de croix dans
certaines, cela signifie que les tâches repérées en haut des colonnes n'ont pas
d'antériorité. Elles sont alors de rang 1. On note ces tâches, puis on barre les
lignes horizontales correspondant à ces tâches et on réitère l'opération
précédente. On détermine les tâches de rang 2 et ainsi de suite.

Les rangs (ou niveaux) déterminés permettent de positionner le début des

différentes tâches lors de la construction du graphe.

29
 Matrice (ou grille) de dépouillement :

Après → A B C D E
Avant
A X X
B X
C X
D
E

Nous en déduisons le réseau PERT correspondant à l'application proposée :

A (3) D (3)
1 2 4

B (4) C (2)
E (4)

RANG 1ou RANG 3 ou

Niveau I Niveau II Niveau III
RANG 2 ou

Calculs sur le graphe :

La méthode PERT a pour but de planifier la durée d'un projet, aussi nous
devons mener des calculs sur le graphe afin d'en déduire des renseignements
sur son exécutabilité.

Quelques définitions à retenir :

- Début au plus tôt d'exécution d'une tâche : C'est le maximum des fins au plus
tôt des tâches qui la déclenche (Il peut exceptionnellement y avoir un retard
ou chevauchement si le cahier des charges du projet le précise et que la
faisabilité est vérifiée).
- Début au plus tard d'une tâche : C'est la date de fin au plus tard de la tâche
moins la durée de la tâche.
- Fin au plus tôt : C'est la date de début au plus tôt plus la durée de la tâche.
30
- Fin au plus tard : C'est le minimum des dates de début au plus tard des
tâches qu'elle enclenche.
- Marge totale : C'est le retard admissible du début d'une tâche qui n'entraîne
aucun recul de la date de fin du projet, mais qui consomme les marges libres
des opérations suivantes. C'est la date de début au plus tard moins la date
de début au plus tôt.
- Marge libre : C'est le retard admissible sur une tâche qui n'entraîne pas de
modification des calendriers des tâches suivantes.
C'est la date de début au plus tôt de la tâche suivante moins la durée de la
tâche moins la date de début au plus tôt de la tâche.
- Chemin critique : C'est l'ensemble des tâches dont la marge totale et la
marge libre est nulle. C'est le chemin dont la succession des tâches donne la
durée d'exécution la plus longue du projet et fournit le délai d'achèvement le
plus court. Si l'on prend du retard sur la réalisation de ces tâches, la durée
globale du projet est allongée. Pour l'application précédente, on peut dresser
un tableau de synthèse comme suit :

Tâches Durée Début Début Fin Fin Marge Marge Chemin

(jours) +tôt +tard +tôt +tard libre totale Critique
A 3 0 0 3 3 0 0 A
B 4 0 1 4 5 1 1 -
C 2 3 3 5 5 0 0 C
D 3 3 6 6 9 3 3 -
E 4 5 5 9 9 0 0 E
...
...
Résultats de l'étude :
La durée globale du projet (délai d'achèvement le plus court) = 9 jours.
Le chemin critique est constitué des tâches : A, C, et E.
Il faut vérifier que ces tâches se déroulent correctement et le cas échéant
adopter des actions correctives afin de les fiabiliser.

3. LA METHODE M.P.M.

Principe de la méthode : A l'identique de la méthode PERT cette méthode

permet de réduire la durée totale d'un projet. On étudie les délais sans prendre
en compte les charges et les moyens disponibles.

Notions de base :

31
 La méthode est une représentation graphique qui permet de bâtir un « réseau
».

Ce réseau est constitué par des tâches (ou étapes).

Tâche : Déroulement dans le temps d'une opération. La tâche est pénalisante

car elle demande toujours une certaine durée, des moyens (ou
ressources) et coûte de l'argent.
Contrairement au réseau PERT, ici elle est symbolisée par un
rectangle dans lequel seront indiqués l'action à effectuer et le temps
estimé de réalisation de cette tâche, la date de début et de fin.

Tâche A : 4 jours
Début Fin
:23/10/2000 :26/10/2000

Liaison orientées : Elles représentent les contraintes d'antériorités des tâches.

Exemple de réseau :

Calculs sur le graphe :

La méthode MPM comme la Méthode PERT a pour but de planifier la durée
d'un projet, aussi nous devons mener des calculs sur le graphe afin d'en
déduire des renseignements sur son exécutabilité.
Normalisation du graphe.
Le graphe doit comporter un seul « début » et une seule « fin ». Il n'y a
pas d'autres règles. C'est ce type de graphe qui est le plus souvent utilisé
par les logiciels de planification (comme Microsoft Project).

Méthodologie de construction d'un réseau MPM. (Identique à celle du réseau

PERT)

- Établir la liste des tâches (faire le partitionnement des tâches en fonction des
ressources).

32
 - Déterminer des antériorités : tâches immédiatement antérieures, et tâches
antérieures.
- Déterminer les niveaux d'exécution ou rang des tâches (très facile avec cette
méthode).
- Construire le réseau MPM.
- Calculer la durée du projet, les dates début et de fin des tâches. Déterminer
le chemin critique. Impossible ici de mettre en évidence les marges : voir
diagramme de Gantt.

4. Le diagramme de GANTT

Le diagramme de GANTT est un graphique (chrono gramme) qui

consiste à placer les tâches chronologiquement en fonction des contraintes
techniques de succession (contraintes d'antériorités).
L'axe horizontal des abscisses représente le temps et l'axe vertical
des ordonnées les tâches.
On représente chaque tâche par un segment de droite dont la
longueur est proportionnelle à sa durée. L'origine du segment est calée sur la
date de début au plus tôt de l'opération (« jalonnement au plus tôt ») et
l'extrémité du segment représente la fin de la tâche.
Ce type de graphe présente l'avantage d'être très facile à lire, mais
présente l'inconvénient de ne pas représenter l'enchaînement des tâches.
Cette méthode est généralement utilisée en complément du réseau PERT ou
MPM. On trace le plus souvent le GANTT au plus tôt ou « jalonnement au
plus tôt » et éventuellement au plus tard « jalonnement au plus tard ».

Exemple :
Tâches A B C D E F G H I J K L M
Durée 1 2 1 3 2 5 2 5 2 1 4 5 4
Antériorités - - A - B E C, D - H - I, J F, G K, L

33
 Réseau MPM :

A:1 C:1

D:3 G:2

d B:2 E:2 F:5 L:5 M:4 fin

H:5 I:2 K:4 Délai = 18 jours

J:1

Diagramme de Gantt : (sur tableur) « GANTT au plus tôt »

Début Fin Marge Diagramme de GANTT - Échelle: 1cm = 1 jour

n equ
m
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
e
h tiir
she
tôt tôt C c
euré
âcT D tard tard Tot. Libre
A 1 jour 0 5 1 6 5 0
B 2 jours 0 0 2 2 0 0 B
C 1 jour 1 6 2 7 5 1
D3 0 4 3 7 4 1
E jours 2 2 4 4 0 0
E
F 2 4 4 9 9 0 0
jours F
G 3 7 5 9 4 4
H5 0 3 5 8 3 0
I jours 5 8 9 7 10 3 06
J 2
0 10 1 10 9 3
jours
K 7 9 11 14 3 0
5
L
jours 9 14 14 14 0 0
M 14 18 18 0 L
2
jours M
1 jour
4 jours

5 jours

4
jours

Diagramme de Gantt : (avec Microsoft PROJECT) « GANTT au plus tôt »

34
Analyse :
- Le projet est réalisable en 18 jours ouvrés. Ici, avec les fins de semaines
non travaillées il faudra 3 semaines et 3 jours.
- Les tâches normales sont représentées en bleu.
- Les tâches critiques sont représentées en rouge : B, E, F, L, et M.
- On distingue les marges totales en noir, et les marges libres en vert. Les
tâches C, G, J, et K font apparaître de la Marge Libre.

Remarques : Le diagramme de GANTT sera modifié au fur et à mesure de

l'avancement du projet. Il faut mettre à jour ce diagramme régulièrement. Le
chemin critique peut évoluer en fonction de l'avancement, du retard, ou de
toute modification sur une tâche. Les chemins « sub-critiques » ou «
presque critiques » peuvent alors devenir critiques.

5. Le PERT probabilisé

La durée des tâches est supposée fixe pour réaliser les études
précédentes. Or, généralement, la durée d'une tâche n'est pas fixe et peut
fluctuer. Le PERT probabilisé prend en compte l'incertitude, la fluctuation au
niveau de la durée d'exécution des tâches.
On peut définir pour chaque tâche :

La durée la plus optimiste : a ou do

La durée moyenne : m ou dm
La durée la plus pessimiste : b ou dp

35
On en déduit alors la durée estimée la plus probable d'exécution de la tâche :

te = a + 4.m + b 6 ou de = do + 4 . dm +
dp 6

Ce qui correspond à une distribution de probabilité du type b* :

N
Temps le plus
probable
Temps moyen

Temps le plus
optimiste

Temps le plus
pessimiste

(*) : L’incertitude associée aux résultats d’un mesurage peut être regroupée
en deux catégories en fonction des méthodes utilisées pour estimer leur
valeur numérique :
Les incertitudes standards de type A qui sont évaluées par
des méthodes statistiques Les incertitudes standards de
type B qui sont évaluées par d’autres méthodes.
NB : Aucun rapport avec les erreurs systématiques et aléatoires. Le mot
standard signifie que l’on se réfère à une norme.
On détermine la variance pour chaque durée d'exécution de tâche, temps
estimé, soit : V = (b-a)² / 36
On détermine les temps de début et de fin au
plus tôt, soit : Fto = Cto + t
On détermine les temps de début et de fin au plus
tard, soit : Cta = Fta - t
On détermine alors les écarts possibles :
E = Cta – Cto = Fta – Fto

Les tâches ayant un écart E = 0 sont les tâches critiques dont le non respect
de la durée estimée risque de compromettre le projet.

36
 On considère que la distribution concernant la durée de réalisation du
projet suit une loi normale, ce qui nous permet d'écrire que la variance
relative à l'ensemble du projet est égale à la somme des variances de
chacune des tâches critiques :

V = Va + Vb + Vc + ... + Vn ou σ² = σa² + σb² + σc² + ... + σn²

On en déduit alors l'écart type sur la durée du projet. On peut ainsi

estimer la fiabilité de cette durée.

6. LA METHODE PERT- COST ( Pert – Coût )

Les durées des tâches sont des paramètres sur lesquels l'entreprise peut
agir. Dans de nombreux cas, à travers l'attribution de moyens
supplémentaires, l'entreprise sera capable d'agir.
La gestion des coûts apparaît alors comme le corollaire de la gestion des
temps et il devient concevable d'envisager la gestion du couple coût-durée.
La méthode qui s'y attache et appelée « PERT-COST » ou « PERT-COÛT ».

6.1. Méthodologie :

On associe à chaque tâche du projet :

Un coût normal CN ou Co : coût le plus faible pour l'entreprise pour

mener à bien la tâche avec le minimum de moyens.
Un temps normal de réalisation tn ou to : temps correspondant au coût
normal, c'est à dire à l'utilisation de moyens minimaux.
Un temps accéléré ta ou t* : temps minimum concevable pour réaliser la
tâche, en lui accordant les moyens suffisants.
Un coût accéléré CA : coût correspondant au temps minimum de
réalisation

Si l'on admet l'hypothèse de relation linéaire du coût par rapport au temps de

réalisation, on peut définir un coût marginal d'accélération « CMA » de la
tâche.
CMA =
C
A
–
C
N

37
 t
n
–
t
a
Le « CMA » indique le coût supplémentaire associé à la réduction de la
durée d'exécution de la tâche (exemple : 200 € / heure).

Problèmes pouvant être résolus :

Si l'objectif est défini à priori : Sur quelles tâches faut-il agir pour respecter
l'objectif, avec le minimum de coûts supplémentaires ?

Comment définir cet objectif de date de fin de projet ? La réduction de la

durée d'un projet n'est pas une fin en soi. Elle doit se justifier par des
avantages de diverses natures (nouveau client, concurrence, risque de perte
de marché, ...) Il faut alors comparer ces avantages et les coûts associés
aux différentes durées du projet obtenues.

La méthode « PERT-COST » est souvent empirique et est basée sur

l'analyse du réseau PERT tracé au préalable. On cherche alors à diminuer la
durée du projet en fonction de l'objectif avec un surcout minimum.

Exemple :
Soit le projet suivant :

Tâche Durée Prédécesseurs Réduction Coût Marginal

(jours) (Tâches antérieures) maximale d'accélération (€/j)
(j)
A 1 - - -
B 3 A - -
C 10 B 3 3 000,00 €
D 5 B 1 2 000,00 €
E 3 D, F 2 1 600,00 €
F 3 C - -
G 1 F - -
H 2 F 1 3 000,00 €
I 20 E, G, H 5 5 000,00 €
J 4 I 1 2 500,00 €

38
 K 5 J 2 1 500,00 €

a. Tracer le réseau PERT correspondant à ce projet, en déduire le chemin

critique.
b. L'entreprise souhaite étudier la possibilité de réduire la durée du projet de
3 jours, et de 6 jours. Proposer dans les deux cas, une solution au
moindre coût.
c. Quelle réduction maximale du projet peut-on obtenir ? Quel est alors le
sur-coût engendré ?

Méthodologie proposée :

1. Sélectionner les tâches réductibles du chemin critique.

2. Classer les tâches par ordre croissant de coût (CMA).
3. Agir (réduire) sur les tâches les moins coûteuses.
4. Contrôler, modifier le réseau PERT ou MPM en conséquence. Faire
attention aux chemins presque critiques qui peuvent devenir critiques !
5. Calculer la durée et le surcoût associé. Attention de ne pas compter pour
la durée les tâches réduites en parallèle et de les compter pour le surcout.
6. Comparer plusieurs solutions, si besoin, en calculant le CMA du nouveau
projet.
7. Autres méthodes associées à la planification :

Il existe beaucoup de méthodes permettant de planifier, organiser, gérer,

des projets, des chantiers ou toute opération. Ces méthodes sont pour la
plupart informatisées, mais nécessitent toujours une analyse. L'optimisation
des moyens mis en œuvre pour réaliser un projet nécessite de faire des
hypothèses initiales et doit ensuite toujours faire face aux incertitudes, aléas,
du monde réel. Le « management » des ressources humaines et techniques
doit alors permettre une réalisation satisfaisante du projet.
Il y a bien des « recettes », mais c'est le « bon sens », la maîtrise des
moyens, et la rigueur méthodique qui favorisent cette réussite. Voici encore
quelques « outils- méthodes » disponibles :

- Planning ou graphe « chemin de fer »,

- Gestion assistée par ordinateur (GMAO, GPAO),
- Méthode MRP, ...,
- Lissage des charges, analyse des charges et capacités,
- Méthode SMED,
...

Gestion assistée par ordinateur :

39
 Les logiciels informatiques proposés dans le domaine de la gestion de
projets sont nombreux, on peut aisément utiliser :

- GanttProject, un « graticiel » pour gérer de petits projets en semaines, ou

en jours. - Microsoft Project, le produit grand public pour gérer des projets .

Ces logiciels offrent toutes les possibilités de construction de planning

prévisionnel, et surtout de suivi et de modification du projet en cours. Le projet
peut être à tout moment évalué en terme de délai, de disponibilité des
ressources et de coût.
La lisibilité n'est pas toujours évidente et le risque d'erreur existe toujours
!

Les entreprises utilisent aujourd'hui des logiciels de gestion :

GPAO : Gestion de Production Assistée par Ordinateur : SAP, ...
GMAO : Gestion de Maintenance Assistée par Ordinateur : CARL Master,
Cos Win, Optima Int, ...
Ces logiciels intègrent beaucoup de fonctions (Gestion des stocks,
ordonnancement, calculs des coûts, pilotage de la production et/ou de la
maintenance) qui permettent la planification et le suivi des opérations de
maintenance, mais ne permettent pas de construire des réseaux PERT ou
MPM et exceptionnellement des diagrammes de GANTT.

Lissage des charges, analyse des charges et capacités :

L'adéquation charge - capacité est une vérification de la faisabilité d'une
tâche, d'un projet, de la fabrication d'un lot ou d'une série. C'est une analyse
cruciale pour un ordonnancement satisfaisant.
Pour cela on compare le besoin en ressources aux ressources de même
type disponibles, sur l'horizon considéré.
L'adéquation charge - capacité peut aussi désigner le processus de
décision qui fera rejeter tout ou partie du travail non exécutable par manque
de moyens, ou à l'inverse, décider de se doter de la capacité à l'exécuter.
Charge : volume de travail à exécuter x temps nécessaire pour l'exécuter (+
éventuellement le temps de préparation si la ressource est indisponible
durant cette durée).
Capacité : temps disponible pour exécuter un travail x nombre de
ressources du même type. On peut construire un plan directeur,
basé par exemple sur la méthode MRP : Voir Annexe 1.
On recherche l'équilibrage des charges / capacités, on parle également de «
lissage ».

LEXIQUE :

M.P.M. :

40
 « Méthode des Potentiels Métra » = Planning sous forme de réseau
représentant graphiquement l'ordonnancement des opérations d'un projet.

M.R.P. :
Méthode de management des ressources qui permet de construire un plan
directeur. Méthode de gestion de production utilisée par les progiciels.
Ordonnancement :
L'ordonnancement, c'est l'arrangement qui permet d'exécuter
séquentiellement les tâches ou les ordres de fabrication, de façon à ce que
l'ensemble du projet ou de la production soit achevé dans le temps imparti.
P.E.R.T. :
[Eco.] Planning d'organisation montrant sous forme de réseau maillé
l'enclenchement des tâches relatives à la construction d'un ouvrage.

Planning :
[Eco.] Représentation graphique précisant les débuts et fins de tâches sur la
durée d'un projet, d'un chantier, ainsi que les contraintes d'enclenchement des
tâches les unes par rapport aux autres.

Planning ou graphe chemin de fer :

[Eco.] Graphique faisant intervenir le lieu géographique du déroulement des
tâches : les tâches sont représentées par des droites avec le développement
linéaire du projet en abscisse et le temps en ordonnée.

SMED :
Méthode « Toyota » ou « Single Minute Exchange of Die », c'est à dire réduire
le temps de changement de production à moins de 10 minutes. C'est une des
méthodes permettant l'amélioration de la qualité. La finalité su SMED est de
réduire au maximum le temps d'arrêt requis d'une machine pour procéder à un
changement de fabrication.

2- Gestion des stocks

La gestion des stocks en programmation dynamiqueest une méthode d’optimisation
utilisée pour *minimiser les coûts de stockage, de commande et de rupture de stock*
sur une période donnée.
Dans ces approches on a :
- Minimiser les coûts : On utilise des modèles comme EOQ pour trouver le juste
équilibre entre coûts de stockage et coûts de commande.
- Maximiser les profits : On ajuste les niveaux de stock pour répondre à la
demande tout en évitant les surplus.
- Niveaux de stock optimal : On détermine les quantités à commander et quand,
selon la demande et les coûts.

41
- Exemple : Un magasin veut gérer son stock de produits frais. On peut utiliser la
programmation dynamique pour décider combien commander chaque semaine pour
minimiser les pertes et les coûts.

Objectif :
Déterminer *quand* et *combien* commander pour satisfaire la demande tout en
minimisant les coûts totaux.
3-Chaînes logistiques
La programmation dynamique peut être utilisée pour modéliser et optimiser les
chaînes logistiques, c’est-à-dire l’ensemble des opérations permettant de gérer le
flux de produits, d’informations et de ressources depuis les fournisseurs jusqu’aux
clients finaux.
Dans ce contexte, les décisions sont souvent séquentielles, comme :
- la quantité de produit à commander à chaque période,
- la gestion des stocks,
- la planification des livraisons,
- ou encore l’allocation des ressources de transport.
Exemple d'application : gestion des stocks
On cherche à minimiser les coûts totaux d'une chaîne logistique sur un horizon
donné, en tenant compte :
- des coûts de commande (chaque fois qu’un réapprovisionnement est effectué),
- des coûts de stockage (par unité et par période),
- des coûts de rupture de stock.
Utilisation de la programmation dynamique :
On divise le problème en sous-problèmes : à chaque période, on décide combien
commander en fonction du stock actuel et de la demande future. La relation de
récurrence permet d’exprimer le coût optimal à partir des décisions précédentes.
Ainsi, la programmation dynamique permet de :
- Optimiser la politique d’approvisionnement,
- Réduire les coûts,
- Améliorer la satisfaction client.

4-Allocation de ressources

42
L’allocation de ressources est un aspect essentiel de la programmation dynamique
en recherche opérationnelle. Elle consiste à répartir de manière optimale des
ressources limitées (comme le temps, l’argent, les matériaux ou la main-d'œuvre)
entre différentes activités ou projets pour atteindre un objectif donné, tel que
minimiser les coûts ou maximiser les profits.
Dans un problème d’allocation de ressources, on cherche généralement la meilleure
façon de distribuer les ressources disponibles à chaque étape ou à chaque tâche,
tout en respectant les contraintes imposées. La programmation dynamique permet
de résoudre ce type de problème en décomposant le processus en plusieurs sous-
problèmes plus simples, résolus de manière séquentielle.
Un exemple classique est la répartition d’un budget entre plusieurs projets pour
obtenir le meilleur rendement global. Grâce à la programmation dynamique, on peut
évaluer toutes les options possibles à chaque étape, en tenant compte des décisions
précédentes, pour trouver la solution optimale.
Imaginons une entreprise qui dispose d’un budget de 10 000 FCFA à répartir entre
trois projets A, B et C. Chaque projet a un coût et un rendement associés. Le but est
de répartir ce budget pour maximiser le rendement total.
Grâce à la programmation dynamique, l’entreprise peut modéliser les différentes
combinaisons possibles d’allocation, analyser le rendement de chaque option et
choisir la meilleure. Le problème est résolu étape par étape : on commence par le
premier projet, puis on ajoute progressivement les autres en tenant compte des
ressources déjà utilisées.

Contexte :
Budget total : 10 000 FCFA
Objectif : Allouer le budget aux projets A, B et C pour maximiser le rendement.

| Projet | Coût (FCFA) | Rendement |

|--------|-------------|-----------|
|A | 4 000 |5 |
|B | 3 000 |3 |
|C | 5 000 |6 |

Étapes de la programmation dynamique (simplifiée)

1. Étape 1 : Choisir entre A, B ou C avec le budget disponible.

43
2. Étape 2 : Calculer les combinaisons possibles (ex. A + B, B + C…).
3. Étape 3 : Vérifier les combinaisons valides (qui ne dépassent pas 10 000 FCFA).
4. Étape 4 : Calculer le rendement total de chaque combinaison.
5. Étape 5 : Choisir la combinaison avec le meilleur rendement.

Exemple de combinaisons valides :

| Combinaison | Coût total | Rendement total |
|-------------|------------|-----------------|
|A+B | 7 000 |8 |
|A+C | 9 000 | 11 |
|B+C | 8 000 |9 |
Conclusion : La meilleure combinaison est A + C pour un coût de 9 000 FCFA et un
rendement de 11.
5-Décision séquentielle
a-Qu’est-ce qu’une décision séquentielle ?
Une décision séquentielle est une suite de décisions prises successivement dans le
temps. Chaque décision influence l’état futur du système et conditionne les décisions
suivantes. Contrairement aux décisions ponctuelles, la décision séquentielle repose
sur une vision globale du processus.
Sources : Bertsekas, D. P. (2017). Dynamic Programming and Optimal Control.
Athena Scientific.
b-Principe fondamental de la décision séquentielle
Le principe fondamental de la décision séquentielle en programmation dynamique
est le principe d’optimalité de Bellman. Il stipule qu’une politique optimale possède la
propriété suivante : quelle que soit la décision initiale, les décisions suivantes doivent
constituer une politique optimale pour l’état résultant de la première décision.
Sources : Bellman, R. (1966). Dynamic Programming. Science Journal.
c-États, décisions et transitions
Dans un problème de décision séquentielle, trois éléments essentiels sont définis :
l’état du système (qui décrit la situation à un instant donné), la décision ou action
possible (choisie par le décideur), et la transition d’état (qui décrit comment le
système évolue après une décision). Cette structure permet de modéliser
rigoureusement des problèmes complexes.
Sources : Puterman, M. L. (1994). Markov Decision Processes. Wiley.
d-Importance de la décision séquentielle

44
 La décision séquentielle est essentielle dans de nombreux domaines : gestion des
stocks, planification de production, finance, intelligence artificielle et apprentissage par
renforcement. Elle permet de résoudre des problèmes où l’incertitude, le temps et les
choix successifs jouent un rôle central.
Sources : Sutton, R. S. & Barto, A. G. (2018). Reinforcement Learning: An
Introduction. MIT Press.

VIII – Avantages et limites

Avantages
L'adoption de la programmation dynamique repose sur trois piliers majeurs :
a. Éviter les recalculs superflus (Mémorisation) :
C’est le cœur même de la méthode. Dans un algorithme récursif classique, les mêmes
sous-problèmes sont souvent résolus des dizaines, voire des milliers de fois. La
programmation dynamique stocke le résultat de chaque sous-problème dans une
"table" (tableau ou dictionnaire). Dès qu'un résultat est nécessaire une seconde fois, il
est récupéré instantanément.
b. Accélération massive des algorithmes :
En évitant les calculs redondants, on réduit souvent la complexité temporelle de
manière spectaculaire. Par exemple, pour le calcul de la suite de Fibonacci :
Récursion simple : Complexité exponentielle O(2^n).
Progression dynamique : Complexité linéaire O(n).
Cela permet de traiter des données de grande taille qui seraient impossibles à gérer
autrement.
c. Polyvalence et applications réelles :
Ce n'est pas qu'un concept théorique. Elle est indispensable dans des domaines
variés : Logistique : Problème du sac à dos (optimisation de chargement). Bio
informatique : Comparaison de séquences ADN (algorithme de Needleman-Wunsch).
Réseaux : Calcul d'itinéraires (algorithmes de plus court chemin).

Limites
a-Peut consommer beaucoup de mémoire
La programmation dynamique nécessite le stockage systématique des solutions
intermédiaires afin d’éviter les recalculs. Cette mémorisation, bien qu’efficace pour
améliorer les performances en temps, entraîne une consommation importante de
mémoire. Lorsque le nombre d’états est élevé ou que le problème dépend de

45
plusieurs paramètres, la taille des structures de stockage devient rapidement très
grande, ce qui peut dépasser les capacités mémoire disponibles. Cette contrainte
limite l’utilisation de la programmation dynamique pour certains problèmes de grande
dimension.
Source : Bellman, R. (1957). Dynamic Programming. Princeton University Press.
b-Nécessite une structure optimale
La programmation dynamique n’est applicable que si le problème satisfait le principe
d’optimalité de Bellman, selon lequel toute solution optimale globale est composée
de solutions optimales à ses sous-problèmes. Si cette condition n’est pas respectée,
la décomposition du problème en sous-problèmes indépendants devient impossible
ou inefficace. Par conséquent, certains problèmes ne peuvent pas être résolus par
programmation dynamique, ce qui restreint son champ d’application.
Source : Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009).
Introduction to Algorithms. MIT Press.
c-Complexité parfois difficile à réduire
Bien que la programmation dynamique permette de réduire les recalculs, elle
n’élimine pas toujours une complexité élevée. Dans certains cas, le nombre d’états et
de transitions reste important, ce qui peut conduire à des algorithmes coûteux en
temps de calcul. De plus, la définition des états et des relations de récurrence peut
être complexe, rendant la mise en œuvre difficile. Cette complexité limite parfois
l’efficacité pratique de la programmation dynamique pour des problèmes de grande
taille.
Source : Wikipédia – Programmation dynamique (consulté en 2025).

XI- Conclusion

En somme, la programmation dynamique est une méthode fondamentale en

recherche opérationnelle qui permet de résoudre efficacement des problèmes
complexes en les décomposant en sous-problèmes plus simples. Grâce au principe
d’optimalité de Bellman, elle garantit que la solution globale optimale repose sur des
solutions partielles elles-mêmes optimales.

Nous avons vu que cette technique repose sur la mémorisation des résultats
intermédiaires, ce qui permet d’éviter les recalculs inutiles et d’améliorer
considérablement les performances des algorithmes. À travers les différentes
approches, notamment Top-Down et Bottom-Up, ainsi que les exemples classiques
comme la suite de Fibonacci, le problème du sac à dos et le calcul du plus court
chemin, la programmation dynamique montre toute sa puissance et sa polyvalence.

Enfin, malgré certaines limites liées à la consommation mémoire et à la complexité

de mise en œuvre, la programmation dynamique reste un outil incontournable dans

46
de nombreux domaines tels que la planification, la gestion des ressources, les
chaînes logistiques et la prise de décision. Elle occupe ainsi une place centrale dans
l’optimisation moderne, l’informatique et l’intelligence artificielle.

47