Cours : Recherche Opérationnelle

BTS — Génie Logiciel (GEL)

Recherche Opérationnelle

Résumé : Ce document rassemble un résumé de cours et pédagogique de Recherche

Opérationnelle adapté aux étudiants de BTS Génie Logiciel. Il traite en détail (Partie
1) la Programmation linéaire et la méthode du Simplexe (modélisation, algorithme, cas
particuliers, phases I/II, applications) et (Partie 2) l’Ordonnancement par la méthode
PERT (construction de réseau, calculs avant/arrière, marges, chemin critique, PERT
probabiliste). Le cours contient des définitions, procédures pas à pas, exemples,
exercices, et une bibliographie commentée.

Pré-requis : Algèbre linéaire de base (systèmes linéaires), notions de géométrie du

plan, notions élémentaires de probabilités (moyenne, variance), lecture de tableaux.

i
Table des matières

Introduction générale 1

1 Programmation linéaire et méthode du simplexe 2

1.1 Introduction et objectifs pédagogiques . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Formulation d’un programme linéaire . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Transformations usuelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Interprétation géométrique (rappel) . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Notions de base pour le simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5 Algorithme du simplexe — principes . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5.1 Critère d’optimalité (maximisation) . . . . . . . . . . . . . . . . . . . . . 3
1.6 Simplexe tableau — exemple complet pas à pas . . . . . . . . . . . . . . . . . . . 3
1.6.1 Mise en forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.6.2 Tableau initial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.7 Cas particuliers et méthodes associées . . . . . . . . . . . . . . . . . . . . . . . . 5
1.7.1 Solutions multiples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.7.2 Problème non borné . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.7.3 Dégénérescence et cycling . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.8 Trouver une base initiale : Phase I / Phase II et méthode Big-M . . . . . . . . . 6
1.8.1 Problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.8.2 Méthode Phase I / Phase II . . . . . . . . . . . . . . . . . . . . . . . . 6
1.8.3 Méthode Big-M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.9 Interprétations économiques et analyses . . . . . . . . . . . . . . . . . . . . . . . 6
1.9.1 Sensibilité et analyses post-optimalité . . . . . . . . . . . . . . . . . . . . 6
1.10 Exercices (Partie Simplexe) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.11 Solutions indicatives (exercice 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Ordonnancement : méthode PERT 8

2.1 Introduction & objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Notions de base — vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Représentation des dépendances . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Construction pas à pas d’un réseau PERT . . . . . . . . . . . . . . . . . . . . . . 9
2.5 Calcul des dates — méthode algorithmique . . . . . . . . . . . . . . . . . . . . . 9
2.5.1 Parcours avant (forward pass) — dates au plus tôt . . . . . . . . . . . . . 9
2.5.2 Parcours arrière (backward pass) — dates au plus tard . . . . . . . . . . . 9
2.5.3 Remarque sur AOA vs AON . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.6 Marges (slack) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.7 Chemin critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.8 PERT probabiliste (o, m, p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.9 Exemple complet — pas à pas (très pédagogique) . . . . . . . . . . . . . . . . . . 11
2.9.1 Données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.9.2 Calcul des te et σ 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

ii
Recherche Opérationnelle

2.9.3 Réseau AON (schéma) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.9.4 Parcours avant (calcul ES/EF) . . . . . . . . . . . . . . . . . . . . . . . . 11
2.9.5 Parcours arrière (calcul LS/LF) . . . . . . . . . . . . . . . . . . . . . . . . 12
2.9.6 Marges et chemin critique . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.9.7 Variance projet et probabilités . . . . . . . . . . . . . . . . . . . . . . . . 12
2.10 Variantes et extensions pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.10.1 Plusieurs chemins critiques . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.10.2 Tâches fictives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.10.3 Ressources et ordonnancement à ressources limitées . . . . . . . . . . . . . 13
2.11 Bonnes pratiques pédagogiques pour la présentation en BTS . . . . . . . . . . . . 13
2.12 Exercices (avec corrections indicatives) . . . . . . . . . . . . . . . . . . . . . . . . 13
2.13 Ressources et lectures complémentaires . . . . . . . . . . . . . . . . . . . . . . . . 14
2.14 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Bibliographie 15

iii
Introduction générale

La Recherche Opérationnelle (RO) apporte des méthodes formelles pour modéliser et résoudre
des problèmes de décision en ingénierie, logistique et gestion. Ce cours porte sur deux outils
fondamentaux et complémentaires :
- la Programmation Linéaire (PL) et l’algorithme du Simplexe, pour optimiser une fonction
linéaire sous contraintes linéaires ; - l’Ordonnancement (méthode PERT / CPM), pour planifier
et analyser la temporalité d’un projet, identifier les tâches critiques et estimer la probabilité
d’achèvement.
L’approche est didactique : chaque partie contient des objectifs, notions clés, procédures pas
à pas, exemples et exercices. À la fin du cours, l’étudiant devra être capable de modéliser un
problème simple, appliquer le simplexe manuellement (tableau), construire un réseau PERT,
calculer marges et chemins critiques, et utiliser les formules PERT probabilistes.

Résumé du cours (référence au programme BTS) : Ce cours couvre la modélisation

PL (transformation en forme standard), la résolution par simplexe (tableaux, pivots, phase I/II,
Big-M), la notion de dualité et d’analyse post-optimale (introduction), ainsi que les méthodes
d’ordonnancement (PERT/CPM) utilisées pour la gestion de projet et l’optimisation temporelle.

Compétences à acquérir :
— Construire un modèle de programmation linéaire à partir d’une situation opérationnelle.
— Exécuter un simplexe tableau et interpréter les résultats (solution, sensibilité).
— Détecter et traiter les cas particuliers (non borné, dégénérescence, solutions multiples).
— Construire un réseau PERT, effectuer forward/backward pass, calculer marges et chemins
critiques.
— Appliquer la formule PERT probabiliste (o,m,p → te , σ 2 ) et estimer la probabilité d’achè-
vement d’un projet.

Objectif général (but) du cours : Donner aux étudiants les outils mathématiques et opé-
rationnels nécessaires pour modéliser, analyser et optimiser des problèmes pratiques de ressources
et de planning, en s’appuyant sur la PL et l’ordonnancement PERT.

Objectifs spécifiques :
1. Comprendre la théorie et la géométrie des PL et l’idée du parcours de sommets.
2. Maîtriser le simplexe (mise en forme, tableaux, pivots, choix de la base initiale).
3. Savoir appliquer PERT pour planifier un projet et analyser les risques temporels.
4. Savoir utiliser les résultats d’optimisation pour la prise de décision (interprétation, sensi-
bilité).

Notions clés du cours : Programmation linéaire, forme standard, variables slack/excès/artificielles,

solution de base, tableau du simplexe, coût réduit, pivot, phase I/II, Big-M, dualité, nœud / ac-
tivité, forward/backward pass, marge libre / marge totale, chemin critique, estimation PERT
(o,m,p), variance, approximation normale, Monte-Carlo (mention).

1
Chapitre 1

Programmation linéaire et méthode du

simplexe

1.1 Introduction et objectifs pédagogiques

La programmation linéaire (PL) étudie l’optimisation d’une fonction linéaire sous des contraintes
linéaires. L’algorithme du simplexe est l’outil algorithmique fondamental pour résoudre des PL
en pratique. À l’issue de cette partie, l’étudiant devra :
— savoir formuler un problème en PL (variables, objectif, contraintes) ;
— comprendre la notion de base, solution de base et solution de base admissible ;
— savoir appliquer le simplexe tableau pas à pas sur des exemples concrets ;
— connaître les cas particuliers (non borné, multiple, dégénérescence) et les méthodes pour
obtenir une base initiale (phase I/II, Big-M).

1.2 Formulation d’un programme linéaire

1.2.1 Définition
Un programme linéaire en forme générale :
n
X
Optimiser (max ou min) z = cT x = cj xj ,
j=1

sous les contraintes Ax ≤ b, x ≥ 0,

où A ∈ Rm×n , b ∈ Rm , c ∈ Rn .

1.2.2 Transformations usuelles

Pour appliquer le simplexe, on ramène le PL en forme standard (équations égales) en ajou-
tant :
— des variables d’écart (slack) si ≥ 0 pour transformer aTi x ≤ bi en aTi x + si = bi ;
— des variables d’excès pour aTi x ≥ bi (on soustrait une variable d’excès) ;
— éventuellement des variables artificielles (pour obtenir une base initiale) lorsque nécessaire.
Exemple de transformation : x1 + 2x2 ≤ 8 ⇒ x1 + 2x2 + s1 = 8, s1 ≥ 0.

2
Recherche Opérationnelle

1.3 Interprétation géométrique (rappel)

La région faisable est un polytope convexe (intersection d’un ensemble fini de demi-espaces).
Principe clé : si un optimum existe pour un PL borné, il se trouve en un sommet du polytope
(solution de base). Le simplexe explore ces sommets de façon systématique.

1.4 Notions de base pour le simplexe

Solution de base : en valeur linéaire, choisir m variables (si A a rang m) appelées basiques et
poser les autres à 0 ; résoudre Ax = b pour obtenir la base.
Solution de base admissible : solution de base satisfaisant x ≥ 0.
Variable basique/non basique : basique = dans la base (non nulle généralement), non ba-
sique = fixée à 0.
Tableau du simplexe : représentation tabulaire des équations et de la fonction objectif per-
mettant d’effectuer les pivots.

1.5 Algorithme du simplexe — principes

Résumé de l’algorithme (maximisation) :
1. Partir d’une solution de base admissible (B.A.). Si elle n’existe pas, utiliser phase I / Big-M
pour la trouver.
2. Calculer les coûts réduits (ou indices d’amélioration) pour les variables non basiques.
3. Si tous les coûts réduits indiquent qu’on ne peut pas améliorer l’objectif (critère d’optima-
lité), la solution actuelle est optimale.
4. Sinon, choisir une variable entrante (avec coût réduit favorable) puis déterminer la variable
sortante par le test du rapport (ratio minimum du RHS sur coefficient positif).
5. Effectuer un pivot (opérations sur lignes) pour mettre la variable entrante en base.
6. Retourner au point 2.

1.5.1 Critère d’optimalité (maximisation)

Avec la forme standard et le tableau où la ligne objective est z − j cj xj = 0, on recherche les
P
coefficients négatifs dans la ligne z (ils indiquent qu’en augmentant la variable correspondante z
augmentera). Différentes présentations existent ; la logique opérationnelle demeure : tant qu’une
variable non basique peut améliorer la valeur de z, on continue.

1.6 Simplexe tableau — exemple complet pas à pas

Nous présentons un exemple numérique simple et complet, détaillant chaque étape (idéal
pour TD).
Problème :
Maximiser z = 3x1 + 5x2



x1 ≤4

2x
2 ≤ 12
s.t.


3x1 + 2x2 ≤ 18

x , x
1 2 ≥ 0.

3
Recherche Opérationnelle

1.6.1 Mise en forme standard

Ajouter variables slack s1 , s2 , s3 ≥ 0 :
x1 =
x1 + 0x2 + s1 = 4
0x1 + 2x2 + s2 = 12
3x1 + 2x2 + s3 = 18
Fonction objectif : z − 3x1 − 5x2 = 0.
Base initiale : s1 , s2 , s3 (solution de base admissible triviale).

1.6.2 Tableau initial

Organisons le tableau (colonnes : x1 , x2 , s1 , s2 , s3 ; dernière colonne RHS) :

Base x1 x2 s1 s2 s3 RHS
s1 1 0 1 0 0 4
s2 0 2 0 1 0 12
s3 3 2 0 0 1 18
z -3 -5 0 0 0 0

Étape 1 : variable entrante Choisir la variable non basique avec le coefficient le plus négatif
dans la ligne z (ici −5 pour x2 ). Donc x2 entre en base.

Étape 2 : test du ratio Calculer les ratios RHS / coefficient de x2 pour lignes où coefficient
>0:
Ligne s1 : coef x2 = 0 ⇒ non admissible
Ligne s2 : 12/2 = 6
Ligne s3 : 18/2 = 9
Minimum = 6 ⇒ pivot sur la ligne de s2 ; s2 sort de la base et x2 entre.

Pivot 1 : rendre la colonne de x2 unité Diviser la ligne s2 par 2 :

nouvelle s2 : [0 ; 1 ; 0 ; 1/2 ; 0 ; 6]

Éliminer x2 des autres lignes :

s1 ← s1 − 0 · s2 (reste)
s3 ← s3 − 2 · s2 ⇒ [3 ; 0 ; 0 ; −1 ; 1 ; 6]
z ← z + 5 · s2 ⇒ [−3 ; 0 ; 0 ; 5/2 ; 0 ; 30]
Tableau après pivot 1 :

Base x1 x2 s1 s2 s3 RHS
s1 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
s3 3 0 0 -1 1 6
z -3 0 0 5/2 0 30

Étape 3 : nouvelle variable entrante La ligne z a encore un coefficient négatif −3 pour x1 .

Donc x1 entre en base.

4
Recherche Opérationnelle

Étape 4 : test du ratio Ratios pour les lignes avec coef x1 > 0 :
s1 : 4/1 = 4
x2 : coef 0 ⇒ non admissible
s3 : 6/3 = 2
Minimum = 2 ⇒ pivot ligne s3 . s3 sort, x1 entre.

Pivot 2 : rendre la colonne x1 unité Diviser la ligne s3 par 3 :

nouveau s3 : [1 ; 0 ; 0 ; − 13 ; 1
3 ; 2]

Éliminer x1 des autres lignes :

s1 ← s1 − 1 · s3 ⇒ [0 ; 0 ; 1 ; 1/3 ; −1/3 ; 2]
x2 ← x2 − 0 · s3 (reste)
z ← z + 3 · s3 ⇒ [0 ; 0 ; 0 ; 3/2 ; 1 ; 36]
Tableau final :

Base x1 x2 s1 s2 s3 RHS
s1 0 0 1 1/3 -1/3 2
x2 0 1 0 1/2 0 6
x1 1 0 0 -1/3 1/3 2
z 0 0 0 3/2 1 36

Interprétation Toutes les colonnes des variables de décision x1 , x2 dans la ligne z ont un
coefficient nul : la solution est optimale. Lecture de la solution :

x1 = 2, x2 = 6, s1 = 2, s2 = 0, s3 = 0,

valeur optimale z ⋆ = 36.

Remarque pédagogique : en TD, il est utile de faire faire ces calculs pas à pas aux étudiants
pour qu’ils s’approprient le mécanisme des pivots.

1.7 Cas particuliers et méthodes associées

1.7.1 Solutions multiples
Si après optimisation, une colonne non basique a coût réduit nul, il existe une autre base
donnant la même valeur objective — solutions multiples. Indiquer comment détecter et donner
une brève mention géométrique.

1.7.2 Problème non borné

Si pour une variable entrante, tous les coefficients dans la colonne des contraintes sont ≤ 0,
alors la fonction objectif peut croître indéfiniment → problème non borné. Expliquer exemple
simple.

1.7.3 Dégénérescence et cycling

Dégénérescence : une ou plusieurs variables basiques prennent la valeur 0 (RHS zéro). Peut
conduire à cycling (rare). Mentionner Bland’s rule (choisir la variable entrante/sortante selon
convention d’indice minimal) pour éviter le cycling.

5
Recherche Opérationnelle

1.8 Trouver une base initiale : Phase I / Phase II et méthode

Big-M
1.8.1 Problème
Si le système Ax = b, x ≥ 0 n’admet pas de base évidente (par exemple parce que cer-
taines bi < 0 ou après introduction de variables d’excès), il faut construire une solution de base
admissible artificielle.

1.8.2 Méthode Phase I / Phase II

Phase I :
1. Ajouter des variables artificielles ai pour obtenir une base initiale triviale.
2. Minimiser la somme des variables artificielles (ou leur métrique) pour tenter de les rendre
nulles.
3. Si la valeur minimale est > 0 → pas de solution faisable. Si = 0, supprimer les artificielles
puis passer à la phase II.
Phase II :
1. À partir de la base obtenue en Phase I, résoudre le problème original (optimisation réelle)
par simplexe.

1.8.3 Méthode Big-M

Alternative (plus directe) : ajouter des variables artificielles avec coût très pénalisant ±M
dans l’objectif (M grand). Résultat : l’algorithme tend à privilégier les solutions sans variables
artificielles. Méthode pratique mais attention au conditionnement numérique et au choix de M .

1.9 Interprétations économiques et analyses

1.9.1 Sensibilité et analyses post-optimalité
Après optimisation, on peut étudier :
— l’intervalle de variation admissible des coûts cj qui ne change pas la base optimale ;
— l’effet d’une modification de b (variation des ressources) — prix d’ombre / dualité ;
— la valeur duale (shadow price) associée aux contraintes.
Donner brève introduction au dual et aux prix d’ombre (développer en cours avancé).

1.10 Exercices (Partie Simplexe)

Proposer quelques exercices à donner en TD :
1. Résoudre graphiquement puis par simplexe :

x1 + x2 ≤ 8

max z = 4x1 + 3x2 , 2x1 + x2 ≤ 10

x1 , x2 ≥ 0


2. Problème nécessitant Phase I : résoudre (utiliser Phase I/II).

3. Étudier un exemple de problème non borné et expliquer pourquoi.
4. Exercice sur degenerescence : montrer un cas où une variable basique vaut 0.

6
Recherche Opérationnelle

1.11 Solutions indicatives (exercice 1)

(Fournir en TD solutions détaillées — on peut reprendre la même structure de tableau que
l’exemple traité précédemment.)

7
Chapitre 2

Ordonnancement : méthode PERT

2.1 Introduction & objectifs

L’ordonnancement consiste à organiser les tâches d’un projet dans le temps en respectant
leurs dépendances. Parmi les outils classiques, la méthode PERT est adaptée aux projets où les
durées des tâches sont incertaines (estimation probabiliste). Objectifs pédagogiques :
— Savoir construire un réseau PERT (AON) à partir d’une liste d’activités et de leurs anté-
riorités.
— Maîtriser le calcul des dates au plus tôt / au plus tard (parcours avant/arrière).
— Calculer les marges (libre et totale) et identifier le (les) chemin(s) critique(s).
— Appliquer la version probabiliste PERT (estimations o/m/p → te , σ 2 ) pour estimer la
durée et la probabilité d’achèvement.
— Connaître les limites et bonnes pratiques pour l’usage en gestion de projet logiciel.

2.2 Notions de base — vocabulaire

Événement / nœud / étape : Point marquant le début ou la fin d’une ou plusieurs tâches —
durée nulle.
Tâche / activité : Action entre deux nœuds nécessitant une durée et éventuellement des res-
sources. Dans ce cours, nous utilisons la représentation AON (Activity On
Node) où les activités sont des nœuds.
Tâche fictive : Activité de durée nulle (0) permettant de modéliser des contraintes de précé-
dence logiques ; représentée en pointillés si dessinée en AOA.
ES / EF : Early Start / Early Finish — dates au plus tôt (hâtives).
LS / LF : Late Start / Late Finish — dates au plus tard (tardives).
ML / MT : Marge Libre et Marge Totale.
Chemin critique : Suite d’activités avec marge totale nulle ; fixe la durée minimale du projet.

2.3 Représentation des dépendances

Deux conventions courantes :
— AOA (Activity On Arc) : activités représentées par des arcs, nœuds = événements. Utile
historiquement mais nécessite souvent des tâches fictives.
— AON (Activity On Node) : activités représentées par des nœuds, arcs = précédences. Plus
claire pédagogiquement ; utilisée dans ce document.

8
Recherche Opérationnelle

Relations type :
— Successive : B commence après A.
— Simultanée : A et B partent du même nœud.
— Convergente : plusieurs activités se terminent sur le même nœud ; le successeur attend
toutes les convergences.

2.4 Construction pas à pas d’un réseau PERT

Étapes :
1. Lister toutes les activités avec leur identifiant, durée estimée (ou triplet o/m/p), et anté-
cédents (prédécesseurs).
2. Déterminer les niveaux (facultatif, aide à la mise en page) :
— niveau 0 : activités sans antériorité ;
— niveau k : activités dont les antécédents sont tous de niveau < k.
3. Dessiner le réseau en AON : pour chaque activité créez un nœud ; reliez par des arcs les
activités selon les précédences.
4. Si nécessaire, insérer des tâches fictives (durée 0) pour représenter des contraintes de pré-
cédence non triviales.
5. Vérifier l’absence de cycles (pertinent pour un ordonnancement acyclique) : le graphe doit
être orienté acyclique (DAG).

2.5 Calcul des dates — méthode algorithmique

On calcule les dates au niveau des nœuds/événements (plutôt que pour les activités) ; pour
AON on utilisera ES/EF (dates de début/fin hâtives) et LS/LF.

2.5.1 Parcours avant (forward pass) — dates au plus tôt

Initialisation : choisir nœud de départ tstart = 0. Pour tout nœud j parcouru topologique-
ment :
ES(j) = max {EF (i)}, EF (j) = ES(j) + dj ,
i∈pred(j)

où pred(j) est l’ensemble des prédécesseurs du nœud j et dj la durée de l’activité représentée

par le nœud j (pour AON). Si pred(j) = ∅, alors ES(j) = 0.
En pratique, on calcule ES/EF activité par activité en avançant du début vers la fin.

2.5.2 Parcours arrière (backward pass) — dates au plus tard

Initialisation : fixer LF (dernier nœud) = EF (dernier nœud) (durée minimale trouvée par
forward pass). Puis pour chaque nœud i en parcours inverse :

LF (i) = min {LS(j)}, LS(i) = LF (i) − di ,

j∈succ(i)

où succ(i) est l’ensemble des successeurs du nœud i.

2.5.3 Remarque sur AOA vs AON

Si vous utilisez AOA (activités = arcs), formules sont appliquées aux événements (nœuds)
et les durées sont sur les arcs ; la logique numérique reste identique mais l’implantation diffère
légèrement.

9
Recherche Opérationnelle

2.6 Marges (slack)

Pour une activité reliant le nœud i au nœud j (ou pour une activité- nœud k en AON), on
définit :
— Marge libre (ML) : retard maximal possible pour l’activité sans retarder le début des
activités successeurs.
M L = ES(j) − EF (i) = ES(j) − (ES(i) + di ).
— Marge totale (MT) : retard maximal possible pour l’activité sans augmenter la durée totale
du projet.
M T = LF (j) − EF (i) = LF (j) − (ES(i) + di ).
Activité critique si M T = 0 (donc ML = 0 aussi si successeurs immédiats sont sur chemin
critique).

2.7 Chemin critique

Le chemin critique est la chaîne d’activités (ou de nœuds) reliant le début à la fin et composée
uniquement d’activités avec marge totale nulle. La durée totale du projet est égale à la somme
des durées le long d’un chemin critique (ou à EF du nœud terminal).
Remarques :
— Il peut y avoir plusieurs chemins critiques ; alors le projet est particulièrement sensible aux
retards.
— Toute augmentation de durée d’une activité critique augmente la durée projet d’autant.

2.8 PERT probabiliste (o, m, p)

Quand les durées sont incertaines on utilise pour chaque activité trois estimations :
— o : durée optimiste (meilleur scénario plausible),
— m : durée la plus probable,
— p : durée pessimiste.
On approxime la distribution de la durée par une loi bêta asymétrique ; PERT propose une
approximation de l’espérance et de la variance :
p−o 2
 
o + 4m + p 2
te = , σ = .
6 6
Pour estimer la durée totale du projet on :
1. calcule te et σ 2 pour chaque activité,
2. identifie le (ou les) chemin(s) critique(s) (en utilisant te comme durée),
3. P
approxime la durée projet comme la somme des te le long du chemin critique : E[T ] =
i∈C te (i),
4. approxime la variance P du projet comme la somme des variances le long du (des) chemin(s)
critique(s) : Var(T ) ≈ i∈C σ 2 (i),
5. suppose (approximativement) que T est gaussien : T ∼ N (E[T ], Var(T )) et calcule des
probabilités avec la CDF normale Φ :
 D − E[T ] 
P (T ≤ D) ≈ Φ p .
Var(T )
Limites : indépendance des durées (souvent approximative), dominance d’une grosse variance
par une activité remet en cause l’approximation normale ; si doute, utiliser Monte-Carlo.

10
Recherche Opérationnelle

2.9 Exemple complet — pas à pas (très pédagogique)

Nous reprenons un exemple adapté au niveau BTS pour montrer toutes les étapes explicite-
ment.

2.9.1 Données
Activités A à H, relations et estimations (o,m,p) fournies ici ; nous calculons te et σ 2 et
menons le calcul complet.

Table 2.1 – Activités, prédécesseurs et estimations

Activité Prédécesseur(s) o m p
A - 2 3 4
B - 1 2 3
C A 2 4 6
D B 1 1 2
E B 1 3 5
F C,D 2 3 4
G E 2 2 2
H F,G 1 2 3

2.9.2 Calcul des te et σ 2

Appliquer te = (o + 4m + p)/6 et σ 2 = ((p − o)/6)2 :

Activité te (jours) σ 2 (jours2 )

A 3.0 0.111
B 2.0 0.111
C 4.0 0.444
D 1.0 0.028
E 3.0 0.444
F 3.0 0.111
G 2.0 0.000
H 2.0 0.111

2.9.3 Réseau AON (schéma)

A B D
3.0 2.0 1.0

C E
F GH
4.0 3.0 2.0

2.9.4 Parcours avant (calcul ES/EF)

Effectuons le calcul étape par étape (on note ES/EF pour chaque activité) :

11
Recherche Opérationnelle

— A : ES(A)=0, EF(A)=ES+3=3.
— B : ES(B)=0, EF(B)=2.
— C : ES(C)=EF(A)=3, EF(C)=7.
— D : ES(D)=EF(B)=2, EF(D)=3.
— E : ES(E)=EF(B)=2, EF(E)=5.
— F : ES(F)=max(EF(C),EF(D))=max(7,3)=7, EF(F)=10.
— G : ES(G)=EF(E)=5, EF(G)=7.
— H : ES(H)=max(EF(F),EF(G))=max(10,7)=10, EF(H)=12.
Durée minimale projet (en utilisant te ) : EF(H) = 12 jours.

2.9.5 Parcours arrière (calcul LS/LF)

Initialiser LF(H)=12 :
— H : LF(H)=12, LS(H)=10.
— F : LF(F)=LS(H)=10, LS(F)=7.
— G : LF(G)=LS(H)=10, LS(G)=8.
— E : LF(E)=LS(G)=8, LS(E)=5.
— D : LF(D)=LS(F)=7, LS(D)=6.
— C : LF(C)=LS(F)=7, LS(C)=3.
— B : LF(B)=min(LS(D),LS(E))=min(6,5)=5, LS(B)=3.
— A : LF(A)=min(LS(B),LS(C))=min(3,3)=3, LS(A)=0.

2.9.6 Marges et chemin critique

Calculer les marges totales MT = LF - EF(précédent) (ou MT = LF(j) - ES(i) - d) et marquer
les activités critiques (MT = 0).
Activités critiques trouvées : A (MT=0), C (MT=0), F (MT=0), H (MT=0). Chemin critique
principal : A → C → F → H (durée 12 jours). On note aussi que B→E→G→H peut présenter
marges nulles selon variations ; ici leurs MT sont non nulles (vérifier cas par cas).

2.9.7 Variance projet et probabilités

Pour le chemin critique A,C,F,H :

E[T ] = 3 + 4 + 3 + 2 = 12.

V ar(T ) = 0.111 + 0.444 + 0.111 + 0.111 = 0.777.

√
σT = 0.777 ≈ 0.882 jours.
Probabilité d’achever en ≤ 13 jours :
13 − 12
z= ≈ 1.13, P ≈ Φ(1.13) ≈ 0.87.
0.882
Probabilité d’achever en ≤ 11 jours :
11 − 12
z= ≈ −1.13, P ≈ 0.13.
0.882
Interprétation : il y a environ 87% de chances de finir dans 13 jours ou moins, et seulement
13% de chances de finir en 11 jours ou moins.

12
Recherche Opérationnelle

2.10 Variantes et extensions pratiques

2.10.1 Plusieurs chemins critiques
Si plusieurs chemins ont MT=0, le projet est extrêmement sensible : il suffit d’un retard sur
n’importe lequel de ces chemins pour retarder le projet. En probabiliste, il faut alors prendre en
compte la variance combinée — la méthode PERT classique se focalise sur un chemin critique
identifié ; si plusieurs existent, le calcul d’incertitude devient plus délicat.

2.10.2 Tâches fictives

Utiles surtout en AOA pour représenter des contraintes logiques non directes. En AON, on
peut généralement les éviter.

2.10.3 Ressources et ordonnancement à ressources limitées

PERT/CPM planifie les precedences et les durées mais n’intègre pas directement les contraintes
de ressources (personnel, machines). Pour cela utiliser méthodes de lissage (leveling), heuristiques
ou techniques avancées (programmation linéaire, contraintes, ordonnancement à ressources limi-
tées).

2.11 Bonnes pratiques pédagogiques pour la présentation en BTS

— Montrer d’abord un exemple simple (4–6 activités) et faire le forward/backward pass à la
main en classe.
— Insister sur la lecture des marges : ML vs MT — donner interprétations concrètes (ex. “tu
peux retarder cette tâche de 2 jours sans retarder ses successeurs”).
— Utiliser une représentation AON claire (activity-on-node) pour éviter les tâches fictives lors
de l’apprentissage initial.
— Présenter la version probabiliste (o,m,p) après que les étudiants maîtrisent la version dé-
terministe.
— Faire manipuler un outil (GanttProject, ProjectLibre, Excel) pour confronter calculs ma-
nuels et rendu logiciel.
— Préparer une annexe « vérification numérique » montrant comment une petite modification
(allongement d’une tâche critique ou non critique) affecte la durée projet.

2.12 Exercices (avec corrections indicatives)

Exercice 1 (construction et chemin critique)
Données : activités (durées unitaires) et précédences :
— A (-) : 4
— B (-) : 3
— C (A) : 2
— D (A) : 5
— E (B,C) : 3
— F (D,E) : 2
Construire le réseau, calculer ES/EF et LS/LF, identifier le chemin critique et la durée totale.
Correction (rapide) : forward pass → EF final = 4→... (laisser aux étudiants le détail ; cor-
rection à donner en TD).

13
Recherche Opérationnelle

Exercice 2 (PERT probabiliste)

Pour l’exemple complet A–H (déjà fourni), calculer :
1. la probabilité d’achever en 13 jours (voir calcul précédent),
2. la probabilité d’achever en 10 jours.
Réponse : P(13) 0.87 ; P(10) : z = (10 − 12)/0.882 ≈ −2.27 ⇒ P ≈ 0.012 (1.2%).

Exercice 3 (impact d’une variation)

Dans l’exemple A–H, si la durée de F augmente de 2 jours (de 3 à 5), quelle est la nouvelle
durée projet ? Quel est l’impact si on augmente E de 2 jours (de 3 à 5) ? Expliquez.
Correction (rapide) : F critique → augmentation directe de 2 jours → projet = 14 jours. Pour
E : MT(E)=2 → augmenter E de 2 jours consomme sa marge, projet inchangé ; augmenter E de
3 jours retarde projet d’1 jour.

2.13 Ressources et lectures complémentaires

— Project Management Institute — PMBOK Guide (chapitres CPM/PERT).
— Tutoriels universitaires sur PERT / CPM (exercices et outils).
— Outils pratiques : GanttProject, ProjectLibre, MS Project.
— Monte-Carlo pour PERT : si vous souhaitez aller plus loin, apprendre à simuler les durées
par distribution et estimer la distribution empirique de la durée projet.

2.14 Conclusion
La méthode PERT est un outil pédagogique et pratique pour l’ordonnancement des pro-
jets comportant des incertitudes. Elle donne des résultats exploitables (chemin critique, marges,
estimation probabiliste) et constitue une bonne base pour aborder des problématiques plus avan-
cées (ordonnancement à ressources limitées, optimisation multi-objectifs). Pour les étudiants de
BTS, la méthode PERT, associée à des exercices manuels et à l’utilisation d’outils, permet de
comprendre les enjeux temporels et les risques de retard dans la gestion de projet logiciel.

14
Bibliographie

[1] G. B. Dantzig, "Linear Programming and Extensions", Princeton University Press, 1963.
(Classique sur le simplexe.)
[2] F. S. Hillier, G. J. Lieberman, "Introduction to Operations Research", McGraw-Hill. (Ou-
vrage d’introduction, chapitres PL et ordonnancement.)
[3] Project Management Institute, "A Guide to the Project Management Body of Knowledge
(PMBOK Guide)". (Référence gestion de projet : PERT/CPM.)
[4] United States Navy / Booz Allen (années 1950), travaux fondateurs sur PERT/CPM.
(Contexte historique.)
[5] A. Makhorin et al., "GLPK — GNU Linear Programming Kit", documentation et tutoriels
(outil pratique).
[6] S. Mitchell et al., "PuLP : A Linear Programming Toolkit for Python" — pour mise en
pratique informatique.

15